LeetCode 题解记录(2)

习题 / OJ / LeetCode
字数统计: 5.1k   |   阅读时长≈ 22 分钟

分享一些自己LeetCode题目的题解。

*标记的题目为待优化题目。

#565 [Medium] 数组嵌套 Array Nesting

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到并返回最大的集合S，S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]… 以此类推，不断添加直到S出现重复的元素。

又用暴力解了一次。。虽然很难受但是确实也有用。。

看起来像是一个图论题找最大环，但相比普通图来说这个图有更多的性质——所有节点的出入度都为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
class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int ans = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i] == -1) continue;
            int deep = 0, index = i;
            vector<int> vec; //去掉
            bool is_find = false;
            while(true){
                for(int j=0;j<vec.size();j++){ //去掉
                    if(nums[index] == vec[j] || nums[index] == -1) { //去掉第一个条件
                        is_find = true;
                        break;
                    }
                }
                if(is_find) break;
                vec.push_back(nums[index]); //去掉
                int pre_index = index;
                index = nums[index];
                nums[pre_index] = -1;
                deep++;
            }
            if(deep > ans) ans = deep;
        }
        return ans;
    }
};

执行用时 :1244 ms, 在所有 C++ 提交中击败了5.35%的用户

内存消耗 :10.7 MB, 在所有 C++ 提交中击败了78.26%的用户

然后发现这个时间也太TM奇怪了吧。。看了一下自己算法逻辑有点问题，对一些代码做了点优化（如注释）：

执行用时 :28 ms, 在所有 C++ 提交中击败了63.64%的用户

内存消耗 :9.8 MB, 在所有 C++ 提交中击败了88.41%的用户

这下舒服了。。

#984 [Medium] 不含AAA或BBB的字符串 String Without AAA or BBB

给定两个整数 A 和 B，返回任意字符串 S，要求满足：

S 的长度为 A + B，且正好包含 A 个 ‘a’ 字母与 B 个 ‘b’ 字母；
子串 ‘aaa’ 没有出现在 S 中；
子串 ‘bbb’ 没有出现在 S 中。

直接构造即可。不妨设 $A>B$ ，那么只需要特殊考虑 A/B>2 的情况即可，剩下的字符串用 A%B 来构造。

更直观的构造使用计数器，哪个剩余字符多写哪个字符，用一个标记来阻止程序连写三个符号。

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
class Solution {
public:
    string strWithout3a3b(int A, int B) {
        int m_A, m_B;
        string ans;
        string m_a_char, m_b_char;
        if(A > B) { m_A = A; m_B = B; m_a_char = "a"; m_b_char = "b";}
        else { m_A = B; m_B = A; m_a_char = "b"; m_b_char = "a";}
        string tri = m_a_char+m_a_char+m_b_char, duo = m_a_char+m_b_char;
        if(m_A / m_B < 2){
            int res = m_A%m_B;
            while(res > 0){
                ans += tri;
                res--;
            }
            while(ans.length() < A+B){
                ans += duo;
            }
        }
        else{
            while(ans.length() +2 < A+B)
                ans += tri;
            while(ans.length() < A+B)
                ans += m_a_char;
        }
        return ans;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了30.65%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了81.08%的用户

#42 [Hard] 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

栈主题训练。先用暴力试一下：对每一层迭代，单独计算每一层中能容纳的雨水量，这样暴力会超时而且和栈似乎没什么关系。。复杂度是 $O(mn)$ ，$m$ 为柱子的最高高度。

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
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0) return 0;
        int ans = 0;
        bool isBreak = false;
        while(!isBreak){
            stack<int> stk;
            isBreak = true;
            for(int i=1;i<height.size();i++){
                if(height[i-1] > 0 && height[i] == 0) stk.push(0);
                if(stk.size() > 0 && height[i] == 0) { stk.top()++; }
                if(height[i-1] == 0 && height[i] > 0 && stk.size() > 0) 
                { ans += stk.top(); stk.pop(); }
                if(height[i-1] > 0) height[i-1]--;
                if(height[i-1] > 0) isBreak = false;
            }
            if(height[height.size()-1] > 0)
                height[height.size()-1]--; 
            if(height[height.size()-1] > 0)
                isBreak = false;

        }
        return ans;
    }
};

新的暴力法，对每个柱子，检索两侧的最高柱子，可以得到这个柱子上的承水量。复杂度 $O(n^2)$ 感觉和上面的差不太多，应该也会被卡时间。

如果先遍历一遍数组，就可以找到每个元素上向左(向右)的最高柱子，不需要对每根柱子都检索一遍，这样复杂度应该可以到 $O(n)$ 了。

使用栈的算法，找到比栈顶低的元素入栈，找到比栈顶高的元素则栈顶弹出，使用当前元素、原栈顶高度和新栈顶高度进行水量计算。复杂度同样是 $O(n)$ 。

双指针法和上面两种思路差不多，同样是单次遍历。由于短板效应，只有在leftMAX < rightMAX 的时候才是左指针向右遍历，否则反之。遍历的时候更新响应的MAX值，并用MAX值减去当前高度作为水量加到答案上。复杂度 $O(n)$ 。

Tips：在存在一个数组height的情况下，关于index的数据结构能同时保存index和响应值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0) return 0;
        stack<int> stk;
        stk.push(0);
        int ans = 0;
        for(int i=1;i<height.size();i++){
            if(height[i] <= height[stk.top()]) {
                stk.push(i); //推入index
            }
            else{
                    while(height[i] > height[stk.top()]){
                        int height_now = height[stk.top()];
                        stk.pop();
                        if(stk.empty()) break;
                        ans += (min(height[i], height[stk.top()])-height_now) * (i-stk.top()-1);
                }
                stk.push(i);
            }
        }
        return ans;
    }
};

执行用时 :16 ms, 在所有 C++ 提交中击败了23.61%的用户

内存消耗 :9.1 MB, 在所有 C++ 提交中击败了78.77%的用户

#84 [Hard] 柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

真正的Hard应该是做不出来的。。

核心问题可以看做求每个柱子的最大等高线宽度。应该是卡了 $O(n^2)$ 的暴力，需要用一些方法优化。我这里维护了一个数组left_w和一个栈stk，stk是一个单调增的柱子序列的index（index也单增），一旦检索到比top元素小的元素，则循环出栈直到新元素能入栈，并处理出栈元素对答案的更新（由于新元素小于出栈元素，出栈元素的右向宽度计数在此终止）。由于是右向检索，还需要left_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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size() == 0) return 0;
        vector<int> left_w(heights.size());
        int ans = 0;
        stack<int> stk;
        stk.push(0);
        for(int i=1;i<heights.size();i++){
            if(heights[i] >= heights[stk.top()]) stk.push(i); //大于栈顶元素则入栈
            while(!stk.empty() && heights[i] <  heights[stk.top()]){//栈空或当前元素大于栈顶元素停止循环
                ans = max(ans, (i-stk.top()+left_w[stk.top()])*heights[stk.top()]);//更新ANS
                left_w[i] = i-stk.top()+left_w[stk.top()];//更新LEFT_W
                stk.pop();
            }
            stk.push(i); //入栈(好像重复了但是还是AC了。。)
        }
        while(!stk.empty()){//遍历完之后若栈非空的处理
            int i = heights.size();
            ans = max(ans, (i-stk.top()+left_w[stk.top()])*heights[stk.top()]);
            stk.pop();
        }
        return ans;
    }
};

执行用时 :36 ms, 在所有 C++ 提交中击败了14.06%的用户

内存消耗 :10.8 MB, 在所有 C++ 提交中击败了7.44%的用户

(明明是 $O(n)$ 的算法，却有着堪比 $O(n^2)$ 的实现。。)

其他方法：

  • 分治：(最坏 $O(n^2)$ 平均 $O(n\log n)$ ，可用线段树优化)

    • 确定了最矮柱子以后，矩形的宽尽可能往两边延伸。
    • 在最矮柱子左边的最大面积矩形（子问题）。
    • 在最矮柱子右边的最大面积矩形（子问题）。

#215* [Medium] 数组中的第K个最大元素 Kth Largest Element in an Array

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

我这里是使用了堆排，排序好久没写了手生。。实际上不需要排序，只需要维护k大小的小顶堆即可，时间复杂度还能优化一下。

同样用快排的话，不需要对pivot两边递归排序。因为每次都知道pivot是第几大的元素，所以可以直接选择一边而放弃另一边。

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(nums.size());
        for(int i=0;i<nums.size();i++){
            heap[i] = nums[i];
            //cout<<"Push: "<<nums[i]<<endl;
            //shiftUp(heap, i);
        }
        sort(heap, k);
        for(int i=0;i<heap.size();i++) cout<<heap[i]<<" ";
        return heap[heap.size()-k];
    }
    
    void shiftUp(vector<int>& heap, int start, int end){
        int parent = start;
        int son = parent*2 + 1;
        while(son <= end){
            if(son + 1 <= end && heap[son] < heap[son+1]) son++;
            if(heap[parent] > heap[son]) return;
            else{
                swap(heap[parent], heap[son]);
                parent = son;
                son = parent*2 + 1;
            }
        }
    }
    
    void sort(vector<int>& heap, int k){
        int len = heap.size();
        for(int i=len/2-1;i>=0;i--)
            shiftUp(heap, i, len-1);
        for(int i=len-1;i>=len-k;i--){
            swap(heap[0],heap[i]);
            shiftUp(heap, 0, i-1);
        }
    }
    
    
    void swap(int &a, int &b){
        int mid = a;
        a = b;
        b = mid;
    }
};

执行用时 :40 ms, 在所有 C++ 提交中击败了35.47%的用户

内存消耗 :9.3 MB, 在所有 C++ 提交中击败了67.49%的用户

#55 [Medium] 跳跃游戏 Jump Game

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

贪心训练。感觉贪心的难点在于判断贪心。。所以在已知贪心的情况下并不是很难。。

从当前步一直往下一个位置迭代，循环更新能够到达的最远位置，直到当前位置达到数组长度/最远位置为止。对最远位置进行判断即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int dis = 1;
        for(int i=0;i<dis && i<nums.size();i++){
            dis = max(dis, i+nums[i]+1);
        }
        if(dis < nums.size()) return false;
        else return true;
    }
};

执行用时 :24 ms, 在所有 C++ 提交中击败了24.26%的用户

内存消耗 :9.9 MB, 在所有 C++ 提交中击败了72.19%的用户

#122 [Easy] 买卖股票的最佳时机II Best Time to Buy and Sell Stock II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

贪心一时爽，一直贪心一直爽。。

把递增的部分的差全部加起来就好了。未来股价都给你了，烂钱还不会恰么。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int profit = 0;
        for(int i=0;i<prices.size()-1;i++){
            profit += max(prices[i+1] - prices[i], 0);
        }
        return profit;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了53.04%的用户

内存消耗 :9.6 MB, 在所有 C++ 提交中击败了7.50%的用户

#45 [Hard] 跳跃游戏II Jump Game II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

一样的，难点在于分析贪心性质。容易知道，对于当前步能走到的位置来说，下一步走最大的位置总是没错的（没有其他选择能比其覆盖了更多的选择）。

写到这里突然想到贪心和DP的一些小区别，一些具有贪心性质的问题，本质在于一些最优的下一步状态，本身还包含着最多的状态选择。这样从全局观点来看，这种局部最优的状态转移也是永远正确的（我的状态比你好，可选状态也比你多）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(vector<int>& nums) {
        int dis = 1, new_dis = 1, min_step = 0;
        if(nums.size() == 0) return 0;
    
        for(int i=0;i<nums.size();i++){
            if(i>=dis){
                min_step++;
                dis = new_dis;
            }
            new_dis = max(new_dis, i+nums[i]+1);
        }
        return min_step;
    }
};

执行用时 :20 ms, 在所有 C++ 提交中击败了32.55%的用户

内存消耗 :10 MB, 在所有 C++ 提交中击败了88.36%的用户

#56 [Medium] 合并区间

给出一个区间的集合，请合并所有重叠的区间。

排序就完事了。区间头尾分两个数组排序，坏处是占空间多。如果排序后的头/尾数组上有关系：$start[i+1]>end[i]$ ，则 $end[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
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        if(intervals.size() == 0) return ans;
        vector<int> start(intervals.size());
        vector<int> end(intervals.size());
        for(int i=0;i<intervals.size();i++){
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        quickSort(start, 0, start.size()-1);
        quickSort(end, 0, end.size()-1);
        int l = start[0], r = end[0];
        for(int i=0;i<start.size()-1;i++){
            if(end[i] < start[i+1]) {
                r = end[i];
                vector<int> vec{l, r};
                ans.push_back(vec);
                l = start[i+1];
            }
        }
        vector<int> vec{l, end[end.size()-1]};
        ans.push_back(vec);
        return ans;
    }
    
    void quickSort(vector<int> &a, int left, int right){
        if(left < right){
            int leftmark = left, rightmark = right, pivot = a[right];
            while(leftmark < rightmark){
                while(a[leftmark] <= pivot && leftmark < rightmark) leftmark++;
                if(leftmark < rightmark) a[rightmark--] = a[leftmark];
                while(a[rightmark] > pivot && leftmark < rightmark) rightmark--;
                if(leftmark < rightmark) a[leftmark++] = a[rightmark];
            }
            a[rightmark] = pivot;
            quickSort(a, left, rightmark-1);
            quickSort(a, rightmark+1, right);
        }
    }
};

执行用时 :32 ms, 在所有 C++ 提交中击败了63.52%的用户

内存消耗 :12.8 MB, 在所有 C++ 提交中击败了5.08%的用户

#136 [Easy] 只出现一次的数字 Single Number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

位运算入门题，我想都没想直接写了个逐个异或，然后竟然AC了。。

查了一下是因为一个简单而重要的性质，一个数和另一个数异或两次之后等于它自己。另外，异或运算满足分配律和交换律。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i=0;i<nums.size();i++){
            ans = ans^nums[i];
        }
        return ans;
    }
};

执行用时 :20 ms, 在所有 C++ 提交中击败了59.35%的用户

内存消耗 :9.6 MB, 在所有 C++ 提交中击败了67.52%的用户

#461 [Easy] 汉明距离 Hamming Distance

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

异或后用移位来计数。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingDistance(int x, int y) {
        int num = x^y;
        int ans = 0;
        while(num != 0){
            if(num % 2 != 0) ans++;
            num>>=1;
        }
        return ans;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了74.90%的用户

内存消耗 :8.2 MB, 在所有 C++ 提交中击败了81.46%的用户

#169 [Easy] 求众数 Majority Element

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

解法很多，直接排序、Hash map都可以。这题的标签有位运算，但是还没想到怎么解，其本质应该是对每一位都取多数。

还有一种BM算法的改版，用计数器计算当前众数的数量，遇到非当前众数则减1，减至零则换众数。由于众数占超过半数，所以真正的众数永远不会被换掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // BM Algo
        int ans = nums[0];
        int score = 1;
        for(int i=1;i<nums.size();i++){
            if(nums[i] != ans) score--;
            if(nums[i] == ans) score++;
            if(score == 0) {
                score = 1;
                ans = nums[i];
            }
        }
        return ans;
    }
};

执行用时 :44 ms, 在所有 C++ 提交中击败了19.24%的用户

内存消耗 :11 MB, 在所有 C++ 提交中击败了85.94%的用户

#62 [Medium] 不同路径 Unique Paths

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

备忘录DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int uniquePaths(int m, int n) {
        int **num = new int*[m];
        for(int i=0;i<m;i++) {
            num[i] = new int[n];
            num[i][0] = 1;
        }
        for(int i=0;i<n;i++) num[0][i] = 1; 
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                num[i][j] = num[i-1][j] + num[i][j-1];
            }
        }
        return num[m-1][n-1];
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了75.63%的用户

内存消耗 :8.5 MB, 在所有 C++ 提交中击败了40.06%的用户

#63 [Medium] 不同路径 II Unique Paths II

加入了障碍物的版本，这里就不细谈了。坑的是数据是卡int类型的，而答案完全没有提到这一点。

#64 [Medium] 最小路径和 Minimum Path Sum

最优子问题性质是显然的。不多说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        for(int i=1;i<grid.size();i++){
            grid[i][0] += grid[i-1][0];
        }
        for(int i=1;i<grid[0].size();i++){
            grid[0][i] += grid[0][i-1];
        }
        for(int i=1;i<grid.size();i++){
            for(int j=1;j<grid[0].size();j++){
                 grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了96.38%的用户

内存消耗 :10.3 MB, 在所有 C++ 提交中击败了99.31%的用户

#120 [Medium] 三角形最小路径和 Triangle

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

和#64差不多，最优子问题性质容易证明。附加题是只使用 $O(n)$ 的额外空间，由于最优子问题所需的记事本确实只需要 $O(n)$ 的空间(由上一行递推)，所以这也是比较显然的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        // O(n) extra space algorithm?
        if(triangle.size()==0) return 0;
        for(int i=1;i<triangle.size();i++){
            for(int j=0;j<triangle[i].size();j++){
                if(j==0) triangle[i][j] += triangle[i-1][j];
                else if(j==i) triangle[i][j] += triangle[i-1][j-1];
                else triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
            }
        }
        int ans = triangle[triangle.size()-1][0];
        for(int i=0;i<triangle[triangle.size()-1].size();i++) 
            ans = min(ans, triangle[triangle.size()-1][i]);
        return ans;
    }
};

执行用时 :12 ms, 在所有 C++ 提交中击败了48.68%的用户

内存消耗 :9.5 MB, 在所有 C++ 提交中击败了98.29%的用户

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2019-2020 thiswinex
  • 访问人数: | 浏览次数:

请我喝奶茶~

支付宝
微信