剑指offer -- 分治算法

发表于 | 分类于
字数统计: 2.2k | 阅读时长 ≈ 10
落日余晖与万里长城 -- 中国

剑指offer – 分治算法

剑指 Offer 07. 重建二叉树

Difficulty: 中等

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

限制：

0 <= 节点个数 <= 5000

Solution

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) {
            inMap[inorder[i]] = i;
        }
        return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    unordered_map<int, int> inMap; // 用来存 index 对应的 inorder 值
    TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return nullptr;
        // 根节点是前序遍历的第一个元素
        int rootIndex = preLeft; int rootValue = preorder[rootIndex];
        int rootIndexInMap = inMap[rootValue];   // 获得根节点在inorder中索引位置
        int leftSize = rootIndexInMap - inLeft; // 获得左子树的节点树

        TreeNode* root = new TreeNode(rootValue); // 创建根节点
        root->left = buildTree(preorder, inorder, preLeft + 1, preLeft + leftSize, inLeft, rootIndexInMap - 1);   // 创建左节点
        root->right = buildTree(preorder, inorder, preLeft + leftSize + 1, preRight, rootIndexInMap + 1, inRight);  // 创建右节点
        return root;
    }    
};

时间复杂度：$O(N)$，N 为节点数

空间复杂度：$O(N)$，哈希表占用空间 $O(N)$，树创建过程中 $O(\log N) \backsim O(N)$

剑指 Offer 16. 数值的整数次方

Difficulty: 中等

实现 ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

1
2
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

1
2
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

1
2
3
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0
  • $-2^{31} \leq n \leq 2^{31} - 1$
  • $-10^4 \leq x^n \leq 10^4$

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0.0) return 0.0;
        long b = n;
        double res = 1.0;
        // 负数情况
        if (b < 0) {
            b = -b;
            x = 1 / x;
        }
        while (b) {
            // 需要分奇偶情况，奇数情况 x^n = x(x^(n/2))^2
            // 偶数情况 x^n = (x^(n/2))^2
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1; // 右移一位
        }
        return res;
    }
};

时间复杂度：$O(\log N)$，二分的时间复杂度为对数级别。

空间复杂度：$O(1)$，res , b 等变量占用常数大小额外空间。

剑指 Offer 17. 打印从1到最大的n位数

Difficulty: 简单

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数

Solution

1. 不考虑大数问题

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> printNumbers(int n) {
        int maxN = pow(10, n);
        vector<int> res(maxN - 1);
        for (int i = 1; i < maxN; i++) {
            res[i - 1] = i;
        }
        return res;
    }
};

时间复杂度，空间复杂度皆是 $O(10^n)$

2. 考虑大数问题

回溯，排列问题

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 {
private:
    vector<int> nums;
    string s;
public:
    vector<int> printNumbers(int n) {
        s.resize(n, '0');  // 初始化 s
        backtracking(0, n, s);
        return nums;
    }
    
    void backtracking(int idx, int end, string& s) {
        if (idx == end) {
            // 去除首部0的情况
            int j = 0;
            while (j < s.size() && s[j] == '0') j++;
            if (j != s.size()) nums.push_back(stoi(s.substr(j))); 
            // 本题限制输出vector<int>，所以可以用stoi来转换，
            // 如果输出为vector<string>, 则不需要转换
            return;
        }
        for (int i = 0; i <= 9; ++i) {
            // 常见回溯写法
            s[idx] = i + '0';
            backtracking(idx + 1, end, s);
            s[idx] = '0'; // 回溯
        }
    }
};

注意：回溯算法 可以看 carl 大佬写的专题！

时间复杂度：$O(10^n)$，递归生成的排列数量为 $10^n - 1$。

空间复杂度：$O(10^n)$，中间获得的结果存于 nums 中。

剑指 Offer 33. 二叉搜索树的后序遍历序列

Difficulty: 中等

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3

示例 1：

1
2
输入: [1,6,3,2,5]
输出: false

示例 2：

1
2
输入: [1,3,2,6,5]
输出: true

提示：

  1. 数组长度 <= 1000

Solution

方法一：递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return recur(postorder, 0, postorder.size() - 1);
    }
    bool recur(vector<int>& postorder, int i, int j) {
        if (i >= j) return true;
        int p = i;
        // 找到左子树，其中 postorder[j] 代表根节点
        while (postorder[p] < postorder[j]) p++;
        int m = p;   // m 为左右子树拐点，在右子树中第一个
        // 找到右子树，其中 postorder[j] 代表根节点
        while (postorder[p] > postorder[j]) p++;
        // 只有 p 遍历到 根节点，左右子树都递归返回 true 才返回 true
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
};

时间复杂度：$O(N^2)$，每次调用 recur(i,j) 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N) 。

空间复杂度：$O(N)$，最差情况下（即当树退化为链表），递归深度将达到 N。

方法二：单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> stk;
        int root = INT_MAX;
        for (int i = postorder.size() - 1; i >= 0; i--) {
            if (postorder[i] > root) return false;
            while (!stk.empty() && stk.top() > postorder[i]) {
                root = stk.top();
                stk.pop();
            }
            stk.push(postorder[i]);
        }
        return true;
    }
};

时间复杂度：$O(N)$，遍历 postorder 所有节点，各节点均入栈/出栈一次，使用 $O(N)$ 时间。

**空间复杂度：**最差情况下，单调栈 stack 存储所有节点，使用 $O(N)$ 额外空间。

剑指 Offer 51. 数组中的逆序对

Difficulty: 困难

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

1
2
输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

Solution

方法一：暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        // 暴力解法 (超时)
        int n = nums.size();
        if (n < 2) return 0;
        int count = 0;
        int i = 0, j = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[i]) {
                    count++;
                }
            }
        }
        return count;
    }
};

时间复杂度：$O(N^2)$，两层遍历

空间复杂度：$O(1)$，count 所需的额外空间

方法二：归并排序

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:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        vector<int> temp(n);
        return mergeSort(nums, temp, 0, n - 1);
    }
    int mergeSort(vector<int>& nums, vector<int>& temp, int left, int right) {
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        int res = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                // 皆是顺序对
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                res += mid - i + 1; // 此时 j 所指向的数，与 i 指向及其以后数皆构成逆序对
            }
        }
        // 如果 i 还未遍历到 mid，则说明 j == right + 1, 
        // 此时虽然 i 指向元素与后半部分元素会构成逆序对, 但是已经在前面计算过了，不用重复
        while (i <= mid) temp[k++] = nums[i++];
        
        // 如果 j 还未遍历到 mid，则说明 i == mid + 1, 此时 j 所指向元素与前半部分元素皆构成顺序对
        while (j <= right) temp[k++] = nums[j++]; 
        
        // 归并排序常规操作：temp 覆写 nums
        for (int l = 0; l < k; l++) nums[l + left] = temp[l];
        return res;
    }
};

参考 我自己写的排序算法总结中的归并排序： 排序算法 | CongZ’s Blog (czgitaccount.github.io)

由于主要思想就是归并排序，故时间复杂度与空间复杂度与归并排序相同。

时间复杂度：$O(N\log N)$

空间复杂度：$O(N)$

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解

回溯算法__代码随想录



----------- 本文结束 -----------




0%