破晓的知识屋
0%

2022年9月

发表于 更新于 分类于 ， ， 阅读次数： Valine：
本文字数： 17k 阅读时长 ≈ 16 分钟

[toc]

2022-09-27#

https://leetcode.cn/problems/c32eOV/

找循环链表入口，步骤如下：

  1. 先是1个快节点，1个慢节点，然后两个能相碰那就说明有环。
  2. 然后慢节点再走一遍，和快节点重新相遇，能计算出环的长度
  3. 然后再从头部开始，一个节点先走环的长度步， 然后两个节点一起开始走，相遇后就是入口了

2022-09-25#

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

凡是问你找到缺的数字， 都要考虑是否用位运算

1~n中找到缺失的数字， 则你可以在造一个真正的1~n，然后异或起来即可

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[] missingTwo(int[] nums) {
        int sum = 0;
        for (int i = 0;i<nums.length;i++) {
            sum ^= nums[i];
        }
        int n = nums.length + 2;
        for (int i =1;i<=n;i++) {
            sum ^= i;
        }
        int bits = (~(sum-1)) & (sum);
        int num1 = 0;
        int num2 = 0;
        for (int num : nums) {
            if ((num & bits) > 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        for (int i = 1;i<=n;i++) {
            if ((i&bits) > 0) {
                num1 ^= i;
            } else {
                num2 ^= i;
            }
        }
        return new int[]{num1, num2};
    }
}

2022-09-24#

508. 出现次数最多的子树元素和 - 力扣（LeetCode）

搜索后用哈希表存储即可。

List快速转int[]的方法：

1
res.stream().mapToInt(Integer::intValue).toArray();

1130. 叶值的最小代价生成树 - 力扣（LeetCode）

一开始想着贪心，结果不行，并不能最前面选的是最优，那后面都是最优，即不能从上往下。

实际上要从下往上， 用动态规划存储，很容易就能处理了。

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<Integer, Integer> caches = new HashMap<>();

    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[][] maxs = new int[n][n];
        for (int i = 0; i < n;i++) {
            maxs[i][i] = arr[i];
        }
        
        for (int len = 2; len <= n;len++) {
            for (int i = 0; i+len - 1 < n;i++) {
                int minSum = Integer.MAX_VALUE;
                int j = i + len - 1;
                for (int k = i;k < j;k++) {
                    int mul = maxs[i][k] * maxs[k+1][j];
                    minSum = Math.min(minSum, mul + dp[i][k] + dp[k+1][j]);
                }
                dp[i][j] = minSum;
                for (int k = i;k<=j;k++) {
                    maxs[i][j] = Math.max(maxs[i][j], arr[k]);
                }
            }
        }
        return dp[0][n-1];
    }
}

1652. 拆炸弹 - 力扣（LeetCode）

题目数据量很小，直接暴力即可，如果数据量大了，可以改成使用滑动窗口。

2022-09-23 链·表题做懵逼，注意复用方法#

707. 设计链表 - 力扣（LeetCode）

这么简单的链表题为啥写了一个小时

因为数量级很小，不用维护复杂度，因此不用考虑设计一个尾节点，这会增加维护成本。

直接先写一个基础的getNode(index)方法，其他所有方法都基于这个来。

怎么避免写错或者写漏指针？

画一个图， 确认一下这次动作会有2根线变化，还是会有4根线变化，确认变化数量，从而避免遗漏。

注意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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class MyLinkedList {
    
    static class Node {
        Node pre;
        Node next;
        int val;
        public Node(int val) {
            this.val = val;
        }
    }

    Node head = new Node(0);
    int count = 0;
    public MyLinkedList() {

    }
    
    public int get(int index) {
        Node node = getNode(index);
        return node != null ? node.val : -1;
    }

    public Node getNode(int index) {
        if (index < 0) {
            return head;
        }
        Node node = head.next;
        while(node != null && index>0) {
            node = node.next;
            index--;
        }
        return node;
    }
    
    public void addAtHead(int val) {
        Node node = new Node(val);
        if (head.next != null) {
            head.next.pre = node;
        }
        node.next = head.next;
        head.next = node;
        node.pre = head;
        count++;
    }
    
    public void addAtTail(int val) {
        Node node = new Node(val);

        Node tail = getNode(count-1);
        
        tail.next = node;
        node.pre = tail;
        count++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > count) {
            return;
        }
        Node node = getNode(index-1);
        Node newNode = new Node(val);
        Node next = node.next;

        node.next =newNode;
        newNode.pre = node;
        newNode.next = next;
        if (next != null) {
            next.pre = newNode;
        }

        count--;
    }
    
    public void deleteAtIndex(int index) {
        Node node = getNode(index);
        if (node == null || head == node) {
            return;
        }
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        if (next != null) {
            next.pre = pre;
        }
        count--;
    }
}

改进版L:

实际上addIndex就可以替代Head和tail了，避免反复写

1
2
3
4
5
6
7
8
9

public void addAtHead(int val) {
    addAtIndex(0, val);
}

public void addAtTail(int val) {
    addAtIndex(size, val);
}

2022-09-20#

划分组可以用DP而不是DFS#

698. 划分为k个相等的子集 - 力扣（LeetCode）

先是最基础的DFS搜索，记忆化（因为只有16位很明显要状态压缩记忆化）

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
58
59
60
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        if (sum %k != 0) {
            return false;
        }
        int subSum = sum/k;
        dfs(nums, k, 0, subSum, 0, new boolean[nums.length]);
        return res;
    }
    boolean res = false;
    Set<Integer> set = new HashSet<>(); 
    void dfs(int[] nums, int k, int count, int needSum, int nowSum, boolean[] vis) {
        if (res) {
            return;
        }

        int key = 0;
       for (int i = 0; i  < vis.length;i++) {
            if (vis[i]) {
                key += (1<<i);
            }
       }
        if (set.contains(key)) {
            return;
        }

        if (count == k) {
            int useCount = 0;
            for (int i = 0; i  < vis.length;i++) {
                if (vis[i]) {
                    useCount++;
                }
            }
            if (useCount == nums.length) {
                res = true;
            }
            set.add(key);
            return;
        }
        for (int i = 0; i < nums.length;i++) {
            if (vis[i]) {
                continue;
            }
            int nextSum = nowSum + nums[i];
            if (nextSum > needSum) {
                continue;
            }
            vis[i] = true;
            if (needSum == nextSum) {
                dfs(nums, k, count+1, needSum, 0, vis);
            } else {
                dfs(nums, k, count, needSum, nextSum, vis);
            }
            vis[i] = false;
        }
        set.add(key);
    }
}

其实可以用动态规划， 脑子里对这种优先想到的是 明确一个值例如1101， 去掉某个1找到他的前置状态然后判断

这种坏处在于必须按1的个数先遍历， 比较麻烦

可以从0， 找到任意一个1，尝试放入，并修改下一次的状态， 后面遇到对应状态已经设置过了就不处理了， 类似于上卖弄过程的反向的Dp。 前提你要确认Dp的状态是不会被变更的，这里的Dp和dpSum在位一致的情况下是不会更新的。

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
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum %k != 0) {
            return false;
        }
        int subSum = sum/k;
        Arrays.sort(nums);
        int n = nums.length;
        boolean[] dpFlag = new boolean[1<<n];
        int[] dpSum = new int[1<<n];
        dpFlag[0] = true;
        // 从下往上压缩扩散压缩
        for (int i = 0; i < 1<<n;i++) {
            if (!dpFlag[i]) {
                continue;
            }
            for (int j = 0; j < n;j++) {
                // 放到一组内大于目标值，肯定不符合要求
                if (dpSum[i] + nums[j] > subSum) {
                    break;
                }
                // 
                if ((i &(1<<j)) > 0) {
                    continue;
                }
                int nextIndex = i | (1<<j);
                if (dpFlag[nextIndex]) {
                    continue;
                }
                // 取余是因为如果正好满足一组，就可以直接清0了
                dpSum[nextIndex] = (dpSum[i] + nums[j])%subSum; 
                dpFlag[nextIndex] = true;
            }
        }

        // n位全是1， 是(1<<n) - 1, 注意不是1<<n-1
        return dpFlag[(1<<n)-1];
    }

}

2022-09-16#

第一题： 多个连续区间长度、面积问题——扫描线#

多个连续区间，叠加部分要去掉或者叠加某个价值，这种题常见于那种任务流

区间的坐标很大导致无法遍历坐标值， 但可以遍历起点和终点坐标。

如果是求多个连续区间叠加后的横向长度（去除覆盖部分） ，就是最基础的扫描线应用

每次碰到关键点， 就将当前宽度（只能是0或者1）乘上（当前位置减去上一个位置）

然后直接更新上一个位置

并修改宽度（你只要考虑当前线段数量是否为0还是1）

求叠加线段长度的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public long getYLen(List<int[]> yList) {
    Collections.sort(yList, (a,b)->(a[0] - b[0]));
    int last = -1;
    int count = 0;
    long sum = 0;
    for (int[] yp : yList) {
        int y = yp[0];
        boolean isStart = yp[2] == 0;
        // 当前线段数量大于等于1，宽度就为1
        sum += (count>=1?1:0) * (y - last);
        
        // 根据是起点还是终点更新线段数量
        if (isStart) {
            count++;
        } else {
            count--;
        }
        last = y;
    }
    sum %= MOD;
    return (int)sum;
}

而这题求的是面积

因此是二维的扫描线应用，即用到了两个方向上的扫描线

先是按x作为扫描点，从左往右遍历

每次遇到起点或者终点时， 先尝试计算 当前宽度 * （当前点-上一个点）

当前宽度则根据上面的y轴叠加线段的计算方式计算

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
public int rectangleArea(int[][] rectangles) {
    List<int[]> xlist = new ArrayList<>();
    for (int i = 0; i < rectangles.length;i++) {
        int[] rect = rectangles[i];
        int xLeft = rect[0];
        int xRight = rect[2];
        xlist.add(new int[]{xLeft, i, 0});
        xlist.add(new  int[]{xRight, i, 1});
    }
    Collections.sort(xlist, (a,b)->(a[0] - b[0]));

    List<int[]> ylist = new ArrayList<>();
    int lastX = 0;
    long res = 0;
    for (int[] xp : xlist) {
        int x = xp[0];
        int i = xp[1];
        boolean isLeft = xp[2] == 0;
        int[] rect = rectangles[i];
        int yDown = rect[1];
        int yUp = rect[3];
        if (isLeft) {
            // 把之前那段面积先加起来
            long ylen = getYLen(ylist);
            long sum = ylen * (x - lastX);
            sum %= MOD;
            res += sum;
            res %= MOD;
            // 接着加入这段新的y区间
            ylist.add(new int[]{yUp, i, 1});
            ylist.add(new int[]{yDown, i, 0});
            lastX = x;
        } else {
            // 右点
            // 先计算之前的面积
            long ylen = getYLen(ylist);
            long sum = ylen * (x - lastX);
            sum %= MOD;
            res += sum;
            res %= MOD;
            // 删除这段y区间
            // 删除的时候要注意用迭代器
            Iterator<int[]> it = ylist.iterator();
            while (it.hasNext()) {
                if (it.next()[1] == i) {
                    it.remove();
                }
            }
            lastX = x;
        }
    }

    return (int)res;
}

2022-09-15#

672. 灯泡开关 Ⅱ - 力扣（LeetCode）

这题最佳题解是找规律，逐步定位到只需要判断前面4个灯泡即可。

但是这个找规律其实并不好找，不符合计算机思维。实际上可以不用得到只判断4个灯泡这个条件。而是知道以下几点即可：

  1. 每个开关只有开奇数次才算生效。 因此要么0要么1，4个开关可以理解成4位二进制
  2. 当二进制中1的个数小于等于按压次数时，只要取余相同，则一定可以得到这种情况

那么基于这个，就可以直接模拟计算出16种按压情况下，n位灯泡的总数（用hashset）不用找那个规律。

注意编号是从1到n的

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
class Solution {
    public int flipLights(int n, int presses) {
        Set<String> sets = new HashSet<>();
        for (int i = 0; i < 16;i++) {
           int[] arr = new int[n];

           int[] bits = new int[4];
           int sum = 0;
           for (int j = 0; j < 4;j++) {
               bits[j] = (i>>j)&1;
                sum += bits[j];
            }
           if (sum <= presses && sum %2 == presses %2) {              
                StringBuilder sb= new StringBuilder();
                for (int j = 0; j < arr.length;j++) {
                    if (bits[0] == 1) {
                        arr[j] = arr[j] ^ 1;
                    }
                    if (bits[1] ==1 && j %2 == 0) {
                        arr[j] = arr[j] ^ 1;
                    }
                    if (bits[2] ==1 && j %2 == 1) {
                        arr[j] = arr[j] ^ 1;
                    }
                    if (bits[3] ==1 && j %3 == 0) {
                        arr[j] = arr[j] ^ 1;
                    }
                    sb.append(arr[j]);
                }
                sets.add(sb.toString());
           }
        }
        System.out.println(sets);
        return sets.size();
    }
}

2022-09-14#

第一题：前缀和+哈希或者前缀和+单调栈#

1124. 表现良好的最长时间段 - 力扣（LeetCode）

又是涉及sum[i]、sun[j]然后求j-i最大的题目

然后果不其然想歪了怎么也写错了

最后要么用哈希记录最左端位置，因为是逐个按1或者-1增加前缀和的，那么当你是-5的时候，前面如果有-6，则一定是最前面的-6， 如果没有-6说明不行。 如果你是5的前缀和，那默认当前位置最长了。

要么是单调栈，但是是特殊的单调栈，不会出栈，只是构造递减的栈，然后反向遍历，这个根本想不到。

这题实际上偏难了不算中等题。

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
class Solution {
    public int longestWPI(int[] hours) {
        int[] pre = new int[hours.length];
        int sum = 0;
        for (int i = 0; i < hours.length;i++) {
            if (hours[i] > 8) {
                sum++; 
            } else {
                sum--;
            }
            pre[i] = sum;
        }
        Map<Integer, Integer> sumToIndexMap = new HashMap<>();
        int res = 0;       
        for (int i = 0; i < hours.length;i++) {
            if (pre[i] > 0) {
                res = Math.max(res, i + 1);
            } else {
                int needPre = pre[i] - 1;
                if (sumToIndexMap.containsKey(needPre)) {
                    int lastIndex = sumToIndexMap.get(needPre);
                    res = Math.max(res, i - lastIndex);
                }
                if (!sumToIndexMap.containsKey(pre[i])) {
                    sumToIndexMap.put(pre[i], i);
                }
            }
        }
        return res;
    }
}

第二题： 注意java中|也是特殊正则符号，需要转移#

2315. 统计星号 - 力扣（LeetCode）

关键地方：

1
String[] ss = s.split("\\|");

注意|的写法

第三题#

1619. 删除某些元素后的数组均值 - 力扣（LeetCode）

2022-09-11#

857. 雇佣 K 名工人的最低成本 - 力扣（LeetCode）

这题想不到的是要按工资比例做排序

最低工资/价值 来从小到大排序

从左到右遍历，选中一个那个就是作为最低工资标准，则前面任意都直接拿价值乘这个工资标准比率即可

而又可以根据k个的quality和可以直接乘……&这个还是蛮难想到的， 但是想懂后其实就是k个最大堆的应用

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
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        Integer[] indexs = new Integer[quality.length];
        int n = quality.length;
        for (int i = 0; i < quality.length;i++) {
            indexs[i] = i;
        }

        Arrays.sort(indexs, (a,b)->(((double)wage[a]/quality[a] - (double)wage[b]/quality[b] > 0 ? 1 : -1)));
        Queue<Integer> minKQueue = new PriorityQueue<>((a,b)->(b-a));
        long sum = 0;
        double res = Double.MAX_VALUE;
        for (int i = 0; i < n;i++) {
            int index = indexs[i];
            int qua = quality[index];
            int wag = wage[index];
            double rate = (double)wag/qua;
            if (minKQueue.size() < k) {
                minKQueue.offer(qua);
                sum += qua;
            } else if (minKQueue.size() == k && qua < minKQueue.peek()) {
                sum -= minKQueue.poll();
                minKQueue.offer(qua);
                sum += qua;
            }

            if (minKQueue.size() == k) {
                res = Math.min(res, sum * rate);
            }
        }
        return res;
    }
}

2022-09-08#

667. 优美的排列 II - 力扣（LeetCode）

规律题，还好没纠结

1662652885074

对于1~n的数字， 想要满足有n-1个前后差值不同，必须满足

[1, n, 2 , n-1, 3, n-2] 这样最小和最大值交叉出现

而如果是相同，则就是按顺序出现

那么想要任意k个差值不同，那就前面先都按顺序， 后面再交叉出现即可

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[] constructArray(int n, int k) {
        int[] res = new int[n];
        int index = 0;
        for(int i = 1; i <n-k;i++) {
            res[index++] = i;
        }
        int left = n-k;
        int right = n;
        while(left <=right) {
            if (index < n) {
                res[index++] = left;
            }
            if (index < n) {
                res[index++] = right;
            }
            left++;
            right--;
        }
        return res;
    }
}

2022-09-07#

第一题： 如果计算3个点是否一个直线#

1037. 有效的回旋镖 - 力扣（LeetCode）

y1 - y2 / (x1-x2) = (y1-y3) / (x1-x3)

即以(x1,y1)为出发点，确定和另外两个点是否都是同一个斜率

为了防止x1-x2为0的情况，转化为相乘的形式即可

第二题：修改跟节点#

1666. 改变二叉树的根节点 - 力扣（LeetCode）

1662563625565

其实就是按照她这个规则修改，而且就是从叶子到root修改

那就是每次要把儿子节点带上来，而且要注意修改父节点的指向，很麻烦

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node flipBinaryTree(Node root, Node node) {
        dfs(root, node, null);
        return node;    
    }

    public void dfs(Node root, Node node, Node son) {
        if (node == null) {
            return ;
        }
        if (node.left == son) {
            node.left = null; 
        } else {
            node.right = null;
        }
        if (node == root) {
            node.parent = son;
            return ;
        }
        Node left = node.left;
        Node parent = node.parent;
        if (left != null) {
            node.right = left;
        }
        node.left = parent;
        dfs(root, parent, node);
         node.parent = son;
        return ;
    }
}

2022-09-06#

1404. 将二进制表示减到 1 的步骤数 - 力扣（LeetCode）

剑指 Offer II 002. 二进制加法 - 力扣（LeetCode）

都是模拟二进制加法，都是注意反过来计算，然后最后末尾补1好一点

剑指 Offer II 093. 最长斐波那契数列 - 力扣（LeetCode）

这个问题因为涉及a+b=c，前面有a和b两个数字才能决定c， 因此状态应该是a和b共同决定，因此dp要有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
public int lenLongestFibSubseq(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < arr.length;i++) {
        map.put(arr[i], i);
    }

    int[][] dp = new int[arr.length+1][arr.length+1];
    int res = 0;
    for (int i = 0; i < arr.length;i++) {
        int num = arr[i];
        for (int j = i-1;j>=0;j--) {
            int num2 = arr[j];
            int num3 = num - num2;
            if (!map.containsKey(num3) || num3 >=num2) {
                dp[j][i] =  2;
            } else {
                int index3 = map.get(num3);
                dp[j][i] = dp[index3][j] + 1;
            }
            res = Math.max(res, dp[j][i]);
        }
    }
    return res != 2 ? res : 0;
}

2022-09-05#

1974. 使用特殊打字机键入单词的最少时间 - 力扣（LeetCode）

1667. 修复表中的名字 - 力扣（LeetCode）

SQL中存在

1
CONCAT(UPPER(left(name, 1)), LOWER(RIGHT(name, length(name) - 1)))

这些函数， 可以把第一个大写，其他都小写

1741. 查找每个员工花费的总时间 - 力扣（LeetCode）

group by是可以针对2组key进行的

1
select event_day as day, emp_id, sum(out_time-in_time) as total_time from employees group by event_day,emp_id;

统计每个员工每天的工作总时间

2022-09-04 周赛#

2022-09-03：双周赛#

2022-09-02#

第一题： 递归简单题#

364. 加权嵌套序列和 II - 力扣（LeetCode）

题目比较难理解，类似于给了一个树， 注意maxDepth也就是树的最大深度的意思

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
class Solution {
        int maxDep = 0;
    public int depthSumInverse(List<NestedInteger> nestedList) {
                Map<Integer, Integer> counts = new HashMap<>();
        for (NestedInteger nest : nestedList) {
            dfs(nest, 1);
        }
        int sum = 0;
        for (NestedInteger nest : nestedList) {
            sum += dfs2(nest, 1, maxDep);
        }
        return sum;
    }

    public void dfs(NestedInteger nest, int dep) {
            maxDep = Math.max(maxDep, dep);
        if(nest.isInteger()) {
            return ;
        } else {
            List<NestedInteger> nexts = nest.getList();
            int maxDep = 0;
            for (NestedInteger next : nexts) {
                dfs(next, dep + 1);
            }
        }
    }

    public int dfs2(NestedInteger nest, int dep, int maxDep) {
        if(nest.isInteger()) {
            int num = nest.getInteger();
            return num * (maxDep - dep + 1);
        } else {
            List<NestedInteger> nexts = nest.getList();
            int sum = 0;
            for (NestedInteger next : nexts) {
                sum += dfs2(next, dep + 1, maxDep);
            }
            return sum;
        }
    }

}

第二题：对角线判断#

2319. 判断矩阵是否是一个 X 矩阵 - 力扣（LeetCode）

1662168968681

主要考察对 正方形对角线的处理, 确定y的情况下，这一行上符合对角线的点是(y, y)和(y, xlen - 1 - y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkXMatrix(int[][] grid) {
    int ylen = grid.length;
    int xlen = grid[0].length;
    for (int y = 0; y < ylen;y++) {
        int x1 = y;
        int x2 = xlen - 1 - y;
        if (grid[y][x1] == 0 || grid[y][x2] == 0) {
            return false;
        }
        for (int x = 0; x < xlen;x++) {
            if (x == x1 || x == x2) {
                continue;
            }
            if (grid[y][x] != 0) {
                return false;
            }
        }
    }
    return true;
}

第三题：加法树只要元素都一致那就是相等#

1612. 检查两棵二叉表达式树是否等价 - 力扣（LeetCode）

1662169121771

其实无论什么顺序， 因为只有加法，都是一样的，只要元素（叶子节点）完全一致即可,也可以用map判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkEquivalence(Node root1, Node root2) {
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();
    get(root1, list1);
    get(root2, list2);
    Collections.sort(list1);
    Collections.sort(list2);
    return list1.equals(list2);
}

public void get(Node node, List<Integer> list) {
    if (node == null) {
        return ;
    }
    if (node.val != '+') {
        list.add((int)node.val);
    }
     get(node.left, list);
     get(node.right, list) ;
}

2022-09-01#

第一题：简单二叉树递归#

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

没啥好说的直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean evaluateTree(TreeNode root) {
        int val = root.val;
        if (val == 1) {
            return true;
        } else if (val == 0) {
            return false;
        } else if (val == 2){
            return evaluateTree(root.left) || evaluateTree(root.right);
        } else  {
           return evaluateTree(root.left) && evaluateTree(root.right);
        }
    }
}

第二题：简单回文判断#

2330. 有效的回文 IV - 力扣（LeetCode）

没看懂这题的意义是啥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean makePalindrome(String s) {
        int left = 0, right = s.length()-1;
        int count = 0;
        while(left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                count++;
            }
            left++;
            right--;
        }
        return count <= 2;
    }
}

第三题：贪心间隔摆放字符要求最长#

1662049690107

这种给几种字母让你排列， 一般都是要间隔放，而且每次都是优先放大的那2个。

这题我就是每次选2个当前最大的，然后放进去。 当都放完，看下有剩余的（且肯定是单个），再找到那个字母数量都+1， 再有剩余就不处理了。和答案思路基本一致

1662049857921

这题里面我用了int[]来表示， 答案定义了Pair类，以后可以参考下

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
class Solution {
   public String longestDiverseString(int a, int b, int c) {
        List<int[]> list = new ArrayList<>();
        int[][] arr = new int[][]{{'a', a},{'b', b},{'c',c}};

        while(arr[0][1] > 0 || arr[1][1] > 0 || arr[2][1] > 0) {
            // 如何得到3个的排序？
            // 每次选前2个放进来
            Arrays.sort(arr, (x,y)->(y[1] - x[1]));
            if (arr[1][1] != 0) {
                list.add(new int[]{arr[0][0], 1});
                arr[0][1]--;
                list.add(new int[]{arr[1][0], 1});
                arr[1][1]--;
            } else {
                list.add(new int[]{arr[0][0], 1});
                arr[0][1]--;
                for (int i = 0; i < list.size() && arr[0][1] > 0;i++) {
                    int[] ar = list.get(i);
                    if (ar[0] == arr[0][0]) {
                        ar[1]++;
                        arr[0][1]--;
                    }
                }
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int[] ar : list) {
            sb.append((char)ar[0]);
            if (ar[1] ==2) {
                sb.append((char)ar[0]);
            }
        }
        return sb.toString();
    }
}