2022-07-30

[Zheaoli]

2022-07-30

[gongpeione]

/*
 * @lc app=leetcode id=105 lang=javascript
 *
 * [105] Construct Binary Tree from Preorder and Inorder Traversal
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length && !inorder.length) {
        return;
    }

    // the first element of the preorder array
    // is always the root node of the binary tree
    const rootVal = preorder[0];

    // we can find the root val's index in the inorder array
    // it means that reset elements from the left of the mid
    // builds up the left binary tree
    const mid = inorder.indexOf(rootVal);

    // create binary tree
    const rootNode = new TreeNode(
        rootVal,
        // the left tree could build up with elements in the indorder from 0 to mid - 1
        // and with the elements in preorder from 1 to mid
        buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid)),
        buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1))
    );

    return rootNode;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件

[SaraadKun]

952. 按公因数计算最大组件大小

class Solution {

    int N = 20010, ans = 1;
    int[] f = new int[N], cnts = new int[N];
    //初始化UF
    {
        for (int i = 0; i < N; i++) {
            f[i] = i;
            cnts[i] = 1;
        }
    }

    private int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    private void union(int x, int y) {
        int idx = find(x), idy = find(y);
        if (idx == idy) {
            return;
        }
        //union时更新连通块的计数以及ans
        cnts[idy] += cnts[idx];
        f[idx] = idy;
        ans = Math.max(ans, cnts[idy]);
    }

    public int largestComponentSize(int[] nums) {
        //直接gcd枚举数字判断喜提TLE,故将每个数字分解质因数,维护 质因数 -> [数字下标集合] 的映射关系加速查找
        //用下标维护数据可以将数据范围从1e5降到2*1e4
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int cur = nums[i];
            //寻找质因数并更新映射
            for (int j = 2; j * j <= cur; j++) {
                if (nums[i] % j == 0) {
                    add(map, j, i);
                    while (cur % j == 0) {
                        cur /= j;
                    }
                }
            }
            //若操作完成后cur大于1,则cur必然是一个质数
            if (cur > 1) {
                add(map, cur, i);
            }
        }
        for (Integer key : map.keySet()) {
            List<Integer> list = map.get(key);
            //只需遍历到一遍list,list中的元素就全部联通了
            for (int i = 1; i < list.size(); i++) {
                union(list.get(0), list.get(i));
            }
        }
        return ans;
    }

    private void add(Map<Integer, List<Integer>> map, int key, int val) {
        List<Integer> list = map.getOrDefault(key, new ArrayList<>());
        list.add(val);
        map.put(key, list);
    }
}

---

WeChat: Saraad