• LeetCode 周赛笔记 —— 2022年8月 第一周


    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),进而算出坏数对的数目。

    /**
    * 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保存某一类型前一次出现的天数即可。

    /**
    * 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

    战绩:

    • 1
    • 2
    • 3
    • 4

    305周赛

    2637.算数三元组的数目

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

    /**
    * 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

    2370.最长理想子序列

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

    • ts的一个子序列
    • 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 ) O(n^2) O(n2),根据这道题的数据范围,n最大能取到 1 0 5 10^5 105,那么 n 2 n^2 n2就达到了 1 0 10 10^{10} 1010 的计算次数,是会超时的。当晚一直没想出如何优化/(ㄒ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

    战绩:

    • 1
    • 2
    • 3
    • 4

    总结

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

    其中,周六晚上的比赛:

    • 第2题坏数对没有观察出规律,没想到对等式进行移项变换,思路上一直卡在使用归并排序求逆序对上面,这是题目见得太少。

    • 第4题,基本思路正确(贪心),代码实现上有点问题,每次拆数,都尽可能保证,新的最右侧的数最大,这个想法是没错的,但是我拆数的策略错了,我的策略并不能保证拆后新的最右侧的数最大。比如固定右侧为b,举例子[a,b]。当晚我的拆数策略是:若ab的倍数,则直接拆成若干个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个字母。可惜!

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

  • 相关阅读:
    海康研究院出品:具有场景自适应概念学习的无监督目标检测(附论文下载)...
    Rust学习记录(linux)——安装、创建、编译、输入输出
    获取1688app上原数据 API
    手写数据库连接池
    ES6模板字符串详解
    自动化喷涂生产线控制方法概述
    AK F.*ing leetcode 流浪计划之最近公共祖先(倍增算法)
    ADS127L11采集板系统噪声评估
    算法题练习——JS Node+python题解NC53 删除链表的倒数第n个节点、NC127 最长公共子串
    Python酷库之旅-第三方库openpyxl(20)
  • 原文地址:https://blog.csdn.net/vcj1009784814/article/details/126232767