每日一题

  1. 所有题目来源为力扣
  2. 题解为原创，仅为个人当前阶段能想到/能接受的解法，不一定是优解

  3. 🟢简单 🟠中等 🔴困难 ⚪未完成 ⚫未更新

  4. 有回顾价值题集：

  5. 其它题解：我的 LeetCode 题解

🟢 2021.11.01 (237. 删除链表中的节点)

题目

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

img

1
2
3
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

1
2
输入：head = [0,1], node = 0
输出：[1]

提示：

  • 链表中节点的数目范围是 [2, 1000]
  • -1000 <= Node.val <= 1000
  • 链表中每个节点的值都是唯一的
  • 需要删除的节点 node 是 链表中的一个有效节点 ，且 不是末尾节点

题解

额。这实在没什么可写的。因为要删除的必不是末尾节点，那么直接将当前要删除的节点“顶替”成下一个节点就成了。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

ac

🟢 2021.10.31 (500. 键盘行)

题目

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

  • 第一行由字符 "qwertyuiop" 组成。
  • 第二行由字符 "asdfghjkl" 组成。
  • 第三行由字符 "zxcvbnm" 组成。

American keyboard

示例 1：

1
2
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]

提示：

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i] 由英文字母（小写和大写字母）组成

题解

本题显然逃不掉的就是遍历 words 中每一个单词的每一个字母在键盘各行的出现情况，也就是说搜索是高频操作， 据此不妨预打三张 HashMap，存储键盘对应三行存在的字母，然后在遍历 words 的过程中，对每一个 word 的验证就可以依次在三张 HashMap 中 $O(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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    static Set<Character> set1 = new HashSet<>();
    static Set<Character> set2 = new HashSet<>();
    static Set<Character> set3 = new HashSet<>();
    static{
        // 预打三张 HashMap，存储键盘对应三行存在的字母
        set1.add('q'); set1.add('w'); set1.add('e'); set1.add('r'); set1.add('t'); set1.add('y'); set1.add('u'); set1.add('i'); set1.add('o'); set1.add('p'); 
        set2.add('a'); set2.add('s'); set2.add('d'); set2.add('f'); set2.add('g'); set2.add('h'); set2.add('j'); set2.add('k'); set2.add('l'); 
        set3.add('z'); set3.add('x'); set3.add('c'); set3.add('v'); set3.add('b'); set3.add('n'); set3.add('m');
    }
    public String[] findWords(String[] words) {
        boolean legal = true;
        List<String> res = new ArrayList<>();
        for(int i = 0; i < words.length; i++){
            // 依次验证该单词的每一个字母是否全都在对应行存在
            legal = true;
            for(int j = 0; j < words[i].length(); j++){
                if(!set1.contains(Character.toLowerCase(words[i].charAt(j)))){
                    // 存在一个字母不在当前行存在，必然不满足全在当前行（第一行）的条件，直接 break 验证是否全在下一行
                    legal = false;
                    break;
                }
            }
            if(legal){
                // 全在当前行（第一行），加入结果集，验证下一个单词
                res.add(words[i]);
                continue;
            }
            // 逻辑同上，做第二、三行的验证
            legal = true;
            for(int j = 0; j < words[i].length(); j++){
                if(!set2.contains(Character.toLowerCase(words[i].charAt(j)))){
                    legal = false;
                    break;
                }
            }
            if(legal){
                res.add(words[i]);
                continue;
            }
            legal = true;
            for(int j = 0; j < words[i].length(); j++){
                if(!set3.contains(Character.toLowerCase(words[i].charAt(j)))){
                    legal = false;
                    break;
                }
            }
            if(legal){
                res.add(words[i]);
                continue;
            }
        }
        return res.toArray(new String[0]);
    }
}

ac

🟠 2021.10.30 (260. 只出现一次的数字 III)

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

提示：

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • 除两个只出现一次的整数外，nums 中的其他数字都出现两次

题解

首先不难直观地想到通过一次遍历统计 nums 中所有数字的出现次数，然后再选出出现次数为 1 的数字作为答案返回。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        int p = 0;
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for(int i = 0; i < nums.length; i++){
            if(map.get(nums[i]) == 1) res[p++] = nums[i];
        }
        return res;
    }
}

ac

不过这样使用了 $O(n)$ 的空间复杂度，不满足本题的进阶要求，即在时间复杂度为 $O(n)$ 的前提下只使用 $O(1)$ 的空间复杂度。

通过利用 其余所有元素均出现两次 这一条件，结合 x^y^y = x，即用同一个数字异或两次后原数值不变的运算特性可知，若将 nums 中的所有元素全部与 0 异或的话，最终的结果将只是那两个出现一次的数字的异或结果，而其余出现两次的数字在两次异或中被抵消了。借助 2 个目标数字的异或结果，可以得到的一个信息是：异或结果中为 1 的位置，即是目标数字之间的不同位。借助这一信息，选取其中任意一个不同位作为依据，就可以将这两个目标数字分开，使得分开后的最终异或结果即是两个目标数字分别与 0 异或的结果，也就得到了两个目标数字本身的值。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for (int i : nums) sum ^= i;
        int k = -1;
        for (int i = 31; i >= 0 && k == -1; i--) {
            if (((sum >> i) & 1) == 1) k = i;
        }
        int[] ans = new int[2];
        for (int i : nums) {
            if (((i >> k) & 1) == 1) ans[1] ^= i;
            else ans[0] ^= i;
        }
        return ans;
    }
}

ac

⚪ 2021.10.29 (335. 路径交叉)

🔴 未做

🟠 2021.10.28 (869. 重新排序得到 2 的幂)

题目

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例 1：

1
2
输入：10
输出：false

示例 2：

1
2
输入：16
输出：true

示例 3：

1
2
输入：24
输出：false

示例 4：

1
2
输入：46
输出：true

提示：

  1. 1 <= N <= 10^9

题解

由于指数爆炸现象的存在，不难想到在题目 1 <= N <= 10^9 的数据限制下，所有可能的 2 的幂的数量是很少的，又输入 n 能够随意排序，进而不需要考虑数字的顺序问题，其实是降低了难度的。

具体操作上，只需先提前准备好所有可能的 2 的幂，然后将这些 2 的幂的值作为文本，将每一位数字按固定的规则排好序（如从小到大排序）存放在一个待查列表 legalList 中。这样一来，对于输入的 n 只要也按这个规则排好序，排序后的结果若在 legalList 中存在，则说明这组数字能够按其在 legalList 创建时的“打乱”（排序）操作逆向复原得到一个 2 的幂，若不存在于 legalList 中，自然也就不存在复原出 2 的幂的排列操作。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    static List<String> legalList = new ArrayList<>();
    static{
        // 预载好所有可能的 2 的幂（一共也就 30 个）
        long temp = 1;
        for(int i = 1; temp <= 1e9; i++){
            char[] charArray = String.valueOf(temp).toCharArray();
            Arrays.sort(charArray);
            legalList.add(new String(charArray));
            temp = (long)Math.pow(2, i);
        }
    }
    public boolean reorderedPowerOf2(int n) {
        // 按 legalList 同样的规则排序，查表，存在则可被复原为 2 的幂
        char[] charArray = String.valueOf(n).toCharArray();
        Arrays.sort(charArray);
        return legalList.contains(new String(charArray));
    }
}

ac

🔴 2021.10.27 (301. 删除无效的括号)

题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

1
2
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

1
2
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

1
2
输入：s = ")("
输出：[""]

提示：

  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • s 中至多含 20 个括号

题解

因为每一个半括号都有可能被删除，因此首先考虑用回溯遍历解决本题。在每一个下标处，如果对应字符是括号，那么就可以选择保留，也可以选择不保留，直到字符串的最后一个字符扫描完毕，检查其是否构成一个有效的串，

如何检查其括号是否有效呢？非常简单，只需设置一个偏移变量 bias 记录左括号的盈余状态

  • 若扫描并加入了一个左括号，则 bias++
  • 若扫描并加入了一个右括号，则 bias--

那么显然在扫描的途中，一旦出现 bias < 0 则说明串已经出现非法状态，必然无效，不需要再往后扫描了，此时可以剪枝。而在整个串扫描完毕后，检查 bias 的值即可，若为 0 则说明没有左括号盈余，也就是有效，否则无效。

不过这样的遍历耗时还算非常严重的，经过分析思考不难发现仍有可剪枝的地方。由于题目要求删除最小数量的括号，这就给优化提供了一条思路，即在 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
class Solution {
    List<String> res;
    int minRemoved = Integer.MAX_VALUE;
    public List<String> removeInvalidParentheses(String s) {
        res = new ArrayList<>();
        minRemoved = Integer.MAX_VALUE;
        buildRes(s, 0, new StringBuilder(), 0, 0);
        int maxLength = -1;
        // 找到删除括号最小的串的长度
        for(int i = 0; i < res.size(); i++){
            if(res.get(i).length() > maxLength) maxLength = res.get(i).length();
        }
        // 只保留与删除括号最小串长度相同的串作为答案
        for(int i = 0; i < res.size(); i++){
            if(res.get(i).length() != maxLength) res.remove(res.get(i--));
        }
        return res;
    }
    public void buildRes(String s, int index, StringBuilder sb, int bias, int removed){
        // 当前删除的括号数若已经超过了已有的有效串所删除的括号数，则剪枝
        if(removed > minRemoved) return; 
        // 遍历到末尾，检查串是否有效、串是否已存在结果集中
        if(index == s.length()){
            if(bias == 0 && !res.contains(sb.toString())){ 
                res.add(0, sb.toString());
                // 更新构成有效串可删除的最小括号数
                if(removed < minRemoved) minRemoved = removed;
            }
            return;
        }
        char current = s.charAt(index);
        // 非括号元素不能删除，直接添加
        if(current != '(' && current != ')'){
            sb.append(current);
            buildRes(s, index + 1, sb, bias, removed);
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        // 若中途 bias<0 则说明必构成无效串，剪枝
        if(bias + (current == '(' ? 1 : -1) >= 0){
            // bias 合法，录用该括号字符
            sb.append(current);
            buildRes(s, index + 1, sb, bias + (current == '(' ? 1 : -1), removed);
            sb.deleteCharAt(sb.length() - 1);
        }
        // 不录用(删除)该字符
        buildRes(s, index + 1, sb, bias, removed + 1);
    }
}

ac

🟢 2021.10.26 (496. 下一个更大元素 I)

题目

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

1
2
3
4
5
6
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
    对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
    对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1

示例 2:

1
2
3
4
5
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

题解

首先最简单最直接的思路，就是遍历 nums1 中的元素，对于 nums1 中的元素，去 nums2 中从头遍历（因为 nums2 无序）寻找它的相应位置，在找到相应位置后，在其位置后方继续寻找到第一个比它大的元素，存放在结果数组中的相应位置即可。

可以注意到，nums1 和 nums2 的长度均小于 $10^3$ 数量级，因此通过 $O(n^2)$ 的暴搜算法时间也能控制在 $10^6$ 以内，故是够能顺利 AC 的。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++){
            // 预设没找到的结果为 -1
            int greater = -1;
            int j = 0;
            // 在 nums2 中定位 nums1[i]
            for(; j < nums2.length; j++) if(nums2[j] == nums1[i]) break;
            // 在对应位置之后，开始寻找第一个比 nums1[i] 大的值
            for(j++; j < nums2.length; j++){
                if(nums2[j] > nums1[i]){
                    greater = nums2[j];
                    break;
                }
            }
            res[i] = greater;
        }
        return res;
    }
}

ac

不过这样显然是比较低效率的做法，在 nums2 中寻找 nums1[i] 的过程中，其实中途遍历了很多其它元素，而这些被遍历过的元素在后面作为 nums1[i] 的时候，又要重头来找，导致时间复杂度来到平方级别。为了避免重复搜索，可以牺牲 $O(n)$ 的空间复杂度，预先建立 nums[2] 中值和下标的对应关系，这样就省去了对于 nums1 中的每个元素都要重新遍历 $nums2$ 的冗余搜索。

优化版完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>(); // <value, index>
        for(int i = 0; i < nums2.length; i++) map.put(nums2[i], i);
        // 直接定位到 nums2 中的对应位置 startIndex 开始搜索下一个比 nums1[i] 大的值
        for(int i = 0; i < nums1.length; i++){
            int greater = -1;
            // 若 nums2 中不存在对应值，则置 nums2.length 可跳过整轮循环避免冗余搜索
            int startIndex = map.getOrDefault(nums1[i], nums2.length);
            for(int j = startIndex; j < nums2.length; j++){
                if(nums2[j] > nums1[i]){
                    greater = nums2[j];
                    break;
                }
            }
            res[i] = greater;
        }
        return res;
    }
}

ac

🟠 2021.10.25 (240. 搜索二维矩阵 II)

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -10^9 <= target <= 10^9

题解

首先可以按照无序数组遍历，从左到右，从上到下的次序，但是相应的时间复杂度就为 $O(mn)$，为了充分利用 matrix 每行递增、每列递增的特性，不难发现只需以自右向左，自上向下的次序，就可以实现 $O(m+n)$ 的搜索。

在从左到右，从上到下的遍历情况下，若当前元素的值小于目标值，那么并不能够确定目标值就在当前列下，因为后一列的元素也可能小于目标值，也就是说按照检索可能列的方式，会出现多个可能列的情况，进而无法单向遍历，若该列没有找到目标值，就必然要回溯检查下一列，进而沦为了 $O(mn)$ 的情况。

但按照自右向左，自上向下的次序，若当前元素的值大于目标值，那么是可以绝对确定目标值一定不在当前列的，因此可以不回溯地将搜索列向左移动一列。同时，若当前元素值小于目标值，同样可以确定目标值一定不在当前行，因此可以不回溯地将搜索行向下移动一行，进而确保每一步检查移动都必然向着正确的方向在走，不存在回溯，做到 $O(m+n)$ 的时间复杂度。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0) return false;
        int n = matrix[0].length;
        int i = 0, j = n - 1;
        for(; i < m; i++){
            for(; j >= 0; j--){
                if(target == matrix[i][j]) return true;
                if(target > matrix[i][j]) break;
            }
        }
        return false;
    }
}

ac

⚪ 2021.10.24 (638. 大礼包)

🟠 未解决

🟢 2021.10.23 (492. 构造矩形)

题目

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

1
2
3
4
5
1. 你设计的矩形页面必须等于给定的目标面积。

2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。

3. 长度 L 和宽度 W 之间的差距应当尽可能小。

你需要按顺序输出你设计的页面的长度 L 和宽度 W。

示例：

1
2
3
4
输入: 4
输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。

说明:

  1. 给定的面积不大于 10,000,000 且为正整数。
  2. 你设计的页面的长度和宽度必须都是正整数。

题解

由要求1和2可知，矩形宽度最大不可能超过 $\sqrt{area}$，因此只需遍历区间 $[1,\;\lfloor\sqrt{area}\rfloor]$ 内可能的宽度，然后记录长宽差值最小的那一对长宽即可。所谓“可能的宽度，即宽度对应的长度也是整数，即使用面积对宽度求取的余数为零即可。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] constructRectangle(int area) {
        int maxW = (int)Math.pow(area, 0.5);
        int l = area, w = 1, minDelta = Integer.MAX_VALUE;
        for(int i = 1; i <= maxW; i++){
            // invalid width
            if(area % i != 0) continue;
            // valid width
            int tempL = area / i;
            if(tempL - i < minDelta) {
                // closer pair
                l = tempL;
                w = i;
                minDelta = l - w;
            }
        }
        return new int[]{l, w};
    }
}

ac

但是不难发现，只有尽可能大的宽度才能对应尽可能小的长宽差值，那么最小的长宽差值必然是由最大的有效宽度确定。据此将遍历的方向调换，这样找到的第一对有效长宽就是对应本题的答案了，虽然空间复杂度也是 $O(n)$，但求解效率却显然要远高于之前的代码。

调换遍历策略后的完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] constructRectangle(int area) {
        int maxW = (int)Math.pow(area, 0.5);
        int l = area, w = 1;
        for(w = maxW; w >= 0; w--){
            if(area % w != 0) continue;
            l = area / w;
            break;
        }
        return new int[]{l, w};
    }
}

ac

🟠 2021.10.22 (229. 求众数 II)

题目

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

1
2
输入：[3,2,3]
输出：[3]

示例 2：

1
2
输入：nums = [1]
输出：[1]

示例 3：

1
2
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示：

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

题解

借助 HashMap 统计所有数字的出现次数，若出现次数大于 $\frac{1}{3}$ 则加入结果 List 中即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int threshold = nums.length/3;
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int num : nums){
            int newCount = map.getOrDefault(num, 0) + 1;
            map.put(num, newCount);
            if(newCount>threshold && !list.contains(num)) list.add(num);
        }
        return list;
    }
}

ac

🟢 2021.10.21 (66. 加一)

题目

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

1
2
3
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

1
2
3
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

1
2
输入：digits = [0]
输出：[1]

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

题解

按照正常的加法思路，从低位加一，然后检查进位，若有进位就将低位置零，并检查高一位加一后是否溢出，以此类推。特别地，考虑到进位可能产生的整个数字位数增加的情况，将每位的处理结果先添加到 List 中，最后将 List 映射转换回整型数组返回，这样可以方便地在最高位产生进位时，容易地向数字最高位前增加一位新数字。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] plusOne(int[] digits) {
        List<Integer> list = new ArrayList<>();
        int c = 0;
        for(int i = digits.length - 1; i >= 0; i--){
            if(i == digits.length - 1) digits[i] -=- 1;
            digits[i] -=- c;
            c = 0;
            if(digits[i] > 9){
                digits[i] = 0;
                c = 1;
            }
            list.add(0, digits[i]);
        }
        if(c != 0) list.add(0, 1);
        // List<Integer> to int[]
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

ac

⚪ 2021.10.20 (453. 最小操作次数使数组元素相等)

🟢 未做

🟠 2021.10.19 (211. 添加与搜索单词)

题目

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

  • WordDictionary() 初始化词典对象
  • void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
  • bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

提示：

  • 1 <= word.length <= 500
  • addWord 中的 word 由小写英文字母组成
  • search 中的 word 由 ‘.’ 或小写英文字母组成
  • 最多调用 50000 次 addWord 和 search

题解

首先容易想到最直接的遍历方法，直接用一个 List 存储添加的 word，在搜索时，首先检查搜索 word 和当前遍历的 List 中的单词的长度，若两者长度不同，则必然不匹配，可以直接跳过。若两者长度相同，则开始逐字母比较两个单词是否相匹配，特别地，对于搜索的 word 中为 . 的位，认为其匹配。

不过这样做在提交后会超时。为了减少遍历的数据量，可以通过以 word 的长度为依据，使用多个 List 存储的办法来实现。如待搜索的的单词长度为 n，那么只需要遍历长度为 n 的单词的 List 即可，而不需要在添加过的所有单词中遍历，进而优化了时间开销。为了实现 List 的按长度分类，使用 HashMap<Integer, List<String>> 即可。

完整代码：

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
class WordDictionary {
    HashMap<Integer, List<String>> map;
    public WordDictionary() {
        map = new HashMap<>();
    }
    public void addWord(String word) {
        // 检查是否有该长度单词的 List，若没有则为该长度创建一个 List 并将该单词存入
        List<String> list = map.getOrDefault(word.length(), null);
        if(list == null){
            list = new ArrayList<String>();
            list.add(word);
            map.put(word.length(), list);
        } else {
            list.add(word);
        }
    }
    public boolean search(String word) {
        int length = word.length();
        // 检查是否有该长度单词的 List，若没有则不可能匹配
        List<String> list = map.getOrDefault(length, null);
        if(list == null) return false;
        // 若有该长度的 List，则遍历对应 List，对遍历到的单词进行逐字母比较
        for(int i = 0; i < list.size(); i++){
            boolean found = true;
            for(int j = 0; j < length; j++){
                if(word.charAt(j) == '.') continue;
                if(list.get(i).charAt(j) != word.charAt(j)){
                    found = false;
                    break;
                }
            }
            // 若有匹配就不必再往后寻找，直接返回匹配成功的结果
            if(found) return true;
        }
        // List 中所有单词没有匹配的，返回匹配失败的结果
        return false;
    }
}

ac

🟢 2021.10.18 (476. 数字的补数)

题目

给你一个 正 整数 num ，输出它的补数。补数是对该数的二进制表示取反。

示例 1：

1
2
3
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

提示：

题解

非常简单，很容易想到直接取反后会导致符号位的变化，由于题给 num 必是正数，因此取反后符号位必是 1，为了得到正确结果，只需在取反后将符号位置 0 即可。为了找到符号位的位置，显然可以构造一个高位 1，将高位 1 不断右移，从高位到低位找到所给 num 的最高位 1，那么其符号位就在对应最高位 1 的左移一位处。

完整代码：

1
2
3
4
5
6
7
class Solution {
    public int findComplement(int num) {
        int i = 1 << 30;
        while((num&i)==0) i>>=1;
        return ~num&((i<<1)-1);
    }
}

ac

⚪ 2021.10.17

🔴 事务繁忙，无空做

⚪ 2021.10.16

🔴 事务繁忙，无空做

🟠 2021.10.15 (38. 外观数列)

题目

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

  • countAndSay(1) = "1"
  • countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1
2
3
4
5
6
7
8
9
10
1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

img

示例 1：

1
2
3
输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

1
2
3
4
5
6
7
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

  • 1 <= n <= 30

题解

以字符串String res = "1" 为初始状态，按照题意以 res = countString(res) 规则递归地“读”出字符串即可。

完整代码：

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
class Solution {
    public String countAndSay(int n) {
        String res = "1";
        for(int i = 1; i < n; i++){
            res = countString(res);
        }
        return res;
    }
    public String countString(String s) {
        char hold = s.charAt(0);
        int count = 1;
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) != hold) {
                sb.append(String.valueOf(count));
                sb.append(hold);
                hold = s.charAt(i);
                count = 1;
            }
            else count++;
        }
        sb.append(String.valueOf(count));
        sb.append(hold);
        return sb.toString();
    }
}

ac

🟢 2021.10.14 (剑指 Offer II 069. 山峰数组的顶部)

题目

略

题解

从头开始按顺序找到第一个比后一个数大的数字下标，即是山峰位置。此办法需要遍历数组，故时间复杂度为 $O(n)$。

完整代码：

1
2
3
4
5
6
7
8
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for(int i = 0; i < arr.length-1; i++){
           if(arr[i] > arr[i+1]) return i;
        }
        return -1;
    }
}

ac

🟢 2021.10.13 (412. Fizz Buzz)

题目

写一个程序，输出从 1 到 n 数字的字符串表示。

\1. 如果 n 是3的倍数，输出“Fizz”；

\2. 如果 n 是5的倍数，输出“Buzz”；

\3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

题解

按要求写即可，完整代码：

1
2
3
4
5
6
7
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList<>();
        for(int i = 1; i <= n; i++) res.add((i%3==0&&i%5==0)?"FizzBuzz":((i%3==0)?"Fizz":((i%5==0)?"Buzz":String.valueOf(i))));
        return res;
    }
}

ac

🟠 2021.10.12 (29. 两数相除)

题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

1
2
3
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

1
2
3
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。除数不为 0。

题解

使用减法的定义，将被除数不断减去除数，看看够完整减去几次，除的商就是几。不过这题坑的地方是溢出的情况，如 $-2^{31}$ 作为除数，$-1$ 作为被除数，结果就溢出了，此外也存在计算中途的溢出情况，也都是 $-2^{31}$ 作为除数的时候的情况。

完整代码：

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 divide(int dividend, int divisor) {
        long l_dividend = dividend;
        long l_divisor = divisor;
        if(dividend == 0) return 0;
        boolean isNegtive = (dividend>0&&divisor<0)||(dividend<0&&divisor>0);
        l_dividend = Math.abs(l_dividend);
        l_divisor = Math.abs(l_divisor);
        if(l_divisor == 1){
            long _res = isNegtive?-l_dividend:l_dividend;
            return (_res < Integer.MIN_VALUE || _res > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)_res;
        }

        long remain = l_dividend;
        int res = 0;
        while(remain >= l_divisor){
            remain -= l_divisor;
            res++;
        }
        return isNegtive?-res:res;
    }
}

ac

🔴 2021.10.11 (273. 整数转换英文表示)

题目

将非负整数 num 转换为其对应的英文表示。

示例 1：

1
2
输入：num = 123
输出："One Hundred Twenty Three"

示例 2：

1
2
输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"

示例 3：

1
2
输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4：

1
2
输入：num = 1234567891
输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

提示：

  • 0 <= num <= 231 - 1

题解

没有任何技巧，就遍历各种位数各种情况各种表示摁写，憨憨一样写的跟坨啥似的，反正 AC 了。

完整代码：

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
class Solution {
    public String numberToWords(int num) {
        if(num == 0) return "Zero";
        String[] suffix = {"", "Thousand", "Million", "Billion"};
        String[] one = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        String[] ten = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        String[] other = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        String str = Integer.toString(num);
        StringBuilder resBuilder = new StringBuilder();
        // full 3 num
        for(int i = 0; i < str.length() / 3; i++){
            String cur = str.substring(str.length()-(i+1)*3, str.length()-3*i);
            if(Integer.parseInt(cur) == 0) continue;
            StringBuilder buffer = new StringBuilder();
            if(cur.charAt(0) != '0'){
                buffer.append(one[Integer.parseInt(String.valueOf(cur.charAt(0)))]);
                buffer.append(" ");
                buffer.append("Hundred");
                buffer.append(" ");
            }
            if(cur.charAt(1) != '0'){
                if(cur.charAt(1) == '1'){
                    buffer.append(ten[Integer.parseInt(String.valueOf(cur.charAt(2)))]);
                } else { buffer.append(other[Integer.parseInt(String.valueOf(cur.charAt(1)))]);
                }
            }
            if(cur.charAt(1) != '1'){
                if(cur.charAt(1) != '0' && cur.charAt(2) != '0') buffer.append(" ");
                buffer.append(one[Integer.parseInt(String.valueOf(cur.charAt(2)))]);
            }
            if(i > 0) buffer.append(" ");
            buffer.append(suffix[i]);
            if(i > 0) buffer.append(" ");
            resBuilder.insert(0, buffer.toString());
        }
        // unfull 3 num
        StringBuilder buffer = new StringBuilder();
        if(str.length() % 3 == 1){
            // 1 num unfull
            buffer.append(one[Integer.parseInt(String.valueOf(str.charAt(0)))]);
            buffer.append(" ");
            buffer.append(suffix[str.length()/3]);
        } else if(str.length() % 3 == 2){
            // 2 num unfull
            if(str.charAt(0) == '1'){
                buffer.append(ten[Integer.parseInt(String.valueOf(str.charAt(1)))]);
            } else {
                buffer.append(other[Integer.parseInt(String.valueOf(str.charAt(0)))]);
                //buffer.append(" ");
            }
            if(str.charAt(0) != '1'){
                if(str.charAt(0) != '0' && str.charAt(1) != '0') buffer.append(" ");
                buffer.append(one[Integer.parseInt(String.valueOf(str.charAt(1)))]);
            }
            buffer.append(" ");
            buffer.append(suffix[str.length()/3]);
        }
        if(str.length() % 3 != 0){
            buffer.append(" ");
            resBuilder.insert(0, buffer.toString());
        }
        return resBuilder.toString().replace("  ", " ").trim();
    }
}

ac

🟢 2021.10.10 (441. 排列硬币)

题目

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例 1：

img

1
2
3
输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

提示：

  • 1 <= n <= 2^31 - 1

题解

一元二次方程送分题。令

要使得 $k$ 的取值恰好为小于等于 $n$ 的整数，那么显然

完整代码：

1
2
3
4
5
class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.floor(Math.pow(1+8*(long)n,0.5)-1)/2);
    }
}

ac

在编码的时候遇到了一个小插曲，测试的时候有些用例会溢出输出 0，原因是输入数据的取值范围为 $1 \leq n \leq 2^{31} - 1$，而 $n$ 是整型的，因此 $8\times n$ 的上限是 $2^{33} - 8$，依旧作为整型存储的话自然可能会溢出，只需在乘以 $8$ 之前将 $n$ 转为 long 型，使得乘出来的结果也是 long 就行了。

⚪ 2021.10.09 (352. 将数据流变为多个不相交区间)

🔴 不会，也没看题解，没空

🟠 2021.10.08 (187. 重复的DNA序列)

题目

所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：

1
2
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

1
2
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

  • 0 <= s.length <= 105
  • s[i] 为 'A'、'C'、'G' 或 'T'

题解

从头开始遍历所有以 s[i] 为起点长度为 10 的子串 ss，对遍历过程中的所有字串，向后嵌套遍历是否存在以 s[i+j] 为起点长度为 10 与 ss 相同的字串，即为答案，加入答案 List 中，一通操作猛如虎，然后 TLE。

朴素 $O(n^2)$ 超时解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        for(int i = 0; i <= s.length() - 10; i++){
            String maybeRes = s.substring(i, i+10);
            if(res.indexOf(maybeRes) != -1) continue;
            // Check whether maybeRes is a result;
            for(int j = i + 1; j <= s.length() - 10; j++){
                if(maybeRes.equals(s.substring(j, j+10))){
                    res.add(maybeRes);
                    break;
                }
            }
        }
        return res;
    }
}

tle

如果这题用 JavaScript 做的话很容易想到对象映射的方式实现 $O(n)$，但无奈对 Java 实在不熟。。不知道在 Java 中怎么实现自己的想法，经过了解学习后知道了 Java 中有个存储键值对的 HashMap<> 泛型类，看来是可以用这个实现的。

经过尝试和调试，成功 AC 了，算是通过这题对 Java 类库有点收获了。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        HashMap<String, Integer> hashMap = new HashMap<>();
        for(int i = 0; i <= s.length() - 10; i++){
            String maybeRes = s.substring(i, i+10);
            int count = hashMap.getOrDefault(maybeRes, 0);
            if(count == 1) res.add(maybeRes);
            hashMap.put(maybeRes, count+1);
        }
        return res;
    }
}

ac

🟢 2021.10.07 (434. 字符串中的单词数)

题目

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

1
2
3
输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

题解

设置一个状态记录器 start，遍历字符串中的字符，当字符为非空格时，将状态 start 记录为 true，当字符为空格时，如果 start 为 true，则说明一个单词结束，将计数器自增，并把 start 置回 false，等待下一个单词。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int countSegments(String s) {
        boolean start= false;
        int res = 0;
        for(char c : s.toCharArray()){
            if(c == ' ' && start) res -=- 1;
            start = (c != ' ');
        }
        return res + (start ? 1 : 0);
    }
}

ac

🟢 2021.10.06 (414. 第三大的数)

题目

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

1
2
3
输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

1
2
3
输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

1
2
3
4
输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

题解

使用插入排序来维护一个长度为 3 的排序数组即可，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。因为研一上半学期的 Java 课程有一项考核点是用 Java 做 20 道 LC，所以之后也写写 Java 了，完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int thirdMax(int[] nums) {
        // The range of input data contain Integer.MIN_VALUE, so use long here
        long[] list = {Long.MIN_VALUE, Long.MIN_VALUE, Long.MIN_VALUE};
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < 3; j++){
                // Tick only once for same values
                if(nums[i] == list[j]) break;
                // Move smaller num backward for inserting list[j]
                if(nums[i] > list[j]) {
                    for(int k = 2; k > j; k--) list[k] = list[k-1];
                    list[j] = nums[i];
                    break;
                }
            }
        }
        // Check whether there is a third big num
        return (int)(list[2] == Long.MIN_VALUE ? list[0] : list[2]);
    }
}

ac

🟠 2021.10.05 (284. 窥探迭代器)

题目

请你设计一个迭代器，除了支持 hasNext 和 next 操作外，还支持 peek 操作。

实现 PeekingIterator 类：

  • PeekingIterator(int[] nums) 使用指定整数数组 nums 初始化迭代器。
  • int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
  • bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
  • int peek() 返回数组中的下一个元素，但 不 移动指针。

题解

没什么好写的，完整代码：

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
/**
 * // This is the Iterator's API interface.
 * // You should not implement it, or speculate about its implementation.
 * function Iterator() {
 *    @ return {number}
 *    this.next = function() { // return the next number of the iterator
 *       ...
 *    }; 
 *
 *    @return {boolean}
 *    this.hasNext = function() { // return true if it still has numbers
 *       ...
 *    };
 * };
 */

/**
 * @param {Iterator} iterator
 */
var PeekingIterator = function(iterator) {
    this.iterator = iterator;
    this.nextElem = this.iterator.next();
};

/**
 * @return {number}
 */
PeekingIterator.prototype.peek = function() {
    return this.nextElem;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.next = function() {
    const res = this.nextElem;
    this.nextElem = this.iterator.hasNext() ? this.iterator.next() : null;
    return res;
};

/**
 * @return {boolean}
 */
PeekingIterator.prototype.hasNext = function() {
    return this.nextElem != null;
};

ac

🟢 2021.10.04 (482. 密钥格式化)

题目

有一个密钥字符串 S ，只包含字母，数字以及 ‘-‘（破折号）。其中， N 个 ‘-‘ 将字符串分成了 N+1 组。

给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分组之间需要用 ‘-‘（破折号）隔开，并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

示例 1：

1
2
3
4
输入：S = "5F3Z-2e-9-w", K = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
     注意，两个额外的破折号需要删掉。

示例 2：

1
2
3
输入：S = "2-5g-3-J", K = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

提示:

  1. S 的长度可能很长，请按需分配大小。K 为正整数。
  2. S 只包含字母数字（a-z，A-Z，0-9）以及破折号’-‘
  3. S 非空

题解

显然，完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var licenseKeyFormatting = function(s, k) {
    s = s.split('-').join('').toUpperCase();
    var res = [], c = 0, rest = s.length % k;
    for(var i in s){
        res.push(s[i]);
        if(((c-rest)%k == k-1 || c == rest-1)&&c!=s.length-1) res.push('-');
        c++;
    }
    return res.join('').toUpperCase();
};

ac

🟠 2021.10.03 (166. 分数到小数)

题目

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 $10^4$ 。

示例 1：

1
2
输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

1
2
输入：numerator = 2, denominator = 1
输出："2"

示例 3：

1
2
输入：numerator = 2, denominator = 3
输出："0.(6)"

提示：

  • -2^31 <= numerator, denominator <= 2^31 - 1
  • denominator != 0

题解

按除法规则进行除，并记录历史余数，如果余数为 0，说明计算结束，如果余数已经出现过了，说明结果是无限循环小数，可以终止计算，且循环是从余数第一次产生位置的商的后一位开始（后一位是因为，余数是上一次商后的做差结果，是用来给下一次商的，故循环从下一次商开始）。

按照这个模型编码，完整代码：

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
/**
 * @param {number} numerator
 * @param {number} denominator
 * @return {string}
 */
var fractionToDecimal = function(numerator, denominator) {
    // abs x and y, otherwise Math.floor(x/y) may get an unexpected result
    var negtive = (numerator / denominator) < 0 ? true : false;
    var res = [], x = Math.abs(numerator), y = Math.abs(denominator), dev = 0, rem = 0, remHistory = [], point = false;
    while(true){
        dev = Math.floor(x / y);
        res.push(dev);
        rem = x - dev * y;
        if(rem == 0) break;
        if(!point) { res.push("."); point = true; }
        if(remHistory.indexOf(rem) == -1){
            remHistory.push(rem);
            x = rem * 10;
        } else break;
    }
    if(rem != 0){
        // handle xunhuan
        // next dev is for the position after the rem times 10, so +1, and +1 again for the dot.
        res.splice(remHistory.indexOf(rem) + 2, 0, "(");
        res.push(")");
    }
    if(negtive){
        res.splice(0, 0, "-");
    }
    return res.join('');
};

ac

🟢 2021.10.02 (405. 数字转换为十六进制数)

题目

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

  1. 十六进制中所有字母(a-f)都必须是小写。
  2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，六进制字符串中的第一个字符将不会是0字符。
  3. 给定的数确保在32位有符号整数范围内。
  4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

1
2
3
4
输入:
26
输出:
"1a"

示例 2：

1
2
3
4
输入:
-1
输出:
"ffffffff"

题解

常规的解法是，若数字为负数，那么加上 $2^{32}$ 的偏移量（转为补码），然后不断对 16 取余数，小于 10 的转换为 '0' ~ '9'，大于 10 的转换为 a ~ f 即可。

另外，更加简洁的解法是利用位运算，因为位运算在计算机底层会自动解释为补码运算，因此使用位运算就完全不用管负数补码的事了，直接每四位转十六进制就完事，同时这也是 LC 给的官解。完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} num
 * @return {string}
 */
var toHex = function(num) {
    if(num === 0) return "0";
    var hexList = [];
    // parse from high bits, ignore front zero by if(temp > 0 || hexList.length > 0)
    for(var i = 7; i >= 0; i--){
        var temp = num >> (i*4) & 0xf;
        if(temp > 0 || hexList.length > 0){
            var hex = temp < 10 ? String.fromCharCode('0'.charCodeAt() + temp)
                                : String.fromCharCode('a'.charCodeAt() + temp - 10);
            hexList.push(hex);
        }
    }
    return hexList.join('');
};

ac

不过，既然有这个机会，就重新复习以下机组原码反码补码二进制十六进制转换这些内容。我们首先将数字转成二进制原码，再将原码转为补码，然后对补码按每四位编码为十六进制数，最后切掉前导零，以字符串形式返回即可，就是写起来有点麻烦。

完整代码：

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
/**
 * @param {number} num
 * @return {string}
 */
const BIT2HEXLIST = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];

var toHex = function(num) {
    return dec2Hex(num);
};

/* @param {num} decimal number */
var dec2Hex = (num) => binary2Hex(complementCode(originalCode(num)));

/* @param {num} decimal number */
function originalCode(num){
    (res = []).length = 32, i = 0;
    res.fill(0);
    // record the symbol
    negtive = num < 0 ? -1 : undefined;
    num = Math.abs(num);
    // parse to binary code
    while(num!=0){
        res[i++] = num % 2;
        num = Math.floor(num/2);
    }
    if(negtive) res[31] = 1;
    return res.reverse();
}
/* @param {oriCode} bit array with length 32 */
function complementCode(oriCode){
    if(!oriCode) return;
    // complement code of positive number is original code itself
    if(oriCode[0] == 0) return oriCode;
    // get complement code by inverse bits before the last bit 1
    var res = [], startInverse = false;
    for(var i = oriCode.length - 1; i >= 0; i--){
        if(startInverse) res[i] = 1 - oriCode[i];
        else res[i] = oriCode[i];
        if(oriCode[i] == 1) startInverse = 1
    }
    // negtive number's symbol bit is 1
    res[0] = 1;
    return res;
}

/* @param {binCode} bit array with length 32 */
function binary2Hex(binCode){
    res = [];
    // parse to hex every 4 bits
    for(var i = 0; i < binCode.length; i+=4){
        res[i/4] = BIT2HEXLIST[binCode[i]*8 + binCode[i+1]*4 + binCode[i+2]*2 + binCode[i+3]];
    }
    // find the first bit that isn't zero
    var sliceIndex;
    for(var i in res) {
        if(res[i] != "0"){
            sliceIndex = i;
            break;
        }
    }
    // all 0
    if(!sliceIndex) return "0";
    // slice sliceIndex ~ res.length-1 to ignore front zeros
    res = res.slice(sliceIndex);
    // to string
    return res.join('');
}

ac

🟢 2021.10.01 (1436. 旅行终点站)

国庆快乐！🎉🎉🎉

题目

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

示例 1：

1
2
3
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

1
2
输入：paths = [["A","Z"]]
输出："Z"

提示：

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。

题解

首先是最直觉的递归，不断寻找下一站，最终找到终点站返回，递归版完整代码：

1
2
3
4
5
6
7
8
9
10
var destCity = function(paths) {
   return destStation(paths[0][0], paths);
};

function destStation(currentStation, paths){
    for(var pair of paths){
        if(pair[0] == currentStation) return destStation(pair[1], paths);
    }
    return currentStation;
}

ac

这样虽然能 AC，但是不够优雅，每次从头开始遍历 paths 导致 $O(n^2)$ 的时间复杂度，并且递归开栈也造成了 $O(n)$ 的空间复杂度。我们不妨首先遍历一次 paths，在遍历过程中将源地和目的地构造成一对键值对，这样就方便搜索了，虽然还是 $O(n)$ 的空间复杂度，但时间复杂度从 $O(n^2)$ 降到了 $O(n)$。

完整代码：

1
2
3
4
5
6
var destCity = function(paths) {
   var mem = [], res = paths[0][0];
   for(var pair of paths) mem[pair[0]] = pair[1];
   while(mem[res]) res = mem[res];
   return res;
};

ac

🟠 2021.09.30 (223. 矩形面积)

题目

给你 二维 平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

  • 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
  • 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：

rectangle-plane

1
2
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45

提示：

  • -104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104

    题解

首先计算两个矩形的面积之和

1
var all = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);

然后考虑重合部分，特别地，当一个矩形的右边在另一个矩形的左侧等情况时，两个矩形是没有重合部分的，即：

1
if(ax2 <= bx1 || ax1 >= bx2 || ay1 >= by2 || ay2 <= by1) return all;

对于重合部分，只需要找到重合矩形的左上角和右下角即可，该坐标不难计算，详见完整代码：

1
2
3
4
5
6
7
8
9
10
11
var computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
    var all = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
    if(ax2 <= bx1 || ax1 >= bx2 || ay1 >= by2 || ay2 <= by1) return all;
    // cal overlap area
    var cx1 = Math.max(ax1, bx1);
    var cx2 = Math.min(ax2, bx2);
    var cy1 = Math.max(ay1, by1);
    var cy2 = Math.min(ay2, by2);
    var overlap = (cx2 - cx1) * (cy2 - cy1);
    return all - overlap;
};

ac

🔴 2021.09.29 (517. 超级洗衣机)

题目

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

示例 1：

1
2
3
4
5
6
输入：machines = [1,0,5]
输出：3
解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2

示例 2：

1
2
3
4
5
输入：machines = [0,3,0]
输出：2
解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1

提示：

  • n == machines.length
  • 1 <= n <= 104
  • 0 <= machines[i] <= 105

题解

一天学完了 JS，接下来要两天速通 Vue 了，没空写题解辽。

$O(n^3)$ 暴力超时代码（困难题果然还是不能暴力的呢）：

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
/**
 * @param {number[]} machines
 * @return {number}
 */
var findMinMoves = function(machines) {
    var clothesCount = 0;
    machines.forEach(function(value) {clothesCount+=value;});
    if(clothesCount % machines.length != 0) return -1;
    // ------------------------------------------------------
    // find a min move way
    var avrCount = clothesCount / machines.length;
    var minMoves = 0;
    while(!isBanlance(machines, avrCount)){
        // check every machine's both side
        // if one side lack and self own clothes, then give clothes to the lacked side
        for(var i = 0; i < machines.length; i++){
            if(machines[i] > 0){
                var lack = isBothSideLack(i, machines, avrCount);
                if(lack[0] == 1) { machines[i]--; machines[i-1]++; }
                // can only give clothes to one of sides, so use else syntax
                else if(lack[1] == 1) { machines[i]--; machines[i+1]++; }
            }
        }
        minMoves++;
    }
    return minMoves;
};
function isBothSideLack(index, machines, avrCount){
    var leftBanlanceCount = index * avrCount;
    var rightBanlanceCount = (machines.length - index - 1) * avrCount;
    var leftCount = 0, rightCount = 0;
    var lack = [0, 0];
    for(var i = 0; i < index; i++) leftCount += machines[i];
    if(leftCount < leftBanlanceCount) lack[0] = 1;
    for(var i = index + 1; i < machines.length; i++) rightCount += machines[i];
    if(rightCount < rightBanlanceCount) lack[1] = 1;
    return lack;
}
function isBanlance(machines, avrCount){
    for(var value of machines){ if(value != avrCount) return false; }
    return true;
}

image-20210929115247903

$O(n)$ AC 完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} machines
 * @return {number}
 */
var findMinMoves = function(machines) {
    var clothesCount = 0;
    machines.forEach(function(value) {clothesCount+=value;});
    if(clothesCount % machines.length != 0) return -1;
    // ------------------------------------------------------
    // find a min move way
    var avrCount = clothesCount / machines.length;
    var lackList = [];
    var res = 0;
    // get delta list
    for(var i = 0; i < machines.length; i++){
        lackList[i] = machines[i] - avrCount;
    }
    for(var i = 0; i < machines.length - 1; i++){
        if((Math.abs(lackList[i]) > res)) res = Math.abs(lackList[i]);
        if(lackList[i+1] > res) res = lackList[i+1];
        lackList[i+1] += lackList[i];
    }
    return res;
};

ac

🟠 2021.09.28 (437. 路径总和 III)

题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

ac

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

题解

暴力解，双重遍历。遍历树的所有节点，并对每个节点遍历以该节点为 root 的树到所有节点的路径 val ，对于路径 val 为 targetSum 的情况，自增全局计数器 res。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var res = 0;
var pathSum = function(root, targetSum) {
    // 注意，必须在入口函数初始化全局变量，因为 LC 多个用例执行只会初始化一次全局变量，
    // 也就是后续的全局变量初始值就不是 0 了，就是这个原因导致同一个用例在执行代码时通过，
    // 但在提交时执行不通过的诡异现象，被 WA 了两次呜呜呜
    res = 0;
    dfsNodes(root, targetSum);
    return res;
};
// 遍历从每个节点起始的情况
function dfsNodes(root, targetSum){
    if(root == null) return;
    dfs(root, targetSum, 0);
    if(root.left != null) dfsNodes(root.left, targetSum);
    if(root.right != null) dfsNodes(root.right, targetSum);
};
// 遍历从dfsNodes传入节点到后续所有节点的累加和
function dfs(root, targetSum, lastSum) {
    if(root == null) return;
    var currentSum = lastSum + root.val;
    if(targetSum == currentSum) res++;
    if(root.left != null) dfs(root.left, targetSum, currentSum);
    if(root.right != null) dfs(root.right, targetSum, currentSum);
};

ac

⚪ 2021.09.27 (639. 解码方法 II)

🔴 速通 JavaScript 去了，未做

⚫ 2021.09.26 (371. 两整数之和)

🟠 未更新

🟠 2021.09.25 (583. 两个字符串的删除操作)

题目

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

1
2
3
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

  1. 给定单词的长度不超过500。
  2. 给定单词中的字符只含有小写字母。

题解

本题不难想到转化为求解最长公共子序列长度问题。

最长公共子序列，可以用动态规划来解。定义 dp[i, j] 表示word1 前 i 个字符和 word2 前 j 个字符的最长公共子序列长度。那么则有如下状态转移：

  • 若 word1[i] == word2[j] 则显然 dp[i, j] = dp[i-1, j-1] + 1，表示将当前比较的位加入到前一次的最长公共子序列长度中；
  • 若 word1[i] == word2[j] ，则继承两种上一状态中长度较长的那个长度作为最长长度，即 dp[i, j] = Max(dp[i-1, j], dp[i, j-1])。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length, n = word2.Length;
        int[,] dp = new int[m, n];
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(word1[i] == word2[j]) dp[i,j] = (i==0||j==0)?1:dp[i-1,j-1]+1;
                if(word1[i] != word2[j]) dp[i,j] = Math.Max(i>0?dp[i-1,j]:0, j>0?dp[i,j-1]:0);
            }
        }
        return m - dp[m-1,n-1] + n - dp[m-1,n-1];
    }
}

ac

🟠 2021.09.24 (430. 扁平化多级双向链表)

题目

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：

img

扁平化后的链表如下图：

img

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

1—-2—-NULL
|
3—-NULL

提示：

  • 节点数目不超过 1000
  • 1 <= Node.val <= 10^5

题解

朴素的办法，遍历，遇到有子节点的，就找到子节点那层的最后一个节点，然后捏住首位将整个子节点这层插上来。缺点是每个子层会被遍历两次（找子层尾节点遍历一次，并入住层后继续遍历就被重复遍历了），所以复杂度是 $O(n^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
25
26
27
public class Solution {
    public Node Flatten(Node head) {
        Node p = head;
        while(p != null)
        {
            // have child
            if(p.child != null)
            {
                // find the last node of the layer of child
                Node lastNodeOfChild = GetTheLastNode(p.child);
                // merge child layer
                if(p.next != null) p.next.prev = lastNodeOfChild;
                lastNodeOfChild.next = p.next;
                p.next = p.child;
                p.child.prev = p;
                p.child = null;
            }
            p = p.next;
        }
        return head;
    }
    public Node GetTheLastNode(Node node){
        Node p = node;
        while(p.next != null) p = p.next;
        return p;
    }
}

ac

但更好的办法是递归，这样可以做到 $O(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
public class Solution {
    public Node Flatten(Node head) {
        Merge(head);
        return head;
    }
    public Node Merge(Node head){
        Node p = head;
        while(p != null)
        {
            if(p.child != null)
            {
                Node lastNodeOfChild = Merge(p.child);
                // merge child layer
                if(p.next != null) p.next.prev = lastNodeOfChild;
                lastNodeOfChild.next = p.next;
                p.next = p.child;
                p.child.prev = p;
                p.child = null;
            }
            if(null == p.next) return p;
            p = p.next;
        }
        return p;
    }
}

ac

🟢 2021.09.23 (326. 3的幂)

题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

1
2
输入：n = 27
输出：true

示例 2：

1
2
输入：n = 0
输出：false

题解

直接递归之。完整代码：

1
2
3
4
5
6
7
public class Solution {
    public bool IsPowerOfThree(int n) {
        if(n <= 0) return false;
        if(1 == n) return true;
        return n%3!=0?false:IsPowerOfThree(n/3);
    }
}

ac

🟠 2021.09.22 (725. 分隔链表)

题目

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例 1：

img

1
2
3
4
5
输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：

img

1
2
3
4
输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

提示：

  • 链表中节点的数目在范围 [0, 1000]
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

题解

又是直觉题。显然计算 链表长度 / 分割数量 即是可被均分的每个 section 中的基础节点数量，而 链表长度 % 分割数量 即是均分后剩下来的节点数，由于要求 “任意两部分的长度差距不能超过 1”并且“排在前面的部分的长度应该大于或等于排在后面的长度”，因此将剩下的节点数往前面的 section 中加即可，每个 section 塞一个节点数。

如初始链表有 17 个节点，要均分成 k = 3 份（3 个 section），那么每个 section 就有 17 / 3 = 5 个基础节点个数，不过这样就会多出来 17 % 3 = 2 个节点，只要往前 2 个 section 中多放一个节点即可得到 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution {
    public ListNode[] SplitListToParts(ListNode head, int k) {
        // float pointer
        ListNode p = head;
        // result list
        ListNode[] res = new ListNode[k];
        // length of list
        int length = GetLengthOfLinkList(head);
        if(length < k)
        {
            for(int i = 0; i < length; i++)
            {
                res[i] = new ListNode(p.val, null);
                p = p.next;
            }
            return res;
        }
        else
        {
            int basicElementCountOfSection = length / k;
            int countOfSectionNeedExtra = length % k;
            // cut list to k sections
            for(int i = 0; i < k; i++)
            {
                // head of section
                ListNode sectionP = p;
                // end of section
                ListNode secitonE = sectionP;
                res[i] = sectionP;
                // section i need to contain length/k nodes firstly
                for(int j = 0; j < basicElementCountOfSection - 1; j++) secitonE = secitonE.next;
                // then contain 1 posible extra node to the front sections
                if(countOfSectionNeedExtra != 0) { secitonE = secitonE.next; countOfSectionNeedExtra--; }
                // swich p to next section head
                p = secitonE.next;
                // cut to get the section
                secitonE.next = null;
            }
        }
        return res;
    }
    public int GetLengthOfLinkList(ListNode head)
    {
        ListNode p = head;
        int length = 0;
        while(p != null)
        {
            length++;
            p = p.next;
        }
        return length;
    }
}

ac

🟢 2021.09.21 (58. 最后一个单词的长度)

题目

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

1
2
输入：s = "Hello World"
输出：5

示例 2：

1
2
输入：s = "   fly me   to   the moon  "
输出：4

提示：

  • 1 <= s.length <= 104
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

题解

中秋快乐！🎑

直接倒着找到最后一个单词的最后一个字母，然后触发一个 start 触发器开始记录长度，直至记录到最后一个单词前的第一个空格返回记录的长度即可。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int LengthOfLastWord(string s) {
        bool started = false;
        int res = 0;
        for(int i = s.Length - 1; i >= 0; i--)
        {
            if(s[i] != ' ') { started = true; res++; }
            else if(started) return res;
        }
        return res;
    }
}

当然，也可以直接用库函数一行代码解决：

1
2
3
public class Solution {
    public int LengthOfLastWord(string s) => s.Trim().Split(" ").Last().Length;
}

ac

🟠 2021.09.20 (673. 最长递增子序列的个数)

题目

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

1
2
3
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

1
2
3
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

题解

因为还没有学动态规划，因此最先想到的还是暴力遍历。定义函数 void FindNextNumber(int[] nums, int lastIndex, int currentIndex, int lastLength) 表示从上一数字找下一个可接的递增数字，其中对于 currentIndex 数大于 lastIndex 数的时候，表明可以接，将 lastLength +1 后继续往后找。

不过无论是否满足上面说的情况，都应该走一遍跳过当前数字的路径，确保不漏数。

如示例 1 的 [1,3,5,4,7]，其中 5 可以接在 3 后面，但也应尝试跳过 5，才能捕获到 [1,3,4,7] 这一同样是最长递增的子序列。

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
public class Solution {
    int maxLengh = 0;
    int maxCount = 0;
    public int FindNumberOfLIS(int[] nums) {
        for(int i = 0; i < nums.Length; i++)
        {
            // list start from nums[i]
            FindNextNumber(nums, i, i + 1, 1);
        }
        return maxCount;
    }
    public void FindNextNumber(int[] nums, int lastIndex, int currentIndex, int lastLength)
    {
        // scan to the end
        if(currentIndex == nums.Length)
        {
            // find a longer list
            if(lastLength > maxLengh)
            {
                maxLengh = lastLength;
                maxCount = 1;
            } else if(lastLength == maxLengh) maxCount++;
            return;
        }
        // skip current number no matter its bigger than the last number
        FindNextNumber(nums, lastIndex, currentIndex + 1, lastLength);
        if(nums[currentIndex] > nums[lastIndex])
            FindNextNumber(nums, currentIndex, currentIndex + 1, lastLength + 1);
        
    }
}

说了这么多，但这个暴力解法在序列合适的情况下是会超时的。。。

Update：

喵了一眼 LC 的题解，大概看懂了本题动态规划的思路。首先我们可以设置两个数组：

1
2
3
4
// f[i]: the max length end with nums[i]
int[] f = new int[nums.Length];
// g[i,k]: the count of lenth k end with nums[i]
int[,] g= new int[nums.Length, nums.Length + 1];

其中 f[i] 记录以 nums[i] 为结尾的上升子序列的最大长度，g[i, k] 记录以 nums[i] 为结尾的上升子序列长度为 k 的序列个数。

初始时，数组 f 的值应全为 1，表示可以独立构成长度为 1 的上升子序列，进而 g[:,1] 也全为 1。

设置指针 i 从头往尾扫描，指针 j 从头扫描至 i-1，判断 nums[i] 能否接在 nums[j] 的后面，构成一个上升子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0; i < nums.Length; i++)
{
    // self length is 1 and initialize max length with 1
    g[i,1] = f[i] = 1;
    for(int j = 0; j < i; j++)
    {
        if(nums[j] < nums[i])
        // nums[i] can be connected behind nums[j]
        {
            //...
        }
    }
}

若能构成上升子序列，那么说明以 nums[i] 结尾能够构成长度为 f[j] + 1 的递增子序列，并且构成的长度为 f[j] + 1 的子序列的个数是 nums[i] 同之前元素能构成长度为 f[j] + 1 的递增子序列的个数再加上被接上的 nums[j] 能构成长度为 f[j] 的子序列个数（如 1 3 5，5 能接在 3 后面，那么以 3 结尾能构成几个长度为 2 的序列，就也能以 5 结尾构成几个长度为 3 的序列）。同时，f[i] 应被更新为长度更长的 f[j] + 1，否则 f[i] 保持不变，确保存储的是能够构成的最长子序列长度。按照该逻辑，第 10 行处代码就为：

1
2
g[i, f[j] + 1] += g[j, f[j]];
f[i] = Math.Max(f[i], f[j] + 1);

当整个扫描结束后，f 中就存储了分别以各个元素为结尾能构成的递增子序列的最长长度，g 中就存储了以各个元素为结尾能构成长度为 1 ~ nums.Length 的上升子序列的个数。

显然，要返回最长递增子序列的个数，只需要先用 f 找到最长的长度 k，然后从 g 中累加所有的 g[:,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
public class Solution {
    public int FindNumberOfLIS(int[] nums) {
        // f[i]: the max length end with nums[i]
        int[] f = new int[nums.Length];
        // g[i,k]: the count of lenth k end with nums[i]
        int[,] g= new int[nums.Length, nums.Length + 1];
        for(int i = 0; i < nums.Length; i++)
        {
            // self length is 1 and initialize max length with 1
            g[i,1] = f[i] = 1;
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                // nums[i] can be connected behind nums[j]
                {
                    g[i, f[j] + 1] += g[j, f[j]];
                    f[i] = Math.Max(f[i], f[j] + 1);
                }
            }
        }
        // find the max length
        int maxLength = f.Max();
        // sum max length count
        int res = 0;
        for(int i = 0; i < nums.Length; i++)
        {
            res += g[i, maxLength];
        }
        return res;
    }
}

以原始序列 [1,3,5,4,7,4,8,9] 为例，运行结束后各变量的状态如下图所示，大体上，变量 g 从上至下，从左至右迭代，可供辅助手推理解。

ac

🟠 2021.09.19 (650. 只有两个键的键盘)

题目

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

  • Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
  • Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

示例 1：

1
2
3
4
5
6
7
输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。

示例 2：

1
2
输入：n = 1
输出：0

提示：

  • 1 <= n <= 1000

题解

首先第一直觉尝试了遍历操作，DFS配合剪枝，不过发现59及更大的奇数用例大部分超时了。

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
/* DFS + 剪枝（部分奇数用例超时） */
public class Solution {
    int minStep = 0;
    int target;
    public int MinSteps(int n) {
        if(1 == n) return minStep;
        target = n;
        Operate(1, 0, 0, 1);
        return minStep;
    }
    // op: 0. Copy, 1. Paste
    // step: current step, not last step
    public void Operate(int n, int op, int copied, int step)
    {
        if(minStep > 0 && step >= minStep) return; // cut
        if(0 == op)
        {
            // copy
            copied = n;
            if(copied >= target) return; // cut
            // next operate paste
            Operate(n, 1, copied, step+1);
            // or copy
            Operate(n, 0, copied, step+1);
        } else {
            // paste
            n += copied;
            if(n > target) return; // cut
            if(n == target)
            {
                if(minStep == 0 || step < minStep) 
                {
                    minStep = step;
                    return;
                }
            }
            // next operate paste
            Operate(n, 1, copied, step+1);
            // or copy
            Operate(n, 0, copied, step+1);
        }
    }
}

image-20210919110014978

用例 1000

image-20210919110109228

用例 59 超时

有可能是剪枝不到位，或者数据量太大，此法不可行？总之在这个方向上没做出来。后看了提示之后想到了分解因式完全可以解决此题。

How many characters may be there in the clipboard at the last step if n = 3? n = 7? n = 10? n = 24?

以提示中的 n = 24 为例，由于 2、4、6、8、12 都是 24 的因数，而要使得操作步数最少，必然粘贴的字符数应该尽可能多，那么显然当取 12 个字符粘贴时能够实现更少的复制粘贴次数。因此，只需要寻找 n 的最大因数，然后不断进一步寻找其最大因数的最大的因数，直至最大因数（1除外）是自身时，说明此数是从最开始的一个 A 连续复制得到的。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int MinSteps(int n) {
        if(1 == n) return 0;
        int step = 0, rest = n;
        while(true)
        {
            int from = FindMaxFactor(rest);
            if(from != rest)
            {
                // current rest is generated from pasting `from` (rest/from) times
                step += rest/from;
                rest = from;
            } else break;
        }
        return step += rest;
    }
    public int FindMaxFactor(int n){
        // ignore the case i == 1 and return n can make the code in MinSteps neater
        for(int i = n-1; i > 1; i--) if(n%i==0) return i;
        return n;
    }
}

image-20210919113907617

🟢 2021.09.18 (292. Nim 游戏)

题目

你和你的朋友，两个人一起玩 Nim 游戏：

  • 桌子上有一堆石头。
  • 你们轮流进行自己的回合，你作为先手。
  • 每一回合，轮到的人拿掉 1 - 3 块石头。
  • 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

1
2
3
4
输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

示例 2：

1
2
输入：n = 1
输出：true

示例 3：

1
2
输入：n = 2
输出：true

题解

由题目描述“你们每一步都是最优解”可以发现，示例1的必败情况就是本题的突破口。即双方都只需要将对手引导至剩余4块石头的局面，那么就是最优的取法。那么如何使对手剩下4块呢？其实只需将石头块数对4取余，即将4的倍数多余出来的石头拿走，这样对手就永远处于从4的倍数中取石头的境况中，而随着石头越取越少，倍数越来越小，最终对手必然剩下4的1倍，即4块石头。可见，胜负从开局石头数就已经定了。

完整代码：

1
2
3
4
5
public class Solution {
    public bool CanWinNim(int n) {
        return n % 4 != 0;
    }
}

ac

🟠 2021.09.17 (36. 有效的数独)

题目

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。

示例 1：

输入：board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[“.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[“.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[“.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[“.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
输出：true

题解

根据数独有效性的三条规则，可以分别定义三个记忆变量，记录在某行处某数字是否出现过、在某列处某数字是否出现过、在某区域（九个粗格）内某数字是否出现过。遍历数独数字，若任三条中任一条出现过则数独无效，若遍历完所有格都没有出现过，则数独有效。

完整代码：

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
public class Solution {
    public bool IsValidSudoku(char[][] board) {
        // existedInArea[a,b] 在区域 a 内数字 b 是否出现过
        bool[,] existedInArea = new bool[9,9];
        // existedInColumn[a,b] 在第 a 列数字 b 是否出现过
        bool[,] existedInColumn = new bool[9,9];
        for(int i = 0; i < board.Length; i++)
        {
            // existedInRow[a] 在第 i 行数字 a 是否出现过
            bool[] existedInRow = new bool[9];
            for(int j = 0; j < board[i].Length; j++)
            {
                // skip blank and cal params
                if(board[i][j].Equals('.')) continue;
                // -1 将数独 1~9 位移到 0~8 和数组下标从零开始保持一致
                int num = int.Parse(board[i][j].ToString()) - 1;
                int area = (j/3)*3 + i/3;

                // check row
                if(existedInRow[num]
                || existedInColumn[j, num]
                || existedInArea[area,num]) return false;

                existedInRow[num] = true;
                existedInColumn[j, num] = true;
                existedInArea[area,num] = true;
            }
        }
        return true;
    }
}

ac

🟠 2021.08.25 (797. 所有可能的路径)

题目

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。

译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。

示例 1：

1

1
2
3
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

1

1
2
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

示例 3：

1
2
输入：graph = [[1],[]]
输出：[[0,1]]

提示：

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i（即，不存在自环）
  • graph[i] 中的所有元素 互不相同
  • 保证输入为 有向无环图（DAG）

题解（回溯搜索）

此题数据量较小，且直接给了邻接表，直接进行深度优先遍历即可解决。完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        dfs(graph, 0, new List<int>(){0});
        return res;
    }
    
    public void dfs(int[][] graph, int current, List<int> list)
    {
        // 已达目标点，因为List为引用传参，且在回溯后会被修改，故搜索到有效路径后需构建新List加入结果集合
        if(current == graph.Length - 1) res.Add(new List<int>(list));
        // 遍历当前节点的当所有可达节点
        for(int i = 0; i < graph[current].Length; i++)
        {
            int next = graph[current][i];
            list.Add(next);
            dfs(graph, next, list);
            list.Remove(next);
        }
    }
}

ac

🟠 2021.08.24 (787. K 站中转内最便宜的航班)

题目

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [from_i, to_i, price_i] ，表示该航班都从城市 from_i 开始，以价格 price_i 抵达 to_i。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

输入：
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出：200
解释：
城市航班图如下

1

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入：
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0

输出：500
解释：
城市航班图同上。从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= from_i, to_i < n
  • from_i != to_i
  • 1 <= price_i <= 104
  • 航班没有重复，且不存在自环
  • 0 <= src, dst, k < n
  • src != dst

题解（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
public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 构建邻接表
        List<int[]>[] flightFrom = new List<int[]>[n];
        for(int i = 0; i < n; i++) flightFrom[i] = new List<int[]>();
        foreach(int[] flight in flights) flightFrom[flight[0]].Add(flight);
        // 构建 BFS 队列
        // waiting 记录的是 BFS 过程中入队的等待下一层被遍历的城市编号。关于该 queue 为什么有两维：
        // 队列中加入候遍历元素时必须同时记录其src到i的开销快照，否则直接使用costFromSrc的话其开销可能被修改
        // 如 BFS 深度为 1 时计算的 src 到 i 节点开销为 x，即 costFromSrc[i] = x; 节点 i 入队
        // 入队时该开销 x 是特指深度为 1 时的最小开销，在进入深度为 2 的层次后，在 i 出队之前，
        // 可能找到了到达 i 的更小开销，那么 costFromSrc[i] 就将被覆盖，待 i 在深度为 2 出队时，使用的
        // costFromSrc[i] 已经不是原来的 x 了，那么对应的 costFromSrc[i] + flight[2] 也就不是深度为 2 时
        // i 到 flight[1] 的最小开销了，而是深度为 3 时的最小开销，深度为 2 时到 flight[1] 的正确开销是应是
        // 深度为 1 时的 x 加上 flight[2]，而因为无法保证 costFromSrc[i] 在下一层深度出队前不会被修改，
        // 因此在入队时就需要记录其当前时刻的 costFromSrc[i]，相当于打个快照，记录在数组的第二维。
        Queue<int[]> waiting = new Queue<int[]>();
        waiting.Enqueue(new int[]{src,0});
        // 初始化最小代价数组
        int[] costFromSrc = new int[n];
        for(int i = 0; i < n; i++) costFromSrc[i] = int.MaxValue; costFromSrc[src] = 0;
        // 开始 BFS
        for(int i = 0; i < k+1; i++)
        {
            int lastTermEnqueueCount = waiting.Count;
            for(int j = 0; j < lastTermEnqueueCount; j++)
            {
                int[] source = waiting.Dequeue();
                foreach(int[] flight in flightFrom[source[0]])
                {
                    int newCost = source[1] + flight[2];
                    // 剪枝
                    if(newCost < costFromSrc[flight[1]] && newCost < costFromSrc[dst])
                    {
                        costFromSrc[flight[1]] = newCost;
                        if(flight[1] != dst) waiting.Enqueue(new int[]{flight[1],newCost}); // 剪枝
                    }
                }
            }
        }
        return costFromSrc[dst] == int.MaxValue ? -1 : costFromSrc[dst];
    }
}

ac

🟢 2021.08.23 (1646. 获取生成数组中的最大值)

题目

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

  • nums[0] = 0
  • nums[1] = 1
  • 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
  • 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：n = 7
输出：3
解释：根据规则：
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

示例 2：

1
2
3
输入：n = 2
输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

示例 3：

1
2
3
输入：n = 3
输出：2
解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2

提示：

  • 0 <= n <= 100

题解

没什么好写的，按题目要求计算 nums 数组，然后返回最大值就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int GetMaximumGenerated(int n) {
        if(n==0 || n==1) return n; // 特殊情况
        int[] nums = new int[n+1];
        nums[0] = 0; nums[1] = 1;
        int i = 1, m = -1;
        while(true)
        {
            if(2*i<=n)
            {
                nums[2*i] = nums[i];
                m = nums[2*i] > m ? nums[2*i] : m; // 更新最大值
            } else break;
            if(2*i+1<=n)
            {
                nums[2*i+1] = nums[i] + nums[i+1];
                m = nums[2*i+1] > m ? nums[2*i+1] : m; // 更新最大值
            } else break;
            i++;
        }
        return m;
    }
}

AC

🟠 2021.08.22 (789. 逃脱阻碍者)

题目

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 发生。

如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。

只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。

示例 1：

1
2
3
输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。

示例 2：

1
2
3
输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。

示例 3：

1
2
3
输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。

示例 4：

1
2
输入：ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]
输出：false

示例 5：

1
2
输入：ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0]
输出：true

提示：

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -104 <= xi, yi <= 104
  • 同一位置可能有 多个阻碍者 。
  • target.length == 2
  • -104 <= xtarget, ytarget <= 104

题解

在写题解之前，首先实在忍不住要吐槽，此题的歧义太大了！。。竟然还是谷歌的面试题，无语。

题目说 ghosts 是抓捕玩家的，且只要有可能成功逃脱，就应当返回 true，然而以 示例2 为例，若 player_and_ghost = [[0,0],ghost[0]] 按照 [[0,-1],[0,0]] → [[1,-1],[0,-1]] → [[2,-1],[1,-1]] → [[2,0],[2,-1]] 移动，玩家是完全能够成功逃脱的，且在这个过程中 ghost 同样在全力抓捕玩家（题目说了阻碍者可以采取任何行动方式），但该示例的输出却是 false，实在令人费解。

1

一开始以为是翻译的锅，结果看了看原题，表述同样是”有可能逃脱“：

Return true if it is possible to escape, otherwise return false.

我猜想此题出题人是以 ghosts 和玩家谁能先到终点为出题点，然后为了考察面试者的问题转化能力，于是将谁先到终点这一表述改成了看上去相当复杂的玩家有没有可能逃脱 ghosts 追捕这一表述，然而这两者完全不等价，结果便是弄巧成拙，令人哑语，此题可谓烂出了高度，烂出了境界，烂得登峰造极！

吐槽结束。该题目的正确表述应当是：”只有在你一定能成功逃脱时，输出 true“ 而不应是 “只有在你可能成功逃脱时，输出 true“，照这样来，问题才被转换为比较 ghosts 和玩家谁能够最先跑到终点，因为只要任一 ghost 先到终点并保持不动，玩家才会完全不存在逃脱的可能性，这同时这也是本题的最优解法。

由于移动只能上下左右，且移动速度是一致的，故谁先到达终点连距离都不需算，直接比较玩家与 ghost 们各自同终点为对角线构成矩形的一半周长即可。完整代码如下：

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public bool EscapeGhosts(int[][] ghosts, int[] target) {
        int distance = Math.Abs(target[0])+ Math.Abs(target[1]);
        foreach(int[] ghost in ghosts)
        {
            if(Math.Abs(target[0]-ghost[0])+Math.Abs(target[1]-ghost[1])<=distance) return false;
        }
        return true;
    }
}

AC

🟠 2021.08.21 (443. 压缩字符串)

题目

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

  • 如果这一组长度为 1 ，则将字符追加到 s 中。
  • 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

示例 1：

输入：chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,”2”,”b”,”2”,”c”,”3”]
解释：
“aa” 被 “a2” 替代。”bb” 被 “b2” 替代。”ccc” 被 “c3” 替代。

示例 2：

输入：chars = [“a”]
输出：返回 1 ，输入数组的前 1 个字符应该是：[“a”]
解释：
没有任何字符串被替代。

示例 3：

输入：chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
输出：返回 4 ，输入数组的前 4 个字符应该是：[“a”,”b”,”1”,”2”]。
解释：
由于字符 “a” 不重复，所以不会被压缩。”bbbbbbbbbbbb” 被 “b12” 替代。
注意每个数字在数组中都有它自己的位置。

提示：

  • 1 <= chars.length <= 2000
  • chars[i] 可以是小写英文字母、大写英文字母、数字或符号

题解

此题不难，且容易发现并不需要额外设置 s 串再转储回 chars 中，完全可以在遍历原字符数组 chars 的过程中就地修改 chars 完成要求。

首先设置一个 hold 字符变量，用于存储重复首字符，再设置一个 contiCount 整形变量，用于存储连续重复的 hold 字符数。利用一个初值为 0 的整形 pointer 变量作为覆写 chars 的位置指针，时刻指向下一次要写入的位置，这样 pointer 的值也就同时代表了题目要求返回的数组长度。

在最开始时，hold 是空字符，直接将第一个字符设置为 hold，覆写自己，移动 pointer 并将 contiCount 设置为1，代表重复字符数为1，即字符本身。

此后，当遍历到的字符与 hold 相同时，说明出现的是重复字符，将 contiCount 自增以更新重复字符数；当遍历到的字符与 hold 不同时，说明出现了新字符，此时将之前重复字符的 contiCount 拆分写入 chars后，即可更新 hold 记录为新字符，并将新字符覆写入 chars ，contiCount 重置为1，以此类推。由于期间都是使用移动的 pointer 来指向要覆写的 chars 位，因此每次写入操作都要将 pointer 移动一位。

这里我以压缩字符数组 ['a','b','b','b','c'] 为例，画了一个压缩过程图解，辅助理解。

1

显然，该方法需要遍历一次原数组，且只使用了两个 int 和一个 char 变量，故时间复杂度为 $O(n)$，空间复杂度为 $O(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
public class Solution {
    public int Compress(char[] chars) {
        char hold = '\0'; // 当前暂存的重复首字符
        int contiCount = 0; // 连续重复的字符数
        int pointer = 0; // 覆写chars的位置指针(亦题要返回的s长度)
        foreach(char c in chars)
        {
            if(c.Equals(hold)) contiCount++;
            else
            {
                // 结算上一种char的重复字符数
                if(contiCount>1) // 为0为首次进入，为1不需要追加数字
                {
                    // 将数字拆分覆写入chars
                    string temp = contiCount.ToString();
                    for(int i = 0; i < temp.Length; i++) chars[pointer++] = temp[i];
                }
                // 覆写入新字符
                chars[pointer++] = hold = c;
                // 重置重复字符数
                contiCount = 1;
            }
        }
        // 以重复字符结尾时，不会进入foreach中的else分支，此处单独判断是否有未结算的连续字符数
        if(contiCount!=1)
        {
            string temp = contiCount.ToString();
            for(int i = 0; i < temp.Length; i++) chars[pointer++] = temp[i];
        }
        return pointer;
    }
}

AC

🟢 2021.08.20 (541. 反转字符串 II)

题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：

输入：s = “abcd”, k = 2
输出：“bacd”

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

题解

此题不难，只需按一般情况逆置 k 位字符，然后将字符指针以 2k 长度为单位进行跳转，直接跳转到下一个逆置起点，继续逆置 k 位，以此类推即可。本题我使用 for 循环的循环变量来控制跳转，同时利用 for 循环的循环条件来判断接下来是否够 k 位，进而可以避免循环内部再做 if 判断。

对于最后可能剩下的不够 k 位的情况，单独用一个 if 来捕获，进行剩余字符的逆置。这里我画了一幅图展示完整过程，以供理解。1

理清了思路，代码也就水到渠成了，完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    char temp; // 用于swap的中间变量
    public string ReverseStr(string s, int k) {
        char[] cs = s.ToCharArray(); // string是只读的，转为char[]方便修改
        int i = 0;
        // 逆置满k位的 第2ik ~ 第(2i+1)k-1位
        for(; (2*i+1)*k-1 < s.Length; i++) cs = ReversePartialStr(cs, 2*i*k, (2*i+1)*k-1);
        // 如有剩余不满k位的，则逆置剩余的 第2ik ~ 第s.Length-1位
        return new string(2*i*k < s.Length-1 ? ReversePartialStr(cs, 2*i*k, s.Length-1) : cs);
    }
    // 逆置第left位~第right位
    public char[] ReversePartialStr(char[] cs, int left, int right){
        while(left<right)
        {
            // 交换cs[left]和cs[right]
            temp = cs[left]; cs[left] = cs[right]; cs[right] = temp;
            left++; right--;
        }
        return cs;
    }
}

AC

🟢 2021.08.19 (345. 反转字符串中的元音字母)

题目

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1：

输入：“hello”
输出：“holle”

示例 2：

输入：“leetcode”
输出：“leotcede”

提示：

  • 元音字母不包含字母 “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
public class Solution {
    public string ReverseVowels(string s) {
        char[] cs = s.ToCharArray(); // string是只读的，为了修改内容先转成char[]
        int left = 0; // 设置首尾指针
        int right = s.Length-1;
        char temp; // 用于交换首尾指针元素的中间变量
        while(left<right)
        {
            while(left<right  && cs[left]!='a' && cs[left]!='A'
                              && cs[left]!='e' && cs[left]!='E'
                              && cs[left]!='i' && cs[left]!='I'
                              && cs[left]!='o' && cs[left]!='O'
                              && cs[left]!='u' && cs[left]!='U'
            ) left++; // 从左向右找元音字母
            while(right>left  && cs[right]!='a' && cs[right]!='A'
                              && cs[right]!='e' && cs[right]!='E'
                              && cs[right]!='i' && cs[right]!='I'
                              && cs[right]!='o' && cs[right]!='O'
                              && cs[right]!='u' && cs[right]!='U'
            ) right--; // 从右向左找元音字母
            // 将左右找到的元音字母交换
            temp = cs[left];
            cs[left] = cs[right];
            cs[right] = temp;
            // 交换后记得移动首尾指针 不然就死循环了
            left++;
            right--;
        }
        return new string(cs); // 用修改完成后的char[]构造新string返回
    }
}

AC

🔴 2021.08.18 (552. 学生出勤记录 II)

题目

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

  • 'A'：Absent，缺勤
  • 'L'：Late，迟到
  • 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

  • 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
  • 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。

示例 1：

输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
只有”AA”不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

示例 2：

输入：n = 1
输出：3

示例 3：

输入：n = 10101
输出：183236316

提示：

  • 1 <= n <= 10^5

题解（DFS+记忆化搜索）

这题自己没做出来，看了一眼别人的题解才瞬间被点通了，以后这种序列问题都应该有意识地考虑递归解法结合记忆化搜索来优化。虽然这题的难度系数是困难，但是完全没做出来实在是不应该啊，还是自己太菜了。。

首先需要能够想到基础的递归写法。要统计符合条件的序列数量，那么我们从第一位置开始选字母，然后选好后再选下一位的字母。只有这一位字母的选择满足题目条件才有资格去选下一位字母，这样只要选完了最后一位字母，就找到了一条有效序列。并且由于是每位每种有效情况的字母都遍历了，因此可以做到不重不漏。

定义 int NextDay(int day, int a, int l, int n) 是选下一位字母的递归函数，返回这个参数情况下满足题意的序列个数。因为判断条件和之前状态有关联，因此需要两个参数 a 和 l 把之前状态传进来，其中 a 是前面出现的 Absent 的次数，l 是前面连续出现的 Late 的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int NextDay(int day, int a, int l, int n)
// day: 当前天数; a: 之前 Absent 的次数; l: 之前连续 Late 的天数.
{
    if(day > n) return 1; // n天都选完了，
    
    int count = 0;
    // 1.这天Present，任何情况下都可以放Present，不影响有效性
    count = (count + NextDay(day+1, a, 0, n)) % MOD;
    // 2.如果之前有连续两天Late了，那么今天就不能放Late了，否则就连续三天了，因此l必须<2
    if(l<2) count = (count + NextDay(day+1, a, l+1, n)) % MOD;
    // 3.如果之前已经有Absent了，那么就不能再Absent了，因此a必须严格为0
    if(a==0) count = (count + NextDay(day+1, a+1, 0, n)) % MOD;

    return count;
}

本题的递归逻辑就是这样了，很简洁，也很直觉，很可惜自己并没有往这个方面想，菜是原罪。

当然，直接这样提交的话是会超时的，不过用记忆化搜索优化一下就好了，这个不难。当然这题也可以DP解，但暂时先止步于记忆化搜索，之后DP当专题来专门学习，然后再回过头来拿这些题目练习复习。

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
public class Solution {
    int MOD = (int)1e9+7;
    int[,,] mem; // [day, a, l]
    public int CheckRecord(int n) {
        // Initialize mem
        mem = new int[n+1, 2, 3];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    mem[i,j,k] = -1;
                }
            }
        }
        return NextDay(1, 0, 0, n);
    }
    public int NextDay(int day, int a, int l, int n)
    // day: current day; a: count of absent day before this day;
    // l: conti count of late day before this day.
    {
        if(day > n) return 1;

        if(mem[day,a,l]!=-1) return mem[day,a,l];

        int count = 0;
        // Present this day
        count = (count + NextDay(day+1, a, 0, n)) % MOD;
        // Late this day
        if(l<2) count = (count + NextDay(day+1, a, l+1, n)) % MOD;
        // Absent this day
        if(a==0) count = (count + NextDay(day+1, a+1, 0, n)) % MOD;

        mem[day,a,l] = count;
        return count;
    }
}

AC

🟢 2021.08.17 (551. 学生出勤记录 I)

题目

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

  • 'A'：Absent，缺勤
  • 'L'：Late，迟到
  • 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

  • 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
  • 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：

输入：s = “PPALLP”
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

示例 2：

输入：s = “PPALLL”
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。

提示：

  • 1 <= s.length <= 1000
  • s[i] 为 'A'、'L' 或 'P'

题解

这题没什么好解的，直接按直觉写就击败100%用户了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public bool CheckRecord(string s) {
        int A = 0;
        int L = 0;
        foreach(char c in s)
        {
            if(c=='A') A++; // 缺勤
            if(c=='L') L++;
            else L = 0; // 只记录连续迟到
            if(A==2 || L==3) return false; // 满足缺勤两次或连续迟到三次
        }
        return true;
    }
}

AC

🟠 2021.08.16 (526. 优美的排列)

题目

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

  1. 第 i 位的数字能被 i 整除
  2. i 能被第 i 位上的数字整除

现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除

说明:

  1. N 是一个正整数，并且不会超过15。

题解（DFS）

看完题目首先想到的是暴力解法，即遍历每一位（第 i 位），在每位上再遍历 $[1,N]$ 范围内的所有数，依次选取第 i 位上能够放上的所有满足构成优美排列的数字并进行下一位数的选取，当最后一位数也选取完成后，就构造出了一个优美排列，即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// index: 第 i 位
// n: 可以放置的数的范围上限
int count = 0; // 优美排列数量
public void FindNext(int index, int n)
{
    // 最后一位数已经完成选取，排列已经构造完成
    if(index > n)
    {
        count++;
        return;
    }   
    // 为第 index 位数遍历所有可能的数
    for(int i = 0; i <= n; i++)
    {
        // 检查 i 放在第 index 位是否满足优美排列条件
        if(i%index==0 || index%i==0)
        {
            // 继续放置下一位数
            FindNext(index+1, n);
        }
    }
}

但是这样还有一个问题，即当某个数字 i 在某位处被选取后，是不应当在后面的位处再被选取的，因此我们需要在进入下一位递归前，为当前选取的数字做一个标记，防止被再次选中，并且在递归回溯时取消标记（因为回溯后当前位使用 i 的情况就结束了，通过for循环继续遍历使用其它数的情况）

完整代码：

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
public class Solution {
    bool[] used;
    int count = 0;
    public int CountArrangement(int n) {
        used = new bool[n+1];
        FindNext(1, n);
        return count;
    }
    public void FindNext(int index, int n)
    {
        if(index > n)
        {
            // 一个优美排序构造完成了
            count++;
            return;
        }
        for(int i = 1; i <= n; i++)
        {
            // 检查 i 放在第 index 位是否满足优美排列条件
            if(!used[i] && (i%index==0 || index%i==0))
            { 
                // 将当前数标记为已被使用，防止递归内部被重复使用
                used[i] = true;
                FindNext(index+1, n);
                // 取消该数的使用状态，继续遍历第 index 位放下一个数字的情况
                used[i] = false;
            }
        }
    }
}

执行情况

🟠 2021.08.15 (576. 出界的路径数)

题目

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 $10^9 + 7$ 取余 后的结果。

示例 1：

示例1

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

示例 2：

示例1

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

提示：

  • 1 <= m, n <= 50
  • 0 <= maxMove <= 50
  • 0 <= startRow < m
  • 0 <= startColumn < n

题解（DFS+记忆化搜索）

读完题目，很自然地可以想到通过递归来解决问题。首先不考虑各种限制。

因为第 i 行 j 列最多移动 maxMove 步的出界路径数就是当前格子处移动一步可能的出界数再加上上下左右四个格子处最多移动 maxMove - 1 步的出界路径数的和。

即，若定义 PathCount(int m, int n, int maxMove, int startRow, int startColumn) 为第 startRow 行 startRow 列在 mxn 网格中最多移动 maxMove 步的路径数 count，则

1
2
3
4
5
6
7
8
9
int PathCount(int m, int n, int maxMove, int startRow, int startColumn){
    // ...
    count = 当前格移动一步的出界数 +
    	PathCount(m, n, maxMove-1, startRow-1, startColumn) +
    	PathCount(m, n, maxMove-1, startRow+1, startColumn) +
    	PathCount(m, n, maxMove-1, startRow, startColumn-1) +
    	PathCount(m, n, maxMove-1, startRow, startColumn+1);
    // ...
}

如果将 count 设置为全局变量，在递归过程中更新这个量的话，那么就是

1
2
3
4
5
6
7
8
9
int PathCount(int m, int n, int maxMove, int startRow, int startColumn){
    // ...
    count += 当前格移动一步的出界数;
    count += PathCount(m, n, maxMove-1, startRow-1, startColumn) +
             PathCount(m, n, maxMove-1, startRow+1, startColumn) +
             PathCount(m, n, maxMove-1, startRow, startColumn-1) +
             PathCount(m, n, maxMove-1, startRow, startColumn+1);
    //...
}

那么具体在 PathCount 中，如何实际地更新 count (当前格移动一步的出界数)呢？即什么情况说明已经找到了一条出界路径？

不难想到，当 maxMove 大于 0，即球还可以移动的前提下，若当前所在行号为 0，那么就一定能够向上出界，即找到了一条出界路径，可以将 count++。同理，若当前所在列号为 0、当前所在行号为 m - 1（底边界处）、当前所在列号为 n - 1（右边界处）时也是有效的出界路径。因此 count 的实际更新可以被归结为以下四种情况

1
2
3
4
if(startRow == 0) count++;
if(startRow == m-1) count++;
if(startColumn == 0) count++;
if(startColumn == n-1) count++;

接下来只需要考虑递归出口即可。不难想到，当前位置处于网格之外，或者不能够再移动（maxMove为0）时就到达出口了。

1
2
// 出口条件
if(startRow < 0 || startColumn < 0 || startRow >= m || startColumn >= n || maxMove == 0) return 0;

至此，可以得到如下直觉解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    int mod = (int)1e9 + 7;
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        return PathCount(m, n, maxMove, startRow, startColumn);
    }

    public int PathCount(int m, int n, int maxMove, int startRow, int startColumn){
        // 球已在界外或无法再移动时到达递归出口
        if(startRow < 0 || startColumn < 0 || startRow >= m || startColumn >= n || maxMove == 0) return 0;
        int count = 0;
        // 球向上/下/左/右移动1次即可出界
        if(startRow == 0) count++;
        if(startRow == m-1) count++;
        if(startColumn == 0) count++;
        if(startColumn == n-1) count++;
        // 统计上下左右四个格子的出界情况数，根据题目，每步应该除余 1e9+7 防止溢出
        count += PathCount(m, n, maxMove-1, startRow-1, startColumn); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow+1, startColumn); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow, startColumn-1); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow, startColumn+1); count %= mod;
        return count;
    }
}

这样确实可以解决问题。但是，当输入参数过大导致递归深度过深时，运行时间会爆炸式增长。稍加分析可以发现，在第0层递归时的第一个 PathCount 调用栈中遍历过的格子，可能在后续递归中被大量重复访问，不仅重复访问，而且还会重复开启递归栈，造成时间爆炸。

因此我们可以设置一个变量（int[,,] mem），记录某格处最大走 maxMove 步对应的已经计算过的路径数量，在访问该格时，首先检查变量中该位置最大走 maxMove 步是否有值了，如果有就直接可以直接返回，省去所有重复的递归栈，以此优化原算法，此思想即为记忆化搜索。

最终完整代码：

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
public class Solution {
    int mod = (int)1e9 + 7;
    int[,,] mem; // 记忆第 i 行 j 列处最大移动 maxMove 步的路径数
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // 初始化记忆变量为-1，代表暂没有走过该状态
        mem = new int[m,n,maxMove+1];
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                for(int k = 0; k < maxMove+1; k++)
                {
                    mem[i,j,k] = -1;
                }
            }
        }
        // 开始计数
        return PathCount(m, n, maxMove, startRow, startColumn);
    }

    public int PathCount(int m, int n, int maxMove, int startRow, int startColumn){
        // 球已在界外或无法再移动时到达递归出口
        if(startRow < 0 || startColumn < 0 || startRow >= m || startColumn >= n || maxMove == 0) return 0;
        
        // 若已经走过了该状态，则直接返回该状态对应的路径数，避免重复计算
        if(mem[startRow, startColumn, maxMove] != -1)
            return mem[startRow, startColumn, maxMove];
        
        int count = 0;
        // 球向上/下/左/右移动1次即可出界
        if(startRow == 0) count++;
        if(startRow == m-1) count++;
        if(startColumn == 0) count++;
        if(startColumn == n-1) count++;
        
        // 统计上下左右四个格子的出界情况数，根据题目，每步应该除余 1e9+7 防止溢出
        count += PathCount(m, n, maxMove-1, startRow-1, startColumn); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow+1, startColumn); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow, startColumn-1); count %= mod;
        count += PathCount(m, n, maxMove-1, startRow, startColumn+1); count %= mod;
		
        // 记录当前状态的路径数
        mem[startRow, startColumn, maxMove] = count;
        return count;
    }
}

执行情况

⚪ 2021.08.14 (1583. 统计不开心的朋友)

🟠 未做

⚪ 2021.08.13 (233. 数字 1 的个数)

🔴 不会

⚪ 2021.08.12 (516. 最长回文子序列)

题目

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

题解

🟠 待更新

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int LongestPalindromeSubseq(string s) {
        int[,] maxLength = new int[s.Length, s.Length];
        for(int i = s.Length-1; i >= 0; i--)
        {
            maxLength[i,i] = 1;
            for(int j = i + 1; j < s.Length; j++)
            {
                if(s[i]==s[j])
                {
                    // 左右对称回缩，中间范围最长回文长度加上当前新的首位即为i到j最长回文长度
                    maxLength[i,j] = maxLength[i+1,j-1] + 2;
                }
                else
                {
                    // 记忆上一个最长的序列长度为i到j最长回文长度
                    maxLength[i,j] = Math.Max(maxLength[i+1,j], maxLength[i,j-1]);
                }
            }
        }
        return maxLength[0, s.Length-1];
    }
}

⚪ 2021.08.11 (446. 等差数列划分 II)

🔴 不会

🟠 2021.08.10 (413. 等差数列划分)

题目

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

  • 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

提示：

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000

题解

这题按直觉解就很容易解，依次将第 i 个元素作为子数组的首元素，然后利用首元素和下一个元素计算该子数列的公差，然后开始向后检查，只要每一个元素和前一个元素之差等于公差，那么都构成一个等差子数列，直到与前一位之差不等于公差，第 i 个元素作为首元素就不存在更多等差子数列了，将 i++ 进行后续判断。

如1234578，先将首位设置为第一个元素1，然后利用(12)计算出公差为1，往后(123)中(23)之差为1，就是一个子数列，往后(1234)中(34)之差也为1也是子数列，(12345)中(45)也是，但(123457)中(57)就不是了，那么再往后也不可能再是等差数列了，于是将首位设置为第二个元素同理搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        // 至少三个元素才能构成等差数列
        if(nums.Length < 3) return 0;
        // rear: 计算差值的左元素; front: 计算差值的右元素; delta: 子数组的期待公差
        int rear, front, delta, count = 0;
        for(int i = 0; i < nums.Length-1; i++)
        {
            // 以i为子数组的首元素，计算该子数组(等差数列)期待的公差
            rear = i; front = i+1;
            delta = nums[front] - nums[rear];
            // 只要每一对rear、front之差为期待的公差值就找到了一个子等差数列，移动rear和front继续计算下一对差值
            while(++front < nums.Length)
            {
                if(nums[front] - nums[++rear] == delta) count++;
                else break;
            }
        }
        return count;
    }
}

AC

🟠 2021.08.09 (313. 超级丑数)

题目

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示：

  • 1 <= n <= 106
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • 题目数据 保证 primes[i] 是一个质数
  • primes 中的所有值都 互不相同 ，且按 递增顺序 排列

题解

由于超级丑数是由质因数相乘得到的，因此给定一组质因数后，其对应的超级丑数有无数个，所以肯定是无法通过先计算出所有超级丑数，然后取第 n 个返回的思路了。故应该思考如何从小到大按顺序依次生成超级丑数。

其中一个关键点是，由于超级丑数是由质因数相乘得到的，那么就意味着任一超级丑数一定能被分解成一个质因数和一个更小的超级丑数，也即超级丑数是由更小的超级丑数同质因数生成的。那么反过来，我们借此就可以由最小的超级丑数1，遍历质因数同1相乘，来找到(生成)最小的下一个超级丑数。

1

现在就有了两个超级丑数，并且它们是最小的两个，那么第三个超级丑数就一定是由这两个小的超级丑数同所有质因数相乘得到的结果中最小的那个。不过需要注意的是，质因数并不需要和所有找到的超级丑数相乘再比较，因为我们要找的是最小的那个，只需要和允许相乘的最小的那一个超级丑数相乘就行了，比如质因数4和第 1 个超级丑数相乘了，那么这个质因数就没有必要和第 2 个以及后面的超级丑数相乘了，因为往后一定是乘出来更大的数。

那么如何知道某个质因数应当和第几个超级丑数相乘呢？其实只需要设置一个(质因数->超级丑数)指针，最开始所有质因数都是和最小的超级丑数相乘，当某个质因数 x 被选出来同1相乘的结果最小时，生成了第二个超级丑数，此后 x 就不可能再和 1 相乘了，因此 x 对应的指针就可以向后移动到第二个超级丑数的位置，后面只需要和第二个超级丑数乘就是 x 能生成的最小的超级丑数。

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
37
38
39
40
41
42
43
44
45
public class Solution {
    public int NthSuperUglyNumber(int n, int[] primes) {
        if(n == 1) return 1;

        // 初始化待装n个超级丑数的容器
        int[] uglyNums = new int[n];
        int count = 0;
        uglyNums[0] = 1; // 1是初始的最小的超级丑数
        count++;

        // 初始化pUg为质因数对应的超级丑数指针
        int[] pUg = new int[primes.Length];
        // 初试时全都指向最小的超级丑数1
        for(int i = 0; i < primes.Length; i++) pUg[i] = 0;

        int nextUg, pMove, min;
        // 生成到第n个超级丑数
        while(count!=n)
        {
            // nextUg为各质因数和各自指针指向的超级丑数相乘结果中最小的那一个，首先将最小值初始化为第一个
            nextUg = uglyNums[pUg[0]] * primes[0];
            pMove = 0;
            min = 0;
            // 将质因数同对应的超级丑数相乘，找到最小的那组
            for(int i = 0; i < primes.Length; i++)
            {
                min = uglyNums[pUg[i]] * primes[i];
                if(min < nextUg)
                {
                    nextUg = min;
                    pMove = i; // 记录其指针下标方便移动
                }
            }
            // 如果生成的超级丑数和上一个超级丑数的不同，才添加为超级丑数，否则只移动指针
            if(nextUg!=uglyNums[count-1])
            {
                uglyNums[count] = nextUg;
                count++;
            }
            pUg[pMove]++;
        }
        // 返回第n个超级丑数
        return uglyNums[n-1];
    }
}

AC

0%