07.03 第 075 ~ 087 题（第 09 ~ 12 天）

07.03 第 075 ~ 087 题（第 09 ~ 12 天）

二叉树的完全性检验

分析

如果当前节点不为空，且左子树为空，右子树不为空，则返回false。否则递归判断左右子树是否是完全二叉树。这种思路是错误的，因为如果左子树是完全二叉树，但是没有右子树，而右子树不为空，这棵树也不是完全二叉树。

使用广度优先搜索，即层序遍历实现。用一个bool变量标记是否出现过空节点，一旦出现过空节点，再出现非空节点，直接返回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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // 处理边界
        if(root == nullptr){
            return true;
        }

        queue<TreeNode*> que;
        que.push(root);
        bool foundNull = false;

        while(!que.empty()){
            TreeNode* node = que.front();
            que.pop();

            if(node == nullptr){
                foundNull = true;
            }else{
                if(foundNull){
                    return false;
                }

                que.push(node->left);
                que.push(node->right);
            }
        }

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

二叉树直径

分析

链：从子树中的叶子节点到当前节点的路径。把最长链的长度，作为 dfs 的返回值。根据这一定义，空节点的链长是 −1，叶子节点的链长是 0。

直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个 node，假设直径在这里「拐弯」，也就是计算由左右两条从下面的叶子节点到 node 的链的节点值之和，去更新答案的最大值。

dfs返回链长，当前节点到其他节点的最长路径是左子树链长和右子树链长的较大值。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root){
        if(root == nullptr){
            return -1;
        }
        int leftLen = dfs(root->left) + 1;
        int rightLen = dfs(root->right) + 1;
        ans = max(ans, leftLen + rightLen);
        return max(leftLen, rightLen);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉树的最大宽度

广度优先搜索

左子节点编号2 * i，右子节点为2 * i + 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
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long ans = 1;
        vector<pair<TreeNode*, unsigned long long>> arr;
        arr.emplace_back(root, 1L);
        // 广度优先
        while(!arr.empty()){
            vector<pair<TreeNode*, unsigned long long>> tmp;    // 暂时存放下一层的节点
            // 遍历当前层的每一个节点
            for(auto &[node, index] : arr){
                if(node->left){
                    tmp.emplace_back(node->left, index * 2);
                }
                if(node->right){
                    tmp.emplace_back(node->right, index * 2 + 1);
                }
            }
            // 遍历完当前层，更新最大宽度
            ans = max(ans, arr.back().second - arr[0].second + 1);
            // 更新当前层节点
            arr = move(tmp);
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

std::move是将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有内存的搬迁或者内存拷贝所以可以提高利用效率,改善性能.。

深度优先搜索

遍历时如果是先访问左子节点，再访问右子节点，每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值，需要记录下来进行后续的比较。一次深度优先搜索中，需要当前节点到当前行最左边节点的宽度，以及对子节点进行深度优先搜索，求出最大宽度，并返回最大宽度。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
unordered_map<int, unsigned long long> levelMin;
    int widthOfBinaryTree(TreeNode* root) {
         return dfs(root, 1, 1LL);
    }
    unsigned long long dfs(TreeNode* node, int depth, unsigned long long index){
        // 处理边界
        if(node == nullptr){
            return 0LL;
        }
        // 第一次访问当前层
        if(!levelMin.count(depth)){
            levelMin[depth] = index;
        }
        // 否则计算最大宽度
        unsigned long long leftLen = dfs(node->left, depth + 1, index * 2);
        unsigned long long rightLen = dfs(node->right, depth + 1, index * 2 + 1);
        return max({index - levelMin[depth] + 1LL, leftLen, rightLen});
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

零钱兑换

分析

动态规划：

  1. 划分阶段：按照背包容量即金额进行阶段划分。
  2. 定义状态：dp[i]表示凑成i元需要的最少硬币数。
  3. 状态转移方程：dp[i] = min(dp[i], dp[i-num]+1)
  4. 初始条件：凑成总金额为0所需的最少硬币数为0，dp[0]=0
  5. 返回结果：dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 定义状态
        vector<int> dp(amount + 1, INT_MAX-1);
        dp[0] = 0;  // 凑成0元物品需要0个硬币
        // 枚举物品
        for(int coin : coins){
            // 枚举重量
            for(int i = coin; i <= amount; i++){
                dp[i] = min(dp[i], dp[i-coin] + 1);
            }
        }
        // 返回结果
        return dp[amount] == (INT_MAX - 1) ? -1 : dp[amount];
    }
};
  • 时间复杂度：$O(n \times amount)$
  • 空间复杂度：$O(amount)$

子集

分析

回溯法：递归结束条件是遍历到最后一个元素，然后选择/不选择当前元素进行递归。

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:
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        dfs(nums, path, 0);
        return ans;
    }
    void dfs(vector<int>& nums, vector<int>& path, int index){
        // 递归结束
        if(index == nums.size()){
            ans.push_back(path);
            return;
        }
        // 选择不加入
        dfs(nums, path, index + 1);
        // 选择加入
        path.push_back(nums[index]);
        dfs(nums, path, index + 1);
        path.pop_back();
    }
};
  • 时间复杂度：$O(n \cdot 2^n)$，其中 n 为 nums 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 $O(2^n)$ 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间。
  • 空间复杂度：$O(n)$，不计返回值空间。

最大正方形

分析

  1. 划分阶段：按照正方形的右下角坐标进行阶段划分。
  2. 定义状态：dp[i][j]表示以(i,j)为右下角的且值包含1的正方形的最大边长。
  3. 状态转移方程：如果matrix[i][j] == 0，则dp[i][j] = 0；否则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
  4. 初始条件：dp[i][j] = 0。边界条件：i == 0 || j == 0。即当matrix[i][j] = 0时，无需进行操作，因为初始化为0，如果是1，再根据是否是边界情况来进行不同的操作。
  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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        // 定义状态
        vector<vector<int>> dp(m, vector<int>(n));
        // 遍历矩阵
        int ans = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    // 处理边界条件
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    }
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans * ans;
    }
};
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

两两交换链表中的节点

迭代

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
/**
 * 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* swapPairs(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        ListNode* dummy = new ListNode(-1, head);
        ListNode* pre = dummy;
        ListNode* left = head;
        ListNode* right = left->next;

        while(left && right){
            ListNode* next = right->next;
            pre->next = right;
            right->next = left;
            left->next = next;
            pre = left;
            left = next;
            if(left){
                right = left->next;
            }  
        } 
        return dummy->next;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

递归

如果当前节点为空，或者当前节点的next为空，则递归结束，无需交换。否则递归得到当前节点的下下个节点转换后的头，当前节点指向它，当前节点的下个节点指向当前节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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* swapPairs(ListNode* head) {
        // 递归结束
        if(!head || !head->next){
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;

        return newHead;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n),空间复杂度主要取决于递归调用的栈空间。

爬楼梯

迭代

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for(int i = 1; i <= n; i++){
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

最大子数组和

动态规划

  1. 划分阶段：按照子序列的结尾位置进行阶段划分。
  2. 定义状态：dp[i]表示以nums[i]结尾的序列的最大和。
  3. 状态转移方程：dp[i] = max(0, dp[i-1]) + nums[i]。
  4. 初始条件：dp[0] = nums[0]。
  5. 返回结果：维护一个最大和变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        // 定义状态
        vector<int> dp(n);
        dp[0] = nums[0];
        int ans = dp[0];
        // 枚举数字
        for(int i = 1; i < n; i++){
            dp[i] = max(0, dp[i-1]) + nums[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

这种方法可以进一步优化，由于在计算dp[i]时只需要用到dp[i-1]，而前面的都无需维护，所以用一个变量记录dp[i-1]即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        // 定义状态
        int pre = nums[0];
        int ans = pre;
        // 枚举数字
        for(int i = 1; i < n; i++){
            pre = max(0, pre) + nums[i];
            ans = max(ans, pre);
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

分治法

维护四个变量：

  • lSum：以l为左端点的最大子段和，lSum要么等于左子区间的lSum，要么等于左子区间的iSum+右子区间的lSum，取较大值。
  • rSum：以r为右端点的最大子段和，rSum要么等于右子区间的rSum，要么等于右子区间的iSum+左子区间的rSum，取较大值。
  • mSum：[l, r]区间的最大子段和：mSum可能是左子区间的mSum，也可能是右子区间的mSum，也可能跨越左右子区间，即左子区间的rSum+右子区间的lSum。
  • iSum：[l, r]整个区间和，等于左子区间的iSum+右子区间的iSum。
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:
    // 维护四个状态
    struct Status{
        int lSum, rSum, mSum, iSum;
    };

    // 线段树的pushup操作
    Status pushUp(Status left, Status right){
        int lSum = max(left.lSum, left.iSum + right.lSum);
        int rSum = max(right.rSum, right.iSum + left.rSum);
        int iSum = left.iSum + right.iSum;
        int mSum = max({left.mSum, right.mSum, left.rSum + right.lSum});

        return (Status){lSum, rSum, mSum, iSum};
    }

        // 获取子区间的和
    Status get(vector<int>& nums, int left, int right){
        // 递归结束
        if(left == right){
            return (Status){nums[left], nums[left], nums[left], nums[left]};
        }
        // 递归计算左右区间
        int mid = (left + right) / 2;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid + 1, right);
        // 合并
        return pushUp(lSub, rSub);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};
  • 时间复杂度：O(n)，把递归的过程看作是一颗二叉树的先序遍历。
  • 空间复杂度：O(logn)，递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)。

分治法不仅可以解决区间 [0,n−1]，还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是线段树。

全排列

分析

  • 递归终止条件：到达叶子节点，即index == n。
  • 明确选择：固定当前元素nums[index]，与后面的元素进行交换，然后进行下一层递归，最后还原。
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:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
    
    void dfs(vector<int>& nums, int index){
        // 递归终止
        if(index == nums.size()){
            res.push_back(nums);
            return;
        }
        // 对于每一个元素
        for(int i = index; i < nums.size(); i++){
            swap(nums[index], nums[i]); // 交换
            dfs(nums, index + 1);   // 固定index+1位的元素
            swap(nums[index], nums[i]); // 还原
        }
    }
};
  • 时间复杂度：$O(n \cdot n!)$
  • 空间复杂度：O(n)

括号生成

分析

  • 明确所有选择：每个位置上有2个选择，即(或者)，只有当左括号数量大于右括号数量时，当前位置才可以选择)。
  • 明确终止条件：当前节点为叶子节点，即左括号右括号剩余数都是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
class Solution {
public:
    vector<string> res;

    vector<string> generateParenthesis(int n) {
        string path;
        dfs(path, n, n);
        return res;
    }

    void dfs(string path, int left, int right){
        // 递归终止
        if(left == 0 && right == 0){
            res.push_back(path);
            return;
        }
        // 选择左括号
        if(left > 0){
            dfs(path + "(", left - 1, right);
        }
        // 选择右括号
        if(right > left){
            dfs(path + ")", left, right - 1);
        }
    }
};
  • 时间复杂度：$\frac{4^n}{\sqrt{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
class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        dfs(candidates, target, 0, path, 0);
        return res;
    }

    void dfs(vector<int>& candidates, int target, int index, vector<int>& path, int sum){
        // 递归终止
        if(sum == target){
            res.push_back(path);
            return;
        }
        if(index == candidates.size()){
            return;
        }

        // 不选择当前元素
        dfs(candidates, target, index + 1, path, sum);

        // 选择当前元素，但和不能大于目标
        if(sum + candidates[index] <= target){
            path.push_back(candidates[index]);
            dfs(candidates, target, index, path, sum + candidates[index]);  // 注意可以无限选择
            path.pop_back();
        }
    }
};
  • 时间复杂度：上界是$O(n \cdot 2^n)$
  • 空间复杂度：O(target)，除答案数组外，空间复杂度取决于递归的栈深度。

复原IP地址

分析

  • 明确所有选择：针对字符串中的每个数字，通常面临两个选项。第1个选项是将当前字符拼接到当前分段数字的末尾，拼接之后的数字应该在0到255之间。第2个选项是当前字符作为一个新的分段数字的开始。需要注意的是，一个IP地址最多只有4个分段数字，并且当开始一个新的分段数字时前一个分段数字不能是空的。
  • 明确终止条件：完成一次ip地址的复原，即index到达最后，且分段点数量达到3，且当前分段合法。
  • 传入参数：字符串，当前索引，当前分段，分段数，ip地址字符串。

子段合法标准：数值小于等于255且要么等于0要么第一个字符不为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
class Solution {
public:
    vector<string> res;

    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, "", 0, "");
        return res;
    }

    void dfs(string s, int index, string seg, int segI, string ip){
        // 加入结果集
        if(index == s.length() && segI == 3 && isValid(seg)){
            res.push_back(ip + seg);
        }else if(index < s.length() && segI <= 3){
            char ch = s[index];
            // 后续字符加到当前子段
            if(isValid(seg + ch)){
                dfs(s, index + 1, seg + ch, segI, ip);
            }
            // 重新开启新子段
            if(seg.length() > 0 && segI < 3){
                dfs(s, index + 1, string(1, ch), segI + 1, ip + seg +'.');
            }
        }
    }

    bool isValid(string seg){
        int num = stoi(seg);
        if(num <= 255 && (seg == "0" || seg[0] != '0')){
            return true;
        }else{
            return false;
        }
    }
};
  • 时间复杂度：$O(2^n)$
  • 空间复杂度：O(n)

总结

这一节的题之前基本上都做过，但这次做思路还是会不清晰，以后不能只是盲目地刷题，每周末要抽时间回顾一下本周做过的题。

算法笔记 > 面试篇
#leetcode-notes
07.03 第 075 ~ 087 题（第 09 ~ 12 天）
http://example.com/2024/11/10/posts/0703/
作者
Xuan Yang
发布于
2024年11月10日
许可协议