Leetcode 日记：日常练习篇

Leetcode 日记：日常练习篇

三月 01, 2022

179. 最大数

题目描述：

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    static bool cmp (int &a, int &b){
            string aa = to_string(a) + to_string(b);
            string bb = to_string(b) + to_string(a);
            return aa > bb;
    }

    string largestNumber(vector<int>& nums) {
        string ans;
        sort(nums.begin(), nums.end(), cmp);
        if(nums[0] == 0) return "0";
        for(auto &n : nums){
            ans += to_string(n);
        }
        return ans;
    }
};

769. 最多能完成排序的块

题目描述：

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int res = 0, max_value = arr[0];
        for(int i = 0; i < n; i++){
            max_value = max(arr[i], max_value);
            if(max_value == i){
                ++res;
            }
        }
        return res;
    }
};

739. 每日温度

题目描述：

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        if(n == 1)  return {0};
        stack<int> ss;
        vector<int> res(n);
        for(int i = 0; i < n; i++){
            while(!ss.empty()){
                int pre_index = ss.top();
                if(temperatures[i] <= temperatures[pre_index]){
                    break;
                }
                ss.pop();
                res[pre_index] = i - pre_index;
            }
            ss.push(i);
        }
        return res;
    }
};

218. 天际线问题

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

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

lefti 是第 i 座建筑物左边缘的 x 坐标。
righti 是第 i 座建筑物右边缘的 x 坐标。
heighti 是第 i 座建筑物的高度。
你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。

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

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

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
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> ans;
priority_queue<pair<int, int>> max_heap; 
int i = 0, len = buildings.size();
int cur_x, cur_h;
while (i < len || !max_heap.empty()) {
    //如果最高的矩阵和当前矩阵重合，处理左端点
    if (max_heap.empty() || i < len && buildings[i][0] <= max_heap.top().second) {
        cur_x = buildings[i][0];
        //相同的左端点全部入队，选择最高高度
        while (i < len && cur_x == buildings[i][0]) {
            max_heap.emplace(buildings[i][2], buildings[i][1]);
            //遍历矩阵
            ++i;
        } 
    } else {
        //如果最高的矩阵和当前矩阵不重合，处理之前重合矩阵的右端点
        cur_x = max_heap.top().second;
        //选择其右侧重合的矩阵（不包括本矩阵）最高高度
        while (!max_heap.empty() && cur_x >= max_heap.top().second) {
            max_heap.pop();
        } 
    }
    cur_h = (max_heap.empty()) ? 0 : max_heap.top().first;
    if (ans.empty() || cur_h != ans.back()[1]) {
        ans.push_back({cur_x, cur_h});
    } 
}
return ans;
    }
};

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )

1
2
3
4
5
6
7
8
9
10
11
12
class NumArray {
    vector<int> psum;
public:
    NumArray(vector<int>& nums): psum(nums.size() + 1, 0) {
        partial_sum(nums.begin(), nums.end(), psum.begin() + 1);

    }
    
    int sumRange(int left, int right) {
        return psum[right+1] - psum[left];
    }
};

210. 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[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
29
30
31
32
33
34
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> indegree(numCourses, 0), res;
        for(const auto & prerequisite: prerequisites){
            graph[prerequisite[1]].push_back(prerequisite[0]);
            ++indegree[prerequisite[0]];
        }
        queue<int> q;
        for(int i = 0; i < indegree.size(); ++i){
            if(!indegree[i]){
                q.push(i);
            }
        }
        while(!q.empty()){
            int u = q.front();
            res.push_back(u);
            q.pop();
            for(auto v: graph[u]){
                --indegree[v];
                if(!indegree[v]){
                    q.push(v);
                }
            }

        }
        for (int i = 0; i < indegree.size(); ++i){
            if(indegree[i])
                return {};
        }
        return res;
    }
};

30. 串联所有单词的子串

思路：指定移动步长+指定开始位置

经典滑动窗口模版题，一一把题目中的要求实现即可，目前做过的滑窗题都可以套模版

  • 最重要的条件「长度相同」，暗示滑动窗口移动的步长 stride 为 words[0].size()
  • 窗口的长度应为 words.size() * stride
  • 当前窗口的长度计算公式为 right - left + stride

需要设定滑动窗口的起始位置，起始位置可选范围为 [0, stride-1]

时间复杂度：O(30 n 30) 遍历起始位置最大 30 次，滑动窗口遍历整个 s 为 n 次，滑窗内 substr 的截取和判断为最大 30 次

空间复杂度：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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = s.size();
        int stride = words[0].size();
        int limit = words.size() * stride;

        unordered_map<string, int> need;
        for (auto w : words) {
            need[w]++;
        }
        vector<int> ans;
        for (int start = 0; start <= stride - 1; start++) {
            // left 和 right 指向的是当前步子的第一个下标
            int left = start;
            int right = start;
            int cnt = 0;  // 记录窗口内满足要求的单词数量
            unordered_map<string, int> window;
            while (right < n) {
                // 右边届入窗
                string cur_right = s.substr(right, stride);
                if (need.count(cur_right)) {
                    window[cur_right]++;
                    if (window[cur_right] == need[cur_right]) {
                        cnt++;
                    }
                }
                // 左边届收缩
                if (right - left + stride > limit) {
                    string cur_left = s.substr(left, stride);
                    if (need.count(cur_left)) {
                        if (window[cur_left] == need[cur_left]) {
                            cnt--;
                        }
                        window[cur_left]--;
                    }
                    left += stride;
                }
                // 采集答案
                if (right - left + stride == limit && cnt == need.size()) {
                    ans.push_back(left);
                }
                right += stride;
            }
        }

        return ans;
    }
};

窗口的数据结构：应根据各种数据结构的特点来选取

哈希表，unordered_map
优先队列，priority_queue
红黑树，multiset、set、multimap、map
单调队列，deque实现

应用条件：

原数据必须满足单调性，不满足的可以用前缀和。例如560. 和为 K 的子数组原数据中含有负数，破坏了单调性

思考（也是考点）：

  1. 窗口使用什么数据结构
  2. 达到窗口限定后，左边届该怎样收缩，如果无法以常规方法收缩，考虑延时删除策略（在采集答案前进行）
  3. 怎样采集答案
  4. 滑窗的步长
  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
void slidingWindow(string s, string t) {
    int left = 0;
    int right = 0;
    int valid = 0; // 窗口内已凑齐的字符种类数量
    unordered_map<char, int> window;
    unordered_map<char, int> need; // 需要凑齐的字符和对应数量
    for (char c : t) need[c]++;

    while (right < s.size()) {
        // 右边届入窗口，进行窗口内数据的一系列更新
        window[s[right]]++;
        if (window[s[right]] == need[s[right]]) {
            valid++;
        }  // 注意：先加，再判断

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // 左边界移出窗口，进行窗口内数据的一系列更新
            if (window[s[left]] == need[s[left]]) {
                valid--;
            }  // 注意：先判断，再减
            window[s[left]]--;
            left++;  // 注意：左边届的收缩，要写在所有处理完成的最后
        }
        // 采集答案...
        right++;  // 注意：右边届的扩展，要写在所有处理完成的最后
    }
}