leetcode 面试经典150题

发表于 更新于 分类于

leetcode 面试经典150题


[TOC]

数组 / 字符串

88. 合并两个有序数组【easy】

image-20240923211250769

分析：

  时间复杂度O(m+n)，空间复杂度O(1)解法。关键是空间复杂度，需要注意的是，nums1长度是n+m，后面n是空着的，由此考虑从后往前填，即填成一个从后往前看非递增排序的整数数组。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        while(m + n)
        {
            if(m && n) nums1[m + n] = nums1[m - 1] >= nums2[n - 1] ? nums1[--m] : nums2[--n];
            else if(n) nums1[m + n] = nums2[--n];
            else break;
        }

    }
};

189. 轮转数组【mid】【原地】【翻转】【数论】

image-20240923211927868

分析：

  关键在于如何原地解决。（其他两种方法，1.辅助数组空间复杂度O(n)，2.使用reverse.reverse(0,n),reverse(0, k),reverse(k,n)）

  思考过程有点类似环形的一些操作，可以考虑展开。即把数组接到后面去，变成一个长度为mn的数组，那么从0这个点右跳k的这个操作一定会回到0这个点，只不过是后面接上去的某个数组的0。由此配合取模分类的一些奇怪的操作很容易想到，他从0开始跳就只能跳某一类点。

  在此基础上，可以借鉴官方题解。假设回到0时跳了a圈，且在此过程中遍历了b个元素。那么an=bk,a和b是我们比较关心的。而an一定是n，k的公倍数，又因为我们第一次回到起点时就结束了，故a尽可能的小，所以an=lcm（n，k），则b=lcm(n，k)/k。

  由此可以计算出单次遍历可以访问b= n/gcd(n,k)个元素，一共需要遍历n/b趟。

AC代码：

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:
    
    
    void rotate(vector<int>& nums, int k) {
    
        int tmp, pos;
        int n = nums.size();
        int cnt = __gcd(n, k);
        int b = n / __gcd(n, k);

        for(int i = 0; i < cnt; ++i)
        {
            pos = i;
            tmp = nums[pos];
            for(int j = 1; j <= b; ++j)
            {
                pos = (pos + k) % n;
                swap(nums[pos], tmp);
            }
        }
        
    }
};

122. 买卖股票的最佳时机 II【mid】【简单dp】

image-20241015185433909

分析：

  比较简单的一个n*2的线性dp，但是自己sb了，想了半天妹想起来。dp数组第二维表示选还是不选的那种。主要是看到任何时候最多只能持有一张股票。

  dp[i][0]表示第i天结束后，手上没有股票的情况下，前i天的最大利润。

  dp[i][1]表示有的情况下。

  转移方程：

1
2
3
dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

134. 加油站【mid】【遍历】

image-20241015221609279

分析：

  方法1：

image-20241015221526484

  方法2：（来自官方题解）

  从第一个可能的起点x开始遍历，若其最远能到达点y，而无法到达y+1，那么x~y之间的点都无法到达y+1，故可以直接从y+1开始遍历，总体复杂度O(n)。

AC代码:

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 Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        vector<bool> flag(n + 5, false);
        vector<int> pos(n + 5, 0);
        vector<int> vt(n + 5, 0);

        for(int i = 0; i < n; ++i) flag[i] = (gas[i] >= cost[i]);

        //for(int i = 0; i < n; ++i) cout << i << ' ' << flag[i] << '\n';
        
        for(int i = n - 1; i >= 0; --i)
        {
            if(!flag[i]) continue;
            int sum = gas[i] - cost[i];
            int p = i;
            //cout << i << ' ' << sum << ' ' << p << '\n';
            while(true)
            {
                p = (p + 1) % n;
                if(p == i) return i;
                if(flag[p] && p > i) 
                { 
                    sum += vt[p];
                    p = pos[p];
                }

                if(sum + gas[p] >= cost[p]) sum += (gas[p] - cost[p]);
                else 
                {
                    pos[i] = p;
                    vt[i] = sum;
                    break;
                }
                //cout << p << ' ' << sum << '\n';
            }
        }

        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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        int x = 0;
        while(x < n)
        {
            int y = x, sum = 0, cnt = 0;
            while(cnt < n)
            {
                y = (x + cnt) % n;
                sum += gas[y] - cost[y];
                if(sum >= 0) ++cnt;
                else break; 
            }

            if(cnt == n) return x;
            else x += cnt + 1;
        }

        return -1;
    }
};

135. 分发糖果【hard】【思维】

image-20241017220256329

分析：

  解法1：

  首先，对于极小值点，其糖果是固定的1，注意这里的极小值点和数学上的不同。对于i，只要满足如下两个条件即可。

  • ratings[i]小于左侧第一个不等于ratings[i]的值x或左侧没有元素。
  • ratings[i]小于右侧第一个不等于ratings[i]的值x或右侧没有元素。

  对于其他的点j，取值受其左侧最近的极小值点和右侧最近的极小值点影响，即ans1[j]和ans2[j]，而最终的ans[j] = max(ans1[j], ans2[j])。

  由此发现，比较麻烦的是那种相邻相等的元素。为此，可以先进行预处理，把一个三元组(值，左界，有界)放到一个vector中。

  解法2：(来自官方题解)

  关键的一条规则在于「相邻的孩子中，评分高的孩子必须获得更多的糖果」，而将这条规则拆成两个规则，分别计算满足两个规则下，每个孩子最少获得多少糖果，之后取max即可。具体如下：

  • 左规则：当 ratings[i−1]<ratings[i] 时，i号学生的糖果数量将比 i−1 号孩子的糖果数量多1,否则i的糖果数量为1。
  • 左规则：当 ratings[i+1]<ratings[i] 时，i号学生的糖果数量将比 i−1 号孩子的糖果数量多1,否则i的糖果数量为1。

  解法3：(来自官方题解，非常巧妙)

  首先，记录前一个同学的糖果数量pre。之后根据当前同学与前一个同学的ratings大小关系判断当前同学是在递增序列还是在递减序列，我们认为任何一个同学不会同时存在于递增序列和递减序列中。

  • 若ratings[i] > ratings[i-1]，则在递增序列内，当前同学获得pre+1个糖果，当前递增序列长度++inc。
  • 若ratings[i] == ratings[i - 1]，认为i在一个新的递增序列内，获得1个糖果，递增序列长度为1。
  • 若ratings[i] < ratings[i - 1]，认为i在一个递减序列内，当前同学获得1个糖果，并为当前递减序列之前的同学每人再分配1个糖果。同时，递减序列长度++dec。此时我们可以发现，这一步对答案的贡献正好为递减序列长度dec（这一过程结合官方题解中的柱状图很好理解，或者就想明白递减序列中的同学的糖果是通过多次分配获得的）。另外，需要额外注意的是，当递减序列长度dec等于上一个递增序列长度inc的时候，需要将上一个递增序列的最后一个同学视为递减序列的第一个同学。为此，dec需要额外++。

AC代码:

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        
        int n = ratings.size();
        vector<int> ans1(n + 5, 0), ans2(n + 5, 0);
        vector<pair<int, pair<int, int>>> tmp;
        vector<int> vt;

        int l = 0, r = 0;
        for(int i = 1; i < n; ++i)
        {
            if(ratings[i] == ratings[i - 1]) ++r;
            else 
            {
                tmp.push_back({ratings[i - 1], {l, r}});
                l = r = i;
            }
        }
        tmp.push_back({ratings[n - 1], {l, r}});
        
        if(tmp.size() == 1) return n;

        for(int i = 0; i < tmp.size(); ++i)
        {
            if(i == 0) 
            {
                if(tmp[i].first < tmp[i + 1].first)
                    for(int j = tmp[i].second.first; j <= tmp[i].second.second; ++j) 
                        vt.push_back(j), ans1[j] = ans2[j] = 1;
            }
            else if(i == tmp.size() - 1)
            {
                if(tmp[i].first < tmp[i - 1].first)
                    for(int j = tmp[i].second.first; j <= tmp[i].second.second; ++j) 
                        vt.push_back(j), ans1[j] = ans2[j] = 1;
            }
            else 
            {
                if(tmp[i].first < tmp[i - 1].first && tmp[i].first < tmp[i + 1].first)
                    for(int j = tmp[i].second.first; j <= tmp[i].second.second; ++j) 
                        vt.push_back(j), ans1[j] = ans2[j] = 1;
            }
        }

        for(auto x : vt)
        {
            //cout << x << ' ';
            //左侧更新
            for(int i = x + 1; i < n; ++i)
            {
                if(ratings[i] < ratings[i - 1]) break;
                else if(ratings[i] == ratings[i - 1]) ans1[i] = 1;
                else ans1[i] = ans1[i - 1] + 1;
            }
            //右侧更新
            for(int i = x - 1; i >= 0; --i)
            {
                if(ratings[i] < ratings[i + 1]) break;
                else if(ratings[i] == ratings[i + 1]) ans2[i] = 1;
                else ans2[i] = ans2[i + 1] + 1;
            }
        }

        //putchar('\n');

        int ans = 0;
        for(int i = 0; i < n; ++i) 
        {
            //cout << i << ' ' << ans1[i] << ' ' << ans2[i] << '\n';
            ans1[i] = max(ans1[i], ans2[i]);
            ans += ans1[i];
        }

        return ans;
    }
};
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 candy(vector<int>& ratings) {
        
        int n = ratings.size();
        vector<int> left(n + 5);
        
        for(int i = 0; i < n; ++i) 
        {
            if(i > 0 && ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
            else left[i] = 1;
        }

        int right = 1, ans = 0;
        for(int i = n - 1; i >= 0; --i)
        {
            if(i < n - 1 && ratings[i] > ratings[i + 1]) ++right;
            else right = 1;
            ans += max(left[i], right);
        }

        return ans;
    }
};
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 candy(vector<int>& ratings) {
        
        int n = ratings.size();
        int ans = 1;
        
        int inc = 1, dec = 0, pre = 1;
        for(int i = 1; i < n; ++i)
        {
            if(ratings[i] >= ratings[i - 1]) 
            {
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ans += pre;
                inc = pre;
                dec = 0;
            }
            else 
            {
                ++dec;
                if(dec == inc) ++dec;
                ans += dec;
                pre = 1;
            }
        }

        return ans;
    }
};

151. 反转字符串中的单词【easy】【快慢指针】

分析：

  经典的要求原地算法，还是反转，大概率使用reverse。

  除此之外，比较难处理的是奇怪的空格，注意理解代码中idx、start、en的含义即可。

AC代码：

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
class Solution {
public:
    string reverseWords(string s) {
        
        reverse(s.begin(), s.end());
        int n = s.size();

        int idx = 0, en;
        for(int start = 0; start < n; ++start)
        {
            if(s[start] != ' ')
            {
                if(idx != 0) s[idx++] = ' ';

                en = start;
                while(en < n && s[en] != ' ') s[idx++] = s[en++];

                reverse(s.begin() + idx - (en - start), s.begin() + idx);

                start = en;
            }
        }

        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

68.文本左右对齐【hard】【模拟】【size_t】

分析：

  读懂题意后会发现实际上就是一个模拟。但是，这个过程中遇到了一个坑。

  vt.size()的返回值类型是size_t(各种容器都是)，size_t是无符号整数，具体多少位，取决于机器架构（32位或者是64位）。int和size_t进行大小比较的时候，会自动将int转换为size_t，而size_t是无符号数，所以当int是负数的时候，比较就会出错。

AC代码：

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
84
85
86
87
88
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        
        vector<vector<string>> tmp(305, vector<string>());         
        vector<int> sLen(305, 0);
        vector<string> ans;
        
        string s;
        int n = words.size();
        int cnt = 0;
        int sum = 0;
        int len = maxWidth;
        
        for(int i = 0; i < n; ++i) 
        {
            if(len >= (int)words[i].size()) 
            {
                tmp[cnt].push_back(words[i]);
                sum += words[i].size();
            }
            else
            {
                len = maxWidth;
                tmp[++cnt].push_back(words[i]);
                sum = words[i].size();
            }
            len -= words[i].size();
            --len;
            sLen[cnt] = sum;
        }

        int wordscnt, wordslen, spaceCnt, spaceLen, less, mod, lessCnt, L;
        for(int i = 0; i < 305; ++i)
        {
            const auto& vt = tmp[i];
            
            if(vt.size() == 1) 
            {
                s = vt.front();
                spaceLen = maxWidth - s.size();
                while(spaceLen--) s += " ";
                ans.push_back(s);
                if(tmp[i + 1].size() == 0) break;
            }
            else
            {
                s = "";
                spaceLen = maxWidth - sLen[i];
                spaceCnt = vt.size() - 1;
                wordslen = sLen[i];
                wordscnt = vt.size();
                less = spaceLen / spaceCnt;
                mod = spaceLen % spaceCnt;
                lessCnt = spaceCnt - mod;
                if(tmp[i + 1].size() == 0)
                {
                    for(int j = 0; j < vt.size(); ++j)
                    {
                        s += vt[j];
                        if(j != vt.size() - 1) s += " ";
                    }
                    L = s.size();
                    for(int j = 0; j < maxWidth - L; ++j) s += " ";
                    ans.push_back(s);
                    break;
                }
                else
                {
                    for(int j = 0; j < vt.size(); ++j)
                    {
                        s += vt[j];
                        if(j == vt.size() - 1) break;
                        if(mod)
                        {
                            for(int k = 0; k <= less; ++k) s += " ";
                            --mod;
                        }
                        else for(int k = 0; k < less; ++k) s += " ";
                    }
                    ans.push_back(s);
                }
            }

        }
        return ans;
    }
};