06.04 第 038 ~ 050 题（第 13 ~ 16 天）

06.04 第 038 ~ 050 题（第 13 ~ 16 天）

两数相加

分析

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        int carry = 0;
        while(l1 && l2){
            int sum = l1->val + l2->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        // 剩余部分
        while(l1){
            int sum = l1->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l1 = l1->next;
        }
        while(l2){
            int sum = l2->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l2 = l2->next;
        }        
        // 如果有进位
        if(carry){
            ListNode* node = new ListNode(carry);
            cur->next = node;
        }
        return dummy->next;
    }
};
  • 时间复杂度：O(max(m, n))
  • 空间复杂度：O(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
35
class MinStack {
public:
    stack<int> stk;
    stack<int> minStk;    
    MinStack() {
        minStk.push(INT_MAX);
    }
    
    void push(int val) {
        stk.push(val);
        minStk.push(min(minStk.top(), val));
    }
    
    void pop() {
        stk.pop();
        minStk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return minStk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

如果我们想去掉辅助栈 minStk，可以使用一个变量来记录当前的最小值，然后在插入或删除时进行动态更新。我们可以在栈中保存上一个最小值。，从而在每次插入、删除、获取最小值时都只需要操作一个栈。以下是实现思路：

  • 在 push 操作时，如果新插入的元素小于或等于当前最小值，则将当前最小值入栈，并更新最小值为新元素。
  • 在 pop 操作时，如果弹出的元素等于当前最小值，则需要将最小值恢复为栈中前一个最小值（即上次的最小值）。
  • 在 getMin 操作时直接返回当前最小值。
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 MinStack {
public:
    stack<int> stk;
    int minVal;
    
    MinStack() {
        minVal = INT_MAX;
    }
    
    void push(int val) {
        if (val <= minVal) {
            stk.push(minVal);  // 保存当前最小值
            minVal = val;       // 更新最小值
        }
        stk.push(val);           // 入栈
    }
    
    void pop() {
        if (stk.top() == minVal) {  // 如果弹出的是当前最小值
            stk.pop();              // 弹出当前最小值
            minVal = stk.top();     // 恢复上一个最小值
        }
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return minVal;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

有效的括号

分析

用栈来实现，如果是左括号就入栈，如果是右括号，检查栈顶元素是否匹配，如果不匹配，返回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
class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(char ch : s){
            if(ch == '(' || ch == '[' || ch == '{'){
                stk.push(ch);
            }
            else{
                if(!stk.empty() && check(stk.top(), ch)){
                    stk.pop();
                }
                else{
                    return false;
                }
            }
        }
        // 检查栈是否为空
        if(stk.empty()){
            return true;
        }
        return false;
    }
    bool check(char ch1, char ch2){
        if(ch1 == '(' && ch2 == ')'){
            return true;
        }
        if(ch1 == '[' && ch2 == ']'){
            return true;
        }
        if(ch1 == '{' && ch2 == '}'){
            return true;
        }
        return false;
    }

};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

[!NOTE]
今天刷的题目都比较简单，需要注意的是最小栈那道题，在评论区看到有面试的时候问空间复杂度如何优化。

基本计算器II

分析

用一个栈，保存这些（进行乘除运算后的）整数的值。对于加减号后的数字，将其直接压入栈中；对于乘除号后的数字，可以直接与栈顶元素计算，并替换栈顶元素为计算后的结果。

具体来说，遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式：

  • 加号：将数字压入栈；
  • 减号：将数字的相反数压入栈；
  • 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。

代码实现中，若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 preSign 为当前遍历的字符。

遍历完字符串 s 后，将栈中元素累加，即为该字符串表达式的值。

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
class Solution {
public:
    int calculate(string s) {
        // 定义数字栈
        vector<int> stk;
        char preSign = '+';
        int num = 0;
        int n = s.length();
        // 遍历字符串
        for(int i = 0; i < n; i++){
            // 如果是数字
            if(isdigit(s[i])){
                num = num * 10 + int(s[i] - '0');
            }
            if(!isdigit(s[i]) && s[i] != ' ' || i == n-1){
                switch(preSign){
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    default:
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

用栈实现队列

分析

使用两个栈，inStack 用于输入，outStack 用于输出。

  • push：放入inStack.
  • pop：如果 outStack 输出栈为空，将 inStack 输入栈元素依次取出，按顺序压入 outStack 栈。这样 outStack 栈的元素顺序和之前 inStack 元素顺序相反，outStack 顶层元素就是要取出的队头元素，将其移出，并返回该元素。如果 outStack 输出栈不为空，则直接取出顶层元素。
  • peek：如果 outStack 输出栈为空，将 inStack 输入栈元素依次取出，按顺序压入 outStack 栈。这样 outStack 栈的元素顺序和之前 inStack 元素顺序相反，outStack 顶层元素就是要取出的队头元素，无需移出，只返回该元素。如果 outStack 输出栈不为空，则直接返回顶层元素。
  • empty：如果 inStack 和 outStack 都为空，则队列为空，否则队列不为空。
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 MyQueue {
public:
    stack<int> inStack;
    stack<int> outStack;
    MyQueue() {

    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if(outStack.empty()){
            // 将inStack元素逐个压入out
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int num = outStack.top();
        outStack.pop();
        return num;
    }
    
    int peek() {
        int num;
        if(outStack.empty()){
            // 逐个弹出并压入
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    
    bool empty() {
        if(inStack.empty() && outStack.empty()){
            return true;
        }
        return false;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
  • 时间复杂度：O(1)
  • 空间复杂度：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
class Solution {
public:
    string decodeString(string s) {
        vector<string> cStack;
        stack<int> nStack;
        int num = 0;
        string res = "";
        // 遍历字符串
        for(char ch : s){
            // 如果是数字，就累加
            if(isdigit(ch)){
                num = num * 10 + int(ch - '0');
            }
            // 如果是左括号，将数字，当前字符串入栈，并清除这两个变量
            else if(ch == '['){
                cStack.push_back(res);
                nStack.push(num);
                res = "";
                num = 0;
            }
            // 如果是右括号，弹出字符串和数字
            else if(ch == ']'){
                string curStr = cStack.back();
                cStack.pop_back();
                int curNum = nStack.top();
                nStack.pop();
                res = curStr + copyStr(res, curNum);
            }
            // 如果是普通字符，直接添加到res
            else{
                res += ch;
            } 
        }
        return res;
    }
    string copyStr(string &str, int n){
        string result = "";
        for (int i = 0; i < n; ++i) {
            result += str;
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

最长有效括号

动态规划

  1. 划分阶段：按照最长有效括号子串的结束位置进行阶段划分。
  2. 定义状态：dp[i]表示以s[i]为结尾的最长有效括号子串长度。
  3. 状态转移方程：
    • 如果s[i] == '('，则以s[i]为结尾的字符串不可能是有效括号子串，dp[i] = 0。
    • 如果s[i] == ')'，需要考虑 s[i - 1] 来判断是否能够构成有效括号对：
      • 如果s[i-1] == '(，dp[i] 取决于「以字符 s[i - 2] 为结尾的最长有效括号长度」 + 「s[i - 1] 与 s[i] 构成的有效括号对长度（2）」，即 dp[i] = dp[i - 2] + 2。如果i-2 < 0，则dp[i] = 2。
      • 如果s[i-1] == ')'，以 s[i - 1] 为结尾的最长有效长度为 dp[i - 1]，则我们需要看 i - 1 - dp[i - 1] 位置上的字符 s[i - 1 - dp[i - 1]]是否与 s[i] 匹配。
        • 如果 s[i - 1 - dp[i - 1]] == '('，则说明 s[i - 1 - dp[i - 1]]与 s[i] 相匹配，此时我们需要看以 s[i - 1 - dp[i - 1]] 的前一个字符 s[i - 2 - dp[i - 1]] 为结尾的最长括号长度是多少，将其加上 s[i - 1 - dp[i - 1]]与 s[i]，从而构成更长的有效括号对：即dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2，如果 s[i - dp[i - 1] - 2] 不存在，即i - dp[i - 1] - 2 < 0，则dp[i] = dp[i-1] + 2。
  4. 初始条件：dp[0] = 0。
  5. 返回结果：max(dp[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
class Solution {
public:
    int longestValidParentheses(string s) {
        // 定义状态
        int n = s.length();
        vector<int> dp(n);
        int res = 0;
        // 遍历字符串
        for(int i = 1; i < n; i++){
            // 如果是左括号
            if(s[i] == '('){
                dp[i] = 0;
            }
            // 否则看s[i-1]，如果是左括号
            else if(s[i-1] == '('){
                // i-2的位置下标是否合法
                if(i - 2 < 0){
                    dp[i] = 2;
                }
                else{
                    dp[i] = dp[i-2] + 2;
                }
            }
            // 如果s[i-1]是右括号，看s[i - 1 - dp[i - 1]]和s[i]是否匹配
            else if(i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '('){
                // 看i-dp[i-1]-2是否合法
                int index = i - dp[i-1] - 2;
                if(index < 0){
                    dp[i] = dp[i-1] + 2;
                }
                else{
                    dp[i] = dp[index] + dp[i-1] + 2;
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

栈

  1. 定义一个变量 ans 用于维护最长有效括号的长度，初始时，ans = 0。
  2. 定义一个栈用于判定括号对是否匹配（栈中存储的是括号的下标），栈底元素始终保持「最长有效括号子串的开始元素的前一个元素下标」。
  3. 初始时，我们在栈中存储 -1 作为哨兵节点，表示「最长有效括号子串的开始元素的前一个元素下标为 -1」。
  4. 然后从左至右遍历字符串。
    • 如果遇到左括号，则入栈；
    • 如果遇到右括号，将栈顶弹出，弹出后：
      • 如果栈为空，说明刚刚弹出的不是左括号，而是最长有效括号子串的开始元素的前一个元素下标，此时无法完成合法匹配。将当前右括号的坐标 i 压入栈中，充当「下一个有效括号子串的开始元素前一个下标」。
      • 栈不为空，说明匹配，当前合法匹配的长度为i-stack.top()。然后更新最大长度。
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 longestValidParentheses(string s) {
        // 定义栈，初始化
        stack<int> stack;
        stack.push(-1);
        int res = 0;
        // 遍历字符串
        for(int i = 0; i < s.length(); i++){
            // 如果是左括号，入栈
            if(s[i] == '('){
                stack.push(i);
            }
            // 如果是右括号，弹出栈顶
            else{
                stack.pop();
                // 判断弹出的是左括号还是前一个元素的下标
                if(stack.empty()){
                    stack.push(i);
                }
                else{
                    int len = i - stack.top();
                    res = max(res, len);
                }
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

接雨水

相向双指针

对前后缀分解方法的空间优化，某个位置能接多少水，取决于它前面的所有木板的最高值，及后面所有木板的最高值，两者之间的最小值-它自身的高度，就是这个位置能接的水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        // 记录前后最大高度
        int preMax = 0;
        int sufMax = 0;
        // 定义双指针
        int left = 0;
        int right = n - 1;
        int res = 0;
        // 相向而行
        while(left < right){
            preMax = max(preMax, height[left]);
            sufMax = max(sufMax, height[right]);
            // 更新
            res += preMax < sufMax ? preMax - height[left++] : sufMax - height[right--];
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

单调栈

如果当前元素小于栈顶元素，无法接水，所以入栈；如果当前元素大于等于栈顶元素，不断出栈，出栈后如果栈为空，表明只是两根相邻的柱子，无法接水，否则可以计算面积，高度取当前栈顶（索引为left）和当前元素的较小值，宽是i - 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
27
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        // 定义栈
        stack<int> stack;
        // 遍历所有元素
        for(int i = 0; i < height.size(); i++){
            // 如果栈不为空，且当前元素大于等于栈顶元素
            while(!stack.empty() && height[i] >= height[stack.top()]){
                int bottomHeight = height[stack.top()];
                stack.pop();
                // 如果栈为空，无法接水
                if(stack.empty()){
                    break;
                }
                // 记录左边界
                int left = stack.top();
                int h = min(height[left], height[i]) - bottomHeight;
                ans += h * (i - left - 1);
            }
            // 入栈
            stack.push(i);
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

用队列实现栈

分析

和用两个栈实现队列类似。

  • push：一个队列为主队列，一个为辅助队列，当入栈操作时，先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。
  • pop：直接返回。
  • top：直接返回。
  • empty：主队列为空。
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
class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;
    MyStack() {
        
    }
    
    void push(int x) {
        queue2.push(x);
        // 把1中的元素放入2
        while(!queue1.empty()){
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }
    
    int pop() {
        int ans = queue1.front();
        queue1.pop();
        return ans;   
    }
    
    int top() {
        return queue1.front();
    }
    
    bool empty() {
        return queue1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
  • 时间复杂度：入栈操作的时间复杂度为O(n)。出栈、取栈顶元素、判断栈是否为空的时间复杂度为O(1)。
  • 空间复杂度：O(n)

三数之和

对撞指针

先进行排序。固定一个元素x，然后将left指针指向它的下一个元素y，right指向末尾，三数相加大于target则向左移动right，否则向右移动left，直至两指针相撞，然后移动x，再进行对撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        // 循环遍历
        for(int i = 0; i < n-2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // 此时两数之和的目标
            int target = 0 - nums[i];
            // 定义对撞指针
            int left = i + 1, right = n - 1;
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum == target){
                    ans.push_back({nums[i], nums[left], nums[right]});
                    // 跳过重复的left和right值
                    for(left += 1; left < right && nums[left] == nums[left-1]; left++);
                    for(right -=1; right > left && nums[right] == nums[right+1]; right--);
                }
                else if(sum > target){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ans;
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)

缺失的第一个正数

分析

将当前数组视为哈希表。一个长度为 n 的数组，对应存储的元素值应该为 [1, n + 1] 之间，其中还包含一个缺失的元素。

  1. 遍历一遍数组，将当前元素放到其对应位置上（比如元素值为 1 的元素放到数组第 0 个位置上、元素值为 2 的元素放到数组第 1 个位置上，等等）。实际上这样操作后，比n大的元素不会被操作，或者说，当数组中存在一个比n大的元素时，必然有至少一个值小于等于n，它一定会被找到。
  2. 然后再次遍历一遍数组。遇到第一个元素值不等于下标 + 1 的元素，就是答案要求的缺失的第一个正数。
  3. 如果遍历完没有在数组中找到缺失的第一个正数，则缺失的第一个正数是 n + 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        // 第一次遍历
        for(int i = 0; i < n; i++){
            // 只考虑1~n之间的数
            while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1]){
                int index1 = i;
                int index2 = nums[index1] - 1;
                swap(nums[index1], nums[index2]);
            }
        }
        // 第二次遍历
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return n + 1;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

最长连续序列

哈希表

  1. 先将数组存储到集合中进行去重，用变量curLen和ans记录当前序列和最长序列的长度。
  2. 遍历集合，判断当前元素num的num-1是否在集合中，如果不在集合中，说明num是序列的起始，如果在集合中，直接跳过。
  3. 对于起始元素num，判断num+1,num+2,…是否在集合中，并更新序列长度，最后更新ans。
  4. 返回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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> set;
        // 存入集合，去重
        for(int i = 0; i < n; i++){
            set.insert(nums[i]);
        }
        // 维护长度变量
        int ans = 0;
        // 遍历集合
        for(const int& num : set){
            // 确定序列起始
            if(set.count(num-1) == 0){
                int curNum = num + 1;
                int curLen = 1;
                // 枚举
                while(set.count(curNum) != 0){
                    curLen++;
                    curNum++;
                }
                ans = max(ans, curLen);
            }
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

总结

主要涉及栈、队列、哈希表等内容，注意单调栈的部分，之后需要更多的练习。

单调栈

单调栈视频讲解

算法笔记 > 面试篇
#leetcode-notes
06.04 第 038 ~ 050 题（第 13 ~ 16 天）
http://example.com/2024/10/28/posts/0604/
作者
Xuan Yang
发布于
2024年10月28日
许可协议