Leaky Cauldron
0%

Posted on

题目(LeetCode #1087)

花括号展开

给定一个表示单词列表的字符串 s 。单词中的每个字母都有一个或多个选项。

  • 如果有一个选项，则字母按原样表示。
  • 如果有多个选项，则用大括号分隔选项。例如, "{a,b,c}" 表示选项 ["a", "b", "c"] 。

例如，如果 s = "a{b,c}" ，第一个字符总是 'a' ，但第二个字符可以是 'b' 或 'c' 。原来的列表是 ["ab", "ac"] 。

请你 按字典顺序 ，返回所有以这种方式形成的单词。

示例1：

输入：s = “{a,b}c{d,e}f”
输出：[“acdf”,”acef”,”bcdf”,”bcef”]

示例2：

输入：s = “abcd”
输出：[“abcd”]

提示：

  • 1 <= S.length <= 50
  • s 由括号 '{}' , ',' 和小写英文字母组成。
  • 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
36
37
38
39
class Solution {
    private char[] sArr;
    private List<String> result; // 用 List 存再排序比直接用 TreeSet 要快
    private StringBuilder builder;

    public String[] expand(String s) {
        sArr = s.toCharArray();
        result = new ArrayList<>();
        builder = new StringBuilder();

        dfs(0);

        Collections.sort(result);
        return result.toArray(new String[0]);
    }

    private void dfs(int idx) {
        if (idx == sArr.length) {
            result.add(builder.toString());
            return;
        }

        if (sArr[idx] == '{') {
            int rIdx = ++idx;
            while (rIdx < sArr.length && sArr[rIdx] != '}') rIdx++;

            for (int i = idx; i < rIdx; i++) {
                if (sArr[i] == ',') continue;
                builder.append(sArr[i]);
                dfs(rIdx + 1);
                builder.deleteCharAt(builder.length() - 1);
            }
        } else {
            builder.append(sArr[idx]);
            dfs(idx + 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

Posted on Edited on

LeetCode #290

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入：pattern = “abba”, s = “dog cat cat dog”
输出：true

示例 2:

输入：pattern = “abba”, s = “dog cat cat fish”
输出：false

示例 3:

输入：pattern = “aaaa”, s = “dog cat cat dog”
输出：false

提示:

  • 1 <= pattern.length <= 300
  • pattern 只包含小写英文字母
  • 1 <= s.length <= 3000
  • s 只包含小写英文字母和 ' '
  • s 不包含 任何前导或尾随对空格
  • s 中每个单词都被 单个空格 分隔

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] splitStrs = s.split(" ");
        if (splitStrs.length != pattern.length()) return false;

        Map<Character, String> map = new HashMap<>();

        for (int i = 0; i < splitStrs.length; i++) {
            char ch = pattern.charAt(i);
            if (map.containsKey(ch)) {
                if (!splitStrs[i].equals(map.get(ch))) return false;
            } else if (map.containsValue(splitStrs[i])) return false;
            else map.put(ch, splitStrs[i]);
        }

        return true;
    }
}

LeetCode #291

单词规律 II

给你一种规律 pattern 和一个字符串 s，请你判断 s 是否和 pattern 的规律相匹配。

如果存在单个字符到字符串的 双射映射 ，那么字符串 s 匹配 pattern ，即：如果pattern 中的每个字符都被它映射到的字符串替换，那么最终的字符串则为 s 。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。

示例 1：

输入：pattern = “abab”, s = “redblueredblue”
输出：true
解释：一种可能的映射如下：
‘a’ -> “red”
‘b’ -> “blue”

示例 2：

输入：pattern = “aaaa”, s = “asdasdasdasd”
输出：true
解释：一种可能的映射如下：
‘a’ -> “asd”

示例 3：

输入：pattern = “aabb”, s = “xyzabcxzyabc”
输出：false

提示：

  • 1 <= pattern.length, s.length <= 20
  • pattern 和 s 由小写英文字母组成

题解

参考题解：@czwhl123

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 {
    Map<Character, String> map = new HashMap<>();

    public boolean wordPatternMatch(String pattern, String s) {
        // 边界条件，如果pattern读完了字符串也正好读完就true，如果字符串没读完就false
        if (pattern.length() == 0) return s.length() == 0;

        char ch = pattern.charAt(0);
        // 从 1 位开始尝试是否有映射，由于每个 pattern 至少得对应一个字符，
        // 所以如果字符串剩下的字符少于 pattern 剩下的字符数就可以停止循环了
        for (int i = 1; i <= s.length() - pattern.length() + 1; i++) {
            // mapS 是 ch 的映射，有则返回映射，没有则等于 null
            String subS = s.substring(0, i), mapS = map.get(ch);
            // 这个 pattern 有映射，并且等于这段字符；
            // 或者这段字符不是 pattern 的映射并且没有其他映射,
            // 则可以假设这个映射成立并继续尝试匹配剩下的字符
            if (subS.equals(mapS) || (mapS == null && !map.containsValue(subS))) {
                // 不管是否是正确答案，先放进 map 里面尝试
                map.put(ch, subS);
                // 如果正好对了就返回 true
                if (wordPatternMatch(pattern.substring(1), s.substring(i))) return true;
                // 如果不对那就把这个映射取消继续下一个循环进行尝试
                else if (mapS == null) map.remove(ch);
            }
        }
        return false;
    }
}

Posted on Edited on

LeetCode #341

扁平化嵌套列表迭代器

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

  • NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
  • int next() 返回嵌套列表的下一个整数。
  • boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

1
2
3
4
5
initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示：

  • 1 <= nestedList.length <= 500
  • 嵌套列表中的整数值在范围 [-10^6, 10^6] 内

题解

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
public class NestedIterator implements Iterator<Integer> {
    private List<Integer> numList = new ArrayList<>();
    private int idx = 0;

    public NestedIterator(List<NestedInteger> nestedList) {
        addNums(nestedList);
    }

    private void addNums(List<NestedInteger> nestedList) {
        for (NestedInteger tmp : nestedList) {
            if (tmp.isInteger()) numList.add(tmp.getInteger());
            else addNums(tmp.getList());
        }
    }

    @Override
    public Integer next() {
        return numList.get(idx++);
    }

    @Override
    public boolean hasNext() {
        return idx < numList.size();
    }
}

LeetCode #339

嵌套列表权重和

给定一个嵌套的整数列表 nestedList ，每个元素要么是整数，要么是列表。同时，列表中元素同样也可以是整数或者是另一个列表。

整数的 深度 是其在列表内部的嵌套层数。例如，嵌套列表 [1,[2,2],[[3],2],1] 中每个整数的值就是其深度。

请返回该列表按深度加权后所有整数的总和。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：10
解释：因为列表中有四个深度为 2 的 1 ，和一个深度为 1 的 2。

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：27
解释：一个深度为 1 的 1，一个深度为 2 的 4，一个深度为 3 的 6。所以，1 + 4x2 + 6x3 = 27。

示例 3：

输入：nestedList = [0]
输出：0

提示：

  • 1 <= nestedList.length <= 50
  • 嵌套列表中整数的值在范围 [-100, 100] 内
  • 任何整数的最大 深度 都小于或等于 50

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int result = 0;

    public int depthSum(List<NestedInteger> nestedList) {
        calSum(nestedList, 1);
        return result;
    }

    private void calSum(List<NestedInteger> nestedList, int level) {
        for (NestedInteger tmp : nestedList) {
            if (tmp.isInteger()) result += level * tmp.getInteger();
            else {
                calSum(tmp.getList(), level + 1);
            }
        }
    }
}

LeetCode #364

加权嵌套序列和 II

给你一个整数嵌套列表 nestedList ，每一个元素要么是一个整数，要么是一个列表（这个列表中的每个元素也同样是整数或列表）。

整数的 深度 取决于它位于多少个列表内部。例如，嵌套列表 [1,[2,2],[[3],2],1] 的每个整数的值都等于它的 深度 。令 maxDepth 是任意整数的 最大深度 。

整数的 权重 为 maxDepth - (整数的深度) + 1 。

将 nestedList 列表中每个整数先乘权重再求和，返回该加权和。

示例 1：

输入：nestedList = [[1,1],2,[1,1]]
输出：8
解释：4 个 1 在深度为 1 的位置， 一个 2 在深度为 2 的位置。
1x1 + 1x1 + 2x2 + 1x1 + 1x1 = 8

示例 2：

输入：nestedList = [1,[4,[6]]]
输出：17
解释：一个 1 在深度为 3 的位置， 一个 4 在深度为 2 的位置，一个 6 在深度为 1 的位置。
1x3 + 4x2 + 6x1 = 17

提示：

  • 1 <= nestedList.length <= 50
  • 嵌套列表中整数的值在范围 [-100, 100]
  • 任意整数的最大 深度 小于等于 50

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private int maxDepth = 0;
    private int[] depthMap = new int[51];

    public int depthSumInverse(List<NestedInteger> nestedList) {
        sortNums(nestedList, 1);
        int result = 0;
        for (int i = 1; i <= 50; i++) result += (maxDepth - i + 1) * depthMap[i];

        return result;
    }

    public void sortNums(List<NestedInteger> nestedList, int depth) {
        for (NestedInteger tmp : nestedList) {
            maxDepth = Math.max(depth, maxDepth);
            if (tmp.isInteger()) depthMap[depth] += tmp.getInteger();
            else sortNums(tmp.getList(), depth + 1);
        }
    }
}

Posted on Edited on

LeetCode #285

二叉搜索树中的中序后继

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点。

示例 1：

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：

  • 树中节点的数目在范围 [1, 104] 内。
  • -10^5 <= Node.val <= 10^5
  • 树中各节点的值均保证唯一。

题解

利用二叉搜索树中序遍历单调递增求解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    private TreeNode result = null;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || result != null) return result;
        inorderSuccessor(root.left, p);
        if (root.val > p.val && result == null) result = root;
        inorderSuccessor(root.right, p);

        return result;
    }
}

LeetCode #510

二叉搜索树中的中序后继 II

给定一棵二叉搜索树和其中的一个节点 node ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

一个节点 node 的中序后继是键值比 node.val 大所有的节点中键值最小的那个。

你可以直接访问结点，但无法直接访问树。每个节点都会有其父节点的引用。节点 Node 定义如下：

1
2
3
4
5
6
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

示例 1：

输入：tree = [2,1,3], node = 1
输出：2
解析：1 的中序后继结点是 2 。注意节点和返回值都是 Node 类型的。

示例 2：

输入：tree = [5,3,6,2,4,null,null,1], node = 6
输出：null
解析：该结点没有中序后继，因此返回 null 。

示例 3：

输入：tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15
输出：17

示例 4：

输入：tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13
输出：15

示例 5：

输入：tree = [0], node = 0
输出：null

提示：

  • 树中节点的数目在范围 [1, 104] 内。
  • -10^5 <= Node.val <= 10^5
  • 树中各结点的值均保证唯一。

题解

二叉搜索树中的任意节点的中序后继可能有两种情况：

  • 如果该节点有右子树，则后继在右孩子节点的左子树的最低点

  • 如果该节点没有右子树，则后继在相对该节点树中较高的地方，向上找直到某个节点 node，node 在其父节点的左子树上为止

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public Node inorderSuccessor(Node node) {
        if (node.right != null) {
            node = node.right;
            while (node.left != null) node = node.left;
            return node;
        }

        /* 只要 node 在其父节点的右子树上就一直往上找 */
        while (node.parent != null && node.parent.right == node) node = node.parent;
        return node.parent;
    }
}

Posted on

题目(LeetCode #333)

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小。其中，最大指的是子树节点数最多的。

二叉搜索树（BST）中的所有节点都具备以下属性：

  • 左子树的值小于其父（根）节点的值。
  • 右子树的值大于其父（根）节点的值。

注意：子树必须包含其所有后代。

示例 1：

输入：root = [10,5,15,1,8,null,7]
输出：3
解释：本例中最大的 BST 子树是高亮显示的子树。返回值是子树的大小，即 3 。

示例 2：

输入：root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
输出：2

提示：

  • 树上节点数目的范围是 [0, 104]
  • -10^4 <= Node.val <= 10^4

题解

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 largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) return countNodes(root);

        int l = largestBSTSubtree(root.left);
        int r = largestBSTSubtree(root.right);

        return Math.max(l, r);
    }

    private boolean isBST(TreeNode node, int low, int high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return isBST(node.left, low, node.val) && isBST(node.right, node.val, high);
    }

    private int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

Posted on

题目(LeetCode #270)

给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。

注意：

给定的目标值 target 是一个浮点数
题目保证在该二叉搜索树中只会存在一个最接近目标值的数

示例：

输入: root = [4,2,5,1,3]，目标值 target = 3.714286
输出: 4

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int closestValue(TreeNode root, double target) {
        if (root == null) return Integer.MAX_VALUE;

        double diff = Math.abs(root.val - target);
        int left = closestValue(root.left, target);
        if (Math.abs(left - target) < diff) return left;

        int right = closestValue(root.right, target);
        if (Math.abs(right - target) < diff) return right;

        return root.val;
    }
}

Posted on Edited on

题目

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。 答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2：

输入: root = [1], target = 1, k = 3
输出: []

提示:

  • 节点数在 [1, 500] 范围内
  • 0 <= Node.val <= 500
  • Node.val 中所有值 不同
  • 目标结点 target 是树上的结点。
  • 0 <= k <= 1000

链式前向星

本题的难点在于建图，用以保存相邻节点之间的关系。树实际上也是无向图，在此可引入链式前向星的方法，用数组保存保存图中节点的关系。

一个简单的链式前向星实现主要包含以下元素：

  • idx：对图中的边进行编号；
  • heads 数组：保存图中的所有节点；
  • edges 数组：保存图中每条边的权重；
  • ends 数组：保存每条边的终点索引；
  • nexts 数组：保存下一条边的索引。

代码模板如下（参考: @Scarb）：

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
int N; // 最大节点数量
int M; // 最大边数

int idx = 0;				// 边索引
int[] heads = new int[N];	// heads[a] 表示以 a 节点为起点的最新一条边的索引
int[] edges = new int[M];	// edges[idx] 表示索引为 idx 的边的权重
int[] ends = new int[M];	// ends[idx] 表示索引为 idx 的边的终点节点在 heads 中的索引
int[] nexts = new int[M];	// nexts[idx] 表示索引为 idx 的边的下一条同起点的边的索引，用于找到同起点的下一条边

Arrays.fill(heads, -1);		// 设置所有节点都没有边

// 添加一条起点为 a，终点为 b，权重为 w 的边，边的索引为 idx，采用了类似尾插法的方法
public void add(int a, int b, int w) {
    ends[idx] = b;
    edges[idx] = w;
    nexts[idx] = a;
    heads[a] = idx++;
}

// 遍历从 a 出发的所有的边
// 从head[a]取出a节点最新一条边的索引idx，开始遍历。
// 每次通过next[idx]获取以该节点为起点的下一条边的索引
// 直到下一条边的索引为-1，即没有下一条边
for (int idx = head[a]; idx != -1; idx = nexts[idx]) {
    int end = ends[idx];
    int w = edges[idx];
}

题解

链式前向星 + 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
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 Solution {
    private int N = 501, M = N * 4, idx = 0;
    private int[] head = new int[N], end = new int[M], next = new int[M];
    private boolean[] visited = new boolean[N];
    private List<Integer> result;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Arrays.fill(head, -1);
        dfs(root);

        visited[target.val] = true;

        result = new ArrayList<>();
        find(target.val, k);

        return result;
    }

    private void add(int a, int b) {
        end[idx] = b;
        next[idx] = head[a];
        head[a] = idx++;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            add(root.val, root.left.val);
            add(root.left.val, root.val);
            dfs(root.left);
        }
        if (root.right != null) {
            add(root.val, root.right.val);
            add(root.right.val, root.val);
            dfs(root.right);
        }
    }

    private void find(int root, int k) {
        if (k == 0) {
            result.add(root);
            return;
        }

        for (int h = head[root]; h != -1; h = next[h]) {
            int e = end[h];
            if (!visited[e]) {
                visited[e] = true;
                find(e, k - 1);
            }
        }
    }
}

链式前向星 + BFS

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
class Solution {

    private int N = 501, M = N * 4, idx = 0;
    private int[] heads = new int[N], ends = new int[M], nexts = new int[M];
    private boolean[] visited = new boolean[N];

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> result = new ArrayList<>();
        Arrays.fill(heads, -1);
        dfs(root);

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(target.val);
        visited[target.val] = true;

        while (!queue.isEmpty() && k >= 0) {
            for (int i = queue.size(); i > 0; i--) {
                int cur = queue.poll();
                if (k == 0) {
                    result.add(cur);
                    continue;
                }

                for (int h = heads[cur]; h != -1; h = nexts[h]) {
                    int e = ends[h];
                    if (!visited[e]) {
                        queue.add(e);
                        visited[e] = true;
                    }
                }
            }
            k--;
        }

        return result;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            add(root.val, root.left.val);
            add(root.left.val, root.val);
            dfs(root.left);
        }
        if (root.right != null) {
            add(root.val, root.right.val);
            add(root.right.val, root.val);
            dfs(root.right);
        }
    }

    private void add(int a, int b) {
        ends[idx] = b;
        nexts[idx] = heads[a];
        heads[a] = idx++;
    }
}

保存父节点 + 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
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 Solution {
    private Map<TreeNode, TreeNode> parentMap;
    private Set<TreeNode> visited;
    private List<Integer> result;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        parentMap = new HashMap<>();
        dfs(root);

        visited = new HashSet<>();
        visited.add(target);

        result = new ArrayList<>();
        find(target, k);

        return result;
    }

    private void find(TreeNode root, int k) {
        if (k == 0) {
            result.add(root.val);
            return;
        }

        if (root.left != null && !visited.contains(root.left)) {
            visited.add(root.left);
            find(root.left, k - 1);
        }

        if (root.right != null && !visited.contains(root.right)) {
            visited.add(root.right);
            find(root.right, k - 1);
        }

        TreeNode parent = parentMap.get(root);
        if (parent != null && !visited.contains(parent)) {
            visited.add(parent);
            find(parent, k - 1);
        }
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            parentMap.put(root.left, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parentMap.put(root.right, root);
            dfs(root.right);
        }
    }
}

Posted on

题目(LeetCode #1485)

给你一个二叉树，树中每个节点都含有一个附加的随机指针，该指针可以指向树中的任何节点或者指向空（null）。

请返回该树的 深拷贝 。

该树的输入/输出形式与普通二叉树相同，每个节点都用 [val, random_index] 表示：

  • val：表示 Node.val 的整数
  • random_index：随机指针指向的节点（在输入的树数组中）的下标；如果未指向任何节点，则为 null 。
    该树以 Node 类的形式给出，而你需要以 NodeCopy 类的形式返回克隆得到的树。NodeCopy 类和 Node 类定义一致。

示例1：

输入：root = [[1,null],null,[4,3],[7,0]]
输出：[[1,null],null,[4,3],[7,0]]
解释：初始二叉树为 [1,null,4,7] 。
节点 1 的随机指针指向 null，所以表示为 [1, null] 。
节点 4 的随机指针指向 7，所以表示为 [4, 3] 其中 3 是树数组中节点 7 对应的下标。
节点 7 的随机指针指向 1，所以表示为 [7, 0] 其中 0 是树数组中节点 1 对应的下标。

示例2：

输入：root = [[1,4],null,[1,0],null,[1,5],[1,5]]
输出：[[1,4],null,[1,0],null,[1,5],[1,5]]
解释：节点的随机指针可以指向它自身。

示例3：

输入：root = [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]
输出：[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0]]

提示：

  • tree 中节点数目范围是 [0, 1000]
  • 每个节点的值的范围是 [1, 10^6]

题解

本题与 复制带随机指针的链表 类似，可先根据左右子树通过 DFS 复制树结构，同时使用 Map 保存原节点和克隆节点的关系，再遍历 Map 创建 random 指针即可。

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 Map<Node, NodeCopy> nodeMap;

    public NodeCopy copyRandomBinaryTree(Node root) {
        nodeMap = new HashMap<>();
        NodeCopy rootCopy = dfs(root);

        for (Map.Entry<Node, NodeCopy> entry : nodeMap.entrySet()) {
            Node node = entry.getKey();
            NodeCopy nodeCopy = entry.getValue();

            nodeCopy.random = nodeMap.get(node.random);
        }

        return rootCopy;
    }

    private NodeCopy dfs(Node root) {
        if (root == null) return null;
        if (nodeMap.containsKey(root)) return nodeMap.get(root);

        NodeCopy rootCopy = new NodeCopy(root.val);
        rootCopy.left = dfs(root.left);
        rootCopy.right = dfs(root.right);
        nodeMap.put(root, rootCopy);

        return rootCopy;
    }
}

也可直接通过 DFS 递归地复制 random 指针，通过 Map 保存已经复制过的节点，避免栈溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private Map<Node, NodeCopy> nodeMap;

    public NodeCopy copyRandomBinaryTree(Node root) {
        nodeMap = new HashMap<>();
        return dfs(root);
    }

    private NodeCopy dfs(Node root) {
        if (root == null) return null;
        if (nodeMap.containsKey(root)) return nodeMap.get(root);

        NodeCopy rootCopy = new NodeCopy(root.val);
        nodeMap.put(root, rootCopy); // 创建 rootCopy 后立即放入 map 中，以下三个 dfs 要用到，否则会栈溢出
        rootCopy.left = dfs(root.left);
        rootCopy.right = dfs(root.right);
        rootCopy.random = dfs(root.random);

        return rootCopy;
    }
}

可简化为如下形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private Map<Node, NodeCopy> nodeMap = new HashMap<>();

    public NodeCopy copyRandomBinaryTree(Node root) {
        if (root == null) return null;
        if (nodeMap.containsKey(root)) return nodeMap.get(root);

        NodeCopy rootCopy = new NodeCopy(root.val);
        nodeMap.put(root, rootCopy);
        rootCopy.left = copyRandomBinaryTree(root.left);
        rootCopy.right = copyRandomBinaryTree(root.right);
        rootCopy.random = copyRandomBinaryTree(root.random);

        return rootCopy;
    }
}

Posted on Edited on

LeetCode #235

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private TreeNode result;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        lca(root, p, q);
        return result;
    }

    private void lca(TreeNode root, TreeNode p, TreeNode q) {
        if (((long) root.val - p.val) * (root.val - q.val) <= 0) result = root;
        else if (root.val < p.val && root.val < q.val) lca(root.right, p, q);
        else lca(root.left, p, q);
    }
}

LeetCode #236

二叉树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private TreeNode result;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        lca(root, p, q);
        return result;
    }

    private void lca(TreeNode root, TreeNode p, TreeNode q) {
        if (((long) root.val - p.val) * (root.val - q.val) <= 0) result = root;
        else if (root.val < p.val && root.val < q.val) lca(root.right, p, q);
        else lca(root.left, p, q);
    }
}

LeetCode #1644

二叉树的最近公共祖先 II

给定一棵二叉树的根节点 root，返回给定节点 p 和 q 的最近公共祖先（LCA）节点。如果 p 或 q 之一 不存在 于该二叉树中，返回 null。树中的每个节点值都是互不相同的。

根据维基百科中对最近公共祖先节点的定义：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是 后代节点 中既包括 p 又包括 q 的最深节点（我们允许 一个节点为自身的一个后代节点 ）”。一个节点 x 的 后代节点 是节点 x 到某一叶节点间的路径中的节点 y。

示例1：

输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出： 3
解释： 节点 5 和 1 的共同祖先节点是 3。

示例2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例3：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
输出：null
解释：节点 10 不存在于树中，所以返回 null。

提示：

  • 树中节点个数的范围是 [1, 104]
  • -109 <= Node.val <= 109
  • 所有节点的值 Node.val 互不相同
  • p != q

题解

本题不保证 p 和 q 存在于树中，以下为本系列题的通用解，四个题目全都可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private TreeNode result;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return result;
    }

    private int dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return 0;

        int res1 = dfs(root.left, p, q);
        int res2 = dfs(root.right, p, q);
        int res3 = (root == p || root == q) ? 1 : 0;
        int cnt = res1 + res2 + res3;

        if (cnt == 2 && result == null) result = root;

        return cnt;
    }
}

LeetCode #1650

二叉树的最近公共祖先 III

给定一棵二叉树中的两个节点 p 和 q，返回它们的最近公共祖先节点（LCA）。

每个节点都包含其父节点的引用（指针）。Node 的定义如下：

1
2
3
4
5
6
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

根据维基百科中对最近公共祖先节点的定义：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是 后代节点 中既包括 p 又包括 q 的最深节点（我们允许 一个节点为自身的一个后代节点 ）”。一个节点 x 的 后代节点 是节点 x 到某一叶节点间的路径中的节点 y。

示例1：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和 1 的最近公共祖先是 3。

示例2：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和 4 的最近公共祖先是 5，根据定义，一个节点可以是自身的最近公共祖先。

示例3：

输入: root = [1,2], p = 1, q = 2
输出: 1

提示:

  • 树中节点个数的范围是 [2, 105]。
  • -109 <= Node.val <= 109
  • 所有的 Node.val 都是互不相同的。
  • p != q
  • p 和 q 存在于树中。

题解

由于本题加入了 parent，可采用类似求相交链表交点的方法求解。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;

        while (a != b) {
            a = a == null ? q : a.parent;
            b = b == null ? p : b.parent;
        }

        return a;
    }
}

Posted on Edited on

题目(LeetCode #323)

你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。

返回 图中已连接分量的数目 。

示例1：

输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2

示例2：

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出: 1

提示：

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • edges 中不会出现重复的边

题解

BFS

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 int countComponents(int n, int[][] edges) {
        if (n == 0 || edges == null) return 0;

        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) adjList.add(new ArrayList<>());
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }

        int count = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            count++;
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                visited[cur] = true;
                for (int next : adjList.get(cur)) {
                    if (!visited[next]) queue.add(next);
                }
            }
        }


        return count;
    }
}

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
29
30
31
32
33
34
35
class Solution {
    private int n;
    private boolean[] visited;
    List<List<Integer>> adjList;

    public int countComponents(int n, int[][] edges) {
        if (n == 0 || edges == null) return 0;

        this.n = n;
        adjList = new ArrayList<>();
        visited = new boolean[n];
        for (int i = 0; i < n; i++) adjList.add(new ArrayList<>());
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            	count++;
            }
        }

        return count;
    }

    public void dfs(int i) {
        if (visited[i]) return;

        visited[i] = true;
        for (int next : adjList.get(i)) dfs(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class UnionFind {
    private int[] parents, rank;
    int unionCnt = 0;

    public UnionFind(int[] parents) {
        this.parents = parents;
        this.rank = new int[parents.length];
        Arrays.fill(this.rank, 1);
    }

    public int find(int x) {
        if (parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }

    public void union(int x, int y) {
        int xRoot = find(x), yRoot = find(y);

        if (xRoot == yRoot) return;

        unionCnt++;
        if (rank[yRoot] <= rank[xRoot]) parents[yRoot] = xRoot;
        else parents[xRoot] = yRoot;
        if (rank[xRoot] == rank[yRoot]) rank[xRoot]++;
    }
}

class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n == 0 || edges == null) return 0;

        int[] parents = new int[n];
        for (int i = 0; i < n; i++) parents[i] = i;
        UnionFind uf = new UnionFind(parents);

        for (int[] edge : edges) uf.union(edge[0], edge[1]);

        return n - uf.unionCnt;
    }
}