6 篇博文含有标签「分治」

106.从中序与后序遍历序列构造二叉树

2023年11月28日 · 阅读需 2 分钟

1、题干

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

2、思路

后序遍历数组最后一个元素是根节点，中序遍历数组中根节点前、后两边分别是左子树与右子树，根据这两个性质递归即可，时间复杂度最优 $O(n\log{n})$ ，最差 $O(n^2)$

3、代码

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (!inorder.length) return null;

    const rv = postorder.at(-1);
    const root = new TreeNode(rv);

    const c = inorder.indexOf(rv);

    const inLeft = inorder.slice(0, c);
    const inRight = inorder.slice(c + 1);

    const postLeft = postorder.slice(0, c);
    const postRight = postorder.slice(c, postorder.length - 1);

    root.left = buildTree(inLeft, postLeft);
    root.right = buildTree(inRight, postRight);

    return root;
}

427.建立四叉树

2022年4月29日 · 阅读需 7 分钟

Whilconn

1、题干

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的四叉树的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制接受。
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False，将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。

如果你想了解更多关于四叉树的内容，可以参考 wiki 。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

示例 2：

输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：

提示：

n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6

2、解题思路

日常吐槽翻译，题目看了老半天

题目意思是要把 $n * n$ 矩阵分割成 $4$ 等份（左上、右上、左下、右下）；分割之后返回一个 Node，Node 初始化要确定 $3$ 个值：val、isLeaf、children（ $4$ 个子节点）；如果 Node 不是叶子节点就接着递归分割它的 $4$ 个子节点对应的子矩阵。

children：可以先递归求出 $4$ 个子节点，当前节点是否有子节点由 isLeaf 决定
val：所有子节点的 val 之和除以 $4$ 并向上取整（也可以向下取整）
isLeaf：所有子节点的 val 之和是 $4$ 或 $0$ ，且所有子节点都是叶子节点

矩阵大小是 $n * n(n = 2 ^ x, 0 <= x <= 6)$ ，矩阵最小是 $1*1$ 最大是 $64*64$ ，因此除最小矩阵外所有矩阵都可以被 $4$ 等分，没有其他特殊情况需要处理

3、代码

var construct = function (grid) {
    const n = grid.length;

    function dfs(i0, i1, j0, j1) {
        if (i0 === i1 && j0 === j1) return new Node(grid[i0][j0], true);

        // 递归求出4个子节点
        const mi = Math.floor(i1 / 2 + i0 / 2), mj = Math.floor(j1 / 2 + j0 / 2);
        const tl = dfs(i0, mi, j0, mj);
        const tr = dfs(i0, mi, mj + 1, j1);
        const bl = dfs(mi + 1, i1, j0, mj);
        const br = dfs(mi + 1, i1, mj + 1, j1);

        const children = [tl, tr, bl, br];
        // 求出所有子节点的 val 之和
        const val = children.reduce((a, c) => a + c.val, 0);
        // isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点 
        const isLeaf = (val % 4 === 0) && children.every((n) => n.isLeaf);

        // node.val：所有子节点的 val 之和除以 4 并向上取整
        // node.isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
        // 4个子节点：当前节点是否有子节点由 isLeaf 决定
        return new Node(Math.ceil(val / 4), isLeaf, ...(isLeaf ? [] : children));
    }

    return dfs(0, n - 1, 0, n - 1);
};

4、执行结果

1763.最长的美好子字符串

2022年2月1日 · 阅读需 3 分钟

Whilconn

1、题干

当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

1 <= s.length <= 100
s 只包含大写和小写英文字母。

2、解题思路

由题意可知美好子串中不会单独存在大写或小写字母，因此可以在单独的大写或小写字母处断开字符串，对拆分出来的左右子串进行递归查找，直到子串成为美好子串。

3、代码

var longestNiceSubstring = function (s) {
    for (let i = 0; i < s.length; i++) {
        const c = s[i].charCodeAt(0) < 91 ? s[i].toLowerCase() : s[i].toUpperCase();
        if (s.includes(c)) continue;
        const s1 = longestNiceSubstring(s.slice(0, i));
        const s2 = longestNiceSubstring(s.slice(i + 1));
        return s1.length >= s2.length ? s1 : s2;
    }
    return s;
};

4、执行结果

LCR 060.前 K 个高频元素

2022年1月19日 · 阅读需 3 分钟

Whilconn

1、题干

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字

3、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度

时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$

5、解法2-桶排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入按数量存入桶中，最后返回前 k 个数字。其时间复杂度为 $O(n)$ ，解决了进阶问题。

6、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

剑指 Offer II 060.出现频率最高的 k 个数字

2022年1月19日 · 阅读需 3 分钟

Whilconn

1、题干

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字

3、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度

时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$

5、解法2-桶排序

6、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

347.前 K 个高频元素

2021年11月6日 · 阅读需 2 分钟

Whilconn

1、题干

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

解题思路

创建哈希映射map，用于统计数字出现次数，key为数字，value为出现次数
创建数组arr，用于统计每个出现次数对应的数字集合，数组下标代表数字出现次数，值为出现次数与之相等的数字的集合
倒序遍历数组arr，提取前出现频率前 k 高的数字

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        map[nums[i]] = (map[nums[i]] || 0) + 1;
    }

    const matrix = Object.entries(map);
    const arr = [];
    for (let i = 0; i < matrix.length; i++) {
        const [n, c] = matrix[i];
        if (!arr[c]) arr[c] = [];
        arr[c].push(+n);
    }

    const res = [];
    for (let i = arr.length - 1; i > -1; i--) {
        if (arr[i] && res.length < k) {
            res.push(...arr[i].slice(0, k - res.length));
        }
    }

    return res;
};

1、题干​

2、思路​

3、代码​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

2、解题思路​

3、代码​

4、执行结果​

1、题干​

2、解法1-API排序​

3、代码​

4、复杂度​

5、解法2-桶排序​

6、代码​

7、复杂度​

1、题干​

2、解法1-API排序​

3、代码​

4、复杂度​

5、解法2-桶排序​

6、代码​

7、复杂度​

1、题干​

解题思路​

代码​

1、题干

2、思路

3、代码

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

2、解题思路

3、代码

4、执行结果

1、题干

2、解法1-API排序

3、代码

4、复杂度

5、解法2-桶排序

6、代码

7、复杂度

1、题干

2、解法1-API排序

3、代码

4、复杂度

5、解法2-桶排序

6、代码

7、复杂度

1、题干

解题思路

代码