破晓的知识屋
0%

2022-0827

发表于 分类于 ， ， 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

[toc]

第一题：二叉树节点在某层是第几个的求解方法#

662. 二叉树最大宽度 - 力扣（LeetCode）

1661612722021

注意是某一层最左边和最右边节点的距离，不包含右边的null

那么只要知道如果是完全二叉树的话， 他是这一层的第几个即可。

那就是父亲节点列索引乘2或者乘2+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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 0, 0);
        return res;
    }
    Map<Integer, Integer> minHIndex = new HashMap<>();
    void dfs(TreeNode node, int index, int h) {
        if (node == null) {
            return;
        }
        if (!minHIndex.containsKey(h)) {
            minHIndex.put(h, index);
        }
        res = Math.max(index - minHIndex.get(h) + 1, res);
        

        dfs(node.left, index*2, h+1);
        dfs(node.right, index*2+1, h+1);
    }
}

第二题 基于树的简单动态规划#

823. 带因子的二叉树 - 力扣（LeetCode）

1661612958186

排个序，然后按顺序求每个节点作为根节点的情况数，并放入缓存中

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
class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        Arrays.sort(arr);
        int mod = 1000000007;
        Map<Integer, Long> map = new HashMap<>();
        long res = 0;
        for (int i = 0; i < arr.length;i++) {
            int big = arr[i];
            long count = 1;
            for (int j = i-1;j>=0;j--) {
                int numLeft = arr[j];
                if (big % numLeft != 0) {
                    continue;
                }
                int numRight = big / numLeft;
                if (!map.containsKey(numRight)) {
                    continue;
                }
                long count1 = map.get(numLeft);
                long count2 = map.get(numRight);
                count += count1 * count2;
                count %= mod;
            }
            map.put(big, count);
            res += count;
            res %= mod;
        }
        return (int)res;
    }
}

第三题 简单链表+哈希题#

1836. 从未排序的链表中移除重复元素 - 力扣（LeetCode）

1661612941375

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicatesUnsorted(ListNode head) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode node = head;
        Map<Integer, Integer> map = new HashMap<>(); 
        while(node != null) {
            map.put(node.val, map.getOrDefault(node.val, 0) + 1);
            node = node.next;
        }
        ListNode lastNode = newHead;
        node = head;
        while(node != null) {
            if (map.get(node.val) > 1) {
                lastNode.next = node.next;
                node = node.next;
            } else {
                lastNode = node;
                node = node.next;
            }
        }
        return newHead.next;
    }
}