Monodyee

这个屌丝很懒，什么也没留下！

热门标签

LeetCode 周赛笔记 —— 2022年8月第一周_l code去年2022年比赛题

作者：Monodyee | 2024-06-18 00:15:43

踩

l code去年2022年比赛题

文章目录

84双周赛

2363.合并相似物品

签到题，使用简单的哈希表进行合并即可，注意最后需要排序。

/***
* 9ms
**/
class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] i : items1) map.put(i[0], i[1]);
        for (int[] i : items2) map.put(i[0], map.getOrDefault(i[0], 0) + i[1]);
        List<Integer> keyList = new ArrayList<>(map.keySet());
        Collections.sort(keyList);
        List<List<Integer>> ans = new ArrayList<>();
        for (int key : keyList) ans.add(Arrays.asList(key, map.get(key)));
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当然，也可以直接使用TreeMap，会自动根据key进行排序

/**
* 11ms
**/
class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int[] i : items1) map.put(i[0], i[1]);
        for (int[] i : items2) map.put(i[0], map.getOrDefault(i[0], 0) + i[1]);
        List<List<Integer>> ans = new ArrayList<>();
        for (int key : map.keySet()) ans.add(Arrays.asList(key, map.get(key)));
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

周赛当晚我是手写了排序

/**
* 3ms
**/
class Solution {
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        quickSort(items1, 0, items1.length - 1);
        quickSort(items2, 0, items2.length - 1);
        List<List<Integer>> ans = new ArrayList<>();
        int n1 = items1.length, n2 = items2.length;
        int i = 0, j = 0;
        while (i < n1 && j < n2) {
            if (items1[i][0] < items2[j][0]) {
                ans.add(Arrays.asList(items1[i][0], items1[i][1]));
                i++;
            } else if (items1[i][0] > items2[j][0]) {
                ans.add(Arrays.asList(items2[j][0], items2[j][1]));
                j++;
            } else {
                ans.add(Arrays.asList(items1[i][0], items1[i][1] + items2[j][1]));
                i++;
                j++;
            }
        }
        
        while (i < n1) {
            ans.add(Arrays.asList(items1[i][0], items1[i][1]));
            i++;
        }
        while (j < n2) {
            ans.add(Arrays.asList(items2[j][0], items2[j][1]));
            j++;
        }
        
        return ans;
    }
    
    private void quickSort(int[][] arr, int l, int r) {
        if (l >= r) return;
        int x = arr[l + r >>1][0];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (arr[i][0] < x);
            do j--; while (arr[j][0] > x);
            if (i < j) {
                int[] t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        quickSort(arr, l, j);
        quickSort(arr, j + 1, r);
    }
}
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

6142. 统计坏数对的数目

给定一个数组，若i < j并且nums[j] - nums[i] != j - i，则称(i, j)为一个坏数对，求坏数对的数目。

将上面的式子进行一下变形，将等号两边进行一下交换，得到 nums[j] - j != nums[i] - i 。则对于每个位置i，我们可以求出一个数常数c(i) = nums[i] - i，若对每个位置，求出的常数c都是一样的，则整个数组的坏数对数目为0。比如数组[1,2,3,4,5]。每个位置的c(i) = 1。容易得出结论，对于那些c相等的位置i，这些位置之间全都不是坏数对。或者说，对于坏数对(i,j) 一定有c(i) != c(j)。那么我们可以遍历一次，对每个位置求出其c(i)，进而算出坏数对的数目。

—2022/08/30 更新
我们从左往右遍历，对每个位置，统计一下以当前位置为[数对]中右侧的数，能组成多少个坏数对。那么只需要看当前这个数，与当前位置之前的数，能组成多少个坏数对。
当前这个位置为i（下标从0开始），则当前位置之前共有i个数，我们只需要从这i个数中减掉与当前nums[i] - i相同的数的个数即可，剩下的数即可和当前数组成坏数对。

对于所有坏数对i,j，由于一定有i < j，所以无需考虑j,i。即这是组合，而不是排列。 i,j和j,i 只能算一个坏数对，而我们可以只用i,j来进行表示。那么做一次遍历，每次查看以当前位置作为j，能与当前位置之前的位置，组成多少个坏数对，进行累加即可

class Solution {
    public long countBadPairs(int[] nums) {
        // map 中存的是 nums[i] - i 的数有多少个
        Map<Integer, Integer> map = new HashMap<>();
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int u = nums[i] - i;
            int cnt = map.getOrDefault(u, 0);
            ans += i - cnt;
            map.put(u, cnt + 1);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

—2022/08/30 更新 end

/**
* 48ms
**/
class Solution {
    public long countBadPairs(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        // 进行统计计数
        for (int i = 0; i < n; i++) {
            int c = nums[i] - i;
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 采用累加法计算
        long ans = 0;
        long remainNum = n;
        for (int key : map.keySet()) {
            ans += (remainNum - map.get(key)) * map.get(key);
            remainNum -= map.get(key);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

也可以采用排除法，先算出所有数对的总数，然后依次减去不是坏数对的数量

/**
* 39ms
**/
class Solution {
    public long countBadPairs(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        long n = nums.length;
        long total = n * (n - 1) / 2; // 全部数对的数量
        // 进行统计计数
        for (int i = 0; i < n; i++) {
            // 这个数与前面的数是否能形成好数对
            int c = nums[i] - i;
            total -= map.getOrDefault(c, 0);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        return total;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

周赛当晚这道题没做出来。/(ㄒoㄒ)/，一直没想到将等式左右两边进行交换，一直在想用归并排序求逆序对的方法= =。

6174.任务调度器II

简单模拟即可，用一个Map保存某一类型前一次出现的天数即可。

—2022/08/30更新

class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        // 用一个Map存一下每种任务上一次完成的日期即可
        // 然后有一个当前日期(当前指针)
        long cur = 0;
        Map<Integer, Long> lastday = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            cur++;
            int type = tasks[i];
            if (lastday.containsKey(type)) {
                // 看一下上次做的日期
                long d = lastday.get(type);
                long gap = cur - d - 1; // 与当前日期的间隔
                if (gap < space) cur += space - gap;  // 补足间隔
            }
            lastday.put(type, cur);
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

—2022/08/30更新 end

/**
* 39ms
**/
class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        long curDay = 0;
        // 最近一次完成的任务类型以及天数
        Map<Integer, Long> map = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            curDay++;
            if (!map.containsKey(tasks[i])) {
                // 第一次出现该任务
                map.put(tasks[i], curDay);
            } else {
                // 出现重复类型的任务, 获取上一次做这个类型工作的日期
                long doneDay = map.get(tasks[i]);
                long delta = curDay - doneDay - 1;
                if (delta >= space) map.put(tasks[i], curDay); // 间隔时间够了, 直接做
                else {
                    // 需要休息
                    curDay += space - delta; // 休息完后做这件事
                    map.put(tasks[i], curDay);
                }
            }
        }
        return curDay;
    }
}
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

6144.将数组排序的最少替换次数

拆数，且要保持非递减，问最少进行操作的次数。拆数会使数变小，而要保持非递减，要尽可能让右侧的数更大（贪心的思路），所以我们从最右边开始遍历，每当遇到一个递减的两个数，比如[a,9,5]，那么要将左侧更大的那个数进行拆数，这就要拆9这个数，假设拆为2个数，即9 = x + y，那么变成[a,x,y,5]，那么要保证 y <= 5，同时要保证x <= y，且要x尽可能的大，x尽可能的大，才能保证更左侧的数拆数的可能性，尽可能地小。那么容易知道将9拆成4,5就能满足。

更一般的，假设是[16,5], 则最好的拆法是：[4,4,4,4,5]

对[17,5]，最好的拆法是[4,4,4,5,5]，对[18,5]，最好的拆法是[4,4,5,5,5]，对[19,5]，最好的拆法是[4,5,5,5,5]，对[20,5]，是[5,5,5,5,5]

能够观察出规律。假设[x, y]，x > y，那么需要对x进行拆数。当x恰好是y的倍数，则将x拆成数个y即可，操作次数为x / y - 1，比如上面的[20,5]；若y不能整除x，设c = x / y，那么最好的拆法，最左侧的数为x / (c + 1)，需要的操作次数为c。

/**
* 3ms
**/
class Solution {
    public long minimumReplacement(int[] nums) {
        long ans = 0;
        int n = nums.length;
        int right = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= right) {
                right = nums[i];
                continue;
            }
            if (nums[i] % right == 0) ans += nums[i] / right - 1;
            else {
                int c = nums[i] / right;
                ans += c;
                right = nums[i] / (c + 1);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

—2022/08/30 更新

class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        int right = nums[n - 1];
        long ans = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > right) {
                // 需要拆分
                int u = nums[i] / right;
                if (nums[i] % right != 0) u++; // 将该数拆成多少个数
                right = nums[i] / u; // 新的right
                ans += u - 1;
            } else {
                right = nums[i];
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

—2022/08/30 更新 end

战绩：

305周赛

2637.算数三元组的数目

根据题目，严格递增，容易想到用双指针（其实直接暴力也可以），然后同样，将题目中的等式进行移项操作。得到2 * nums[j] = nums[i] + nums[k]，那么固定j，用双指针移动i和k即可。

/**
* 3ms
**/
class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        int n = nums.length;
        int ans = 0;
        for (int j = 1; j < n - 1; j++) {
            int i = 0, k = n - 1;
            while (i < j && j < k) {
                if (nums[i] + nums[k] == 2 * nums[j]) {
                    if (nums[j] - nums[i] == diff) ans++;
                    i++;
                    k--;
                } else if (nums[i] + nums[k] < 2 * nums[j]) {
                    i++;
                } else {
                    k--;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2368.受限条件下可到达节点的数目

一道简单的图的遍历问题，直接用DFS或者BFS即可。

关于图的表示：邻接表，邻接矩阵。此题是稀疏图，故用邻接表表示即可。

邻接表的实现，可以用数组模拟链表，也可以用内置的数据结构

/**
* 数组实现邻接表 + DFS
* 13ms
**/
class Solution {
    int[] h;
    int[] e;
    int[] ne;
    int idx = 0;
    boolean[] ban;
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        h = new int[n];
        e = new int[2 * n];
        ne = new int[2 * n];
        Arrays.fill(h, -1);
        // 建图
        for (int[] e : edges) {
            // 无向图, 连2条边
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        ban = new boolean[n];
        for (int r : restricted) ban[r] = true;
        return dfs(0);
    }
    
    private int dfs(int node) {
        if (ban[node]) return 0;
        int ans = 1;
        ban[node] = true;
        for (int i = h[node]; i != -1; i = ne[i]) {
            int son = e[i];
            ans += dfs(son);
        }
        return ans;
    }
    
    private void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}
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

/**
* map实现邻接表 + BFS
* 101ms
**/
class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        // map 实现邻接表
        Map<Integer, List<Integer>> adjTable = new HashMap<>();
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            if (!adjTable.containsKey(a)) adjTable.put(a, new ArrayList<>());
            if (!adjTable.containsKey(b)) adjTable.put(b, new ArrayList<>());
            adjTable.get(a).add(b);
            adjTable.get(b).add(a);
        }

        boolean[] st = new boolean[n];
        for (int r : restricted) st[r] = true;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        st[0] = true;
        int ans = 1;    
        while(!queue.isEmpty()) {
            int x = queue.poll();
            for (int t : adjTable.get(x)) {
                if (st[t]) continue;
                st[t] = true;
                queue.offer(t);
                ans++;
            }
        }
        return ans;
    }
}
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

/**
* List数组实现邻接表 + BFS
* 48ms
**/
class Solution {
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<Integer>[] adjTable = new List[n];
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            if (adjTable[a] == null) adjTable[a] = new ArrayList<>();
            if (adjTable[b] == null) adjTable[b] = new ArrayList<>();
            adjTable[a].add(b);
            adjTable[b].add(a);
        }
        boolean[] ban = new boolean[n];
        for (int r : restricted) ban[r] = true;
        Queue<Integer> queue = new LinkedList<>();
        int ans = 1;
        ban[0] = true;
        queue.offer(0);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int b : adjTable[x]) {
                if (ban[b]) continue;
                ans++;
                ban[b] = true;
                queue.offer(b);
            }
        }
        return ans;
    }
}
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

2369.检查数组是否存在有效划分

记忆化递归

用函数 canDivide(l, r) 来表示区间[l, r]是否能够有效划分。
每2个连续数字，每3个连续数字，构成一个划分的最小单位。我们先求出每个最小单位的结果。
对于区间[l,r], 存储时，我们将其序列化为一个整数 l * BASE + r, 类似于将二维坐标拉成一维数字。用这样一个整数来表示这个区间。
那么我们先遍历一次数组，预处理出所有大小为2和3的区间。随后进行DFS深搜，并为了减少重复计算，加入记忆化。

这是周赛当时的做法，但是提交后只通过了110/112个测试样例，还剩2个没通过。很可惜，当时应该想到，这种情况一般是数据太大溢出导致的。后来今天复盘时，发现把代码中的int换成long就能提交通过了。（换成int[][] dp 进行状态存储会报超出内存限制）

/**
* 230ms
**/
class Solution {
    
    long BASE = 1_000_00; // 数字最大为 1e6
    
    Set<Long> valid = new HashSet<>();
    
    Set<Long> invalid = new HashSet<>();
    
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        // 预处理
       for (int i = 0; i < n; i++) {
           if (i + 1 < n) {
               if (nums[i] == nums[i + 1]) valid.add(i * BASE + i + 1);
               else invalid.add(i * BASE + i + 1);
           }
           if (i + 2 < n) {
               if (nums[i] == nums[i + 1] && nums[i] == nums[i + 2]) valid.add(i * BASE + i + 2);
               else if (nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1) valid.add(i * BASE + i + 2);
               else invalid.add(i * BASE + i + 2);
           }
       }
        // 把所有有效的最小区间全部拿出来了
        return canDivide(nums, 0, n - 1);
    }
    
    private boolean canDivide(int[] nums, int l, int r) {
        if (l > r) return true; // 不需要分了, 自然就能分了
        if (l == r) return false; // 不能分
        if (valid.contains(l * BASE + r)) return true; // 已经计算完成, 能分
        if (invalid.contains(l * BASE + r)) return false; // 已经计算完成, 不能分
        
        // 未计算完成, 则进行计算
        boolean two = valid.contains(l * BASE + l + 1) && canDivide(nums, l + 2, r);
        boolean three = valid.contains(l * BASE + l + 2) && canDivide(nums, l + 3, r);
        if (two || three) {
            valid.add(l * BASE + r);
        } else {
            invalid.add(l * BASE + r);
        }
        return two || three;
    }
}
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

其实这道题可以用标准的线性动态规划来做

设f[i]表示从[0, i]是否能进行有效划分，f[i] = true表示可划分，false表示不可划分。

状态转移，f[i]可以由下面几个式子做或运算转移过来。

f[i - 2] && nums[i] = nums[i - 1]

f[i - 3] && nums[i] = num[i - 1] = nums[i - 2]

f[i - 3] && nums[i] = nums[i - 1] + 1 = nums[i - 2] + 2

/**
* 6ms
**/
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n];
        if (nums[1] == nums[0]) f[1] = true;
        for (int i = 2; i < n; i++) {
            if (nums[i] == nums[i - 1] && f[i - 2]) f[i] = true;
            if (i == 2 || (i >= 3 && f[i - 3])) {
                if (nums[i] == nums[i - 1] && nums[i] == nums[i - 2]) f[i] = true;
                if (nums[i] == nums[i - 1] + 1 && nums[i - 1] == nums[i - 2] + 1) f[i] = true;
            }
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

—2022/08/30 重做

class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n + 1];
        // 10^5 状态数量
        // 每次状态转移需要的计算量为 O(1)
        f[0] = true;
        for (int i = 2; i <= n; i++) {
            if (i - 1 >= 1 && nums[i - 1] == nums[i - 2] && f[i - 2]) {
                f[i] = true;
            }

            if (i - 2 >= 1 && f[i - 3]) {
                if (nums[i - 1] == nums[i - 2] && nums[i - 1] == nums[i - 3]) f[i] = true;
                if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) f[i] = true;
            }
        }

        return f[n];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

—2020/08/30 重做 end

2370.最长理想子序列

给定一个由小写字母组成的字符串s和一个整数k，若满足如下2个条件，则将字符串t视为理想字符串

t是s的一个子序列
t中每两个相邻字母的绝对差值<=k

求最长的理想字符串的长度。

这道题很容易想到要用动态规划来做，因为与字符串相关的类似的题目，也都用DP的思路。比如求最长上升子序列等经典题目。

我们用f[i]表示，只从[0, i]的区间中选，选出的最长的理想子序列的长度。

周赛当时，我也是这个思路，代码如下

class Solution {
    public int longestIdealString(String s, int k) {
        int n = s.length();
        int[][] f = new int[n][2]; // 只从前n个位置中出现的子序列中, 最长的且不相邻不超过k的
        // f[i] 只在前i个位置中出现的, 最长的且不超过k的
        // 最后一个位置i是否被纳入其中
        // 是, 否
        f[0][0] = 0;
        f[0][1] = 1;
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = 1;
            for (int j = i - 1; j >= 0; j--) {
                int gap = Math.abs(s.charAt(i) - s.charAt(j));
                if (gap <= k) {
                    f[i][1] = Math.max(f[i][1], f[j][1] + 1);
                }
            }
        }
        return Math.max(f[n - 1][0], f[n - 1][1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

由于需要依赖前一个字符，所以采用了两层循环，这样的复杂度达到了 $O(n^2)$ ，根据这道题的数据范围，n最大能取到 $10^5$ ，那么 $n^2$ 就达到了 $10^{10}$ 的计算次数，是会超时的。当晚一直没想出如何优化/(ㄒoㄒ)/

正解：

类似的思路，不过我们开二维数组，第二个维度表示最后一个位置的字符。

即状态数组开为f[n][26]，比如f[5][0]，表示在[0,5]中选，得出的以a为最后一个字符的，最长理想字符串，的最大长度。

我们枚举每个位置，进行状态转移的计算，对于每个位置，我们可以有两种操作

取这个位置的字符作为子序列的末尾
不取这个字符

对于不取这个位置的字符，那么对所有的26个字母c，有f[i][c] = f[i - 1][c]

若取这个位置的字符，那么我们需要枚举前一个位置的字符，只在前一个字符和当前字符相差<=k时，进行状态转移。

/**
* 79ms
**/
class Solution {
    public int longestIdealString(String s, int k) {
        int n = s.length(); 
        int[][] f = new int[n][26];
        f[0][s.charAt(0) - 'a'] = 1;
        for (int i = 1; i < n; i++) {
            // 不取当前位置的字符作为子序列的最后一个字符时
            for (int j = 0; j < 26; j++) f[i][j] = f[i - 1][j];
            // 取当前字符
            int c = s.charAt(i) - 'a';
            for (int j = c - k; j <= c + k; j++) {
                // 前一个字符的有效区间 [c-k, c+k]
                // 注意可能越界
                if (j >= 0 && j < 26) f[i][c] = Math.max(f[i][c], f[i - 1][j] + 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) ans = Math.max(ans, f[n - 1][i]);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

由于状态转换，只依赖于上一层，则可以优化为一维数组

/**
* 25ms
**/
class Solution {
    public int longestIdealString(String s, int k) {
        int n = s.length(); 
        int[] f = new int[26];
        f[s.charAt(0) - 'a'] = 1;
        for (int i = 1; i < n; i++) {
            // 不取当前位置的字符作为子序列的最后一个字符时
            // 取当前字符
            int c = s.charAt(i) - 'a';
            int x = 0;
            for (int j = c - k; j <= c + k; j++) {
                // 前一个字符的有效区间 [c-k, c+k]
                // 注意可能越界
                if (j >= 0 && j < 26) x = Math.max(x, f[j]);
            }
            f[c] = ++x;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) ans = Math.max(ans, f[i]);
        return ans;
    }
}
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

战绩：

总结

这周两场周赛，都只做出2/4道题目。

其中，周六晚上的比赛：

第2题坏数对没有观察出规律，没想到对等式进行移项变换，思路上一直卡在使用归并排序求逆序对上面，这是题目见得太少。
第4题，基本思路正确（贪心），代码实现上有点问题，每次拆数，都尽可能保证，新的最右侧的数最大，这个想法是没错的，但是我拆数的策略错了，我的策略并不能保证拆后新的最右侧的数最大。比如固定右侧为b，举例子[a,b]。当晚我的拆数策略是：若a是b的倍数，则直接拆成若干个b，这个没什么好说的；当 2b > a > b，则拆的数为a / 2，这也是没问题的；对于a > 2b，我的策略就错了，我当时想的是，每次从a中减去一个b，直到剩余的数a'，满足2b > a' > b，然后取拆的数为a' / 2。这是不正确的。

比如[16, 5]，若按我的拆法，则结果是[6,5,5,5]，最后将6 / 2，得到[3,3,5,5,5]，这样拆完后最左侧的数并不能保证最大。实际应该这样拆，先求16 / 5 = 3 ... 1，则我们最终会把16拆成4个数，因为拆的数不能大于5，所以最多等于5。而要使得最左侧的数最大，那么最好的分配方式就是，依次分配。比如把16个数，依次分配到4个槽，那能恰好分为[4,4,4,4]，这样就能让最左侧的数最大了。

同理，若[17,5]，按我原先的拆法，结果是[7,5,5,5]，则[3,4,5,5,5]也是不对的。实际应该是17 / 5 = 3 ... 2。

我们同样要把17分配到4个槽，可以这样想，4个槽，右侧的更大，则我们从右往左，依次循环填入1。填到最后就是[4,4,4,4]，此时还剩1，再填到最右侧，形成[4,4,4,5]。

所以，最左侧的数的计算方法应该是，先求c = a / b，然后最左侧的数为a / (c + 1)。

其实当c > 2时，拆后最左侧的数等于b - 1，为了兼容c == 2时的情况，按照a / (c + 1)来进行计算

周日早上的比赛

第3题，虽然当晚我的方法有点笨拙（记忆化DFS），但是代码是没问题的，提交后110/112，只有2个用例没通过。但是我没有意识到是用例的数据太大导致可能溢出。第二天才发现这个问题，把当晚的代码拿出来，把其中的int改为long，提交就通过了，虽然耗时很长。这是很可惜的一个点，本来周日早上的比赛可以A掉3题的。
第4题，有思路，思路是正确的，但是时间复杂度很高，会超时。后面也没有想到能如何优化。DP的关键在于状态转移，状态转移一般也是枚举最后一个位置的可能情况，我想到了需要依赖前一个子序列的最后一个位置的字符，但是没想到第二维度可以直接枚举全部的26个字母。可惜！

总的来说，这周的两场周赛都不难，我见的题目太少，有些思路，解法想不到。所以还是要多多参加周赛，多多刷题。下周继续！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/732806

LeetCode 周赛笔记 —— 2022年8月 第一周_l code去年2022年比赛题