LYL's Blog
0%

leetcode刷题系列之数组

发表于 分类于
本文字数： 108k 阅读时长 ≈ 1:38

这篇文章是leetcode刷题系列的第1部分——数组。这里把有代表性的题目发出来，共计82道。主要涉及滑动窗口、哈希表、堆、二分搜索、扫描线、区间相关、拓扑排序、树状数组等算法。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

167. 两数之和 II - 输入有序数组

给定一个有序整数数组和一个目标数，在数组中找到总和等于目标数的两个元素，返回它们的索引。

Example:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 左右指针
vector<int> twoSum(vector<int> nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n - 1;
    while(left < right) {
        int sum = nums[left] + nums[right];
        if(sum == target) {
            return {left + 1, right + 1};
        }
        else if(sum < target) {
            left++;
        }
        else {
            right--;
        }
    }
    return {};
}
1. 两数之和

给定一个无序整数数组和一个目标数，在数组中找到总和等于目标数的两个元素，返回它们的索引。

Example:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
// 借助 hashtable 记录元素的存在情况
vector<int> twoSum(vector<int> nums, int target) {
    unordered_map<int, int> mapping;
    for(int i = 0; i < nums.size(); i++) {
        if(mapping.count(target - nums[i])) {
            return {mapping[target - nums[i]], i};
        }
        else {
            mapping[nums[i]] = i;
        }
    }
    return {};
}
560. Subarray Sum Equals K

给定一个整数数组和一个目标数，返回数组中其总和等于目标数的连续子数组的个数。

Example:

1
2
Input: nums = [1,1,1], k = 2
Output: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 因为这题数组中可以存在负数, 所有不能使用滑动窗口方法
// 暴力解法 超时
int subarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    int res = 0;
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = i; j < n; j++) {
            sum += nums[j];
            if(sum == k) {
                res++;
            }
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 借助前缀和思想
// 使用 hashtable 记录所有的前缀和及其对应的数目
int subarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    unordered_map<int, int> mapping;
    int res = 0, sum = 0;
    // 必须存在的 base case
    // 表示 sum 直接等于 k 的情况
    mapping[0] = 1;
    for(int i = 0; i < n; i++) {
        sum += nums[i];
        if(mapping.count(sum - k)) {
            res += mapping[sum - k];
        }
        mapping[sum]++;
    }
    return res;
}
724. Find Pivot Index

给定一个整数数组，请计算该数组的枢轴索引。枢轴索引使得该索引左侧的所有数字的总和等于在该索引右侧的所有数字的总和。

如果索引在数组的左边缘，则左总和为0，因为左侧没有元素，这也适用于数组的右边缘。如果存在多个枢轴索引，返回最左边的。 如果不存在这样的索引，则返回-1。

Example 1:

1
2
3
4
5
6
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

1
2
3
4
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

1
2
3
4
5
6
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// T: O(N), S: O(N)
int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n + 1);
    // 计算前缀和数组
    // 子数组和 nums[i..j] = prefix[j + 1] - prefix[i]
    for(int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    for(int i = 0; i < n; i++) {
        if((prefix[i] - prefix[0]) == (prefix[n] - prefix[i + 1])) {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// T: O(N), S: O(1)
int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int leftSum = 0;
    for(int i = 0; i < n; i++) {
        if(sum - leftSum - nums[i] == leftSum) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
}
523. Continuous Subarray Sum

给定一个非负整数数组和目标整数k，编写一个函数以检查该数组是否具有大小至少为2的连续子数组，该子数组的总和为k的倍数。

Example 1:

1
2
3
>Input: [23, 2, 4, 6, 7],  k = 6
>Output: True
>Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

1
2
3
>Input: [23, 2, 6, 4, 7],  k = 6
>Output: True
>Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
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
// 基本数学知识 (a - b) % c = 0 --> a % c = b % c
// 借助前缀和思想
// 使用哈希表记录所有的 (前缀和对 k 的余数) 及其 (对应的索引)
bool checkSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    unordered_map<int, int> mapping;
    int sum = 0;
    // 必须存在的 base case
    // 为了处理 sum 本身 对 k 取余为 0 的情况
    // 也就是说这时满足条件的数组是首元素打头的子数组
    mapping[0] = -1;
    for(int i = 0; i < n; i++) {
        sum += nums[i];
        int mod = sum % k;
        // 记住对于前缀和数组
        // 子数组和 nums[i..j] = prefixSum[j + 1] - prefixSum[i]
        // 就理解了为什么是 > 1 而不是 >= 1 了
        if(mapping.count(mod)) {
            if(i - mapping[mod] > 1) {
                return true;
            }
        }
        else {
            mapping[mod] = i;
        }
    }
    return false;
}
1089. 复写零

给定固定长度的整数数组arr，请复制每次出现的零，将其余元素向右移动。请注意，不会写入超出原始数组长度的元素。

对输入数组进行就地修改，不要从函数中返回任何内容。

Example 1:

1
2
3
Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

1
2
3
Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]
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
// 好的解法, 时间复杂度为 O(n)
void duplicateZeros(vector<int> &arr) {
    int n = arr.size();
     // 提前计算出原始数组中 0 的个数
    int zerosCnt = count(arr.begin(), arr.end(), 0);
    if(zerosCnt == 0) {
        return;
    }
    for(int i = n - 1; i >= 0; i--) {
        if(arr[i] != 0) {
            // 计算非零元素的新索引
            // 在此处, 保证 zerosCnt 变量始终是大于 0 的
            // 且表示此非零元素前面的 0 的个数
            int newPos = i + zerosCnt;
            // 如果有效就搬过去
            if(newPos < n) {
                arr[newPos] = arr[i];
            }
            // 原索引处赋 0
            arr[i] = 0;
        }
        else {
            // 每次遇到一个 0, 就减 1
            zerosCnt--;
            // 前面没有 0 了, 就不需要搬移了
            if(zerosCnt == 0) {
                break;
            }
        }
    }
}
941. Valid Mountain Array

给定一个整数数组arr，当且仅当它是有效的山峰数组时，才返回true。当且仅当满足以下条件时，arr是一个山峰数组：

  • arr.size() >= 3
  • There exists some i with 0 < i < arr.size() - 1

such that：

  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.size() - 1]
img

Example 1:

1
2
Input: arr = [2,1]
Output: false

Example 2:

1
2
Input: arr = [3,5,5]
Output: false

Example 3:

1
2
Input: arr = [0,3,2,1]
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 直接模拟就行
bool validMountainArray(vector<int>& arr) {
    int n = arr.size();
    int i = 0;
    // 递增扫描
    while(i + 1 < n && arr[i] < arr[i + 1]) {
        i++;
    }
    // 最高点不能是数组的第一个位置或最后一个位置
    if(i == 0 || i == n - 1) {
        return false;
    }
    // 递减扫描
    while(i + 1 < n && arr[i] > arr[i + 1]) {
        i++;
    }
    return i == n - 1;
}
448. Find All Numbers Disappeared in an Array

给定一个整数数组，其中1 ≤ a[i] ≤ n (n = 数组大小)，某些元素出现两次，而另一些元素出现一次。查找[1，n]包含的所有未出现在此数组中的元素。

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> findDisappearedNumbers(vector<int>& nums) {
    int n = nums.size();
    // 将所有出现过的值作为索引 (值减 1 ), 将该索引所在处的值映射为负数
    for(int i = 0; i < n; i++) {
        int index = abs(nums[i]) - 1;
        if(nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    vector<int> res;
    // 最后没被映射为负数的值, 其对应的索引 +1 就是未出现的值
    for(int i = 0; i < n; i++) {
        if(nums[i] > 0) {
            res.push_back(i + 1);
        }
    }
    return res;
}
442. Find All Duplicates in an Array

给定一个整数数组，即1 ≤ a[i] ≤ n (n = 数组大小)，其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> findDuplicates(vector<int>& nums) {
    vector<int> res;
    // 将所有出现过的值作为索引 (值减 1 ), 将该索引所在处的值映射为负数
    for(int i = 0; i < nums.size(); i++) {
        int index = abs(nums[i]) - 1;
        // 如果已经被映射为负数, 说明之前这个数出现过一次了
        if(nums[index] < 0) {
            res.push_back(index + 1);
        }
        else {
            nums[index] = -nums[index];
        }
    }
    return res;
}
1744. Can You Eat Your Favorite Candy on Your Favorite Day?

给你一个下标从0开始的正整数数组candiesCount，其中candiesCount[i]表示你拥有的第i类糖果的数目。同时给你一个二维数组queries，其中queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]。

你按照如下规则进行一场游戏：

  • 你从第0天开始吃糖果。

  • 你在吃完所有第i - 1类糖果之前，不能吃任何一颗第i类糖果。

  • 在吃完所有糖果之前，你必须每天至少吃一颗糖果。

    请你构建一个布尔型数组answer，满足answer.length == queries.length。answer[i]为true的条件是：在每天吃不超过dailyCap_i颗糖果的前提下，你可以在第favoriteDay_i天吃到第favoriteType_i类糖果；否则answer[i]为false。注意，只要满足上面3条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。

    请你返回得到的数组answer。

示例：

1
2
3
4
5
6
输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：
1. 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果
2. 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果
3. 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 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
// 前缀和 + 区间交集
// 对每一颗糖果依次进行编号
vector<bool> canEat(vector<int> candiesCount, vector<vector<int>> queries)
{
    int n = candiesCount.size();
    // 用 long 防止后面的乘法和加法溢出
    vector<long> prefixSum(n + 1);
    for(int i = 1; i <= n; i++)
        prefixSum[i] = prefixSum[i - 1] + candiesCount[i - 1];
    vector<bool> res;
    res.reserve(queries.size());
    for(auto &query : queries)
    {
        // 每天至少吃 1 颗, 至多吃 query[2] 颗
        // 因此在第 query[1] 天能吃到的糖果的编号范围是 [x1, y1]
        long x1 = query[1] + 1;
        long y1 = long((query[1] + 1)) * query[2];
        // 类型为 query[0] 的糖果的编号范围为 [x2, y2]
        long x2 = prefixSum[query[0]] + 1;
        long y2 = prefixSum[query[0] + 1];
        // 如果有交集就满足条件
        res.push_back(x1 <= y2 && x2 <= y1);
    }
    return res;
}
710. 黑名单中的随机数

给你输入一个正整数N，代表左闭右开区间[0,N)，再给你输入一个数组blacklist，其中包含一些「黑名单数字」，且blacklist中的数字都是区间[0,N)中的数字。

编写一个函数以随机返回[0，N)中的一个整数，该整数不在blacklist中。

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
// 基本思路是记录下实际有效的数字的个数 actual
// 通过一个哈希表将黑名单中的在 [0, actual) 范围内的数字映射到 [actual N) 中不在黑名单中的数字身上
class Solution {
private:
    int actual;
    unordered_map<int, int> mapping;
    
public:
    Solution(int N, vector<int>& blacklist) {
        // 先把黑名单中的所有数字放在哈希表中
        // 便于快速得到 [actual, N) 范围内的数字是否在黑名单中
        for(int val : blacklist) {
            mapping[val] = 0;
        }
        actual = N - blacklist.size();
        for(int val : blacklist) {
            // 黑名单中在 [0, actual) 范围内的数字才需要映射
            if(val < actual) {
                N--;
                // 从后向前映射
                // 如果映射为的数字已经在黑名单中了
                // 就跳过
                while(mapping.count(N)) {
                    N--;
                }
            	mapping[val] = N;
            }
        }
    }
    
    int pick() {
        int i = rand() % actual;
        // 如果这个数字在黑名单中, 需要返回其映射
        if(mapping.count(i) > 0) {
            return mapping[i];
        }
        return i;
    }
};
528. Random Pick with Weight

给定一个正整数数组w，其中w[i]描述第i个索引的权重。

我们需要调用函数pickIndex()，该函数随机返回范围为[0，w.size())的整数。 pickIndex()应该返回与其在w数组中的权重成比例的数。 例如，对于w = [1，3]，选择索引0的概率为1 / (1 + 3) = 0.25，而选择索引1的概率为3 / (1 + 3) = 0.75。或者说，选择索引i的概率为w[i] / sum(w)。

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
// 采用前缀和数组
// 从 [0, sum(w)) 区间内随机产生一个数
// 看这个随机数落在前缀和数组的哪个区间内
// 比如 w = {1, 4, 7, 2};
// prefixSum = {0, 1, 5, 12, 14};
// 从 [0, 14) 区间内随机产生一个数
// 落在 [0, 1) 区间返回 0
// 落在 [1, 5) 区间返回 1
// 落在 [5, 12) 区间返回 2
// 落在 [12, 14) 区间返回 3
class Solution {
private:
    vector<int> prefixSum;
    
public:
    Solution(vector<int>& w) : prefixSum(w.size() + 1) {
        for(int i = 0; i < w.size(); i++) {
            prefixSum[i + 1] = prefixSum[i] + w[i];
        }
    }
    
    int pickIndex() {
        int target = rand() % prefixSum.back();
        // 通过二分搜索加快搜索速度
        // 右边界搜索第一个大于目标值的索引
        int lo = 0, hi = prefixSum.size();
        while(lo < hi) {
            int mi = (hi + lo) / 2;
            if(prefixSum[mi] <= target) {
                lo = mi + 1;
            }
            else {
                hi = mi;
            }
        }
        return lo - 1;
    }
};
11. Container With Most Water

给你n个非负整数a1, a2, ..., an，每个数代表坐标中的一个点(i, ai) 。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0) 。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

返回容纳的水量。

Example:

img 
1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxArea(vector<int>& height) {
    int n = height.size();
    // 左右指针解法
    int left = 0, right = n - 1;
    int res = 0;
    while(left < right) {
        if(height[left] <= height[right]) {
            res = max(res, (right - left) * height[left]);
            // 小的变化, 大的不变
            left++;
        }
        else {
            res = max(res, (right - left) * height[right]);
            // 小的变化, 大的不变
            right--;
        }
    }
    return res;
}
42. Trapping Rain Water

给定n个表示海拔图的非负整数，其中每个条的宽度为1，计算下雨后它可以捕集多少水。

Example:

img 
1
2
3
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
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
// 对于每一个槽, 它所能接的水量取决于它左边最高的柱子和右边最高的柱子中的较低者
// 较低的值减去自身的高度就为该槽所能接的水量

// 使用了备忘录的方法
// 提前计算出每个槽左边最高的柱子和右边最高的柱子(包括它自己的高度)
// left_max[i] 表示第 i 个槽左边最高的柱子的高度
// right_max[i] 表示第 i 个槽右边最高的柱子的高度
// 时间复杂度为 O(n), 但空间复杂度也为 O(n)
int trap(vector<int>& height) {
    if(height.empty()) {
        return 0;
    }
    int n = height.size();
    vector<int> left_max(n);
    vector<int> right_max(n);
    // base case
    left_max.front() = height.front();
    right_max.back() = height.back();
    for(int i = 1; i < n; i++) {
        left_max[i] = max(height[i], left_max[i - 1]);
    }
    for(int i = n - 2; i >= 0; i--) {
        right_max[i] = max(height[i], right_max[i + 1]);
    }
    int res = 0;
    for(int i = 0; i < n; i++) {
        res += min(left_max[i], right_max[i]) - height[i];
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 使用双指针解法
// 边走边记录左边柱子最高值和右边柱子最高值
// 优化后的时间复杂度为 O(n), 空间复杂度为 O(1)
int trap(vector<int>& height) {
    int n = height.size();
    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int res = 0;
    while(left < right) {
        left_max = max(left_max, height[left]);
        right_max = max(right_max, height[right]);
        if(left_max < right_max) {
            res += left_max - height[left];
            left++;
        }
        else {
            res += right_max - height[right];
            right--;
        }
    }
    return res;
}
1395. Count Number of Teams

n名士兵站成一排。每个士兵都有一个独一无二的评分rating。每3个士兵可以组成一个作战单位，分组规则如下：

  1. 从队伍中选出下标分别为i、j、k的3名士兵，他们的评分分别为rating[i]、rating[j]、rating[k]；
  2. 作战单位需满足：rating[i] < rating[j] < rating[k]或者rating[i] > rating[j] > rating[k]，其中0 <= i < j < k < n。

你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

Example 1:

1
2
3
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

1
2
3
Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

1
2
Input: rating = [1,2,3,4]
Output: 4
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
// 提前求得每个元素右边的比它大的元素个数和比它小的元素个数
// 通过两次 O(n2) 的循环, 将时间复杂度减少到 O(n2), 但空间复杂度为 O(n)
int numTeams(vector<int>& rating) {
    int n = rating.size();
    vector<int> right_max(n);
    vector<int> right_min(n);
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(rating[i] < rating[j]) {
                right_max[i]++;
            }
            else {
                right_min[i]++;
            }
        }
    }
    int res = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(rating[i] < rating[j]) {
                res += right_max[j];
            }
            else {
                res += right_min[j];
            }
        }
    }
    return res;
}
1
//
480. Sliding Window Median

中值是有序整数列表中的中间值。 如果列表的大小是偶数，则没有中间值，此时，中位数是两个中间值的平均值。

给定一个数组num，存在一个大小为k的滑动窗口，该窗口从数组的最左边移到最右边。 你只能在窗口中看到k个数字。 每次滑动窗口向右移动一个位置。 你的工作是输出原始数组中每个窗口的中值数组。

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

1
2
3
4
5
6
7
8
Window position               Median
---------------               ------
[1  3  -1] -3  5  3  6  7       1
1  [3  -1  -3] 5  3  6  7      -1
1  3  [-1  -3  5] 3  6  7      -1
1  3  -1  [-3  5  3] 6  7       3
1  3  -1  -3  [5  3  6] 7       5
1  3  -1  -3  5  [3  6  7]      6

Therefore, return the median sliding window as[1,-1,-1,3,5,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
29
30
31
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<double> median;
    multiset<int> window(nums.begin(), next(nums.begin(), k));
    // k 为奇数, mid 指向中间元素, k 为偶数, mid 指向中间两个元素的后一个元素
    // 之后每一次插入和删除元素都要维护 mid 正确性
    auto mid = next(window.begin(), k / 2);
    for(int i = k; ; i++) {
        if(k & 1) {
            median.push_back(*mid);
        }
        else {
            median.push_back((double(*prev(mid)) + double(*mid)) * 0.5);
        }
        if(i == n) {
            break;
        }
        // 如果插入相同的元素
        // multiset 的 insert 操作将其插入到范围上界
        window.insert(nums[i]);
        if(nums[i] < *mid) {
            mid--;
        }
        if(nums[i - k] <= *mid) {
            mid++;
        }
        // 删除时从范围下界删除可保证 mid 不失效
        window.erase(window.lower_bound(nums[i - k]));
    }
    return median;
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    if(k & 1) {
        return medianSlidingWindowForOdd(nums, k);
    }
    return medianSlidingWindowForEven(nums, k);
}

// 只考虑 k 为奇数的情况
vector<double> medianSlidingWindowForOdd(vector<int>& nums, int k) {
    vector<double> median;
    multiset<int> window(nums.begin(), next(nums.begin(), k));
    // 窗口内有奇数个元素时, mid 指向中间元素
    // 窗口内有偶数个元素时, mid 指向中间两个元素的后一个元素
    // 之后每一次插入和删除元素都要维护 mid 正确性
    auto mid = next(window.begin(), k / 2);
    for(int i = k; ; i++) {
        median.push_back(*mid);
        if(i == nums.size()) {
            break;
        }
        // 注意, 插入前集合中的元素数为奇数个
        // 如果插入相同的元素, multiset 的 insert 操作将其插入到范围上界
        window.insert(nums[i]);
        if(nums[i] >= *mid) {
            // 如果插入在 mid 右边
            ++mid;
        }
        // 插入后变为偶数个元素了
        if(nums[i - k] < *mid) {
            // 如果在 mid 左边删除
            window.erase(window.find(nums[i - k]));
        }
        else if(nums[i - k] > *mid) {
            // 如果在 mid 右边删除
            window.erase(window.find(nums[i - k]));
            --mid;
        }
        else {
            // 如果删除的就是 mid
            mid = window.erase(mid); // 注意 erase 会返回删除元素的后继元素迭代器
            --mid;
        }
    }
    return median;
}

// 只考虑 k 为偶数的情况
vector<double> medianSlidingWindowForEven(vector<int>& nums, int k) {
    vector<double> median;
    multiset<int> window(nums.begin(), next(nums.begin(), k));
    // 窗口内有偶数个元素时, mid 指向中间元素
    // 窗口内有奇数个元素时, mid 指向中间两个元素的后一个元素
    // 之后每一次插入和删除元素都要维护 mid 正确性
    auto mid = next(window.begin(), k / 2);
    for(int i = k; ; i++) {
        median.push_back((double(*prev(mid)) + double(*mid)) * 0.5);
        if(i == nums.size()) {
            break;
        }
        // 注意, 插入前集合中的元素数为偶数个
        // 如果插入相同的元素, multiset 的 insert 操作将其插入到范围上界
        window.insert(nums[i]);
        if(nums[i] < *mid) {
            // 如果插入在 mid 左边
            --mid;
        }
        // 插入后变为奇数个元素了
        if(nums[i - k] < *mid) {
            // 如果在 mid 左边删除
            window.erase(window.find(nums[i - k]));
            ++mid;
        }
        else if(nums[i - k] > *mid) {
            // 如果在 mid 右边删除
            window.erase(window.find(nums[i - k]));
        }
        else {
            // 如果删除的就是 mid
            mid = window.erase(mid); // 注意 erase 会返回删除元素的后继元素迭代器
        }
    }
    return median;
}
239. Sliding Window Maximum

给你一个整数数组num，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7
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
// 单调队列保证从队头到队尾是递减的
class MonoQ {
private:
    deque<int> monoQ;
    
public:
    // 如果入队的值比队尾的值大, 就把队尾元素 pop 掉, 这样保证是递减的
    void push(int val) {
        while(!monoQ.empty() && monoQ.back() < val) {
            monoQ.pop_back();
        }
        monoQ.push_back(val);
    }
    // pop 的时候如果不是队头元素就什么也不做
    void pop(int val) {
        if(monoQ.front() == val) {
            monoQ.pop_front();
        }
    }
    // 最大值就是队头元素
    int maxVal() {
        return monoQ.front();
    }
};
// 维护一个大小为 k 的递减队列
// 这个队列就相当于是题目中的滑动窗口
// 只是单调之后取其中的最大值很方便
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> res;
    MonoQ monoQ;
    for(int i = 0; i < n; i++) {
        monoQ.push(nums[i]);
        // 如果窗口内的元素数等于 k
        if(i >= k - 1) {
            // 最大值就是队头元素
            res.push_back(monoQ.maxVal());
            // pop 掉最左边的将要出窗口的元素
            monoQ.pop(nums[i - k + 1]);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 当然也可以不先写好一个单调队列类
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> res;
    // 用 deque 模拟队列
    deque<int> monoQ;
    for(int i = 0; i < n; i++) {
        while(!monoQ.empty() && monoQ.back() < nums[i]) {
            monoQ.pop_back();
        }
        monoQ.push_back(nums[i]);
        if(i >= k - 1) {
            res.push_back(monoQ.front());
            if(monoQ.front() == nums[i - k + 1]) {
                monoQ.pop_front();
            }
        }
    }
    return res;
}
1834. Single-Threaded CPU

给你一个二维数组tasks，用于表示n项从0到n - 1编号的任务。其中tasks[i] = [enqueueTimei, processingTimei]意味着第i项任务将会于enqueueTimei时进入任务队列，需要processingTimei的时长完成执行。

现有一个单线程CPU，同一时间只能执行最多一项任务，该CPU将会按照下述方式运行：

  • 如果CPU空闲，且任务队列中没有需要执行的任务，则CPU保持空闲状态。
  • 如果CPU空闲，但任务队列中有需要执行的任务，则CPU将会选择执行时间最短的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
  • 一旦某项任务开始执行，CPU在执行完整个任务前都不会停止。
  • CPU可以在完成一项任务后，立即开始执行一项新任务。

返回CPU处理任务的顺序。

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
>Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
>Output: [0,2,3,1]
>Explanation: The events go as follows: 
>- At time = 1, task 0 is available to process. Available tasks = {0}.
>- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
>- At time = 2, task 1 is available to process. Available tasks = {1}.
>- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
>- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
>- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
>- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
>- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
>- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

1
2
3
4
5
6
7
8
9
10
>Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
>Output: [4,3,2,0,1]
>Explanation: The events go as follows:
>- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
>- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
>- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
>- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
>- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
>- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
>- At time = 40, the CPU finishes task 1 and becomes idle.
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
using Pair = pair<int, int>;
vector<int> getOrder(vector<vector<int>>& tasks) {
    int taskCount = tasks.size();
    for(int taskId = 0; taskId < taskCount; taskId++) {
        tasks[taskId].push_back(taskId);
    }
    sort(tasks.begin(), tasks.end());
    vector<int> res;
    priority_queue<Pair, vector<Pair>, greater<Pair>> tasksQueue;
    int taskId = 0;
    long timeStamp = 0; // 时刻
    while(taskId < taskCount || !tasksQueue.empty()) {
        if(tasksQueue.empty()) {
            timeStamp = max(timeStamp, (long)tasks[taskId][0]);
        }
        while(taskId < taskCount && tasks[taskId][0] <= timeStamp) {
            tasksQueue.push({tasks[taskId][1], tasks[taskId][2]});
            taskId++;
        }
        auto [duration, id] = tasksQueue.top();
        tasksQueue.pop();
        timeStamp += duration;
        res.push_back(id);
    }
    return res;
}
912. 排序数组

给你一个整数数组nums，请你将该数组升序排列。

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
void sortArray(vector<int> &nums) {
    // 下滤操作, 复杂度正比于完全二叉树的高度为 log(n)
    // 参数 n 代表 [有效堆] 数组的长度, 可用于验证待下滤元素 hole 的左右孩子节点的合法性
    auto down = [&](int hole, int n) {
        // 先保存待下滤的值, hole 代表洞号
        int holeVal = nums[hole];
        // 先找到待下滤元素的左孩子
        for(int lc = 2 * hole + 1; lc < n; lc = 2 * hole + 1) {
            // 如果右子节点存在并且左子节点的值小于等于右子节点
            if(lc + 1 < n && nums[lc] <= nums[lc + 1]) {
                lc++;
            }
            // 此时, lc 指向孩子节点中较大的那一个
            // 如果待下滤的值比孩子中较大的还大, 就不需要下滤了
            if(nums[lc] <= holeVal) {
                break;
            }
            nums[hole] = nums[lc];
            // 产生新的洞号
            hole = lc;
        }
        nums[hole] = holeVal;
    };
    int n = nums.size();
    // 获取末元素的父亲, 也就是最后一个内部节点
    int lastInternal = (n - 1 - 1) / 2;
    // 建堆操作, 复杂度为 O(n)
    while(lastInternal >= 0) {
        down(lastInternal--, n);
    }
    for(int i = n - 1; i > 0; i--) {
        // 此时最大元素是首元素
        // 首尾交换, 末元素就位
        swap(nums[i], nums[0]);
        // 将新首元素下滤
        down(0, i);
    }
}
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
// 归并排序, 自顶向下递归实现
vector<int> sortArray(vector<int> &nums) {
    int n = nums.size();
    // 排序 [0, n - 1] 之间的元素
    mergeSort(nums, 0, n - 1);
    return nums;
}
// 左闭右闭区间
void mergeSort(vector<int> &nums, int lo, int hi) {
    // 单元素自动有序
    if(hi - lo < 1) {
        return;
    }
    int mi = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mi);
    mergeSort(nums, mi + 1, hi);
    merge(nums, lo, mi, hi);
}
// 左闭右闭区间
// [lo, mi] 和 [mi + 1, hi] 分别是有序的
void merge(vector<int> &nums, int lo, int mi, int hi) {
    // 辅助空间, 存储 [mi + 1, hi] 元素
    vector<int> helper(next(nums.begin(), mi + 1), next(nums.begin(), hi + 1));
    // 对两个数组中的元素, 依次从后向前比较
    // 从后向前放置元素, 先放较大者
    int i = mi;
    int j = hi - mi - 1;
    int k = hi;
    // 注意 i 的终止条件
    while(i >= lo && j >= 0) {
        // 注意, 这里如果是 >= 就不稳定了
        if(nums[i] > helper[j]) {
            nums[k--] = nums[i--];
        }
    	else {
        	nums[k--] = helper[j--];
        }
    }
    while(j >= 0) {
        nums[k--] = helper[j--];
    }
}

/* 归并排序, 自底向上迭代实现 */
vector<int> sortArray(vector<int>& nums) {
    int sz = nums.size();
    // 中间节点相对于起点的位置是 1 个 step
    // 终点相对于起点是 2 个 step
    // step 从 1 开始直到等于数组的长度 sz 
    for(int step = 1; step <= sz; step *= 2) {
        // 注意, 这里 lo 从 0 开始直到等于 sz - 1
        for(int lo = 0; lo < sz; lo += 2 * step) {
            // 因为 merge 函数实现的原因, 都是闭区间, 而且 [lo, mi] 和 [mi + 1, hi] 分别是有序的
            // 所以这里求出的 mi 和 hi 都需要减 1
            merge(nums, lo, min(lo + step - 1, sz - 1), min(lo + 2 * step - 1, sz - 1));
        }
    }
    return nums;
}
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
// quick sort
vector<int> sortArray(vector<int> &nums) {
    int n = nums.size();
    quickSort(nums, 0, n - 1);
    return nums;
}

// 左闭右闭区间
void quickSort(vector<int> &nums, int lo, int hi) {
    if(lo >= hi) {
        return;
    }
    // 随机置乱闭区间 [lo, hi] 内的元素
    auto shuffle = [&](int lo, int hi) {
        for(int i = lo; i <= hi; i++) {
            int j = rand() % (hi - i + 1) + i;
            swap(nums[i], nums[j]);
        }
    };
    auto partition = [&](int lo, int hi) {
        shuffle(lo, hi);
        int i = lo, j = lo;
        while(++j <= hi) {
            if(nums[j] <= nums[lo]) {
                swap(nums[++i], nums[j]);
            }
        }
        swap(nums[lo], nums[i]);
        return i;
    };
    int pivot = partition(lo, hi);
    quickSort(nums, lo, pivot - 1);
    quickSort(nums, pivot + 1, hi);
}
34. Find First and Last Position of Element in Sorted Array

给定一个以升序排列的整数nums数组，请找到给定目标值的开始和结束位置。如果在数组中未找到目标，则返回[-1，-1]。

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> searchRange(vector<int>& nums, int target) {
    int left = right_bound(nums, target - 1);
    int right = right_bound(nums, target);
    if(left < 0 || left >= nums.size() || nums[left] != target) {
        return {-1, -1};
    }
    return {left, right - 1};
}

// 右边界搜索是返回第一个大于目标值的位置
int right_bound(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size();
    while(lo < hi) {
        int mi = lo + (hi - lo >> 1);
        if(target >= nums[mi]) {
            lo = mi + 1;
        }
        else {
            hi = mi;
        }
    }
    return lo;
}
240. Search a 2D Matrix II

编写一个高效的算法来搜索m x n矩阵matrix中的一个目标值target。该矩阵具有以下特性：

  1. 每行的元素从左到右升序排列。
  2. 每列的元素从上到下升序排列。

Example 1:

img 
1
2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Example 2:

img 
1
2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n = matrix.size();
    if(n == 0) {
        return false;
    }
    int r = 0, c = matrix[0].size() - 1;
    while(r < n && c >= 0) {
        if(target < matrix[r][c]) {
            c--;
        }
        else if(target > matrix[r][c]) {
            r++;
        }
        else {
            return true;
        }
    }
    return false;
}
162. Find Peak Element

峰值元素是指其值严格大于左右相邻值的元素。给你一个输入数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

Example 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

1
2
3
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
int findPeakElement(vector<int>& nums)
{
    int lo = 0, hi = nums.size() - 1;
    while(lo < hi)
    {
        int mi = lo + (hi - lo >> 1);
        if(nums[mi] > nums[mi + 1])
            hi = mi;
        else
            lo = mi + 1;
    }
    return lo;
}
658. Find K Closest Elements

给定一个排序好的数组arr，两个整数k和x，从数组中找到最靠近x（两数之差最小）的k个数。返回的结果必须要是按升序排好的。

整数a比整数b更接近x需要满足：

  • |a - x| < |b - x|或者
  • |a - x| == |b - x|且a < b.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 按照与 x 差值的绝对值进行排序
// 返回排序后数组的前 k 个元素的原始顺序即可
// 时间复杂度为排序的复杂度 O(nlogn)
vector<int> findClosestElements(vector<int>& arr, int k, int x)
{
    vector<int> res(arr);
    sort(res.begin(), res.end(),
         [x](int a, int b)
         {
             return abs(a - x) == abs(b - x) ? a < b : abs(a - x) < abs(b - x);
         });
    res.resize(k);
    sort(res.begin(), res.end());
    return 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 因为数组已经是有序的, 先通过二分搜索找到 x 在数组中的位置
// 根据 x 的位置不同有几种情况
vector<int> findClosestElements(vector<int> &arr, int k, int x) {
    // vector<int> res(k);
    vector<int> res;
    // 里面这段二分搜索是左边界搜索
    // lo 最后指向第一个大于等于 x 的元素
    int lo = 0, hi = arr.size();
    while(lo < hi) {
        int mi = lo + (hi - lo >> 1);
        if(x <= arr[mi]) {
            hi = mi;
        }
        else {
            lo = mi + 1;
        }
    }
    // 如果 x 小于等于数组中的任何数, 那离 x 最近的就是前 k 个元素
    if(lo == 0) {
        // copy_n(arr.begin(), k, res.begin());
        copy(arr.begin(), arr.end(), back_inserter(res));
    }
    // 如果 x 大于等于数组中的任何数, 那离 x 最近的就是后 k 个元素
    else if(lo == arr.size()) {
        // copy_n(arr.end() - k, k, res.begin());
        copy(prev(arr.end(), k), arr.end(), back_inserter(res));
    }
    else {
        // 如果在中间, 就设置两个指针
        // 左右指针离 lo 的位置都为 k, 组成一个窗口
        // 在窗口中移动双指针使得窗口内元素数缩减为最接近 x 的 k 个数即可
        int left = max(lo - k, 0);
        int right = min(lo + k, int(arr.size()) - 1);
        while(right - left > k - 1) {
            if(abs(arr[left] - x) <= abs(arr[right] - x)) {
                right--;
            }
            else {
                left++;
            }
        }
        // copy_n(arr.begin() + left, k, res.begin());
        copy(next(arr.begin(), left), next(arr.begin(), left + k), back_inserter(res));
    }

    return res;
}
719. Find K-th Smallest Pair Distance

给定一个整数数组，返回所有数对之间的第k个最小距离。一对(A, B) 的距离被定义为A和B之间的绝对差值。

Note:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

Example:

1
2
3
4
5
6
7
8
9
10
Input:
nums = [1,3,1]
k = 1
Output: 0 
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 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
36
37
38
39
40
41
42
43
44
45
// 暴力解法
// Time Limit Exceeded
int smallestDistancePair(vector<int>& nums, int k)
{
    vector<int> distances;
    for(int i = 0; i < nums.size(); i++)
        for(int j = i + 1; j < nums.size(); j++)
            distances.push_back(abs(nums[i] - nums[j]));

    int lo = 0, hi = distances.size() - 1;
    while(lo <= hi)
    {
        int pivot = partition(distances, lo, hi);
        if(pivot == k - 1)
            return distances[pivot];
        else if(pivot < k - 1)
            lo = pivot + 1;
        else
            hi = pivot - 1;
    }
    return 0;
}

int partition(vector<int>& nums, int lo, int hi)
{
    int i = lo, j = lo;
    while(++j <= hi)
        if(nums[j] < nums[lo])
            swap(nums[++i], nums[j]);
    swap(nums[lo], nums[i]);
    return i;
}

// 用一个 multiset 实现起来更简单, 但还是 Time Limit Exceeded!
int smallestDistancePair(vector<int>& nums, int k)
{
    multiset<int> setting;
    // 因为核心在这, 计算所有的 pair 复杂度为 O(n2)
    for(int i = 0; i < nums.size(); i++)
        for(int j = i + 1; j < nums.size(); j++)
            setting.insert(abs(nums[i] - nums[j]));

    auto it = next(setting.begin(), k - 1);
    return *it;
}
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
// binary search, a good idea.
// another problem, 373. Find K Pairs with Smallest Sums
int smallestDistancePair(vector<int>& nums, int k)
{
    // 先把数组排序
    sort(nums.begin(), nums.end());
    // pairs 之间的差值最小无非就是 0
    int lo = 0;
    // 最大就是尾元素减去首元素嘛
    int hi = nums.back() - nums[0];
    // 问题转化为在这个范围内找到一个差值
    // 使得有 k - 1 个 pair 的差值不比它大
    // 这种在有序的数值范围内搜索一个特定值就是典型的二分搜索的应用
    while(lo < hi)
    {
        // 取差值的中间
        int mi = lo + (hi - lo) / 2;
        // 下面应用一个滑动窗口算法计算有多少个比 mi 小的差值
        // 不要被两个 while 循环吓到了, 实际复杂度只有 O(n), 不清楚看最下面注释
        int count = 0, left = 0, right = 1;
        while(right < nums.size())
        {
            while(nums[right] - nums[left] > mi)
                left++;
            count += right - left;
            right++;
        }

        // count == number of pairs with distance <= mi
        if(k <= count)
            hi = mi;
        else
            lo = mi + 1;
    }
    return lo;
}

/*
1. Time Complexity:O(NlogW + NlogN), where N is the length of nums, and W is equal to nums[nums.length - 1] - nums[0]. The logW factor comes from our binary search, and we do O(N) work inside our call to possible (or to calculate count). The final O(NlogN) factor comes from sorting.
2. Space Complexity: O(1). No additional space is used except for integer variables.
*/

/*
It is O(N). the possible function is a classic sliding windowing solution, left and right would always increment in each outer loop iteration, that is 'left' and 'right' sweeps elements in the array only once. So time complexity is O(2N) = O(N).
*/
373. Find K Pairs with Smallest Sums

给定两个以升序排列的整形数组nums1和nums2，以及一个整数k。

定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自nums2。

找到和最小的k对数字(u1,v1),(u2,v2)...(uk,vk)。

Constraints:

  • 1 <= nums1.length, nums2.length <= 104
  • -109 <= nums1[i], nums2[i] <= 109
  • nums1 and nums2 both are sorted in ascending order.
  • 1 <= k <= 1000

Example 1:

1
2
3
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

1
2
3
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

1
2
3
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    auto cmp = [](auto& a, auto& b) { return a.first + a.second < b.first + b.second; };
    vector<vector<int>> res;
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    for(int num1 : nums1) {
        for(int num2 : nums2) {
            pq.push({num1, num2});
            if(pq.size() > k) {
                pq.pop();
            }
        }
    }
    
    while(!pq.empty()) {
        res.push_back({pq.top().first, pq.top().second});
        pq.pop();
    }
    
    return res;
}
209. Minimum Size Subarray Sum

给定一个含有n个正整数的数组和一个正整数target。

找出该数组中满足其和≥ target的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。

Example 1:

1
2
3
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

1
2
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

1
2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// T: O(n), S: O(n)
int minSubArrayLen(int target, vector<int>& nums)
{
    vector<int> prefix(nums.size() + 1);
    for(int i = 0; i < nums.size(); i++)
        prefix[i + 1] = prefix[i] + nums[i];

    int left = 0, right = 0;
    int res = INT_MAX;
    while(right < nums.size())
    {
        right++;
        while(prefix[right] - prefix[left] >= target)
        {
            res = min(res, right - left);
            left++;
        }
    }

    return res == INT_MAX ? 0 : res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// T: O(n), S: O(1)
int minSubArrayLen(int target, vector<int>& nums)
{
    int left = 0, right = 0, sum = 0;
    int res = INT_MAX;
    while(right < nums.size())
    {
        sum += nums[right];
        right++;
        while(sum >= target)
        {
            res = min(res, right - left);
            sum -= nums[left];
            left++;
        }
    }
    
    return res == INT_MAX ? 0 : 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
29
30
31
32
33
34
35
36
37
// T: O(nlogn), S: O(n)
int minSubArrayLen(int target, vector<int>& nums)
{        
    vector<int> prefixSum(nums.size() + 1, 0);
    for(int i = 1; i <= nums.size(); i++)
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

    int res = INT_MAX;
    for(int i = 0; i < nums.size(); i++)
    {
        int to_find = target + prefixSum[i];
        // auto it = lower_bound(prefixSum.begin(), prefixSum.end(), to_find);
        // if(it != prefixSum.end())
        //     res = min(res, int(distance(prefixSum.begin(), it)) - i);

        int it = _lower_bound(prefixSum, to_find);
        if(it != prefixSum.size())
            res = min(res, it - i);
    }

    return res == INT_MAX ? 0 : res;
}

int _lower_bound(vector<int>& nums, int target)
{
    int lo = 0, hi = nums.size() - 1;
    while(lo <= hi)
    {
        int mi = lo + (hi - lo >> 1);
        if(target <= nums[mi])
            hi = mi - 1;
        else
            lo = mi + 1;
    }

    return lo;
}
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

给你一个整数数组nums，和一个表示限制的整数limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组，则返回0。

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= limit <= 109

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>Input: nums = [8,2,4,7], limit = 4
>Output: 2 
>Explanation: All subarrays are: 
>[8] with maximum absolute diff |8-8| = 0 <= 4.
>[8,2] with maximum absolute diff |8-2| = 6 > 4. 
>[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
>[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
>[2] with maximum absolute diff |2-2| = 0 <= 4.
>[2,4] with maximum absolute diff |2-4| = 2 <= 4.
>[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
>[4] with maximum absolute diff |4-4| = 0 <= 4.
>[4,7] with maximum absolute diff |4-7| = 3 <= 4.
>[7] with maximum absolute diff |7-7| = 0 <= 4. 
>Therefore, the size of the longest subarray is 2.

Example 2:

1
2
3
>Input: nums = [10,1,2,4,7,2], limit = 5
>Output: 4 
>Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

1
2
>Input: nums = [4,2,2,2,4,4,2,2], limit = 0
>Output: 3
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
// 这题使用一个滑动窗口是毋庸置疑的
// 关键是我们希望实时的知道窗口内元素的最大值和最小值
// 那么我们要将窗口内的元素存储在哪种合适的数据结构中
// 满足我们要求的同时还能保证效率呢
// 1. 二叉搜索树, 我们可以方便的获得其中的最大值和最小值, 并且插入的效率为 o(logn)
//    最小值在树的最左边, 最大值在树的最右边
// 2. 单调队列, 使用两个单调队列, 一个是从队首到队尾递减的顺序, 一个是从队首到队尾递增的顺序
//    这样最大值和最小值分别都在它们的队首, 插入的效率为 O(1)

// 注意窗口中可能存在的重复值的情况
// 这些重复值在搜索树或者在队列中都要同时存在

// 滑动窗口 + multiset
// 时间复杂度为 O(nlogn)
int longestSubarray(vector<int>& nums, int limit)
{
    multiset<int> setting;
    int res = 0;
    int left = 0, right = 0;
    while(right < nums.size())
    {
        setting.insert(nums[right++]);
        while(*setting.rbegin() - *setting.begin() > limit)
            setting.erase(setting.find(nums[left++]));
        res = max(res, right - left);
    }

    return 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
29
30
31
32
33
34
// 小技巧: 对于需要实时获取序列中最大值或最小值的问题, 单调队列是非常适合的数据结构!
// 滑动窗口 + 单调队列
// 时间复杂度为 O(n)
int longestSubarray(vector<int>& nums, int limit)
{
    deque<int> minQ;
    deque<int> maxQ;
    int res = 0;
    int left = 0, right = 0;
    while(right < nums.size())
    {
        while(!minQ.empty() && minQ.back() > nums[right])
            minQ.pop_back();
        while(!maxQ.empty() && maxQ.back() < nums[right])
            maxQ.pop_back();

        minQ.push_back(nums[right]);
        maxQ.push_back(nums[right]);
        right++;
        while(!minQ.empty() && !maxQ.empty() && (maxQ.front() - minQ.front() > limit))
        {
            if(minQ.front() == nums[left])
                minQ.pop_front();

            if(maxQ.front() == nums[left])
                maxQ.pop_front();

            left++;
        }
        res = max(res, right - left);
    }

    return 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
29
30
31
32
33
34
35
36
37
38
39
40
// 用一个数组模拟两个单调队列是真的秀啊
int longestSubarray(vector<int>& nums, int limit)
{
    int res = 0;
    // minL 和 minR 是最小值区间的左右指针, maxL 和 maxR 是最大值区间的左右指针
    int minL = 0, minR = -1, maxL = nums.size(), maxR = nums.size() - 1;
    // l, r 是 nums 的左右指针
    int l = 0, r = 0;
    // 这个数组用来记录最小值和最大值
    vector<int> ascending(nums.size());
    // 开始遍历 nums
    while(r < nums.size())
    {
        // 如果遍历到的数字在最小值区间内, 就收缩最小值区间
        while(minR >= minL && nums[r] < ascending[minR])
            minR--;
        // 如果遍历到的数字在最大值区间内, 就收缩最大值区间
        while(maxR >= maxL && nums[r] > ascending[maxL])
            maxL++;
        // 拓展最小值和最大值区间
        ascending[++minR] = nums[r];
        ascending[--maxL] = nums[r];
        r++;
        // 判断子集长度是否符合 limit 的要求, 如果不符合要求, 就收缩子集
        while(ascending[maxR] - ascending[minL] > limit)
        {
            // 开始收缩子集, 使子集左指针右移
            // 如果子集左指针是最小值, 那么最小值将被移除, 所以更新存储最小值的区间
            if(nums[l] == ascending[minL])
                minL++;
            // 如果子集左指针是最大值, 那么最大值将被移除, 所以更新存储最大值的区间
            if(nums[l] == ascending[maxR])
                maxR--;
            l++;
        }
        res = max(res, r - l);
    }
    // 返回结果
    return res;
}
220. Contains Duplicate III

给你一个整数数组nums和两个整数k和t。请你判断是否存在两个不同下标i和j，使得abs(nums[i] - nums[j]) <= t，同时又满足abs(i - j) <= k。如果存在则返回true，不存在返回false。

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

1
2
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: 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
// 滑动窗口 + 二叉搜索树
// 在 set 中维护一个元素数为 k 的滑动窗口
// 这可保证在 set 中的元素的索引满足 abs(i - j) <= k
// 我们每迭代到数组中的下一个元素 [nums[i], 在更新 set 前
// 都要在其中找到一个在 [nums[i] - k, nums[i] + k] 范围内的值
// 如果存在, 那么就满足 abs(nums[i] - nums[j]) <= t
// 为什么选择 multiset?
// 因为 set 具有自动排序的特性, 并且每次查找、删除和插入的复杂度都为
// 高效的 log(n). 因为我们要频繁地查找在范围 [nums[i] - k,
// nums[i] + k] 内的值, 还要频繁地删除和插入元素以维持固定地滑动窗口大小
// 注意一点, 在计算 nums[i] - k 和 nums[i] + k 的时候可能会出现数值溢出
// 所以要全部用 long
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
    set<long> ms;
    for(size_t i = 0; i < nums.size(); i++)
    {
        // 注意此时 nums[i] 是不包含在窗口内的
        // 并且窗口内的元素数量 ? <= k, 我们以第 ? + 1 个元素为对象
        // 寻找满足条件的另一个元素, 这样每一个元素都会 [被看作对象] 一次
        long valMin = (long)nums[i] - (long)t;
        // iter 指向首次进入 [nums[i] - k, ... 范围的数
        // 因此还要验证这个数是否也在 ..., nums[i] + k] 范围内
        auto iter = ms.lower_bound(valMin);
        // 如果存在这么一个数, 就找到满足条件的两个数了
        if(iter != ms.end() && *iter <= (long)nums[i] + (long)t)
            return true;

        // 当前对象已经处理过了, 将它放进窗口
        // 如果窗口大小超过 k 了, 还要将最左边的那个数剔出窗口
        ms.insert(nums[i]);
        if(ms.size() > k)
            ms.erase(nums[i - k]);
    }
    return 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
// 滑动窗口 + 分桶
// 将数组中的数值按照映射函数分配到相应桶中
// 映射函数为 桶号 id = value / (t + 1)
// 这样可保证
// 1. 映射到同一个桶的数值之差一定小于等于 t
// 2. 相邻桶中也有可能存在差值小于等于 t 的情况
// 3. 不相邻的桶中元素差值必定大于 t
// 如数组为 [1 5 9 1 3 7 8], k = 2, t = 3, 桶宽度为 t + 1 = 4
// 0 号桶: [1 1 3], 1 号桶: [5 7], 2 号桶: [9 8]
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
    long bucketsWidth = long(t) + 1;
    unordered_map<long, long> buckets;
    for(int i = 0; i < nums.size(); i++)
    {
        int id = getKey(nums[i], bucketsWidth);
        // 在一个桶中一定满足条件
        if(buckets.count(id)) return true;
        // 在左边相邻桶中, 再判断差值是否满足条件
        if(buckets.count(id - 1) && nums[i] - buckets[id - 1] <= t)
            return true;
        // 在右边相邻桶中, 再判断差值是否满足条件
        if(buckets.count(id + 1) && buckets[id + 1] - nums[i] <= t)
            return true;
        buckets[id] = nums[i];
        // 保证所有桶中的元素小于等于 k 个
        // 如果大于 k, 就将窗口最左边的元素剔除
        if(buckets.size() > k)
            buckets.erase(getKey(nums[i - k], bucketsWidth));
    }

    return false;
}

int getKey(int value, long bucketsWidth)
{
    int id = value / bucketsWidth;
    // 注意这里如果 value 为负数, 需要将桶号减 1
    // 保证 0 号桶的正确性
    if(value < 0) id--;
    return id;
}
498. Diagonal Traverse

给定一个含有m x n个元素的矩阵（m行，n列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

Example 1:

img 
1
2
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

1
2
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> findDiagonalOrder(vector<vector<int>>& matrix)
{
    if(matrix.empty()) return vector<int>();

    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> v(m + n - 1);

    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            v[i + j].push_back(matrix[i][j]);

    vector<int> res;
    for(int i = 0; i < v.size(); i++)
    {
        if(i % 2 == 0)
            reverse(v[i].begin(), v[i].end());
        res.insert(res.end(), v[i].begin(), v[i].end());
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> findDiagonalOrder(vector<vector<int>>& matrix)
{
    map<int, vector<int>> mapping;
    for(int i = 0; i < matrix.size(); i++)
        for(int j = 0; j < matrix[i].size(); j++)
            mapping[i + j].push_back(matrix[i][j]);

    vector<int> res;
    for(auto& p: mapping)
    {
        if(p.first % 2 == 0)
            res.insert(res.end(), p.second.rbegin(), p.second.rend());
        else
            res.insert(res.end(), p.second.begin(), p.second.end());
    }

    return res;
}
1424. Diagonal Traverse II

给你一个列表num，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回num中对角线上的整数。

Example 1:

img

1
2
>Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
>Output: [1,4,2,7,5,3,8,6,9]

Example 2:

img

1
2
>Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
>Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> findDiagonalOrder(vector<vector<int>>& nums)
{
    map<int, vector<int>> mapping;
    for(int i = 0; i < nums.size(); i++)
        for(int j = 0; j < nums[i].size(); j++)
            mapping[i + j].push_back(nums[i][j]);

    vector<int> res;
    for(auto& p: mapping)
        res.insert(res.end(), p.second.rbegin(), p.second.rend());

    return res;
}
54. Spiral Matrix

给你一个m行n列的矩阵matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

Example 1:

img 
1
2
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

img 
1
2
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
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
// Traverse the matrix in the spiral order by keeping four variables
// u for the uppermost row, d for the downmost row
// l for the leftmost column, r for the rightmost column.
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
    int m = matrix.size();
    int n = matrix[0].size();
    int u = 0, d = m - 1, l = 0, r = n - 1;
    
    int p = 0;
    vector<int> order(m * n);
    while (u <= d && l <= r)
    {
        for(int col = l; col <= r; col++)
            order[p++] = matrix[u][col];
        if(++u > d) break;
        
        for(int row = u; row <= d; row++)
            order[p++] = matrix[row][r];
        if(--r < l) break;
        
        for(int col = r; col >= l; col--)
            order[p++] = matrix[d][col];
        if(--d < u) break;
        
        for(int row = d; row >= u; row--)
            order[p++] = matrix[row][l];
        if(l++ > r) break;
    }
    
    return order;
}
1288. Remove Covered Intervals

Given a list of intervals, remove all intervals that are covered by another interval in the list.

Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

After doing so, return the number of remaining intervals.

Constraints:

  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 0 <= intervals[i][0] < intervals[i][1] <= 10^5
  • All the intervals are unique.

Example 1:

1
2
3
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

1
2
Input: intervals = [[1,4],[2,3]]
Output: 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
27
28
29
30
31
32
33
34
// 所谓区间问题, 就是线段问题, 让你合并所有线段、找出线段的交集等等.
// 主要有两个技巧:
// 1. 排序, 常见的排序方法就是按照区间起点或者终点排序. 一般都是先按照起点升序排序.
//    若起点相同，则按照终点降序排序
// 2. 画图, 就是说不要偷懒, 勤动手, 两个区间的相对位置到底有几种可能,
//    不同的相对位置我们的代码应该怎么去处理
int removeCoveredIntervals(vector<vector<int>>& intervals)
{
    auto cmp = [](auto& a, auto& b){ return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0]; };
    sort(intervals.begin(), intervals.end(), cmp);
    vector<vector<int>> res;
    res.reserve(intervals.size());
    res.push_back(intervals[0]);
    int left = intervals[0][0], right = intervals[0][1];
    for(int i = 1; i < intervals.size(); i++)
    {
        auto& interval = intervals[i];
        // 区间相交
        if(right >= interval[0] && right < interval[1])
        {
            right = interval[1];
            res.push_back(interval);
        }
        // 区间不相交
        else if(right <= interval[0])
        {
            left = interval[0];
            right = interval[1];
            res.push_back(interval);
        }
        // 区间被覆盖的扔掉就行了
    }
    return res.size();
}
56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Example 1:

1
2
3
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
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>> merge(vector<vector<int>>& intervals)
{
    auto cmp = [](auto& a, auto& b){ return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0]; };
    sort(intervals.begin(), intervals.end(), cmp);
    vector<vector<int>> res;
    int left = intervals[0][0], right = intervals[0][1];
    for(int i = 1; i < intervals.size(); i++)
    {
        auto& interval = intervals[i];
        // 区间相交
        // 可能会有 [3, 3] 这样的区间, 判定和 [1, 3] 相交就行了
        // 不然的话会被当做不相交被加进去
        if(right >= interval[0] && right <= interval[1])
            right = interval[1];
        // 区间不相交
        else if(right < interval[0])
        {
            res.push_back({left, right});
            left = interval[0];
            right = interval[1];
        }
        // 区间被覆盖的扔掉就行了
    }
    // 注意最后一个区间可能没被加进去
    if(res.empty() || res.back() != vector<int>({left, right}))
        res.push_back({left, right});
    return res;
}
57. Insert Interval

给你一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

Example 1:

1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

1
2
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

1
2
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
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
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
{
    vector<vector<int>> res;

    int a1 = newInterval[0], b1 = newInterval[1];
    bool found = false;
    for(int i = 0; i < intervals.size(); i++)
    {
        int a2 = intervals[i][0], b2 = intervals[i][1];
        // 相交
        if(b2 >= a1 && b1 >= a2)
        {
            a1 = min(a1, a2);
            b1 = max(b1, b2);
        }
        // 不相交
        else if(b1 < a2 && !found)
        {
            res.push_back({a1, b1});
            res.push_back({a2, b2});
            found = true;
        }
        else
        {
            res.push_back({a2, b2});
        }
    }
    if(!found) res.push_back({a1, b1});
    return res;
}
986. Interval List Intersections

给定两个由一些闭区间组成的列表，firstList和secondList，其中firstList[i] = [start_i, end_i]而secondList[j] = [start_j, end_j]。每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集 。

形式上，闭区间[a, b]（其中a <= b）表示实数x的集合，而a <= x <= b。

两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3]和[2, 4]的交集为[2, 3]。

Example 1:

img 
1
2
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Example 2:

1
2
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

Example 3:

1
2
Input: firstList = [], secondList = [[4,8],[10,12]]
Output: []

Constraints:

  • 0 <= firstList.length, secondList.length <= 1000
  • firstList.length + secondList.length >= 1
  • 0 <= start_i < end_i <= 109
  • endi < start_(i + 1)
  • 0 <= start_j < end_j <= 109
  • endj < start_(j + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList)
{
    vector<vector<int>> res;
    int i = 0, j = 0;
    while(i < firstList.size() && j < secondList.size())
    {
        int a1 = firstList[i][0], b1 = firstList[i][1];
        int a2 = secondList[j][0], b2 = secondList[j][1];
        if(b1 >= a2 && b2 >= a1)
            res.push_back({max(a1, a2), min(b1, b2)});
        if(b1 <= b2) i++;
        else j++;
    }
    return res;
}
435. Non-overlapping Intervals

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

  • 可以认为区间的终点总是大于它的起点。
  • 区间[1,2]和[2,3]的边界相互“接触”，但没有相互重叠。

Constraints:

  • 1 <= intervals.size() <= 2 * 10^4

Example 1:

1
2
3
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

1
2
3
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

1
2
3
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
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 eraseOverlapIntervals(vector<vector<int>>& intervals)
{
    sort(intervals.begin(), intervals.end());
    int res = 0;
    int a1 = intervals[0][0], b1 = intervals[0][1];
    for(int i = 1; i < intervals.size(); i++)
    {
        int a2 = intervals[i][0], b2 = intervals[i][1];
        // 如果相交就移除后面那个区间
        if(b2 > a1 && b1 > a2)
        {
            a1 = min(a1, a2);
            b1 = min(b1, b2);
            res++;
        }
        else
        {
            a1 = a2;
            b1 = b2;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 这题问的是至少删除多少个区间使得不再存在重叠区间
// 换个思路
// 按照区间终点排序
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
    auto cmp = [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; };
    sort(intervals.begin(), intervals.end(), cmp);
    int count = 0;
    int n = intervals.size();
    int pre_end = intervals[0][1];
    for(int i = 1; i < n; i++)
    {
        int start = intervals[i][0];
        // 如果后一个区间的起点比前一个的终点小就重叠了
        if(start < pre_end)
            count++;
        else
            pre_end = intervals[i][1];
    }
    return count;
}
452. Minimum Number of Arrows to Burst Balloons

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为xstart，xend， 且满足xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组points，其中points [i] = [xstart, xend]，返回引爆所有气球所必须射出的最小弓箭数。

Example 1:

1
2
3
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Example 2:

1
2
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Example 3:

1
2
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 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
// 按照区间终点排序
// 最多有多少个不重叠的区间 == n - 至少删除多少个区间使得不再存在重叠区间
// 最多有多少个不重叠的区间就是题目所问的至少需要的箭的数量
int findMinArrowShots(vector<vector<int>>& points)
{
    auto cmp = [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; };
    sort(points.begin(), points.end(), cmp);
    // count 是最多有多少个不重叠的区间
    int count = 1;
    int n = points.size();
    int pre_end = points[0][1];
    for(int i = 1; i < n; i++)
    {
        int start = points[i][0];
        // 如果后一个区间的起点比前一个的终点小就重叠了
        // 因为这题边界触碰也能引爆气球, 所以属于重叠区间
        // 因此不是 >= 号
        if(start > pre_end)
        {
            count++;
            pre_end = points[i][1];
        }
    }
    return count;
}
436. Find Right Interval

给你一个区间数组intervals，其中intervals[i] = [starti, endi]，且每个starti都不同 。

区间i的右侧区间可以记作区间j，并满足startj >= endi，且startj最小化 。

返回一个由每个区间i的右侧区间的最小起始位置组成的数组。如果某个区间i不存在对应的右侧区间，则下标i处的值设为-1。

Constraints:

  • 1 <= intervals.length <= 2 * 10^4
  • intervals[i].length == 2
  • -10^6 <= starti <= endi <= 10^6
  • The start point of each interval is unique.

Example 1:

1
2
3
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

1
2
3
4
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 排序后顺序搜索, 最差情况下时间复杂度为 O(n2)
vector<int> findRightInterval(vector<vector<int>>& intervals)
{
    int n = intervals.size();
    for(int i = 0; i < n; i++)
        intervals[i].push_back(i);
    sort(intervals.begin(), intervals.end());
    vector<int> res(n, -1);
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if(intervals[i][1] <= intervals[j][0])
            {
                res[intervals[i][2]] = intervals[j][2];
                break;
            }
        }
    }
    
    return 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
29
30
31
// 排序后二分搜索, 时间复杂度降为 O(nlogn)
vector<int> findRightInterval(vector<vector<int>>& intervals)
{
    int n = intervals.size();
    for(int i = 0; i < n; i++)
        intervals[i].push_back(i);
    sort(intervals.begin(), intervals.end());
    vector<int> res(n, -1);
    
    for(int i = 0; i < n; i++)
    {
        int index = left_bound(intervals, i, n, intervals[i]);
        if(index < n)
            res[intervals[i][2]] = intervals[index][2];
    }
    
    return res;
}

int left_bound(vector<vector<int>>& intervals, int lo, int hi, vector<int>& interval)
{
    while(lo < hi)
    {
        int mi = lo + ((hi - lo) >> 1);
        if(interval[1] <= intervals[mi][0])
            hi = mi;
        else
            lo = mi + 1;
    }
    return lo;
}
713. Subarray Product Less Than K

给定一个正整数数组nums。找出该数组内乘积小于k的连续的子数组的个数。

Example:

1
2
3
4
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

  • 0 < nums.length <= 50000.
  • 0 < nums[i] < 1000.
  • 0 <= k < 10^6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numSubarrayProductLessThanK(vector<int>& nums, int k)
{
    if(k <= 1) return 0;
    int left = 0, right = 0;
    int product = 1, count = 0;
    while(right < nums.size())
    {
        product *= nums[right++];
        while(product >= k)
            product /= nums[left++];
        count += right - left;
    }
    return count;
}
525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

解题方法说明图：

The following figure illustrates the observation for the sequence [0 0 1 0 0 0 1 1]。

Contiguous_Array

Example 1:

1
2
3
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

1
2
3
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 设置一个计数器 counter, 遇 0 减 1, 遇 1 加 1
// 出现相等的 counter 时则说明从第 1 次出现时的索引开始到当前索引的子数组满足条件
// 并且是最长的
int findMaxLength(vector<int>& nums) {
    int n = nums.size();
    unordered_map<int, int> mapping;
    mapping[0] = -1;
    int res = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
        cnt += nums[i] == 1 ? 1 : -1;
        if(mapping.count(cnt)) {
            res = max(res, i - mapping[cnt]);
        }
        else {
            mapping[cnt] = i;
        }
    }
    return res;
}
18. 四数之和

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a，b，c和d，使得a + b + c + d的值与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
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
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    return nTargetSum(nums, target, 4);
}

vector<vector<int>> nTargetSum(vector<int>& nums, int target, int n) {
    sort(nums.begin(), nums.end());
    int len = nums.size();
    vector<vector<int>> nSumResult;
    vector<int> curVals;
    auto twoSum = [&](int start, int target) {
        int lo = start, hi = len - 1;
        while(lo < hi) {
            int sum = nums[lo] + nums[hi];
            int loVal = nums[lo], hiVal = nums[hi];
            if(sum < target) {
                // 跳过重复数字，避免出现重复结果
                while(lo < hi && nums[lo] == loVal) {
                    lo++;
                }
            }
            else if(target < sum) {
                // 跳过重复数字，避免出现重复结果
                while(lo < hi && nums[hi] == hiVal) {
                    hi--;
                }
            }
            else {
                nSumResult.push_back({loVal, hiVal});
                for(int val : curVals) {
                    nSumResult.back().push_back(val);
                }
                // 跳过重复数字，避免出现重复结果
                while(lo < hi && nums[lo] == loVal) {
                    lo++;
                }
                while(lo < hi && nums[hi] == hiVal) {
                    hi--;
                }
            }
        }
    };
    auto nSum = [&](auto&& nSum, int start, int target, int n) {
        if(n <= 2) {
            // 递归基
            twoSum(start, target);
            return;
        }
        for(int i = start; i < len; i++) {
            curVals.push_back(nums[i]);
            nSum(nSum, i + 1, target - nums[i], n - 1);
            curVals.pop_back();
            // 跳过重复数字，避免出现重复结果
            while(i < len - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    };
    nSum(nSum, 0, target, n);
    return nSumResult;
}
面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回-1。

请设计时间复杂度为O(n)、空间复杂度为O(1)的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 快速选择，使中间元素就位
int majorityElement(vector<int>& nums) {
    int n = nums.size();
    nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        if(nums[i] == nums[n / 2]) {
            cnt++;
        }
    }
    if(cnt > n/2) {
        return nums[n / 2];
    }
    return -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
27
28
// 摩尔投票
int majorityElement(vector<int>& nums) {
    int n = nums.size();
    int cnt = 0;
    int lastNum = 0;
    for(int num : nums) {
        if(cnt == 0) {
            lastNum = num;
            cnt = 1;
        }
        else if(num == lastNum) {
            cnt++;
        }
        else {
            cnt--;
        }
    }
    cnt = 0;
    for(int num : nums) {
        if(num == lastNum) {
            cnt++;
        }
    }
    if(cnt > n/2) {
        return lastNum;
    }
    return -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
27
// 位运算
int majorityElement(vector<int>& nums) {
    int n = nums.size();
    int res = 0, cnt = 0;
    for(int i = 0; i < 32; i++) {
        int mask = (1 << i);
        cnt = 0;
        for(int num : nums) {
            if(num & mask) {
                cnt++;
            }
        }
        if(cnt > n/2) {
            res |= mask;
        }
    }
    cnt = 0;
    for(int num : nums) {
        if(num == res) {
            cnt++;
        }
    }
    if(cnt > n/2) {
        return res;
    }
    return -1;
}
253. Meeting Rooms II

给你一个会议时间安排的数组intervals，每个会议时间都会包括开始和结束的时间intervals[i] = [start_i, end_i]，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1：

1
2
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：

1
2
输入：intervals = [[7,10],[2,4]]
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<pair<int, int>> times;
    for(auto&& interval : intervals) {
        times.emplace_back(interval[0], 1);
        times.emplace_back(interval[1], -1);
    }
    sort(times.begin(), times.end());
    // cnt 记录当前正在进行的会议数
    // res 记录最多的同时进行的会议数
    int cnt = 0, res = 0;
    for(auto&& [_, flag] : times) {
        cnt += flag;
        res = max(res, cnt);
    }
    return res;
}
1094. Car Pooling

假设你是一位顺风车司机，车上最初有capacity个空座位可以用来载客。由于道路的限制，车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表trips[][]，其中trips[i] = [num_passengers, start_location, end_location]包含了第i组乘客的行程信息：

  • 必须接送的乘客数量；

  • 乘客的上车地点；

  • 以及乘客的下车地点。

  • 这些给出的地点位置是从你的初始出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

    请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回false）。

Example 1:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

1
2
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

1
2
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Constraints:

  1. trips.length <= 1000
  2. trips[i].length == 3
  3. 1 <= trips[i][0] <= 100
  4. 0 <= trips[i][1] < trips[i][2] <= 1000
  5. 1 <= capacity <= 100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 将这 1000 个距离点看作一个数组, 数组中元素是那一距离点的乘客数
// 把路程中每一个位置的乘客数在数组中构造出来
// 时时比较乘客数是否超过客容量
bool carPooling(vector<vector<int>>& trips, int capacity) {
    // 距离最远就 1000 个距离单位
    vector<int> passengers(1001);
    for(auto&& trip : trips) {
        for(int i = trip[1]; i < trip[2]; i++) {
            passengers[i] += trip[0];
            if(passengers[i] > capacity) {
                return false;
            }
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 差分数组
// 将这 1000 个距离点看作一个数组, 数组中元素是那一距离点的乘客数, 初始数组元素都为 0
// 对每一个 trip 更新数组区间的值, 使用差分数组记录这些更新
// 最后还原数组的时候, 判断是否出现超载
bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> diff(1001);
    for(auto&& trip : trips) {
        diff[trip[1]] += trip[0];
        diff[trip[2]] -= trip[0];
    }
    for(int i = 1; i < 1000; i++) {
        diff[i] += diff[i - 1];
        if(diff[i] > capacity) {
            return false;
        }
    }
    return true;
}
1840. Maximum Building Height

在一座城市里，你需要建n栋新的建筑。这些新的建筑会从1到n编号排成一列。

这座城市对这些新建筑有一些规定：

  • 每栋建筑的高度必须是一个非负整数。

  • 第一栋建筑的高度必须是0。

  • 任意两栋相邻建筑的高度差不能超过1。

  • 除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组restrictions的形式给出，其中restrictions[i] = [idi, maxHeighti]，表示建筑idi的高度 不能超过maxHeighti。

    题目保证每栋建筑在restrictions中至多出现一次 ，同时建筑1不会 出现在restrictions中。

    请你返回最高建筑能达到的最高高度 。

示例 1：

img 
1
2
3
4
输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。

示例 2：

img 
1
2
3
4
输入：n = 6, restrictions = []
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,4,5] ，最高建筑的高度为 5 。

示例 3：

img 
1
2
3
4
输入：n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
输出：5
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,3,3,4,4,5,4,3] ，最高建筑的高度为 5 。

Constraints:

  • 2 <= n <= 10^9
  • 0 <= restrictions.length <= min(n - 1, 10^5)
  • 2 <= idi <= n
  • idi is unique.
  • 0 <= maxHeighti <= 10^9
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 maxBuilding(int n, vector<vector<int>>& r) {
    // 增加限制 (1, 0)
    r.push_back({1, 0});
    sort(r.begin(), r.end());
    // 增加限制 (n, n-1)
    if(r.back()[0] != n) {
        r.push_back({n, n - 1});
    }
    int m = r.size();
    // 从左向右传递限制
    for(int i = 1; i < m; i++) {
        r[i][1] = min(r[i][1], r[i - 1][1] + (r[i][0] - r[i - 1][0]));
    }
    // 从右向左传递限制
    for(int i = m - 2; i >= 0; i--) {
        r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]));
    }
    int res = 0;
    for(int i = 0; i < m - 1; ++i) {
        // 计算 r[i][0] 和 r[i + 1][0] 之间的建筑的最大高度
        int best = ((r[i + 1][0] - r[i][0]) + r[i][1] + r[i + 1][1]) / 2;
        res = max(res, best);
    }
    return res;
}
1838. Frequency of the Most Frequent Element

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

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

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

Example 1:

1
2
3
4
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

1
2
3
4
5
6
Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

1
2
Input: nums = [3,9,6], k = 2
Output: 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 降序排序后顺序模拟操作即可
// 时间复杂度为 O(n2), 超时！
int maxFrequency(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end(), greater<int>());
    int n = nums.size();
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        int temp_k = k;
        int j = i + 1;
        for(; j < n; j++) {
            if(nums[i] - nums[j] <= temp_k) {
                temp_k -= nums[i] - nums[j];
            }
            else {
                break;
            }
        }
        cnt = max(cnt, j - i);
    }
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 降序排序后, 滑动窗口模拟操作
// 时间复杂度为 O(n)
int maxFrequency(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    long res = 0, sum = 0;
    long left = 0, right = 0;
    while(right < nums.size()) {
        sum += nums[right];
        right++;
        while((right - left) * nums[right - 1] > sum + k) {
            sum -= nums[left];
            left++;
        }
        res = max(res, right - left);
    }
    return res;
}
1011. Capacity To Ship Packages Within D Days

传送带上的包裹必须在days天内从一个港口运送到另一个港口。

传送带上的第i个包裹的重量为weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在days天内将传送带上的所有包裹送达的船的最低运载能力。

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

1
2
3
4
5
6
Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

1
2
3
4
5
6
7
Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 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
27
28
29
30
31
32
// 船的最低运载能力至少为所有包裹的最大重量
// 最高运载能力充其量不过是一次把所有货物全部运完, 也就是所有货物重量之和
// 知道了最小值和最大值, 现在要我们求中间满足条件的一个最小值
// 如果说从最小值到最大值一个一个去试的话时间复杂度显然是线性的
// 其实这是二分搜索的一个典型应用场景
// 具体使用的是二分法的左边界搜索 (因为要求最低运载量嘛)
int shipWithinDays(vector<int>& weights, int days) {
    auto computeDays = [&](int limit) {
        int days = 1;
        int load = 0;
        for(int weight : weights) {
            if(load + weight > limit) {
                days++;
                load = 0;
            }
            load += weight;
        }
        return days;
    };
    int minLoad = *max_element(weights.begin(), weights.end());
    int maxLoad = accumulate(weights.begin(), weights.end(), 0);
    while(minLoad < maxLoad) {
        int midLoad = minLoad + ((maxLoad - minLoad) >> 1);
        if(days >= computeDays(midLoad)) {
            maxLoad = midLoad;
        }
        else {
            minLoad = midLoad + 1;
        }
    }
    return minLoad;
}
875. Koko Eating Bananas

珂珂喜欢吃香蕉。这里有N堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在hours小时后回来。

珂珂可以决定她吃香蕉的速度K（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉K根。如果这堆香蕉少于K根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在hours小时内吃掉所有香蕉的最小速度K（K为整数）。

Example 1:

1
2
>Input: piles = [3,6,7,11], h = 8
>Output: 4

Example 2:

1
2
>Input: piles = [30,11,23,4,20], h = 5
>Output: 30

Example 3:

1
2
>Input: piles = [30,11,23,4,20], h = 6
>Output: 23
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
// 和上题一样, 吃香蕉的速度至少为 1 吧
// 最大速度充其量不过是一次把最大的一堆全部吃完, 也就是最大堆的香蕉个数
// 知道了最小值和最大值, 现在要我们求中间满足条件的一个最小值
// 如果说从最小值到最大值一个一个去试的话时间复杂度显然是线性的
// 其实这是二分搜索的一个典型应用场景
// 具体使用的是二分法的左边界搜索 (因为要求最小速度嘛)
int minEatingSpeed(vector<int>& piles, int hours) {
    auto computeHours = [&](int speed) {
        int hours = 0;
        for(int pile : piles) {
            // pile / speed 向上取整
            hours += (pile + speed - 1) / speed;
        }
        return hours;
    };
    int minSpeed = 1;
    int maxSpeed = *max_element(piles.begin(), piles.end()) + 1;
    while(minSpeed < maxSpeed) {
        int midSpeed = minSpeed + ((maxSpeed - minSpeed) >> 1);
        if(hours >= computeHours(midSpeed)) {
            maxSpeed = midSpeed;
        }
        else {
            minSpeed = midSpeed + 1;
        }
    }
    return minSpeed;
}
1760. Minimum Limit of Balls in a Bag

给你一个整数数组nums，其中nums[i]表示第i个袋子里球的数目。同时给你一个整数maxOperations。你可以进行如下操作至多maxOperations次：

选择任意一个袋子，并将袋子里的球分到2个新的袋子中，每个袋子里都有正整数个球。
比方说，一个袋子里有5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。

你的开销是单个袋子里球数目的最大值 ，你想要最小化开销。请你返回进行上述操作后的最小开销。

Example 1:

1
2
3
4
5
6
Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

1
2
3
4
5
6
7
8
Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

Example 3:

1
2
Input: nums = [7,17], maxOperations = 2
Output: 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int minimumSize(vector<int>& nums, int maxOperations) {
    int minCost = 1;
    int maxCost = *max_element(nums.begin(), nums.end()) + 1;
    while(minCost < maxCost) {
        int midCost = minCost + (maxCost - minCost >> 1);
        int need = operations(nums, midCost);
        if(need <= maxOperations) {
            maxCost = midCost;
        }
        else {
            minCost = midCost + 1;
        }
    }
    return minCost;
}

int operations(vector<int>& nums, int cost) {
    int op = 0;
    for(int num : nums) {
        op += (num - 1) / cost;
    }
    return op;
}
153. Find Minimum in Rotated Sorted Array

已知一个长度为n的数组，预先按照升序排列，经由1到n次旋转后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
若旋转4次，则可以得到[4,5,6,7,0,1,2]
若旋转7次，则可以得到[0,1,2,4,5,6,7]
注意，数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

给你一个元素值互不相同的数组nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。

Example 1:

1
2
3
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

1
2
3
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

1
2
3
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

  • 1 <= nums.length <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and nums.length times.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findMin(vector<int>& nums) {
    int n = nums.size();
    int lo = 0, hi = n - 1;
    while(lo < hi) {
        int mi = lo + (hi - lo >> 1);
        if(nums[mi] <= nums[hi]) {
            hi = mi;
        }
        else {
            lo = mi + 1;
        }
    }
    return nums[lo];
}
154. Find Minimum in Rotated Sorted Array II

已知一个长度为n的数组，预先按照升序排列，经由1到n次旋转后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
若旋转4次，则可以得到[4,5,6,7,0,1,2]
若旋转7次，则可以得到[0,1,2,4,5,6,7]
注意，数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

给你一个可能存在重复元素值的数组nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

Example 1:

1
2
Input: nums = [1,3,5]
Output: 1

Example 2:

1
2
Input: nums = [2,2,2,0,1]
Output: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findMin(vector<int>& nums) {
    int n = nums.size();
    int lo = 0, hi = n - 1;
    while(lo < hi) {
        int mi = lo + (hi - lo >> 1);
        if(nums[mi] < nums[hi]) {
            hi = mi;
        }
        else if(nums[mi] > nums[hi]) {
            lo = mi + 1;
        }
        else {
            hi--;
        }
    }
    return nums[lo];
}
33. Search in Rotated Sorted Array

整数数组nums按升序排列，数组中的值互不相同。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

1
2
Input: nums = [1], target = 0
Output: -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
27
// 没有重复值
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while(lo <= hi) {
        int mi = lo + (hi - lo >> 1);
        if(target == nums[mi]) {
            return mi;
        }
        if(nums[mi] >= nums[lo]) {
            if(target < nums[mi] && target >= nums[lo]) {
                hi = mi - 1;
            }
            else {
                lo = mi + 1;
            }
        }             
        else {
            if(target > nums[mi] && target <= nums[hi]) {
                lo = mi + 1;
            }
            else {
                hi = mi - 1;
            }
        }
    }
    return -1;
}
81. Search in Rotated Sorted Array II

已知存在一个按非降序排列的整数数组nums，数组中的值不必互不相同。

给你旋转后的数组nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums中存在这个目标值target，则返回true，否则返回false。

Example 1:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: 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
// 有重复值
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while(lo <= hi) {
        int mi = lo + (hi - lo >> 1);
        if(target == nums[mi]) {
            return true;
        }
        // 和 I 题相比, 就添加这一个判断语句就行了
        // 跳过 nums[lo] == nums[mi] == nums[hi] 的情况
        if(nums[lo] == nums[mi] && nums[mi] == nums[hi]) {
            lo++;
            hi--;
        }
        else if(nums[mi] >= nums[lo]) {
            if(target < nums[mi] && target >= nums[lo]) {
                hi = mi - 1;
            }
            else {
                lo = mi + 1;
            }
        }
        else {
            if(target > nums[mi] && target <= nums[hi]) {
                lo = mi + 1;
            }
            else {
                hi = mi - 1;
            }
        }
    }
    return false;
}
1004. Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1‘s in the array if you can flip at most k 0‘s.

Example 1:

1
2
3
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]

Example 2:

1
2
3
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,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
// 滑动窗口, 关注窗口中 0 的个数
int longestOnes(vector<int>& nums, int k) {
    int res = 0;
    int left = 0, right = 0;
    int zeros = 0;
    while(right < nums.size()) {
        zeros += 1 - nums[right++];
        while(zeros > k) {
            zeros += nums[left++] - 1;
        }
        res = max(res, right - left);
    }
    return res;
}

// 魔改到让人看不懂为止
int longestOnes(vector<int>& nums, int k)
{
    int l = 0, r = 0;
    while(r < nums.size())
    {
        k += nums[r++] - 1;
        if(k < 0) k += 1 - nums[l++];
    }
    return r - l;
}
391. 数飞机

给出飞机的起飞和降落时间，用interval序列表示，请计算出天上同时最多有多少架飞机？

  • 如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

样例 1:

1
2
3
4
5
6
7
8
>输入: [[1, 10], [2, 3], [5, 8], [4, 7]
>输出: 3
>解释: 
>第一架飞机在 1 时刻起飞, 10 时刻降落.
>第二架飞机在 2 时刻起飞, 3 时刻降落.
>第三架飞机在 5 时刻起飞, 8 时刻降落.
>第四架飞机在 4 时刻起飞, 7 时刻降落.
>在 5 时刻到 6 时刻之间, 天空中有三架飞机.

样例 2:

1
2
3
>输入: [[1, 2], [2, 3], [3, 4]]
>输出: 1
>解释: 降落优先于起飞.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 扫描线算法
int countOfAirplanes(vector<vector<int>> &airplanes) {
    vector<pair<int, int>> timeSeries;
    for(auto& interval : airplanes) {
        timeSeries.push_back({interval[0], 1}); // 起飞是 1
        timeSeries.push_back({interval[1], -1}); // 降落是 -1
    }
    // 排序时就决定了降落在前, 起飞在后
    // 因为如果起飞时间和降落时间相等的话, 降落的第二个值是 -1, 小于起飞的 1
    sort(timeSeries.begin(), timeSeries.end());
    int count = 0, res = 0;
    for(auto&& [_, p] : timeSeries) {
        count += p;
        res = max(res, count);
    }
    return res;
}
218. The Skyline Problem

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的天际线 。

每个建筑物的几何信息由数组buildings表示，其中三元组buildings[i] = [lefti, righti, heighti]表示：

  • lefti是第i座建筑物左边缘的x坐标。

  • righti是第i座建筑物右边缘的x坐标。

  • heighti是第i座建筑物的高度。

    天际线应该表示为由 “关键点” 组成的列表，格式[[x1,y1],[x2,y2],...]，并按x坐标进行排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y坐标始终为0，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

    注意：输出天际线中不得有连续的相同高度的水平线。例如[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不正确的答案；三条高度为5的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]

示例：

img 
1
2
3
4
5
输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
解释：
图 A 显示输入的所有建筑物的位置和高度，
图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
Video_2021-04-27_200311 Video_2021-04-27_195717 
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
// 使用扫描线算法求解的关键点就在于找出 [高度发生突变] 的位置
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int, int>> geometrixPoints;
    // 将每一个建筑分成两个部分, 每部分都代表这栋建筑的几何点
    // 例如: [2, 9, 10] 可以转换成 [2, -10] [9, 10]
    // 我们用高度是否为负值来标志 左/右 边界点
    for(auto&& building : buildings) {
        geometrixPoints.emplace_back(building[0], 0 - building[2]);
        geometrixPoints.emplace_back(building[1], building[2]);
    }
    // 根据 x 值对这些关键点进行排序
    // 由于 pair 比较的特性, 排序完之后将保证扫描线从左往右走
    // 先出现的建筑先被扫描到, 后出现的建筑后被扫描到
    sort(geometrixPoints.begin(), geometrixPoints.end());
    multiset<int> heights;
    // 将 0 提前放入高度集中可以处理扫描线没有扫到任何建筑导致高度突变到 0 时的情况
    heights.insert(0);
    int maxHeight = 0;
    vector<vector<int>> keyPoints;
    for(auto&& [x_pos, height] : geometrixPoints) {
        if(height < 0) {
            // 是左边界点, 将高度入堆
            heights.insert(abs(height));
        }
        else {
            // 是右边界点, 将高度出堆
            heights.erase(heights.find(height));
        }
        // 当前最大高度
        int curMaxHeight = *heights.rbegin();
        // 看新加入/删除的建筑高度是否影响了建筑的最大高度
        // 当前最大高度不等于原先的最大高度就表示这是一个高度突变点
        if(curMaxHeight != maxHeight) {
            // 添加坐标
            keyPoints.emplace_back(vector{{x_pos, curMaxHeight}});
            // 更新最大高度
            maxHeight = curMaxHeight;
        }
    }
    return keyPoints;
}

/*
vector<pair<int, int>> 对 pair 排序默认的方式是，先比较 first，哪个小则排在前
first 相等则 second 小的排在前。而 first 这里表示横坐标，second 为负时，
表示建筑的左侧在这一位置；second 为正时，表示建筑的右侧在这一位置。

所以对 geometrixPoints 遍历时，首先会取出横坐标小的点。如果 2 个点横坐标相等，
会先取出 second 小的点，对于负数来说，其实就是高度更高的建筑。也就是说，
两个点上有高度不同的建筑，会先取高的出来放入高度集合，集合中高度最大值和之前高度不同，
就直接以更高的高度作为关键点的高度。后面更低高度的建筑加入并不会改变最大高度，
因此不会错误的当作关键点。

如果 second 为正，表示建筑物在此处结束，需要把相应高度从高度集合中删除。
有相同建筑同时在此结束，则会先让较低的建筑离开，因为它们不会改变最大高度。
只有当最高的建筑物离开时，才进行改变。如果一个位置既有建筑物进来，又有建筑物离开，
会先以进来的建筑的高度来更新高度集，原因同理。

这一系列正确的遍历顺序都取决于把高度的负值作为左边界点地标志, 高度的正值作为
右边界点的标志, 并将它们组合成一个 pair 这一巧妙的设计！！！
*/
4. Median of Two Sorted Arrays

给定两个大小分别为m和n的有序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为O(log(m+n))的算法解决此问题吗？

Example 1:

1
2
3
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

1
2
3
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

1
2
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

1
2
Input: nums1 = [], nums2 = [1]
Output: 1.00000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 方法一, 双指针归并两个有序数组
// 时间和空间复杂度都为 O(m + n)
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<int> merged(m + n);
    int i = 0, j = 0, k = 0;
    while(i < m || j < n) {
        if(j >= n || (i < m && nums1[i] < nums2[j])) {
            merged[k++] = nums1[i++];
        }
        else {
            merged[k++] = nums2[j++];
        }
    }
    return double(merged[(m + n) / 2] + merged[(m + n - 1) / 2]) / 2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 方法二, [伪归并] 双指针寻找中位数的位置
// 时间复杂度为 O(m + n), 空间复杂度为 O(1)
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int i = 0, j = 0;
    int preValue = 0, curValue = 0;
    while((i < m || j < n) && (i + j) <= (m + n) / 2) {
        preValue = curValue;
        if(j >= n || (i < m && nums1[i] < nums2[j])) {
            curValue = nums2[i++];
        }
        else {
            curValue = nums2[j++];
        }
    }
    return (m + n) & 1 ? curValue : double(preValue + curValue) / 2;
}
1
// 方法三, 划分数组 + 二分查找, 时间复杂度为 O(log(min(m, n))), 空间复杂度为 O(1)
457. Circular Array Loop

存在一个不含0的环形数组nums，每个nums[i]都表示位于下标i的角色应该向前或向后移动的下标个数：

  • 如果nums[i]是正数，向前移动nums[i]步

  • 如果nums[i]是负数，向后移动nums[i]步

  • 因为数组是环形的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。

    数组中的循环由长度为k的下标序列seq：

  • 遵循上述移动规则将导致重复下标序列seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...所有nums[seq[j]]应当不是全正就是全负

  • k > 1

    如果nums中存在循环，返回true；否则，返回false。

Example 1:

1
2
3
4
5
Input: nums = [2,-1,1,2,2]
Output: true
Explanation:
There is a cycle from index 0 -> 2 -> 3 -> 0 -> ...
The cycle's length is 3.

Example 2:

1
2
3
4
5
Input: nums = [-1,2]
Output: false
Explanation:
The sequence from index 1 -> 1 -> 1 -> ... is not a cycle because the sequence's length is 1.
By definition the sequence's length must be strictly greater than 1 to be a cycle.

Example 3:

1
2
3
4
5
Input: nums = [-2,1,-1,-2,-2]
Output: false
Explanation:
The sequence from index 1 -> 2 -> 1 -> ... is not a cycle because nums[1] is positive, but nums[2] is negative.
Every nums[seq[j]] must be either all positive or all negative.
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
// 时间复杂度为 O(n), 空间复杂度为 O(1)
bool circularArrayLoop(vector<int>& nums)
{
    int n = nums.size();
    auto getnext = [&](int i) { return ((i + nums[i]) % n + n) % n; };
    for(int i = 0; i < n; i++)
    {
        if(nums[i] == 0) continue;
        int slow = i, fast = i;
        // 符号相同则乘积 > 0
        while(nums[i] * nums[getnext(fast)] > 0 && nums[i] * nums[getnext(getnext(fast))] > 0)
        {
            slow = getnext(slow);
            fast = getnext(getnext(fast));
            // 出现环
            if(slow == fast)
            {
                // 排除长度为 1 的环
                if(slow == getnext(slow)) break;
                return true;
            }
        }
        // 上面的 while 循环没有返回, 说明上面访问过的点的路径不会出现环
        // 把访问过的点置 0, 下次不会再次进入同样的无效路径
        slow = i;
        while(nums[i] * nums[slow] > 0)
        {
            int temp = getnext(slow);
            nums[slow] = 0;
            slow = temp;
        }
    }
    return false;
}
41. First Missing Positive

给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为O(n) 并且只使用常数级别额外空间的解决方案。

参考题解：缺失的第一个正数 - 缺失的第一个正数

Example 1:

1
2
Input: nums = [1,2,0]
Output: 3

Example 2:

1
2
Input: nums = [3,4,-1,1]
Output: 2

Example 3:

1
2
Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

  • 1 <= nums.length <= 300
  • -2^31 <= nums[i] <= 2^31 - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 实际上, 对于一个长度为 n 的数组
// 其中没有出现的最小正整数只能在 [1, n+1] 中
// 这是因为如果 [1, n] 都出现了, 那么答案是 n+1
// 否则答案是 [1, n] 中没有出现的最小正整数
// 哈希表, 时间和空间复杂度都为 O(n)
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    unordered_set<int> setting;
    for(int num : nums) {
        setting.insert(num);
    }
    for(int i = 1; i <= n; i++) {
        if(!setting.count(i)) {
            return i;
        }
    }
    return n + 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
27
28
29
30
// 对于本题来说 O(n) 的空间复杂度是不符合要求的
// 由于我们已经得出了一个关键的结论:
// 没有出现的正整数只能在 [1, n+1] 中
// 这和数组的索引就存在着对应关系了
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    // 由于我们只关注 [1, n+1] 内的正整数
    // 因此, 将数组中 <= 0 的数都映射为 n+1 (足够大的正数)
    for(int i = 0; i < n; i++) {
        if(nums[i] <= 0) {
            nums[i] = n + 1;
        }
    }
    // 将数值对应的索引处的数值映射为负数
    for(int i = 0; i < n; i++) {
        int num = abs(nums[i]);
        if(num <= n && nums[num - 1] > 0) {
            nums[num - 1] *= -1;
        }
    }
    // 没有被映射为负数的第一个数的下标 +1
    // 就是缺失的第一个正整数
    for(int i = 0; i < n; i++) {
        if(nums[i] > 0) {
            return i + 1;
        }
    }
    // 否则
    return n + 1;
}
1482. Minimum Number of Days to Make m Bouquets

给你一个整数数组bloomDay，以及两个整数m和k。现需要制作m束花。制作花束时，需要使用花园中相邻的k朵花 。花园中有n朵花，第i朵花会在bloomDay[i]时盛开，恰好可以用于一束花中。请你返回从花园中摘m束花需要等待的最少的天数。如果不能摘到m束花则返回-1。

Example 1:

1
2
3
4
5
6
7
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

1
2
3
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

1
2
3
4
5
6
7
8
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:

1
2
3
Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

1
2
Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

Constraints:

  • bloomDay.length == n
  • 1 <= n <= 10^5
  • 1 <= bloomDay[i] <= 10^9
  • 1 <= m <= 10^6
  • 1 <= k <= n
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
int minDays(vector<int>& bloomDay, int m, int k)
{
    if(m > bloomDay.size() / k) return -1;
    auto [minVal, maxVal] = minmax_element(bloomDay.begin(), bloomDay.end());
    int lo = *minVal, hi = *maxVal;
    while(lo <= hi)
    {
        int mi = lo + (hi - lo) / 2;
        if(canMake(bloomDay, m, k, mi))
            hi = mi - 1;
        else
            lo = mi + 1;
    }
    return lo;
}

bool canMake(vector<int>& bloomDay, int m, int k, int days)
{
    int flowers = 0;
    for(int i = 0; i < bloomDay.size() && m > 0; i++)
    {
        if(bloomDay[i] > days)
        {
            flowers = 0;
        }
        else
        {
            flowers++;
            if(flowers == k)
            {
                m--;
                flowers = 0;
            }
        }
    }
    return m == 0;
}
1109. Corporate Flight Bookings

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

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

请你返回一个长度为n的数组answer，其中answer[i]是航班i上预订的座位总数。

Example 1:

1
2
3
4
5
6
7
8
9
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2:

1
2
3
4
5
6
7
8
Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

Constraints:

  • 1 <= n <= 2 * 10^4
  • 1 <= bookings.length <= 2 * 10^4
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 10^4
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
// 差分数组类
class Difference {
private:
    vector<int> diff;
    
public:
    Difference(const vector<int>& nums) {
        int n = nums.size();
        diff.resize(n);
        for(int i = 0; i < n; i++) {
            if(i == 0) {
                diff[i] = nums[i];
            }
            else {
                diff[i] = nums[i] - nums[i - 1];
            }
        }
    }
    // 将闭区间 [i, j] 元素加上 val
    void add(int i, int j, int val) {
        diff[i] += val;
        if(j + 1 < diff.size()) {
            diff[j + 1] -= val;
        }
    }
    // 返回结果
    vector<int> result() {
        vector<int> res(diff.size());
        res[0] = diff[0];
        for(int i = 1; i < diff.size(); i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
};

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    // 本题相当于原数组元素均为 0
    // 因此其差分数组的元素也都为 0
    vector<int> diff(n);
    Difference difference(diff);
    for(auto& booking : bookings) {
        int i = booking[0] - 1;
        int j = booking[1] - 1;
        int val = booking[2];
        // 将数组 [i..j] 区间内元素加上 val
        difference.add(i, j, val);
    }
    return difference.result();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 差分数组
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    // 本题相当于原数组元素均为 0
    // 因此其差分数组的元素也都为 0
    vector<int> difference(n);
    for(auto&& booking : bookings) {
        int i = booking[0] - 1;
        int j = booking[1] - 1;
        int val = booking[2];
        // 将数组 [i..j] 区间内元素加上 val
        difference[i] += val;
        if(j + 1 < n) {
            difference[j + 1] -= val;
        }
    }
    // 根据差分数组构造原数组
    for(int i = 1; i < n; i++) {
        difference[i] += difference[i - 1];
    }
    return difference;
}
1.64 995. Minimum Number of K Consecutive Bit Flips

在仅包含0和1的数组A中，一次K位翻转包括选择一个长度为K的（连续）子数组，同时将子数组中的每个0更改为1，而每个1更改为0。

返回所需的k位翻转的最小次数，以便数组没有值为0的元素。如果不可能，返回-1。

xample 1:

1
2
3
Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

1
2
3
Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

1
2
3
4
5
6
Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

  1. 1 <= A.length <= 30000
  2. 1 <= K <= A.length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 直接模拟反转过程
// 时间复杂度为 O(nk), 空间复杂度为 O(1)
// 超时 TLE!
int minKBitFlips(vector<int>& A, int K)
{
    int n = A.size();
    int i = 0, cnt = 0;
    while(1)
    {
        // 找到下一个 0 所在的位置
        while(i < n && A[i] != 0) i++;
        // 如果没有 0 了, 就全部翻转成功
        if(i == n) break;
        // 如果需要翻转的不够 K 位, 就不可能翻转成功
        if(i + K > n) return -1;
        // 实际地进行翻转
        for(int j = 0; j < K; j++)
            A[i + j] = 1 - A[i + j];
        // 翻转次数加一
        cnt++;
    }
    return cnt;
}
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
// 差分数组
// 自然而然, 我们会想到使用一个数组来记录每一位的翻转次数
// 但是我们又不希望是通过 [遍历数组的 K 位进行 +1 操作] 来完成记录
// 所以可以借助差分数组来记录每个区间元素被翻转的次数
// 当翻转的次数为奇数次时, 才真的要翻转, 为偶数次时并不需要实际地翻转
// 时间复杂度为 O(n), 空间复杂度为 O(n)
int minKBitFlips(vector<int>& A, int K)
{
    int n = A.size();
    int cnt = 0, sum = 0;
    // 多一个位置防止越位
    vector<int> diff(n + 1);
    for(int i = 0; i < n; i++)
    {
        // 实时计算数组索引 i 处的翻转次数
        // 这时计算的是从索引 i 开始的 K 位被翻转之前的该位已经被翻转的次数
        if(i > 0) diff[i] += diff[i - 1];
        // 判断索引 i 处开始的 K 位是否需要被翻转
        if((A[i] + diff[i]) % 2 == 0)
        {
            if(i + K > n) return -1;
            diff[i] += 1;
            diff[i + K] -= 1;
            cnt++;
        }
        // 这里的逻辑需要好好理一理, 这里相当于一边更新 diff 数组, 一边还原数组的值
    }
    return cnt;
}
307. Range Sum Query - Mutable

给你一个数组nums，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

实现NumArray类：

  • NumArray(int[] nums)：用整数数组nums初始化对象
  • void update(int index, int val)：将nums[index]的值更新为val
  • int sumRange(int left, int right)：返回子数组nums[left, right]的总和（即，nums[left] + nums[left + 1], ..., nums[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
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
// 树状数组又称二叉索引树 (Binary Indexed Tree)
class NumArray
{
public:
    // O(nlogn) 的复杂度建立树状数组
    NumArray(vector<int>& nums) : _nums(nums), bit(_nums.size())
    {
        for(int i = 0; i < _nums.size(); i++)
            add(i + 1, _nums[i]);
    }
    /*
	// O(n) 的复杂度建立树状数组
    NumArray(vector<int>& nums)
    {
		
    }
	*/
    void update(int index, int val)
    {
        // 原有的值为 _nums[index], 要更新为 val, 需要加上 val - _nums[index]
        add(index + 1, val - _nums[index]);
        _nums[index] = val;
    }
    
    int sumRange(int left, int right)
    {
        return getsum(right + 1) - getsum(left);
    }
    
private:
    vector<int> _nums;
    // 注意 bit 数组的索引 [语义] 是从 1 开始
    // 长度和原数组相同
    vector<int> bit;
    int lowbit(int x)
    {
        return x & (-x);
    }
    // 将第 pos 个数加上 val
    // 时间复杂度为 O(logn)
    void add(int pos, int val)
    {
        for(int i = pos; i <= bit.size(); i += lowbit(i))
            bit[i - 1] += val;
    }
    // 返回前 pos 个数的和
    // 时间复杂度为 O(logn)
    int getsum(int pos)
    {
        int res = 0;
        for(int i = pos; i > 0; i -= lowbit(i))
            res += bit[i - 1];
        return res;
    }
};
1310. XOR Queries of a Subarray

有一个正整数数组arr，现给你一个对应的查询数组queries，其中queries[i] = [Li, Ri]。

对于每个查询i，请你计算从Li到Ri的XOR值（即arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。并返回一个包含给定查询queries所有结果的数组。

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
vector<int> bit;
int lowbit(int x)
{
    return x & (-x);
}

void add(int pos, int val)
{
    for(; pos <= bit.size(); pos += lowbit(pos))
        bit[pos - 1] ^= val;
}

int getsum(int pos)
{
    int res;
    for(; pos > 0; pos -= lowbit(pos))
        res ^= bit[pos - 1];
    return res;
}

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries)
{
    bit.resize(arr.size());
    for(int i = 0; i < arr.size(); i++)
        add(i + 1, arr[i]);
    vector<int> res;
    for(auto& query : queries)
        res.push_back(getsum(query[1] + 1) ^ getsum(query[0]));
    return res;
}
315. Count of Smaller Numbers After Self

给定一个整数数组nums，按要求返回一个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。

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
// 树状数组类
class Bit {
private:
    int n;
    vector<int> bit;
    int lowbit(int x) {
        return x & (-x);
    }
    
public:
    Bit(int _n) : n(_n), bit(n + 1) {
        // 本题原数组相当于全 0 数组, 不需要创建 bit
        // for(int i = 0; i < nums.size(); i++)
        //     add(i + 1, nums[i]);
    }
    
    void add(int pos, int val) {
        while(pos <= n) {
            bit[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    int getsum(int pos) {
        int sum = 0;
        while(pos > 0) {
            sum += bit[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
};
// 离散化树状数组
vector<int> countSmaller(vector<int>& nums) {
    int n = nums.size();
    vector<int> temp(nums);
    sort(temp.begin(), temp.end());
    // 离散化数组的方式, 将数组中的元素按照排名映射为 1 ...
    // 这种离散方式, 离散化前后并不需要保留元素的绝对大小, 只关心元素的相对大小
    for(int i = 0; i < n; i++) {
        nums[i] = lower_bound(temp.begin(), temp.end(), nums[i]) - temp.begin() + 1;
    }
    Bit bit(n);
    vector<int> res;
    for(int i = n - 1; i >= 0; i--) {
        res.push_back(bit.getsum(nums[i] - 1));
        bit.add(nums[i], 1);
    }
    reverse(res.begin(), res.end());
    return res;
}
剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例:

1
2
输入: [7,5,6,4]
输出: 5
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
// 树状数组类
class Bit {
private:
    int n;
    vector<int> bit;
    int lowbit(int x) {
        return x & (-x);
    }
    
public:
    Bit(int _n) : n(_n), bit(n + 1) {
        // 本题原数组相当于全 0 数组, 不需要创建 bit
        // for(int i = 0; i < nums.size(); i++)
        //     add(i + 1, nums[i]);
    }
    
    void add(int pos, int val) {
        while(pos <= n) {
            bit[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    int getsum(int pos) {
        int sum = 0;
        while(pos > 0) {
            sum += bit[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
};

// 离散化树状数组 (具体思想参考官方题解)
int reversePairs(vector<int>& nums) {
    int n = nums.size();
    vector<int> temp(nums);
    sort(temp.begin(), temp.end());
    // 离散化数组的另一种方式, 通常需要保留原数组中元素大小时采用, 这里最然不需要
    // 将每个数按次序映射到数组中的对应的位置
    unordered_map<int, int> mapping;
    int i = 1;
    for(int num : temp) {
        mapping[num] = i++;
    }
    Bit bit(n);
    int res = 0;
    for(int i = n - 1; i >= 0; i--) {
        res += bit.getsum(mapping[nums[i]] - 1);
        bit.add(mapping[nums[i]], 1);
    }
    return 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
29
30
31
32
33
34
35
36
37
38
39
int reversePairs(vector<int> data) {
    int n = data.size();
    int cnt = 0;
    // 提前分配空间优化构造析构函数效率
    vector<int> helper(n/2+1);
    // 合并闭区间 [lo, mi] 和 [mi + 1, hi] 的子数组
    auto merge = [&](int lo, int mi, int hi) {
        for(int i = mi + 1; i <= hi; i++) {
            helper[i - mi - 1] = data[i];
        }
        int i = mi;
        int j = hi - mi - 1;
        int k = hi;
        while(i >= lo && j >= 0) {
            if(data[i] > helper[j]) {
                data[k--] = data[i--];
                // 就增加这一行
                cnt += j + 1;
            }
            else {
                data[k--] = helper[j--];
            }
        }
        while(j >= 0) {
            data[k--] = helper[j--];
        }
    };
    function<void(int, int)> mergeSort = [&](int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        int mi = lo + (hi - lo) / 2;
        mergeSort(lo, mi);
        mergeSort(mi + 1, hi);
        merge(lo, mi, hi);
    };
    mergeSort(0, n - 1);
    return cnt;
}
1442. Count Triplets That Can Form Two Arrays of Equal XOR

给你一个整数数组nums。

现需要从数组中取三个下标i、j和k，其中(0 <= i < j <= k < nums.size())。

a和b定义如下：

  • a = nums[i] ^ nums[i + 1] ^ ... ^ nums[j - 1]

  • b = nums[j] ^ nums[j + 1] ^ ... ^ nums[k]

    请返回能够令a == b成立的三元组(i, j , k)的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 前缀异或数组 + 三重循环枚举 i, j, k
// 时间复杂度为 O(n3), 空间复杂度为 O(n)
int countTriplets(vector<int>& nums)
{
    int n = nums.size();
    vector<int> prefix(n + 1);
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] ^ nums[i - 1];
    int res = 0;
    for(int i = 0; i < n; i++)
    	for(int j = i + 1; j < n; j++)
            for(int k = j; k < n; k++)
                if(prefix[j] ^ prefix[i] == prefix[k + 1] ^ prefix[j])
                    res++;
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 注意到如果 a == b
// 那么就有 nums[i] ^ ... ^ nums[j] ^ ... ^ nums[k] == 0
// 也就是说有 prefix[k + 1] == prefix[i]
// 此时对于 (i, k] 中的每一个 j 都是满足的
// 前缀异或数组 + 二重循环枚举 i, k
// 时间复杂度为 O(n2), 空间复杂度为 O(n)
int countTriplets(vector<int>& nums)
{
    int n = nums.size();
    vector<int> prefix(n + 1);
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] ^ nums[i - 1];
    int res = 0;
    for(int i = 0; i < n; i++)
        for(int k = i + 1; k < n; k++)
            if(prefix[i] == prefix[k + 1])
                res += k - i;
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 哈希表 + 一重循环
int countTriplets(vector<int> &nums)
{
    int n = nums.size();
    vector<int> prefix(n + 1);
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] ^ nums[i - 1];
    
    unordered_map<int, int> cnt, total;
    int res = 0;
    for(int k = 0; k < n; ++k)
    {
        if(cnt.count(prefix[k + 1]))
            res += cnt[prefix[k + 1]] * k - total[prefix[k + 1]];
        
        cnt[prefix[k]]++;
        total[prefix[k]] += k;
    }
    
    return res;
}
421. Maximum XOR of Two Numbers in an Array

给你一个整数数组nums，返回nums[i] ^ nums[j]的最大运算结果，其中0 ≤ i ≤ j < n。

进阶：你可以在O(n)的时间解决这个问题吗？

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
struct Trie
{
    Trie* child[2] = {nullptr, nullptr};
};

Trie* root = new Trie;

void insert(int num)
{
    Trie* cur = root;
    for(int i = 30; i >= 0; i--)
    {
        int a = (num >> i) & 1;
        if(!cur->child[a])
            cur->child[a] = new Trie;
        cur = cur->child[a];
    }
}

int check(int num)
{
    Trie* cur = root;
    int res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int a = (num >> i) & 1;
        int b = 1 - a;
        if(cur->child[b])
        {
            res |= (b << i);
            cur = cur->child[b];
        }
        else
        {
            res |= (a << i);
            cur = cur->child[a];
        }
    }
    return res;
}

int findMaximumXOR(vector<int>& nums)
{
    int res = 0;
    for(int num : nums)
    {
        insert(num);
        res = max(res, num ^ check(num));
    }
    return res;
}
1707. Maximum XOR With an Element From Array

给你一个由非负整数组成的数组nums。另有一个查询数组queries，其中queries[i] = [xi, mi]。

第i个查询的答案是xi和任何nums数组中不超过mi的元素按位异或得到的最大值。换句话说，答案是max(nums[j] XOR xi)，其中所有j均满足nums[j] <= mi。如果nums中的所有元素都大于mi，最终答案就是-1。

返回一个整数数组answer作为查询的答案，其中answer.length == queries.length且answer[i]是第i个查询的答案。

题解：与数组中元素的最大异或值 - 与数组中元素的最大异或值 - 力扣（LeetCode）

Example:

1
2
3
4
5
6
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Constraints:

  • 1 <= nums.length, queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 10^9
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
class Solution
{
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries)
    {
        for(int num : nums) insert(num);
        vector<int> res;
        res.reserve(queries.size());
        for(auto query : queries)
            res.push_back(getVal(query[0], query[1]));
        
        return res;
    }
    
private:
    struct Trie
    {
        int minVal = INT_MAX;
        Trie* child[2] = {nullptr, nullptr};
    };
    Trie* root = new Trie;
    
    void insert(int num)
    {
        root->minVal = min(root->minVal, num);
        Trie* cur = root;
        for(int i = 30; i >= 0; i--)
        {
            int bit = (num >> i) & 1;
            if(!cur->child[bit])
                cur->child[bit] = new Trie;
            cur->child[bit]->minVal = min(cur->child[bit]->minVal, num);
            cur = cur->child[bit];
        }
    }
    
    int getVal(int num, int m)
    {
        if(m < root->minVal)
            return -1;
        Trie* cur = root;
        int res = 0;
        for(int i = 30; i >= 0; i--)
        {
            int bit = (num >> i) & 1;
            if(cur->child[bit ^ 1] && cur->child[bit ^ 1]->minVal <= m)
            {
                res |= (1 << i);
                bit = bit ^ 1;
            }
            cur = cur->child[bit];
        }
        return res;
    }
};
1074. Number of Submatrices That Sum to Target

给出矩阵matrix和目标值target，返回元素总和等于目标值的非空子矩阵的数量。

如果(x1, y1, x2, y2)和(x1', y1', x2', y2')两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

题解：【宫水三叶】优化枚举的基本思路与进阶内容 - 元素和为目标值的子矩阵数量 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 前缀子矩阵和 + 暴力枚举
// 从「点」上来确定一个子矩阵, 在 n 和 m 同阶的情况下, 时间复杂度是 O(n^4)
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target)
{
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> prefixsumOfSubMatrix(m + 1, vector<int>(n + 1));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            prefixsumOfSubMatrix[i][j] = matrix[i - 1][j - 1] + prefixsumOfSubMatrix[i - 1][j] + prefixsumOfSubMatrix[i][j - 1] - prefixsumOfSubMatrix[i - 1][ j - 1];
    
    int res = 0;
    for(int rl = 1; rl <= m; rl++)
        for(int cu = 1; cu <= n; cu ++)
            for(int rr = rl; rr <= m; rr++)
                for(int cd = cu; cd <= n; cd++)
                    if(prefixsumOfSubMatrix[rr][cd] - prefixsumOfSubMatrix[rr][cu - 1] - prefixsumOfSubMatrix[rl - 1][cd] + prefixsumOfSubMatrix[rl - 1][cu - 1] == target)
                        res++;
    return 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
29
30
31
32
33
34
35
36
37
38
39
// 从「边」上来确定一个子矩阵, 通过枚举三条边
// 使用哈希表 + 前缀和来加速查找第四条边
// 在 n 和 m 同阶的情况下, 时间复杂度可降到 O(n3)
int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target)
{
    int m = matrix.size(), n = matrix[0].size();
    int res = 0;
    // 枚举上边界
    for(int i = 0; i < m; ++i)
    {
        vector<int> sum(n);
        // 枚举下边界
        for(int j = i; j < m; ++j)
        {
            // 更新每列的元素和
            for(int c = 0; c < n; ++c) sum[c] += matrix[j][c];
            // 遍历 sum 子数组的和
            res += sumsOfSubArrayEqualTarget(sum, target);
        }
    }
    return res;
}
// 计算数组中和等于 target 的子数组个数
// 前缀和 + 哈希表优化 时间复杂度为 O(n)
int sumsOfSubArrayEqualTarget(vector<int>& nums, int target)
{
    unordered_map<int, int> mapping;
    // 表示以首元素开头的子数组的和等于 target
    mapping[0] = 1;
    int res = 0, preSum = 0;
    for(int num : nums)
    {
        preSum += num;
        if(mapping.count(preSum - target))
            res += mapping[preSum - target];
        ++mapping[preSum];
    }
    return res;
}
1738. Find Kth Largest XOR Coordinate Value

给你一个二维矩阵matrix和一个整数k，矩阵大小为m x n由非负整数组成。矩阵中坐标(a, b)的值可由对所有满足0 <= i <= a < m且0 <= j <= b < n的元素matrix[i][j]（下标从0开始计数）执行异或运算得到。

请你找出matrix的所有坐标中第k大的值（k的值从1开始计数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 前缀子矩阵异或 + 小顶堆
int kthLargestValue(vector<vector<int>>& matrix, int k)
{
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> subMatrixXors(m + 1, vector<int>(n + 1));
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            subMatrixXors[i][j] = subMatrixXors[i - 1][j - 1] ^ subMatrixXors[i][j - 1] ^ subMatrixXors[i - 1][j] ^ matrix[i - 1][j - 1];
            pq.push(subMatrixXors[i][j]);
            if(pq.size() > k)
                pq.pop();
        }
    }
    return pq.top();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 前缀子矩阵异或 + 快速选择
int kthLargestValue(vector<vector<int>>& matrix, int k)
{
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> subMatrixXors(m + 1, vector<int>(n + 1));
    vector<int> temp;
    temp.reserve(m * n);
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            subMatrixXors[i][j] = subMatrixXors[i - 1][j - 1] ^ subMatrixXors[i][j - 1] ^ subMatrixXors[i - 1][j] ^ matrix[i - 1][j - 1];
            temp.push_back(subMatrixXors[i][j]);
        }
    }
    nth_element(temp.begin(), prev(temp.end(), k), temp.end());
    return temp[m * n - k];
}
581. Shortest Unsorted Continuous Subarray

给你一个整数数组nums，你需要找出一个连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。

Example 1:

1
2
3
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

1
2
Input: nums = [1,2,3,4]
Output: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 先排序 + 再比较
// 时间复杂度为 O(nlogn)
int findUnsortedSubarray(vector<int>& nums) {
    vector<int> temp(nums);
    sort(temp.begin(), temp.end());
    // 初始化为 -1 和 -2 方便处理数组已经是升序的情况
    int left = -1, right = -2;
    for(int i = 0; i < nums.size(); i++) {
        if(nums[i] != temp[i]) {
            if(left == -1) {
                left = i;
            }
            right = i;
        }
    }
    return right - left + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 双层循环暴力法
// 时间复杂度为 O(n2)
int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size();
    int res = 0, left = INT_MAX, right = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(nums[j] < nums[i]) {
                left = min(left, i);
                right = max(right, j);
            }
        }
    }
    return left == INT_MAX ? 0 : right - left + 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
// 正序和逆序分别遍历
// 时间复杂度为 O(n)
int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size();
    // 初始化为 -1 和 -2 方便处理数组已经是升序的情况
    int left = -1, right = -2;
    int maximun = INT_MIN;
    for(int i = 0; i < n; i++) {
        if(nums[i] < maximun) {
            right = i;
        }
        else {
            maximun = nums[i];
        }
    }
    int minimum = INT_MAX;
    for(int i = n - 1; i >= 0; i--) {
        if(nums[i] > minimum) {
            left = i;
        }
        else {
            minimum = nums[i];
        }
    }
    return right - left + 1;
}
48. Rotate Image

给定一个n × n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

img 
1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
1
2
3
4
5
6
7
8
9
10
// 使用额外空间就比较容易了
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> res(matrix);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            matrix[j][n - i - 1] = res[i][j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 不使用额外空间
// 用翻转实现旋转
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 上下翻转
    for(int i = 0; i < n / 2; i++) {
        for(int j = 0; j < n; j++) {
            swap(matrix[i][j], matrix[n - i - 1][j]);
        }
    }
    // 主对角线翻转
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}
5777. 使数组元素相等的减少操作次数

给你一个整数数组nums，你的目标是令nums中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：

  • 找出nums中的最大值。记这个值为largest并取其下标i（下标从0开始计数）。如果有多个元素都是最大值，则取最小的i。

  • 找出nums中的下一个最大值，这个值严格小于largest，记为nextLargest。

  • 将nums[i]减少到nextLargest。

    返回使nums中的所有元素相等的操作次数。

参考题解：使数组元素相等的减少操作次数 - 使数组元素相等的减少操作次数 - 力扣（LeetCode）

示例 1：

1
2
3
4
5
6
7
输入：nums = [5,1,3]
输出：3
解释：需要 3 次操作使 nums 中的所有元素相等：

1. largest = 5 下标为 0 。nextLargest = 3 。将 nums[0] 减少到 3 。nums = [3,1,3] 。
2. largest = 3 下标为 0 。nextLargest = 1 。将 nums[0] 减少到 1 。nums = [1,1,3] 。
3. largest = 3 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1] 。

示例 3：

1
2
3
4
5
6
7
8
输入：nums = [1,1,2,2,3]
输出：4
解释：需要 4 次操作使 nums 中的所有元素相等：

1. largest = 3 下标为 4 。nextLargest = 2 。将 nums[4] 减少到 2 。nums = [1,1,2,2,2] 。
2. largest = 2 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1,2,2] 。 
3. largest = 2 下标为 3 。nextLargest = 1 。将 nums[3] 减少到 1 。nums = [1,1,1,1,2] 。 
4. largest = 2 下标为 4 。nextLargest = 1 。将 nums[4] 减少到 1 。nums = [1,1,1,1,1] 。

提示：

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 5 * 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 升序排序做法
int reductionOperations(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int res = 0; // 总操作次数
    int cnt = 0; // 每个元素操作次数
    for(int i = 1; i < n; ++i) {
        if(nums[i] != nums[i-1]) {
            ++cnt;
        }
        res += cnt;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 降序排序做法
int reductionOperations(vector<int>& nums) {
    sort(nums.begin(), nums.end(), greater<int>());
    vector<int> count;
    int i = 0, n = nums.size();
    while(i < n) {
        int max_value = nums[i];
        int cnt = 0;
        while(i < n && nums[i] == max_value) {
            cnt++;
            i++;
        }
        count.push_back(cnt);
    }
    count.pop_back();
    partial_sum(count.begin(), count.end(), count.begin());
    return accumulate(count.begin(), count.end(), 0);
}
645. 错误的集合

集合s包含从1到n的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组nums代表了集合s发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

1
2
输入：nums = [1,2,2,4]
输出：[2,3]

提示：

  • 2 <= nums.length <= 1e4
  • 1 <= nums[i] <= 1e4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 法一：哈希表
vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    unordered_set<int> existed;
    vector<int> res(2);
    for(int num : nums) {
        if(existed.count(num)) {
            res[0] = num;
        }
        existed.insert(num);
    }
    for(int i = 1; i <= n; i++) {
        if(existed.count(i) == 0) {
            res[1] = i;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 法二：下标索引原地哈希
vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int a = 0, b = 0;
    for(int i = 0; i < n; i++) {
        int num = abs(nums[i]);
        if(nums[num - 1] < 0) {
            a = num;
        }
        else {
            nums[num - 1] *= -1;
        }
    }
    for(int i = 0; i < n; i++) {
        if(nums[i] > 0) {
            b = i + 1;
        }
    }
    return {a, b};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 法三：数学
vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int sum = (1 + n) * n / 2;
    int sum_1 = 0, sum_2 = 0;
    vector<bool> sets(n + 1);
    for(int num : nums) {
        sum_1 += num;
        if(!sets[num]) {
            sum_2 += num;
        }
        sets[num] = true;
    }
    return {sum_1 - sum_2, sum - sum_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
// 法四：位运算
vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int xors = 0;
    for(int i = 0; i < n; i++) {
        xors = xors ^ (i + 1) ^ nums[i];
    }
    int lowbit = xors & (-xors);
    int a = 0, b = 0;
    for(int i = 0; i < n; i++) {
        if(nums[i] & lowbit) {
            a = a ^ nums[i];
        }
        else {
            b = b ^ nums[i];
        }
        if((i + 1) & lowbit) {
            a = a ^ (i + 1);
        }
        else {
            b = b ^ (i + 1);
        }
    }
    for(int num : nums) {
        if(a == num) {
            return {a, b};
        }
    }
    return {b, a};
}
462. 最少移动次数使数组元素相等 II

给定一个非空整数数组，找到使所有数组元素相等所需的最小操作数，其中每次操作可将选定的一个元素加1或减1。

参考题解：

C++｜中位数｜简单证明 - 最少移动次数使数组元素相等 II

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
// 要使得操作数最小, 最终的值一定是中位数
int minMoves2(vector<int>& nums) {
    int n = nums.size();
    // nth_element(nums.begin(), next(nums.begin(), n/2), nums.end());
    _nth_element(nums, n/2);
    int midVal = nums[n/2];
    int res = 0;
    for(int num : nums) {
        res += abs(num - midVal);
    }
    return res;
}
// 快速选择算法，使得 k 索引处的元素就位
void _nth_element(vector<int>& nums, int k) {
    // 对 [lo, hi] 区间内的元素进行洗牌算法
    auto shuffle = [&](int lo, int hi) {
        for(int i = lo; i <= hi; i++) {
            int j = rand() % (hi - i + 1) + i;
            swap(nums[i], nums[j]);
        }
    };
    // 以首元素为轴点，对 [lo, hi] 区间内元素进行划分
    auto partition = [&](int lo, int hi) {
        shuffle(lo, hi);
        int i = lo, j = lo;
        while(++j <= hi) {
            if(nums[j] < nums[lo]) {
                swap(nums[++i], nums[j]);
            }
        }
        swap(nums[lo], nums[i]);
        return i;
    };
    int lo = 0, hi = int(nums.size()) - 1;
    while(lo <= hi) {
        int mi = lo + ((hi - lo) >> 1);
        int p = partition(lo, hi);
        if(p == k) {
            return;
        }
        else if(p < k) {
            lo = p + 1;
        }
        else {
            hi = p - 1;
        }
    }
}
31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

参考链接：下一个排列算法详解：思路+推导+步骤，看不懂算我输

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void nextPermutation(vector<int>& nums) {
    // next_permutation(nums.begin(), nums.end());
    int n = nums.size();
    int left = n - 2;
    while(left >= 0 && nums[left] >= nums[left + 1]) {
        left--;
    }
    if(left >= 0) {
        int right = n - 1;
        while(right >= 0 && nums[right] <= nums[left]) {
            right--;
        }
        swap(nums[left], nums[right]);
    }
    reverse(next(nums.begin(), left + 1), nums.end());
}
128. 最长连续序列

给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为O(n)的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 排序 + 去重 + 计数
int longestConsecutive(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) {
        return 0;
    }
    sort(nums.begin(), nums.end());
    unique(nums.begin(), nums.end());
    int res = 0, cnt = 1;
    for(int i = 1; i < n; i++) {
        if(nums[i] == nums[i - 1] + 1) {
            cnt++;
        }
        else {
            res = max(res, cnt);
            cnt = 1;
        }
    }
    return max(res, cnt);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 哈希表
int longestConsecutive(vector<int>& nums) {
    unordered_set<int> existed;
    for(int num : nums) {
        existed.insert(num);
    }
    int res = 0;
    for(int num : existed) {
        if(existed.count(num - 1) == 0) {
            int maxVal = num;
            while(existed.count(maxVal + 1)) {
                maxVal++;
            }
            res = max(res, maxVal - num + 1);
        }
    }
    return res;
}
207. 课程表

你这个学期必须选修n门课程，记为0到n - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组p给出，其中p[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi。例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。

请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

示例：

1
2
3
输入：n = 2, p = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 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
27
28
// 拓扑排序
bool canFinish(int n, vector<vector<int>>& p) {
    vector<vector<int>> adj(n);
    vector<int> in(n);
    for(auto&& v : p) {
        adj[v[1]].push_back(v[0]);
        in[v[0]]++;
    }
    queue<int> q;
    for(int i = 0; i < n; i++) {
        if(in[i] == 0) {
            q.push(i);
        }
    }
    vector<int> res;
    while(!q.empty()) {
        int from = q.front();
        q.pop();
        res.push_back(from);
        for(auto to : adj[from]) {
            in[to]--;
            if(in[to] == 0) {
                q.push(to);
            }
        }
    }
    return res.size() == n;
}
1462. 课程表 IV

你总共需要上n门课，课程编号依次为0到n-1。有的课会有直接的先修课程，比如如果想上课程0，你必须先上课程1，那么会以[1, 0]数对的形式给出先修课程数对。

给你课程总数n和一个直接先修课程数对列表p和一个查询对列表q。

对于每个查询对q[i]，请判断q[i][0]是否是q[i][1]的先修课程。请返回一个布尔值列表，列表中每个元素依次分别对应q每个查询对的判断结果。

注意：如果课程a是课程b的先修课程且课程b是课程c的先修课程，那么课程a也是课程c的先修课程。

参考链接：图最短路径算法之弗洛伊德算法（Floyd） | Echo Blog

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& p, vector<vector<int>>& q) {
    vector<vector<bool>> adj(n, vector<bool>(n));
    for(auto&& v : p) {
        adj[v[0]][v[1]] = true;
    }
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
            }
        }
    }
    vector<bool> res;
    for(auto&& v : q) {
        res.push_back(adj[v[0]][v[1]]);
    }
    return res;
}
329. 矩阵中的最长递增路径

给定一个m x n整数矩阵matrix，找出其中最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到 边界外（即不允许环绕）。

img

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
// 1. 建图: 对于每一个点, 都有一个指向比其大的方向的路径
// 2. 从所有入度为 0 的点出发分别进行 dfs
// 3. 相当于是找到以各个出发节点为根的树的最大深度
int longestIncreasingPath(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> adj(m * n);
    vector<int> in(m * n);
    auto getId = [n](int i, int j) {
        return i * n + j;
    };
    vector<int> memo(m * n, -1);
    auto dfs = [&](auto&& dfs, int from) {
        if(adj[from].empty()) {
            return 1;
        }
        if(memo[from] != -1) {
            return memo[from];
        }
        int len = 0;
        for(auto to : adj[from]) {
            len = max(len, 1 + dfs(dfs, to));
        }
        return memo[from] = len;
    };
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i + 1 < m && matrix[i][j] < matrix[i + 1][j]) {
                adj[getId(i, j)].push_back(getId(i + 1, j));
                in[getId(i + 1, j)]++;
            }
            if(j + 1 < n && matrix[i][j] < matrix[i][j + 1]) {
                adj[getId(i, j)].push_back(getId(i, j + 1));
                in[getId(i, j + 1)]++;
            }
            if(i - 1 >= 0 && matrix[i][j] < matrix[i - 1][j]) {
                adj[getId(i, j)].push_back(getId(i - 1, j));
                in[getId(i - 1, j)]++;
            }
            if(j - 1 >= 0 && matrix[i][j] < matrix[i][j - 1]) {
                adj[getId(i, j)].push_back(getId(i, j - 1));
                in[getId(i, j - 1)]++;
            }
        }
    }
    int res = 1;
    for(int i = 0; i < m * n; i++) {
        if(in[i] == 0) {
            res = max(res, dfs(dfs, i));
        }
    }
    return res;
}
444. 序列重建

验证原始的序列org是否可以从序列集seqs中唯一地重建。序列org是1到n整数的排列，其中1 ≤ n ≤ 10^4。重建是指在序列集seqs中构建最短的公共超序列。（即使得所有seqs中的序列都是该最短序列的子序列）。确定是否只可以从seqs重建唯一的序列，且该序列就是org。

示例 1：

1
2
3
4
输入：
org: [1,2,3], seqs: [[1,2],[1,3]]
输出：false
解释：[1,2,3] 不是可以被重建的唯一的序列，因为 [1,3,2] 也是一个合法的序列。

示例 2：

1
2
3
输入：org: [1,2,3], seqs: [[1,2]]
输出：false
解释：可以重建的序列只有 [1,2]。

示例 3：

1
2
3
输入：org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
输出：true
解释：序列 [1,2], [1,3] 和 [2,3] 可以被唯一地重建为原始的序列 [1,2,3]。

示例 4：

1
2
输入：org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
输出：true
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
// 拓扑排序
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    if(seqs.empty()) {
        return false;
    }
    int n = org.size();
    vector<int> in(n + 1);
    vector<vector<int>> adj(n + 1);
    unordered_set<int> all_set;
    for(auto&& seq : seqs) {
        int m = seq.size();
        for(int i = 0; i < m; i++) {
            if(seq[i] <= 0 || seq[i] > n) {
                return false;
            }
            if(i == 0) {
                all_set.insert(seq[i]);
                continue;
            }
            int from = seq[i - 1];
            int to = seq[i];
            adj[from].push_back(to);
            in[to]++;
            all_set.insert(to);
        }
    }
    vector<int> res;
    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if(in[i] == 0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        if(q.size() > 1) {
            return false;
        }
        int from = q.front();
        q.pop();
        res.push_back(from);
        for(int to : adj[from]) {
            in[to]--;
            if(in[to] == 0) {
                q.push(to);
            }
        }
    }
    return org == res;
}