Tong's Blog

Welcome to my Blog

0%

备战华为刷题笔记

发表于 更新于
本文字数： 45k 阅读时长 ≈ 41 分钟

二分法

爱吃香蕉的珂珂

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有n堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在h小时后回来。
珂珂可以决定她吃香蕉的速度k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉k根。如果这堆香蕉少于k根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在h小时内吃掉所有香蕉的最小速度k（k为整数）。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23

解析：

设吃香蕉的速度为x，二分查找的下界为1，每小时最少吃一根；上界为一堆香蕉最多的总数目。当一堆香蕉的个数是pile，吃掉这堆香蕉需要[pile/x]小时，计算出吃掉所有香蕉的时间。如果在速度为x的情况下可以在h小时内吃完，则最小速度小于或等于x，调整上界为x；否则最小速度一定大于x，因此将下界调整为x+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1, right = 1000000001;
    // 寻找最小速度，找左边界
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(piles, mid, h)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
// 判断当前速度能否在h小时内完成
int f(vector<int>& piles, int x, int h) {
    int hours = 0;
    for (int i = 0; i < piles.size(); i++) {
        hours += piles[i] / x;
        if (piles[i] % x > 0) {
            hours++;
        }
    }
    return hours <= h;
}

有序矩阵中第 K 小的元素

378. 有序矩阵中第 K 小的元素

给你一个n x n矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个不同的元素。
你必须找到一个内存复杂度优于 O(n^2) 的解决方案。

1
2
3
4
5
6
7
8
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：
输入：matrix = [[-5]], k = 1
输出：-5

解析：

二分查找，矩阵内元素从左上到右下递增。matrix[0][0] 为最小值，matrix[n-1][n-1]为最大值，现在我们将其分别记作l和r。可以发现一个性质：任取一个数 mid 满足 l ≤ mid ≤ r，那么矩阵中不大于mid的数，肯定全部分布在矩阵的左上角。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int left = matrix[0][0];
    int right = matrix[n-1][n-1];
    // 寻找左边界
    while (left < right) {
        int mid = left + (right - mid) / 2;
        if (check(matrix, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
// 判断不大于mid的总数，是否大于k；
bool check(vector<vector<int>>& matrix, int k, int mid) {
    int n = matrix.size();
    int count = 0;
    int tmp = n - 1;
    for (int i = 0; i < n; i++) {
        while (tmp >= 0 && matrix[tmp][i] > mid) {
            tmp--;
        }
        count += (tmp + 1);
    }
    return count >= k;
}

搜索旋转排序数组

33. 搜索旋转排序数组

整数数组nums按升序排列，数组中的值互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2]。
给你 旋转后 的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

解析：

数组局部有序，可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int search(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] >= nums[0]) { // 左半区域有序
            if (target >= nums[0] && nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else { // 右半区域有序
            if (target <= nums[n-1] && nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return -1;
}

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,4,4,5,6,6,7]在下标 5 处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]。
给你 旋转后 的数组nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums中存在这个目标值target，则返回true，否则返回 false 。

1
2
3
4
5
6
7
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

解析：

对于数组中有重复元素的情况，二分查找时可能会有 a[l]=a[mid]=a[r]，此时无法判断区间 [l,mid] 和区间[mid+1,r]哪个是有序的。例如nums=[3,1,2,3,3,3,3]，target=2，首次二分时无法判断区间[0,3]和区间[4,6]哪个是有序的。
对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool search(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[left] == nums[mid] && nums[mid] == nums[right-1]) {
            left++;
            right--;
        }
        else if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else {
            if (target <= nums[right-1] && nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return false;
}

在 D 天内送达包裹的能力

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：
输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：
输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

解析：

二分查找转化为判定问题。假设当船的运载能力为x时，我们可以在days天内运送完所有包裹，那么只要运载能力大于x，我们同样可以在days天内运送完所有包裹：我们只需要使用运载能力为x时的运送方法即可。

二分查找的左边界为一个包裹重量的最大值，即weights数组中的最大值；右边界为weights数组之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int shipWithinDays(vector<int>& weights, int days) {
    int left = 0, right = 1;
    for (auto& w : weights) {
        left = max(left, w);
        right += w;
    }

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (getDays(weights, mid) <= days) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int getDays(vector<int>& weights, int x) {
    int days = 0;
    for (int i = 0; i < weights.size();) {
        int cap = x;
        while (i < weights.size()) {
            if (cap < weights[i]) break;
            else {
                cap -= weights[i++];
            }
        }
        days++;
    }
    return days;
}

找出第 K 小的数对距离

719. 找出第 K 小的数对距离

数对 (a,b)由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组nums和一个整数 k ，数对由nums[i]和nums[j]组成且满足0 <= i < j < nums.length。返回所有数对距离中第 k 小的数对距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1：
输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

示例 2：
输入：nums = [1,1,1], k = 2
输出：0

示例 3：
输入：nums = [1,6,1], k = 3
输出：5

解析：

排序+二分+双指针

先将数组排序，第k小的数对距离在区间[0, max(nums) - min(nums)]，令left = 0，right = max(nums) - min(nums)，在该区间内进行二分。对于当前搜索距离mid，计算所有距离小于等于mid的数对数目count，使用双指针：初始左端点i=0，从小到大枚举所有数对的右端点j，移动左端点直到nums[j] - nums[i] <= mid，那么右端点为j且距离小于等于mid的数对数目为j-i，计算这些数目之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int left = 0, right = nums[n-1] - nums[0] + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int i = 0, j = 0; j < n; j++) {
            while (nums[j] - nums[i] > mid) {
                i++;
            }
            count += j - i;
        }
        if (count >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

分割数组的最大值

410. 分割数组的最大值

给定一个非负整数数组nums和一个整数m，你需要将这个数组分成m个非空的连续子数组。

设计一个算法使得这m个子数组各自和的最大值最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9

示例 3：
输入：nums = [1,4,4], m = 3
输出：4

解析：

二分查找+贪心（使……最大值尽可能的小）

选定一个值x，线性的验证是否存在一种分割方案，满足最大分割子数组的和不超过x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int splitArray(vector<int>& nums, int m) {
    int n = nums.size(), left = 0, right = 1;
    for (auto& a : nums) {
        left = max(left, a);
        right += a;
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int i = 0; i < n;) {
            int sum = mid;
            while (i < n) {
                if (nums[i] > sum) {
                    break;
                }
                else {
                    sum -= nums[i++];
                }
            } 
            count++;
        }
        if (count <= m) {
            right = mid;
        } else {
            left = mid + 1;
        }
    } 
    return left;
}

两球之间的磁力

1552. 两球之间的磁力

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有n个空的篮子，第i个篮子的位置在position[i]，Morty 想把m个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于x和y，那么它们之间的磁力为|x - y|。
给你一个整数数组position和一个整数m，请你返回最大化的最小磁力。

image-20220807181250174 
1
2
3
4
5
6
7
8
9
示例 1：
输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：
输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

解析：

假定最小磁力为ans，小于ans的答案也一定合法。既然我们存在一种放置的方法使得相邻小球间距的最小值大于等于 ans，那么也一定大于 [1,ans−1] 中的任意一个值，而大于 ans 的均不合法，因此我们可以对答案进行二分查找。在区间[left, right]之间查找，每次取mid为平均值：

  • 如果当前mid合法，令ans = mid，并将区间缩小为[mid + 1, right];
  • 如果当前mid不合法，则将区间缩小为[left, mid - 1].

预先对给定的篮子的位置进行排序，那么从贪心的角度考虑，第一个小球放置的篮子一定是 position 最小的篮子，即排序后的第一个篮子。那么为了满足上述条件，第二个小球放置的位置一定要大于等于 position[0]+x，接下来同理。因此我们从前往后扫 position 数组，看在当前答案 x 下我们最多能在篮子里放多少个小球，我们记这个数量为 cnt，如果 cnt 大于等于 m，那么说明当前答案下我们的贪心策略能放下 m 个小球且它们间距均大于等于 x ，为合法的答案，否则不合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int maxDistance(vector<int>& position, int m) {
    sort(position.begin(), position.end());
    int n = position.size();
    int left = 1, right = position[n-1] - position[0];
    int ans = -1;
    // 寻找满足成立条件的右边界
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(position, mid, m)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}
// 检查以x为最小磁力，得到的分组cnt是否大于等于m
bool check(vector<int>& position, int x, int m) {
    int pre = position[0], cnt = 1;
    for (int i = 1; i < position.size(); i++) {
        if (position[i] - pre >= x) {
            cnt++;
            pre = position[i];
        }
    }
    return cnt >= m;
}

小张刷题计划

LCP 12. 小张刷题计划

为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。

在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。

1
2
3
4
5
6
7
8
9
10
11
示例 1：

输入：time = [1,2,3,3], m = 2
输出：3
解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。

示例 2：

输入：time = [999,999,999], m = 4
输出：0
解释：在前三天中，小张每天求助小杨一次，这样他可以在三天内完成所有的题目并不花任何时间。

解析：

题意解析为：给定一个数组，将其划分为M份，使得每份元素之和的最大值最小，每份可以任意减去其中一个元素。

如果不考虑每份可以任意减去一个元素，就是一个经典的二分问题，具有单调最优的性质：如果最大值为 t 可以满足条件划分，那么最大值为 t+1 也可以。所以就直接二分最大值 t，找到最小满足条件的 t 即可。

本题加了一个条件：每份可以删除任意一个数组。为了能够让最大值最小，显然每份中删去的一定是最大元素，所以在二分判定可行性时，维护当前序列的最大值，然后记录删除最大值的结果，也就是说二分的判定是：是否可以让每组删除最大值之后，总和都小于等于 t。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int minTime(vector<int>& time, int m) {
    int n = time.size();
    int left = 0, right = 1;
    for (auto& t : time) {
        right += t;
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (getDays(time, mid) <= m) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int getDays(vector<int>& time, int x) {
    int useday = 1, totaltime = 0, maxtime = 0;
    for (int i = 0; i < time.size(); i++) {
        int nextime = min(maxtime, time[i]);
        if (nextime + totaltime <= x) {
            totaltime += nextime;
            maxtime = max(maxtime, time[i]);
        } else {
            useday++;
            totaltime = 0;
            maxtime = time[i];
        }
    }
    return useday;
}

差分

航班预订统计

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

解析：

差分数组：第i个数即为原数组第i-1个元素和第i个元素的差值，也就是说对差分数组求前缀和即可得到原始数组。
遍历给定的预定数组，对差分数据进行更新，完成修改。对于预定记录booking=[l,r,inc]，我们需要让d[l−1] 增加 inc，d[r] 减少inc。特别地，当 r 为 n 时，我们无需修改d[r]，因为这个位置溢出了下标范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> res(n, 0);
    for (int i = 0; i < bookings.size(); i++) {
        int first = bookings[i][0] - 1;
        int last = bookings[i][1];
        res[first] += bookings[i][2];
        if (last < n) {
            res[last] -= bookings[i][2];
        }
    }
    for (int i = 1; i < n; i++) {
        res[i] += res[i-1];
    }
    return res;
}

所有排列中的最大和

1589. 所有排列中的最大和

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + … + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。

你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。

由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1：
输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。

示例 2：
输入：nums = [1,2,3,4,5,6], requests = [[0,1]]
输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。

示例 3：
输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。

解析：

利用差分数组，求解区间内每个下标被查询的次数，count数组记录每个下标的数据被查询的次数，在得到数组 counts 之后，对数组nums 和数组 counts 排序。倒序遍历数组，当查询次数大于0时，计算最大和 sum += nums[i] * count[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
    int n = nums.size();
    vector<int> count(n, 0);
    for (auto& req : requests) {
        int first = req[0];
        int last = req[1];
        count[first]++;
        if (last + 1 < n) count[last+1]--;
    }
    for (int i = 1; i < n; i++) {
        count[i] += count[i-1];
    }
    sort(nums.begin(), nums.end());
    sort(count.begin(), count.end());
    long long sum = 0;
    int Mod = 1000000007;
    for (int i = n - 1; i >= 0 && count[i] > 0; i--) {
        sum += (long long) nums[i] * count[i];
    }
    return (int)(sum % Mod);
}

拼车

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

1
2
3
4
5
6
7
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

解析：

构建差分数组，对原始数组进行频繁的区间增减操作，根据trips数组对区间进行增减，1 <= trips.length <= 1000，因此差分数组的长度设为1001.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> res(1001, 0);
    for (auto& trip : trips) {
        int first = trip[1];
        int last = trip[2];
        res[first] += trip[0];
        res[last] -= trip[0];
    }
    for (int i = 0; i < res.size(); i++) {
        if (i > 0) res[i] += res[i-1];
        if (res[i] > capacity) {
            return false;
        }
    }
    return true;
}

会议室

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)， 为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

1
2
3
4
5
6
7
示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例 2:
输入: [[7,10],[2,4]]
输出: 1

解析：

如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间

把时间线想象成一个初始值为 0 的数组，每个时间区间 [i, j] 就相当于一个子数组，这个时间区间有一个会议，那我就把这个子数组中的元素都加一。最后遍历数组，求最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int minMeetingRooms(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<int> begin(n, 0);
    vector<int> end(n, 0);
    for (int i = 0; i < n; i++) {
        begin[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    sort(begin.begin(), begin.end());
    sort(begin.begin(), begin.end());
    
    int count = 0;
    int res = 0, i = 0, j = 0;
    while (i < n && j < n) {
        if (begin[i] < end[j]) {
            count++;
            i++;
        } else {
            count--;
            j++;
        }
        res = max(res, count);
    }
    return res;
}

买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
     
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
     
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

解析：

构建差分数组，count记录获得利润，只加差分为正的值。

1
2
3
4
5
6
7
8
9
10
int maxProfit(vector<int>& prices) {
	int count = 0;
    for (int i = 1; i < prices.size(); i++) {
        int diff = prices[i] - prices[i - 1]; 
        if (diff > 0) {
           count += diff;
        } 
    }
    return count;
}

并查集

省份数量

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

image-20220808115241997

解析：

可以把 n 个城市和它们之间的相连关系看成图，城市是图中的节点，相连关系是图中的边，给定的矩阵 isConnected 即为图的邻接矩阵，省份即为图中的连通分量。

使用并查集计算连通分量数，初始时，每个城市都属于不同的连通分量。遍历矩阵 isConnected，如果两个城市之间有相连关系，则它们属于同一个连通分量，对它们进行合并。遍历矩阵 isConnected 的全部元素之后，计算连通分量的总数，即为省份的总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Find(vector<int>& parent, int index) { // 寻找根节点
    if (parent[index] != index) {
        parent[index] = Find(parent, parent[index]); 
        // 递归进行路径压缩
    }
    return parent[index];
}

void Union(vector<int>& parent, int index1, int index2) { // 建立连通性
    parent[Find(parent, index1)] = Find(parent, index2);
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int cities = isConnected.size();
    vector<int> parent(cities, 0);
    for (int i = 0; i < cities; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < cities; i++) {
        for (int j = i+1; j < cities; j++) {
            if (isConnected[i][j] == 1) {
                Union(parent, i, j);
            }
        }
    }
    int provinces = 0;
    for (int i = 0; i < cities; i++) {
        if (parent[i] == i) {
            provinces++;
        }
    }
    return provinces;
}

执行交换操作后的最小汉明距离

1722. 执行交换操作后的最小汉明距离

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：
输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：
输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

解析：

利用并查集建立连通性关系，遍历 allowedSwaps 数组中所有元素，从而构建 source 数组中位置之间的联通关系。需要使用哈希表记录为每个联通分支维护位置的集合，为每个联通分支 k 维护 target 中对应位置元素的集合。随后，汉明距离的最小值，就是这两个集合之间不同的元素的数量。
注意：允许集合中的元素出现重复，因此使用C++中的unordered_multiset数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int Find(vector<int>& parent, int index) { // 寻找根节点
    if (parent[index] != index) {
        parent[index] = Find(parent, parent[index]); 
        // 递归进行路径压缩
    }
    return parent[index];
}

void Union(vector<int>& parent, int index1, int index2) { // 建立连通性
    parent[Find(parent, index1)] = Find(parent, index2);
}
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
    int n = source.size();
    vector<int> parent(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    for (const auto& allowed : allowedSwaps) {
        Union(parent, allowed[0], allowed[1]);
    }

    unordered_map<int, unordered_multiset<int>> s, t;
    // 为每个联通分支维护位置的集合
    for (int i = 0; i < n; i++) {
        int fa = Find(parent, i);
        s[fa].insert(source[i]);
        //t[fa].insert(target[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) { 
        auto& m = s[Find(parent, i)];
        // 如果通过下标找到的连通块中,有target[i]这个元素,那么将其删掉,反之res++
        auto t = m.find(target[i]);
        // 不能使用 m.erase(x),不然会删掉所有的x,应该先定位到其具体位置,再删除
        //（因为该元素已经被用来对应了，后续无法再使用，所以要删除）
        if (t != m.end()) {
            m.erase(t);
        } else {
            res++;
        }

        //if (s.find(i) == s.end()) continue;
        // for (int x : s[i]) {
        //     if (t[i].find(x) == t[i].end()) {
        //         res++;
        //     } else {
        //         t[i].erase(t[i].find(x));
        //     }
        // }
    }
    return res;
}

双指针

替换后的最长重复字符

424. 替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

解析：

双指针加滑动窗口：

right指针指向区间右端点，然后找到其最远的left左端点的位置，满足该区间内，出现次数最多的字符数量为maxCnt，区间长度减去maxCnt为剩余的字符数（即非最长重复字符）数量不超过k个。

实际代码中，由于字符串中仅包含大写字母，我们可以使用一个长度为 26 的数组维护每一个字符的出现次数。每次区间右移，我们更新右移位置的字符出现的次数，然后尝试用它更新重复字符出现次数的历史最大值，最后我们使用该最大值计算出区间内非最长重复字符的数量，以此判断左指针是否需要右移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int characterReplacement(string s, int k) {
    vector<int> count(26, 0);
    int left = 0, right = 0;
    int maxCnt = 0;
    int res = 0;
    while(right < s.size()) {
        count[s[right] - 'A']++;
        maxCnt = max(maxCnt, count[s[right] - 'A']);
        if (right - left + 1 > maxCnt + k) {
            count[s[left] - 'A']--;
            left++;
        }
        res = max(res, right - left + 1);
        right++;
    }
    return res;
}

字符串的排列

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

1
2
3
4
5
6
7
8
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false

解析：

双指针+滑动窗口，保证窗口的大小为s1的长度n，用一个cnt数组记录s1中各个字符出现的次数，两个指针left和right， right每次右移动一次，统计一次进入区间的字符x，若此时cnt[x] < 0，则向右移动左指针，增加离开区间的字符cnt值直到cnt[x] >= 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool checkInclusion(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    if (n > m) return false;
    vector<int> count(26, 0);
    for (const auto& c : s1) {
        count[c-'a']++;
    }
    int left = 0, right = 0;
    while (right < s2.size()) {
        int x = (s2[right] - 'a');
        right++;
        count[x]--;
        while (count[x] < 0) {
            count[s2[left] - 'a']++;
            left++;
        }
        if (right - left == n) {
            return true;
        }
    }
    return false;
}

划分字母区间

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

1
2
3
4
5
6
7
8
示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

解析：

遍历字符串，count数组记录每个字符最后一次出现的位置，即出现最远的位置。双指针left和right初始指向0，对于right访问到的字符，更新right为该字符最后一次出现的位置，遍历left到right之间的窗口，如果窗口内的字符最后一次出现的位置更远则更新右端点right。窗口内的字符检查完毕后，计算窗口长度并记录在res中，将left和right更新到right+1的位置，重复以上步骤直到right到达末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> partitionLabels(string s) {
    vector<int> count(26, 0);
    for (int i = 0; i < s.size(); i++) {
        count[s[i]-'a'] = i;
    }
    int left = 0, right = 0;

    vector<int> res;
    while (right < s.size()) {
        right = count[s[right] - 'a'];
        int index = left + 1;
        while (index < right) {
            if (count[s[index]-'a'] > right) {
                right = count[s[index]-'a'];
            }
            index++;
        }
        right++;
        res.push_back(right - left);
        left = right;        

    }
    return res;
}

前缀和

连续的子数组和

523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

  • 子数组大小 至少为 2 ，且
  • 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：
输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：
输入：nums = [23,2,6,4,7], k = 13
输出：false

解析：

前缀和+哈希表

计算前缀和数组元素与k的余数，当更新后的前缀和数组，出现两个元素的值（前缀和余数）相等，计算两个元素的距离如果大于2，表示存在子数组之和为k的整数倍。利用哈希表存储前缀和余数对应的位置索引。注意：哈希表中设置余数为0的下标为-1，方便计算子数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool checkSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    if (n < 2) {
        return false;
    }
    unordered_map<int, int> map;
    map[0] = -1;
    int remain = 0;
    for (int i = 0; i < n; i++) {
        remain = (nums[i] + remain) % k;
        if (map.find(remain) != map.end()) {
            int index = map[remain];
            if (i - index >= 2) {
                return true;
            }
        } else {
            map[remain] = i;
        }
    }
    return false;
}

和相同的二元子数组

930. 和相同的二元子数组

给你一个二元数组nums，和一个整数goal，请你统计并返回有多少个和为goal 的非空子数组。

子数组 是数组的一段连续部分。

1
2
3
4
5
6
7
8
9
示例 1：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2：
输入：nums = [0,0,0,0,0], goal = 0
输出：15

解析：

哈希表存储每一种前缀和出现的次数，假设原数组前缀和数组为sum，且子数组(i,j]的区间和为goal，那么sum[j] - sum[i] = goal; 因此可枚举j，查询满足条件的i的数量。假设当前枚举到元素nums[j]，只需要查询哈希表中元素sum[j] - goal的数量即可。最后这些元素的总数量即为所有和为 goal的子数组数量。

构建回文串检测

1177. 构建回文串检测

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

1
2
3
4
5
6
7
8
9
10
示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

解析：

前缀和暴力求解：

记录某一个区间内的字符出现频率，出现奇数次的字母记录下来，根据奇数次字符出现次数再进行操作，使用一个二维数组pre[i][j]来保存字符串s前i个字符中字符’a’+j(0<=j<=26)出现的次数，最后在区间 [l,r] 中可通过pre[r+1][j]-pre[l][j]来得到某个区间内某字符的出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    vector<vector<int>> pre(100005, vector<int>(26, 0));
    for (int i = 1; i <= s.size(); i++) {
        pre[i][s[i-1]-'a']++;
        for (int j = 0; j < 26; j++) {
            pre[i][j] += pre[i-1][j];
        }
    }
    int odd = 0;
    vector<bool> res;
    for (auto& q : queries) {
        odd = 0;
        for (int i = 0; i < 26; i++) {
            odd += (pre[q[1]+1][i] - pre[q[0]][i]) % 2;
            // 字符出现奇数次则++
        }
        odd /= 2;
        res.push_back(odd <= q[2]);
    }
    return res;
}

最大的幻方

1895. 最大的幻方

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部****相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

示例 1：

img

1
2
3
4
5
6
7
输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

img

1
2
输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

解析：

枚举正方形+前缀和优化

按照从大到小的顺序枚举正方形的边长edge，再枚举给定的矩阵grid所有的边长为edge的正方形，并依次判断它们是否满足幻方的要求。可以预处理出矩阵grid每一行与每一列的前缀和，这样每一行或每一列的区间内求和可在O(1)的时间内完成，假设l=min(m, n),egde的范围[1, l]，那么，求和的时间复杂度为O(l)，总时间的复杂度为O(mnl^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int largestMagicSquare(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    // 每一行的前缀和
    vector<vector<int>> rowsum(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        rowsum[i][0] = grid[i][0];
        for (int j = 1; j < n; j++) {
            rowsum[i][j] = rowsum[i][j-1] + grid[i][j];
        }
    }
    // 每一列的前缀和
    vector<vector<int>> colsum(m, vector<int>(n, 0));
    for (int j = 0; j < n; j++) {
        colsum[0][j] = grid[0][j];
        for (int i = 1; i < m; i++) {
            colsum[i][j] = colsum[i-1][j] + grid[i][j];
        }
    }
    // 从大到小枚举正方形边长edge
    for (int edge = min(m, n); edge >= 2; edge--) {
        // 枚举左上角位置（i，j）
        for (int i = 0; i + edge <= m; i++) {
            for (int j = 0; j + edge <= n; j++) {
                // 计算每一行、列、对角线的的值
                int stdsum = rowsum[i][j+edge-1] - (j ? rowsum[i][j-1] : 0);
                bool check = true;

                for (int ii = i+1; ii < i + edge; ii++) {
                    int num = rowsum[ii][j+edge-1] - (j ? rowsum[ii][j-1] : 0);
                    if (num != stdsum) {
                        check = false;
                        break;
                    }
                }

                if (!check) continue;

                for (int jj = j; jj < j + edge; jj++) {
                    int num = colsum[i+edge-1][jj] - (i ? colsum[i-1][jj] : 0);
                    if (num != stdsum) {
                        check = false;
                        break;
                    }
                }  
                if (!check) continue;

                int d1 = 0, d2 = 0; // 两条对角线的和
                // 不使用前缀和，直接遍历求和
                for (int k = 0; k < edge; k++) {
                    d1 += grid[i+k][j+k];
                    d2 += grid[i+k][j+edge-k-1];
                }
                if (d1 == stdsum && d2 == stdsum) {
                    return edge;
                }

            }
        }
    }
    return 1;
}

和为目标值且不重叠的非空子数组的最大数目

1546. 和为目标值且不重叠的非空子数组的最大数目

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。

示例 2：
输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

示例 3：
输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3

示例 4：
输入：nums = [0,0,0], target = 0
输出：3

解析：

贪心解法，满足条件的子数组互不重叠，如果其右端点所有满足条件的子数组的右端点中最小的哪一个，则该子数组一定会被选择。从左到右遍历数组，如果发现有某个以当前下标i为右端点的子数组和为target，就给计数器加一，并从nums数组的下标i+1位置开始，进行下一次寻找。

为了判断是否存在和为target的子数组，在遍历的过程中记录数组的前缀和，并将它们保存在哈希表中。如果位置i对应的前缀和为sum，而sum−target已经存在于哈希表中，就说明找到了一个和为target的子数组。

如果找到一个符合条件的子数组，下一次遍历过程中需要用一个新的哈希表，而不是使用原有的哈希表，需要确保每次找到的子数组的区间不重合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxNonOverlapping(vector<int>& nums, int target) {
    int n = nums.size();
    int res = 0;
    int i = 0;
    while (i < n) {
        unordered_set<int> s{0};
        int sum = 0;
        while (i < n) {
            sum += nums[i];
            if (s.find(sum - target) != s.end()) {
                res++;
                break;
            } else {
                s.insert(sum);
                i++;
            }
        }
        i++;          
    }
    return res;
}

最高频元素的频数

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例 2：
输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：
输入：nums = [3,9,6], k = 2
输出：1

解析：

前缀和+二分

对nums先排序，计算nums对应的前缀和sum。假设右端点为i，区间左侧了l=0，右侧r=i，在区间[l. r]内进行二分，选取合适的mid值，mid=l+(r-l)/2，i固定不变。假设ans=nums[i]*(i-mid+1) - (sum[i]-sum[mid-1]); 假设ans>k; 说明此时该区间不满足条件，需要l=mid+1；假设ans<=k，说明此时该区间满足条件，需要r=mid-1，以求解最优的mid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int maxFrequency(vector<int>& nums, int k) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<long long> sum(n, 0);
    sum[0] = nums[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + nums[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int left = 0, right = i, res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[i] * (long long)(i - mid + 1) - 
                (sum[i] - (mid > 0 ? sum[mid - 1] : 0)) <= k) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (res != -1) ans = max(ans, i - res + 1);
    }
    return ans;
}

优化：滑动窗口

令左边界l=0，依次遍历右边界r，每次求相邻柱子的阴影距离sum[i]，计算得到的sum与k比较，如果sum>k，则移动左指针l，直到sum<=k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxFrequency(vector<int>& nums, int k) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    long long sum = 0;
    int left = 0;
    int res = 1;
    for (int right = 1; right < n; right++) {
        sum += (long long) (nums[right] - nums[right-1]) * (right - left);
        while (sum > k) {
            sum -= nums[right] - nums[left++];
        }
        res = max(res, right - left + 1);
    }
    return res;
}

DFS

矩阵中的最长递增路径

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

img

1
2
3
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

img

1
2
3
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

1
2
输入：matrix = [[1]]
输出：1

解析：

将矩阵看作一个有向图，每个单元格对应图中一个节点，若相邻的两个单元格的节点值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化为在有向图中寻找最长的路径。如果使用朴素深度优先搜索，时间复杂度是指数级，会超出时间限制，因此必须加以优化。

优化方法：记忆化搜索。用矩阵memo作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。当访问到一个单元格（i，j）时，如果memo[i][j] == 0，说明该单元格还未被计算过，进行搜索将计算结果存入缓存；如果memo[i][j] ！= 0，说明该单元格已经计算过，直接从缓存中读取结果。

遍历完矩阵中的所有单元格之后，即可得到矩阵中的最长递增路径的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<int> dirs = {-1, 0, 1, 0, -1};
vector<vector<int>> memo;
int m = 0, n = 0;
int longestIncreasingPath(vector<vector<int>>& matrix) {
    m = matrix.size();
    n = matrix[0].size();
    if (m == 0 || n == 0) return 0;
    memo = vector<vector<int>>(m, vector<int>(n, -1));
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = max(res, dfs(matrix, i, j));
        }
    }
    return res;
}

int dfs(vector<vector<int>>& matrix, int r, int c) {
    if (memo[r][c] != -1) {
        return memo[r][c];
    }

    int maxLen = 1;
    for (int k = 0; k < 4; k++) {
        int x = r + dirs[k];
        int y = c + dirs[k+1];
        if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[r][c]) {
            continue;
        }
        int len = dfs(matrix, x, y) + 1;
        maxLen = max(maxLen, len);
    }
    memo[r][c] = maxLen;
    return maxLen;
}

岛屿数量

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解析：

dfs深度优先搜索，将二维网格看成一个无向图，竖直或水平相邻的1之间有边相连。为了求岛屿的数量，扫描二维网格，遇到位置为1的开始进行dfs搜索，再dfs搜索过程中，每个搜到的1都重新标记为0。最终搜索的次数即为岛屿的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> dirs {-1, 0, 1, 0, -1};
int m = 0, n = 0;
int numIslands(vector<vector<char>>& grid) {
    m = grid.size();
    n = grid[0].size();
    if (m == 0 || n == 0) return 0;
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

void dfs(vector<vector<char>>& grid, int r, int c) {
    grid[r][c] = '0';
    for (int k = 0; k < 4; k++) {
        int x = r + dirs[k], y = c + dirs[k+1];
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0') {
            continue;
        }
        dfs(grid, x, y);
    }
}

单词搜索

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

解析：

dfs回溯，从网格（i，j）位置出发，能否搜索到单词word[index…]，如果可以搜到word末尾，返回true，反之返回false，字符串不匹配之间返回false；遍历当前位置的所有相邻位置，如果可以搜到word[index+1]，则返回true，否则返回false。为了防止重复遍历相同的位置，需要额外维护一个与原数组board大小相同的访问数组visited，标识每个位置是否已经访问过，dfs过程中不走回头路。注意dfs访问结束后将当前位置标志为false回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
vector<int> dirs{-1, 0, 1, 0, -1};
vector<vector<bool>> visited;
int m = 0, n = 0;

bool exist(vector<vector<char>>& board, string word) {
    m = board.size();
    n = board[0].size();
    if (m == 0 || n == 0) return false;
    bool flag = false;
    visited = vector<vector<bool>>(m, vector<bool>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] != word[0]) continue;
            flag = dfs(board, word, i, j, 0);
            if (flag) {
                return true;
            }
        }
    }
    return false;
}
bool dfs(vector<vector<char>>& board, string word, int i, int j, int index) {
    if (board[i][j] != word[index]) {
        return false;
    } else if (index == word.size() - 1) {
        return true;
    }
    visited[i][j] = true;
    bool res = false;
    for (int k = 0; k < 4; k++) {
        int x = i + dirs[k];
        int y = j + dirs[k+1];
        if (x < 0 || x >= m || y < 0 || y >= n) {
            continue;
        }
        if (!visited[x][y]) {
            bool flag = dfs(board, word, x, y, index + 1);
            if (flag) {
                res = true;
                break;
            }
        }
    }
    visited[i][j] = false;
    return res;
}

回溯

字母大小写全排列

784. 字母大小写全排列

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

1
2
3
4
5
6
7
示例 1：
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:
输入: s = "3z4"
输出: ["3z4","3Z4"]

解析：
递归求解，从左至右遍历字符，如果字符为字母，将当前已遍历的字符串全排列复制两份，在第一份字符串末尾添加toupper(s[index]), 在第二份字符串末尾添加tolower(s[index])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> letterCasePermutation(string s) {
    vector<string> ans;
    slove(s, ans, 0);
    return ans;
}

void slove(string s, vector<string>& ans, int index) {
    if (index == s.size()) {
        ans.push_back(s);
        return;
    }

    if (isalpha(s[index])) {
        s[index] = toupper(s[index]);
        slove(s, ans, index + 1);
        s[index] = tolower(s[index]);
        slove(s, ans, index + 1);
    } else {
        slove(s, ans, index + 1);
    }
}

全排列 II

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

1
2
3
4
5
6
7
8
9
10
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解析：

回溯搜索，序列中包含了重复的数字，要求我们返回不重复的全排列。将这个问题看作有 n 个排列成一行的空格，我们需要从左往右依次填入题目给定的 n 个数，每个数只能使用一次。先对原始数组进行排序，需要一个visited数组记录已经使用过的数，index记录path待填入的位置，如果index==n说明已经填完，找到可行解将path存入res中，递归结束。递归过程中，如果这个数还未使用过，尝试填入继续填下一位置，需要注意的是，数组中存在重复的元素，因此需要先排序，需要保证重复的数字只被填入一次，如果两个相邻的数相同，而且第一个数并未被使用过，则后续相同的数应该跳过循环不填入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<vector<int>> res;
vector<int> path;
vector<bool> visited;
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    visited = vector<bool>(nums.size(), 0);
    slove(nums, 0);
    return res;
}

void slove(vector<int>& nums, int index) {
    if (index == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) {
            continue;
        }
        if (!visited[i]) {
            path.push_back(nums[i]);
            visited[i] = true;
            slove(nums, index + 1);
            path.pop_back();
            visited[i] = false;
        }
    }    
}

二叉树

出现次数最多的子树元素和

508. 出现次数最多的子树元素和

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

img

1
2
输入: root = [5,2,-3]
输出: [2,-3,4]

示例 2：

img

1
2
输入: root = [5,2,-5]
输出: [2]

解析：

从根节点出发dfs遍历，对于每棵子树，其子树元素和等于子树根结点的元素值，加上左子树的元素和，以及右子树的元素和。用哈希表统计每棵子树的元素和的出现次数，计算出现次数的最大值maxCnt，最后将出现次数等于maxCnt的所有元素返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
unordered_map<int, int> count;
int maxCnt = 0;
vector<int> findFrequentTreeSum(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    sum(root);
    for (auto it : count) {
        if (it.second == maxCnt) {
            res.push_back(it.first);
        }
    }
    return res;
}

int sum(TreeNode* root) {
    if (root == nullptr) return 0;
    int left = sum(root->left);
    int right = sum(root->right);
    int res = left + right + root->val;
    count[res]++;
    maxCnt = max(maxCnt, count[res]);
    return res;
}

在每个树行中找最大值

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

img 
1
2
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

1
2
输入: root = [1,2,3]
输出: [1,3]

解析：

两种方法：深度优先搜索与广度优先搜索。

深度优先：用树的「先序遍历」来进行「深度优先搜索」处理，用depth标记遍历到的当前节点的高度，当遍历到depth高度的节点就判断是否更新该层节点的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> largestValues(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    dfs(root, res, 0);
    return res;
}

void dfs(TreeNode* root, vector<int>& res, int depth) {
    if (depth == res.size()) {
        res.push_back(root->val);
    } else {
        res[depth] = max(res[depth], root->val);
    }
    if (root->left) {
        dfs(root->left, res, depth + 1);
    }
    if (root->right) {
        dfs(root->right, res, depth + 1);
    }
}

广度优先：队列中存放的是当前层的所有节点，把当前队列中的全部节点拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是下一层的所有节点，即我们是一层一层地进行拓展，然后每一层我们用maxVal记录该层节点的最大值。当该层全部节点都处理完后，maxVal就是该层全部节点中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> largestValues(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        int maxVal = INT_MIN;
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            maxVal = max(maxVal, cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        res.push_back(maxVal);
    }
    return res;
}

二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

img 
1
2
3
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

1
2
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

1
2
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

解析：

深度优先搜索，对于任意节点root，左子树的节点值小于root的值，右子树的节点值大于root的值。将val插入到以root为根的子树上，根据val与root->val的大小关系，确定将val插入到哪个子树中。如果子树不为空，将val插入到对应的子树上；如果子树为空，在此处新建一个以val为值的节点，连接到父节点root上。

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) {
        TreeNode* cur = new TreeNode(val);
        return cur;
    }
    if (root->val > val) {
        root->left = insertIntoBST(root->left, val);
    }
    if (root->val < val) {
        root->right = insertIntoBST(root->right, val);
    }
    return root;
}

二叉树中的最大路径和

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

img 
1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

img 
1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

解析：

后序遍历，dfs遍历计算单边的最大路径和，最终的最长路径为根节点+左子树的最长单边路径+右子树的单边最长路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxPathSum(TreeNode* root) {       
    if (root == nullptr) return 0;

    int ans = INT_MIN;
    dfs(root, ans);
    return ans;
}

// 定义：计算从根节点 root 为起点的最大单边路径和
int dfs(TreeNode* root, int& ans) {
    if (root == nullptr) return 0;

    int left_sum = max(0, dfs(root->left, ans));
    int right_sum = max(0, dfs(root->right, ans));
	// 后序遍历位置，顺便更新最大路径和
    int path_sum = root->val + left_sum + right_sum;
    ans = max(ans, path_sum);
    // 实现函数定义，左右子树的最大单边路径和加上根节点的值
    // 就是从根节点 root 为起点的最大单边路径和
    return max(left_sum, right_sum) + root->val;
}

路径总和 II

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

img 
1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

img 
1
2
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

1
2
输入：root = [1,2], targetSum = 0
输出：[]

解析：

深度优先dfs搜索，对树进行一次遍历，在遍历时记录从根节点到当前节点的路径和，以防止重复计算。当遍历到叶子节点，且此时路径和恰好为目标和，就找到一条可行路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> res;
vector<int> path;

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    dfs(root, targetSum);
    return res;
}
void dfs(TreeNode* root, int target) {
    if (root == nullptr) return;
    path.push_back(root->val);

    if (root->left == nullptr && root->right == nullptr && target == root->val) {
        res.push_back(path);
    }
    if (root->left) dfs(root->left, target - root->val);
    if (root->right) dfs(root->right, target - root->val);
    path.pop_back();
}

获取你好友已观看的视频

1311. 获取你好友已观看的视频

有 n 个人，每个人都有一个 0 到 n-1 的唯一 id 。

给你数组 watchedVideos 和 friends ，其中 watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。

Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。

给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。

示例 1：

img

1
2
3
4
5
6
7
8
9
输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出：["B","C"] 
解释：
你的 id 为 0（绿色），你的朋友包括（黄色）：
id 为 1 -> watchedVideos = ["C"] 
id 为 2 -> watchedVideos = ["B","C"] 
你朋友观看过视频的频率为：
B -> 1 
C -> 2

示例 2：

img

1
2
3
4
输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出：["D"]
解释：
你的 id 为 0（绿色），你朋友的朋友只有一个人，他的 id 为 3（黄色）。

解析：

广度优先搜索+set/map应用+排序

  • 找出所有 Level k 的好友：使用广度优先的方法，从编号为id的节点开始，得到从id到其余所有节点的最短路径，则所有到id的最短路径为k的节点都是level K的好友
  • 统计好友观看过的视频：哈希表来统计level K的好友观看过的视频，key为视频的名称，value为视频被好友观看过的次数，对于队列中的每个节点x，将watchedVedios[x]中的所有视频依次加入到哈希表中。
  • 将视频按照要求排序：在统计完成之后，我们将哈希映射中的所有键值对存储进数组中，并将它们按照观看次数为第一关键字、视频名称为第二关键字生序排序，即可得到最终的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
    int n = friends.size();
    vector<bool> used(n, 0);
    queue<int> q;
    q.push(id);
    used[id] = true;
    // 寻找id的第level级别的好友将其入队
    for (int k = 1; k <= level; k++) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            int u = q.front();
            q.pop();
            for (auto v : friends[u]) {
                if (!used[v]) {
                    q.push(v);
                    used[v] = true;
                }
            }
        }
    }

    unordered_map<string, int> freq;
    // 哈希表存储队列中出现的电影名字与其出现次数
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const string& watched : watchedVideos[u]) {
            freq[watched]++;
        }
    }

    vector<pair<string, int>> videos(freq.begin(), freq.end());
    // 按照出现次数，影片的名字进行排序
    sort(videos.begin(), videos.end(), 
         [&](const pair<string, int>& a, const pair<string, int>& b) {
         return a.second < b.second || (a.second == b.second && a.first < b.first);
    });
    vector<string> res;
    for (auto& v : videos) {
        res.push_back(v.first);
    }
    return res;
}

拓补

690. 员工的重要性

给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。

比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。

1
2
3
4
5
6
示例：

输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

解析：

由于一个员工最多有一个直系领导，可以有零个或若干个直系下属，因此员工之间的领导和下属关系构成树的结构。给定一个员工编号，要求计算这个员工及其所有下属的重要性之和，即为找到以该员工为根节点的子树的结构中，每个员工的重要性之和。

  1. 深度优先搜索dfs

根据给定的员工编号找到员工，从该员工开始遍历，对于每个员工，将其重要性加到总和中，然后对该员工的每个直系下属继续遍历，直到所有下属遍历完毕，此时的总和即为给定的员工及其所有下属的重要性之和。实现过程中，每个员工的编号都不相同，利用哈希表存储每个id对应的员工，即可通过编号找到对应的员工。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getImportance(vector<Employee*> employees, int id) {
    unordered_map<int, Employee*> map;
    for (auto& e : employees) {
        map[e->id] = e;
    }
    return dfs(id, map);
}

int dfs(int id, unordered_map<int, Employee*>& map) {
    Employee* cur = map[id];
    int total = cur->importance;
    for (auto& i : cur->subordinates) {
        total += dfs(i, map);
    }
    return total;
}
  1. 广度优先搜索bfs

和深度优先搜索一样，使用哈希表存储每个员工编号和对应的员工，即可通过员工编号得到对应的员工。根据给定的员工编号找到员工，从该员工开始广度优先搜索，对于每个遍历到的员工，将其重要性加到总和中，最终得到的总和即为给定的员工及其所有下属的重要性之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int getImportance(vector<Employee*> employees, int id) {
    unordered_map<int, Employee*> map;
    for (auto& e : employees) {
        map[e->id] = e;
    }

    int total = 0;
    queue<int> q;
    q.push(id);
    //total += map[id]->importance;
    while (!q.empty()) {
        int cur_id = q.front();
        q.pop();
        Employee* cur = map[cur_id];
        total += cur->importance;
        for (auto& i : cur->subordinates) {
            q.push(i);
            //total += map[i]->importance;
        }
    }

    return total;
}

堆栈

基本计算器 II

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

1
2
3
4
5
6
7
8
9
10
11
示例 1：
输入：s = "3+2*2"
输出：7

示例 2：
输入：s = " 3/2 "
输出：1

示例 3：
输入：s = " 3+5 / 2 "
输出：5

解析：

栈模拟，用一个栈，保存这些（进行乘除运算后的）整数的值。对于加减号后的数字，将其直接压入栈中；对于乘除号后的数字，可以直接与栈顶元素计算，并替换栈顶元素为计算后的结果。遍历字符串s，用变量sign记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号，每次遍历到数字末尾时，根据sign确定计算方式，遇到减号则将数字的相反数入栈。代码实现中，若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int calculate(string s) {
    int res = 0, d = 0;
    char sign = '+';
    stack<int> cal;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            d = d * 10 + (s[i] - '0');
        }
        if (!isdigit(s[i]) && s[i] != ' ' || i == s.size() - 1) {
            if (sign == '+') {
                cal.push(d);
            } else if (sign == '-') {
                cal.push(-d);
            } else if (sign == '*') {
                cal.top() *= d;
                //int tmp = cal.top() * d;
                // cal.pop();
                // cal.push(tmp);
            } else if (sign == '/') {
                cal.top() /= d;
                // int tmp = cal.top() / d;
                // cal.pop();
                // cal.push(tmp);
            }
            sign = s[i];
            d = 0;
        }
    }
    while (!cal.empty()) {
        res += cal.top();
        cal.pop();
    }
    return res;
}

去除重复字母

316. 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

1
2
3
4
5
6
7
示例 1：
输入：s = "bcabc"
输出："abc"

示例 2：
输入：s = "cbacdcbc"
输出："acdb"

​