比题目更值得学习的「正难则反」的思考原则,以及 OJ 的溢出注意点|Java 刷题打卡

简介: 比题目更值得学习的「正难则反」的思考原则,以及 OJ 的溢出注意点|Java 刷题打卡

题目描述



这是 LeetCode 上的 554. 砖墙


Tag : 「哈希表」


你的面前有一堵矩形的、由 n 行砖块组成的砖墙。


这些砖块高度相同(也就是一个单位高)但是宽度不同。每一行砖块的宽度之和相等。


你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。


如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。


你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。


给你一个二维数组 wall ,该数组包含这堵墙的相关信息。


其中,wall[i] 是一个代表从左至右每块砖的宽度的数组。


你需要找出怎样画才能使这条线 穿过的砖块数量最少 ,并且返回 穿过的砖块数量 。

 

示例 1:


网络异常,图片无法展示
|


输入:wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出:2
复制代码


示例 2:


输入:wall = [[1],[1],[1]]
输出:3
复制代码


提示:


  • n == wall.length
  • 1 <= n <= 10410^4104
  • 1 <= wall[i].length <= 10410^4104
  • 1 <= sum(wall[i].length) <= 2 * 10410^4104
  • 对于每一行 i ,sum(wall[i]) 是相同的
  • 1 <= wall[i][j] <= 2312^{31}231 - 1


哈希表



题目要求穿过的砖块数量最少,等效于通过的间隙最多。


我们可以使用「哈希表」记录每个间隙的出现次数,最终统计所有行中哪些间隙出现得最多,使用「总行数」减去「间隙出现的最多次数」即是答案。


如何记录间隙呢?直接使用行前缀记录即可。


就用示例数据来举 🌰 :


网络异常,图片无法展示
|


  • 第 1 行的间隙有 [1,3,5]
  • 第 2 行的间隙有 [3,4]
  • 第 3 行的间隙有 [1,4]
  • 第 4 行的间隙有 [2]
  • 第 5 行的间隙有 [3,4]
  • 第 6 行的间隙有 [1,4,5]


对间隙计数完成后,遍历「哈希表」找出出现次数最多间隙 4,根据同一个间隙编号只会在单行内被统计一次,用总行数减去出现次数,即得到「最少穿过的砖块数」。


代码:


class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, sum = 0; i < n; i++, sum = 0) {
            for (int cur : wall.get(i)) {
                sum += cur;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            map.remove(sum); // 不能从两边穿过,需要 remove 掉最后一个
        }
        int ans = n;
        for (int u : map.keySet()) {
            int cnt = map.get(u);
            ans = Math.min(ans, n - cnt);
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:记所有砖块数量为 n,所有砖块都会被扫描。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(n)O(n)O(n)


关于是否需要考虑「溢出」的说明



类似的问题,在之前 题解 也说过,这里再提一下 ~


当 Java 发生溢出时,会直接转成负数来处理。因此对于本题不会影响正确性(不重复溢出的话)。


可以通过以下例子来体会:


{
    System.out.println(Integer.MIN_VALUE); // -2147483648
    int a = Integer.MAX_VALUE;
    System.out.println(a); // 2147483647
    a += 1;
    System.out.println(a); // -2147483648
    a -= 1;
    System.out.println(a); //2147483647
}
复制代码


这意味着,如果我们在运算过程中如果只涉及「纯加减运算」,而不涉及「乘除」、「取最大值/最小值」和「数值大小判断」的话,Java 是不需要使用 Long 来确保正确性的,因为最终溢出会被转化回来。


按道理,CPP 本身对于 int 溢出的转化处理也是一样的。


但在 LC 上的 CPP 发生溢出时,不会直接转成负数来处理,而是直接抛出异常。因此同样的代码在 LC 上是无法被正常执行的:


{
    cout << INT_MIN << endl; //-2147483648
    int a = INT_MAX; 
    cout << a << endl; // 2147483647
    a += 1; // 溢出报错
    cout << a << endl;
    a -= 1;
    cout << a << endl;
}
复制代码


这是一般性的,对于 LC 上的同一道题,Java 不需要处理溢出,CPP 需要处理的原因。


其实对应到本题,我这里不使用 long long,是因为猜想「题目」中的条件写错了:


1 <= sum(wall[i]) <= 2 * 10^4
错写成了
1 <= sum(wall[i].length) <= 2 * 10^4
复制代码


因为在给定下面两个条件的情况下:


1 <= n <= 10^4
1 <= wall[i].length <= 10^4
复制代码


1<=sum(wall[i].length)<=2∗1041 <= sum(wall[i].length) <= 2 * 10^41<=sum(wall[i].length)<=2104 十分多余。


针对反例:


[
    [2147483647,2147483647,2147483647,2147483647,1,2], 
    [2,2147483647,2147483647,2147483647,2147483647,1]
]
复制代码


我用官方提供的代码,跑的也是 0,所以如果是以官方的代码为评测标准的话,用 long long 反而是 WA 了 🤣


最后


这是我们「刷穿 LeetCode」系列文章的第 No.554 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
12天前
|
Java
Java基础学习day08-作业
本作业涵盖Java中Lambda表达式的应用,包括Runnable与Comparator接口的简化实现、自定义函数式接口NumberProcessor进行加减乘及最大值操作,以及通过IntProcessor处理整数数组,实现遍历、平方和奇偶判断等功能,强化函数式编程实践。
39 5
|
12天前
|
Java API 容器
Java基础学习day08-2
本节讲解Java方法引用与常用API,包括静态、实例、特定类型方法及构造器引用的格式与使用场景,并结合代码示例深入解析。同时介绍String和ArrayList的核心方法及其实际应用。
58 1
|
13天前
|
Java 程序员
Java基础学习day08
本节讲解Java中的代码块(静态与实例)及其作用,深入介绍内部类(成员、静态、局部及匿名)的定义与使用,并引入函数式编程思想,重点阐述Lambda表达式及其在简化匿名内部类中的应用。
92 5
|
13天前
|
Java
Java基础学习day07-作业
本作业包含六个Java编程案例:1)动物类继承与多态;2)加油卡支付系统;3)员工管理类设计;4)学生信息统计接口;5)USB设备控制;6)家电智能控制。综合运用抽象类、接口、继承、多态等面向对象技术,强化Java基础编程能力。
114 3
|
13天前
|
Java
Java基础学习day06-作业
本内容为Java基础学习作业,涵盖两个案例:一是通过Card类及其子类GoldenCard、SilverCard实现加油卡系统,体现封装与继承;二是通过Shape类及子类Circle、Rectangle演示多态与方法重写,强化面向对象编程理解。
39 1
|
13天前
|
设计模式 存储 Java
Java基础学习day07
本节讲解Java中的final关键字、单例设计模式、枚举类、抽象类与接口。涵盖常量定义、单例写法(饿汉式/懒汉式)、枚举特点及应用场景,以及抽象类与接口的使用与区别,助力掌握核心面向对象编程思想。
71 1
|
18天前
|
Java
Java基础学习day05-作业
本文为Java基础学习第五天作业,通过五个案例练习类与对象的定义、构造方法、set/get方法及成员方法的应用。涵盖女友、学生、教师、手机和电影等类的设计与测试,强化面向对象编程基础。
49 2
|
18天前
|
安全 Java 编译器
Java基础学习day06
本节学习Java继承与多态核心概念:继承通过extends实现,子类可复用父类非私有成员,支持单继承与多层继承,遵循就近原则并可用super调用父类成员;方法重写需满足权限与返回值约束,常用于重写toString等。多态基于继承,实现父类引用指向子类对象,提升扩展性但无法直接访问子类独有方法,可通过instanceof安全类型转换。
83 2
|
19天前
|
存储 Java
Java基础学习day05
本节介绍Java面向对象编程基础,涵盖类与对象的概念、构造器、this关键字、封装、Javabean及static修饰符的使用。重点讲解如何通过类设计对象、实现数据封装与方法暴露,并理解静态成员的特点与应用场景。
57 2
|
19天前
|
Java
Java基础学习day04-作业
本作业包含8个Java编程案例,涵盖数组的定义与遍历、求和、最值计算、去极值求平均、元素倍增、二维数组行和计算及查找指定元素等内容,旨在巩固Java基础语法与数组操作技能。
170 1

热门文章

最新文章