假期惊喜，收到公司款项86167.14元

假期惊喜

近日，有网友爆料称，比亚迪在未提前通知员工的情况下，突然发放了利润奖金。

有人获得了七八万元，也有人拿到了十多万元。

一位比亚迪员工的帖子显示，在9月26日下午，他的银行卡突然收到一笔 86167.14元的款项，是比亚迪发放的 2024 年利润奖金。

该员工还指出：比亚迪此次发放奖金没有提前通过邮件通知，而是直接将钱打入账户，显然是想给员工一个惊喜。

前几天我们才提到，迪子一开放招聘系统就直接爆了（不到 24 小时收到简历 20W 份），看来这么多人想进入比亚迪是有道理的。

另外在我们之前写过的几期神仙公司中，不少公司都有一项福利叫「节日礼物」。

那么不知道除了中秋的月饼，端午的粽子，你还见到或收到过什么公司礼物？欢迎评论区交流。

...

回归主题。

国庆假期，安排一些简简单单小算法。

题目描述

平台：LeetCode

题号：554

你的面前有一堵矩形的、由 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

提示：

对于每一行 i， sum(wall[i]) 是相同的

哈希表

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

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

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

就用示例数据来举 🌰 ：

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

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

Java 代码：

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size(), ans = n;
        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 掉最后一个
        }
        for (int u : map.keySet()) ans = Math.min(ans, n - map.get(u));
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int n = wall.size(), ans = n;
        unordered_map<int, int> map;
        for (int i = 0, sum = 0; i < n; i++, sum = 0) {
            for (int cur : wall[i]) {
                sum += cur;
                map[sum]++;
            }
            map[sum]--;
        }
        for (auto& u : map) ans = min(ans, n - u.second);
        return ans;
    }
};

Python 代码：

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n, ans = len(wall), len(wall)
        mapping = defaultdict(int)
        sumv = 0
        for i in range(n):
            for cur in wall[i]:
                sumv += cur
                mapping[sumv] += 1 
            mapping[sumv] -= 1     
            sumv = 0
        for u in mapping:
            ans = min(ans, n - mapping[u])
        return ans

TypeScript 代码：

function leastBricks(wall: number[][]): number {
    let n = wall.length, ans = n;
    const map: Map<number, number> = new Map();
    for (let i = 0, sum = 0; i < n; i++, sum = 0) {
        for (const cur of wall[i]) {
            sum += cur;
            if (map.has(sum)) map.set(sum, map.get(sum) + 1);    
            else map.set(sum, 1);
        }
        map.set(sum, map.get(sum) - 1);
    }
    map.forEach((value: number) => {
        ans = Math.min(ans, n - value);
    });
    return ans;
};