力扣2024周赛题题解

About 4906 wordsAbout 16 min

algoleetcode-weekly-match

2024-06-03

记录在力扣上面做的周赛题，给出自己的解题方法以及学习到的好的解题思路。

第402场周赛（20240616考）

100301. 构成整天的下标对数目 II

题目给定一个整数数组hours, 求 hours[i] + hour[j]是24的倍数。

类似这种给出一个值，求另外一个值的题目，遍历过程中，维护一个哈希数组。

举例：hours[i] = 30，那么需要知道左边有多少个数模24余数是18的数

举例：hours[i] = 12，那么需要知道左边有多少个数模24余数是12的数。

特别的，如果hours[i] 模24的余数是0，那么需要做到左边有多少个模60余数也是0的数

这两种情况可以合并为: 累加左边 (24 - hours[i]%24) % 24的出现的次数

Java

class Solution {
    public long countCompleteDayPairs(int[] hours) {
        long ans = 0;
        long[] cnt = new long[24];
        for(int t: hours){
            ans += (cnt[(24 -t % 24) % 24]);
            cnt[t%24]++;
        }
        return ans;
    }
}

Python

Code...

Code...

100316. 施咒的最大总伤害

想到了用dp，但是没有写出来。

第401场周赛（20240609考）

3178. 找出 K 秒后拿着球的孩子

题目给出两个正整数n和k，从下标0开始向右传递，到达下标n-1之后，从右向左移动，求移动k次到达的下标位置。

可以算出来总共移动的趟数是奇数还是偶数，如果是偶数那么最后的余数一定是从左往右，如果是奇数，那最后的余数肯定是从右往左。

Java

class Solution {
    public int numberOfChild(int n, int k) {
        int q = k / (n-1);
        int r = k % (n-1);
        return q % 2 == 0?r : n-1-r; 
    }
}

@tab Python

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        q, r = divmod(k, n-1)
        return n-r-1 if q%2 else r

3179. K 秒后第 N 个元素的值

杨辉三角变形，题解:组合数学 O(1) 公式（Python/Java/C++/Go）

Java

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 2001;

    private static final long[] FAC = new long[MX];
    private static final long[] INV_FAC = new long[MX];

    static{
        FAC[0] =1;
        for(int i=1;i<MX;i++){
            FAC[i] = FAC[i-1] * i %MOD;
        }
        INV_FAC[MX-1] = pow(FAC[MX-1], MOD-2);
        for(int i = MX-1;i>0;i--){
            INV_FAC[i-1] = INV_FAC[i] * i %MOD;
        }
    }
    private static long comb(int n, int k){
        return FAC[n] * INV_FAC[k] % MOD * INV_FAC[n-k] %MOD;
    }
    public int valueAfterKSeconds(int n, int k) {
        return (int) comb(n+k-1, k);
    }
    private static long pow(long x, int n){
        long res = 1;
        for(;n>0;n /=2){
            if(n % 2 > 0){
                res = res * x % MOD;
            }
            x =  x * x %MOD;
        }
        return res;
    }
}

3180. 执行操作可获得的最大总奖励 I

相同题目；3181. 执行操作可获得的最大总奖励 II

给你一个整数数组rewardValue，长度为n，代表奖励值；最初你的总奖励x为0，所有下标都是为未标记的，你可以执行一下操作任意次：

从区间[0, n-1]中选择一个未标记的下标i
如果rewardValue[i]大于你当前的总奖励x，则将rewardValue[i]加到x上，并标记下标i

以整数形式返回执行最优操作能够获取的最大的奖励。

第 400 场周赛（20240602考）

3168. 候诊室中的最少椅子数

题目给出一个字符串，里面包含大写E和大写L两种字符，如果是大写E的话，就表示有一位顾客进入要占用一把椅子；如果是大写L的话，就表示有一个顾客离开，释放一把椅子，求确保每位进入的顾客都有椅子坐的最少椅子数。

大概得意思就是求最开始有几把椅子才能满足字符串里面顾客的进出。

我们假设开始的椅子数为0，我们循环字符串，求在模拟这个过程中最大需要的椅子数：

class Solution {
    public int minimumChairs(String s) {
        int ans = 0, cnt = 0; // cnt表示候诊室里面人
        for(char ch: s.toCharArray()){
            if(ch == 'E'){
                cnt += 1;
                ans = Math.max(ans, cnt);
            }
            else{
                cnt -= 1;
            }
        }
        return ans;
    }
}

补充：昨天看了灵神的录播，才看到一个牛逼的思路，就是遍历字符串求房子里面最多的人的数量，就是题目的解，真厉害！

3169. 无需开会的工作日

这个题很让我伤心，题目都看得懂，就是做不出来。

题目含义就是，给你一个正整数days，表示员工可以工作的总天数（从1开始），另外给你一个二维数组表示开会的时间，比如meeting[i] = [start_i, end_i]就表示从第start_i开始开会，到end_i结束，可能会有交叉，求员工没有安排会议的天数。

主要的解题思路就是将开会的天数区间进行合并，因为可能存在交叉的情况，所有我们就需要判断合并数组的start和源数组的end的大小关系，只有当合并数组的start小于原数组的end的时候才进行合并。

class Solution {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (p,q) -> p[0]-q[0]);
        int start = 1, end = 0;  // 为什么这样定义？start从1开始，end=0表示最小值
        
        for(int[] dt: meetings){
            if(dt[0] > end){  //  不合并
                days -= (end - start + 1);
                start = dt[0];
                end = Math.max(end, dt[1]); // 求最大的end
            }else{  // 合并
                end = Math.max(end, dt[1]);
            }
        }
        return days - (end - start +1);
    }
}

灵神题解：正难则反+合并区间

第399场周赛

3163. 压缩字符串 III

找到每一段相同的字母的个数，然后在将大于9个的进行拆分。

Java

class Solution {
    public String compressedString(String word) {
        StringBuilder s = new StringBuilder();
        char[] words = word.toCharArray();
        int start = 0;
        for(int i =0;i<words.length;i++){
            if(i+1 == words.length || words[i] != words[i+1]){
                int size = i - start + 1;
                for(int j=0;j<size / 9;j++){
                    s.append(9).append(words[i]);
                }
                if(size % 9 > 0){
                    s.append(size % 9).append(words[i]);
                }
                start = i+1;
            }
        }
        return s.toString();
    }
}

3164. 优质数对的总数 II

相同的题目： 3162. 优质数对的总数 I

大概理解就是以nums2为主视角，在nums1里面找nums2[i]的倍数。

直接上灵神的题解视频，嘎嘎清晰：调和级数枚举线段树【力扣周赛 399】

第 389 场周赛

100248. 字符串及其反转中是否存在同一子字符串

这是一道简单题，给出的题目如下：

给你一个字符串 s，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现, 如果存在这样的子字符串，返回 true，如果不存在，返回 false。

这道题的话，我们只需要枚举原字符串所有的 2 个字符的子串是否在反转的字符串中，就能够得出答案。这里需要注意的是，s[i: i+1]是取不到最后一位 i+1 的字符，所有我们要 s[i: i+2]

Python

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        r = s[::-1]

        for i in range(len(s)-1):
            if s[i: i+2] in r:
                return True

        return False

Java

class Solution {
    public boolean isSubstringPresent(String s) {
        String reverse = new StringBuilder(s).reverse().toString();

        for(int i=0;i<s.length()-1;i++){
            String t = String.valueOf(s.charAt(i)) + String.valueOf(s.charAt(i+1));
            if(reverse.contains(t)){
                return true;
            }
        }
        return false;
    }
}

这里做一个补充，就是关于子串和子序列的概念，以及如何求所有的子串.

子串，必须是原序列中连续的一段，比如abacad，那么acad就是子串
子序列，原序列中可以不连续的一段，比如abacad，那么aad就是子序列

注意，无论是子串还是子序列，元素的顺序都是原序列中的顺序，是不能变化的。

如何求所有的子串？子串的个数与原序列长度的关系？

100236. 统计以给定字符开头和结尾的子字符串总数

给你一个字符串s和一个字符c，返回在字符串s中并且以c字符开头和结果的非空字符串的总数。

做出这道题之后，我突然感悟到，数学才是解决问题的本源。

开始想着枚举所有的子串，判断最前面和最后的字符是否为给定的字符，但是结果不出意外的超时了。最后想着换一种思路来解题。

就是获取到字符串s中c字符的出现次数，然后用排列组合的方式求解。

Python

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        cnt = s.count(c)  # s中c的个数
        res = cnt + (cnt * (cnt -1)) / (2 * 1)  # cnt + 从cnt个中选取两个的所有组合
        return int(res)

Java

class Solution {
    public long countSubstrings(String s, char c) {
        long cnt = s.chars().filter(x->x==c).count();
        return cnt + (cnt*(cnt-1)/2);  
    }
}

但是看过一些题解如下：

设s中有k个c，每个c都可以和它自己或左边的c形成一个符合要求的子串，所以一共有 1+2...+k=k(k+1)/2个。

但是这个怎么理解呢？没有搞懂。

第387场周赛

现在感觉做题主要的思路，如果没有思路的话，整在就没没有办法。今天幸运的做出来了两道题，咱不管排名，第一次干出来两道题。

100243. 将元素分配到两个数组中 I

简单理解题目，题目给出一个nums，将这个nums分成两个数组，然后最后在返回合并的数组，分开的规则就是，第一次操作将nums[1]追加到arr1，将nums[2]追加到arr2，然后后面的就是判断arr1最后一个元素是否大于arr2的最后一个元素，如果大于，就将nums[i]追加到arr1，否则追加到arr2里面。

这个题就按照题目给出的意思实现出来就可以过。

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        if len(nums) <=2:
            return nums
        
        n,m  = [nums[0]], [nums[1]]
        
        for i in range(2, len(nums)):
            if n[-1] > m[-1]:
                n.append(nums[i])
            else:
                m.append(nums[i])
        return n + m

100237. 元素和小于等于 k 的子矩阵的数目

给你一个下标从0开始的整数矩阵grid和一个整数。
返回包含grid左上角元素、元素和小于或等于k的子矩阵的数目。
实例二：
输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20 输出：6 解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

这个题可以构建出来一个dp数组，将每一个位置到左上角的和都计算出来。这里能很容易发现

dp[i][j] = grid[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]，这样就写出了通项公式。

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        #
        lenl = len(grid)
        lenc = len(grid[0])

        dp = [[0 for j in range(lenc)] for i in range(lenl)]
        cnt = 0

        # base case
        dp[0][0] = grid[0][0]
        if dp[0][0] <= k:
            cnt += 1
        for i in range(1, len(grid[0])):  # 列
            t = grid[0][i] + dp[0][i - 1]
            if t <= k:
                cnt += 1
            dp[0][i] = t

        for i in range(1, len(grid)):  # 行
            t = grid[i][0] + dp[i - 1][0]
            if t <= k:
                cnt += 1
            dp[i][0] = t

        # convert
        for i in range(1, lenl):
            for j in range(1, lenc):
                t = grid[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
                dp[i][j] = t
                if t <= k:
                    cnt += 1

        return cnt

100234. 在矩阵上写出字母 Y 所需的最少操作次数

这个题我连题都还没有看懂，先放一放。

100246. 将元素分配到两个数组中 II

这个题是第一道题的一个升级版本。
主要增加的就是一个greaterCount(arr, val) 函数，返回arr中严格大于val的元素数量，来判断要放到那个数组里面。

这个题尝试了一下，但是超时了，还有5个用例没有过，就是用暴力解法来求的，这里贴一下，方便后面研究。

780 / 784 个通过测试用例
状态：超出时间限制
提交时间：3 小时前

在看题解的时候，发现很多是使用离散化 + 树状数组来求解的，这个后面仔细学习一下，这个先放到这里。

题解：

离散化+树状数组 ☆

带你发明树状数组 ☆ ☆

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1 = []
        arr2 = []
        arr1.append(nums[0])
        arr2.append(nums[1])

        for i in range(2, len(nums)):
            g1 = self.gc(arr1, nums[i])
            g2 = self.gc(arr2, nums[i])
            if g1 > g2:
                arr1.append(nums[i])
            elif g1 < g2:
                arr2.append(nums[i])
            elif g1 == g2:
                if len(arr1) < len(arr2):
                    arr1.append(nums[i])
                elif len(arr2) < len(arr1):
                    arr2.append(nums[i])
                else:
                    arr1.append(nums[i])
        return arr1 + arr2

    def gc(self, arr, val):
        cnt = 0
        for i in arr:
            if i > val:
                cnt += 1
        return cnt

第386场周赛

3046. 分割数组

给你一个长度为偶数的整数数组nums，你需要将这个数组分割成nums1和nums2两部分，要求：

nums1.length == nums2.length == nums.length/2
nums1包含互不相同的元素
nums2包含互不相同的元素

如果能分割的话就返回true，否则返回false

根据题意，如果nums[i]的出现的次数超过2，则无法分割，否则可以分割

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        # most_common(n) 返回出现频率最高的n个元素
        # return Counter(nums).most_common(1)[0][1] <= 2  
        
        a = Counter(nums)
        for k, v in a.items():
            if v>2:
                return False
        return True

Counter(nums).most_common() 参考Python中的Counter.most_common()方法

第385场周赛

100212. 统计前后缀下标对 I

给你一个下标从0开始的字符串数组words
定义一个布尔函数isPrefixAndSuffix，它接受两个字符串参数str1和str2；
当str1同时是str2的前缀和后缀时， isPrefixAndSuffix返回true，否则返回false
以整数形式，返回满足i<j 且isPrefixAndSuffix(wrods[i], words[j])为true的下标对(i, j)的数量。

就是按照题目给出的，定义一个方法，来判断str1 是不是str2的前缀和后缀，如果是总是加一。

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        count = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                res = self.isPrefixAndSuffix(words[i], words[j])
                if res:
                    count += 1
        return count

    def isPrefixAndSuffix(self, s1: str, s2: str) -> bool:
        ans = False
        if len(s1) > len(s2):
            return ans

        if len(s1) == len(s2):
            pres, backs = s2, s2
        else:
            pres, backs = s2[:len(s1)], s2[-len(s1):]  # pre , bac

        if s1 == pres and s1 == backs:
            ans = True
        return ans

100229. 最长公共前缀的长度

这道题我整整磨了1个小时我都没有搞出来，哎，难受，最大的问题就是代码的时间复杂度太高了，将近O(n^3)，肯定过不了。

这里参考其他大佬的题解理解一下。

就是用集合保存arr1所有的前缀，比如arr1 = [1, 22, 33] , 那么arr1的所有前缀为(1, 2, 22, 3, 33); 然后在遍历arr2，判断当前元素的前缀是否在集合里面，如果不在直接break，在的话，就计算最长公共前缀

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:

        st = set()
        for s in map(str, arr1):
            for i in range(1, len(s)+1):
                st.add(s[:i])
        
        ans = 0
        for s in map(str, arr2):
            for i in range(1, len(s) + 1):
                if s[:i] not in st:
                    break
                ans = max(ans, len(s[:i]))
        return ans

100217. 出现频率最高的素数

后面有空再做

100208. 统计前后缀下标对 II

这道题是100212的一个升级版，难度为困难，暂时不做，能力还不够。

补充：需要理解一下力扣的一个分数机制。

第一次双周赛 1500 -> 84.1 ->1415.9，我做对了一道题，为什么会扣我84.1分？

第二次周赛：1415.9 +2.9 -> 1418.8 这是啥情况，虽然都是只作对了一道题。

第三次周赛：不知道这次过后我的排名是多少

第 384 场周赛

今天在吃席的时候无意中看到这个力扣的周赛，因为今天是周天，加上自己也没有准备就没有参加，回来无意中又看到了，就把这几道题看一下。

100230. 修改矩阵（2 分）

给你一个下标从 0 开始的整数矩阵 matrix，新建一个从 0 开始的名为 answer 的矩阵，是 answer 与 martix 相等，接着将其中每个值为-1 的元素替换成所在列的最大元素。

我们不用新建 answer，我们直接在 martix 上面修改，判断出每列的最大元素 mx，在判断是否有-1 元素，如果有，就将-1 替换成 mx。

Java

class Solution {
    public int[][] modifiedMatrix(int[][] matrix) {

        for(int i=0;i<matrix[0].length;i++){
            int mx = 0;
            for(int[] row: matrix){
                mx = Math.max(mx, row[i]);
            }
            for(int[] row: matrix){
                if(row[i] == -1){
                    row[i] = mx;
                }
            }
        }
        return matrix;
    }
}

Python3

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        for i in range(len(matrix[0])):
            mx = 0
            for row in matrix:
                mx = max(mx, row[i]);
            for row in matrix:
                if row[i] == -1:
                    row[i] = mx
        return matrix

100186. 匹配模式数组的子数组数目 I （4 分）

100219. 回文字符串的最大数量（5 分）

3036. 匹配模式数组的子数组数目 II（6 分）

第 383 场周赛

说明，本文章的题目由简单到困难，现在的水平只能解决一下简单的题目😂。

我么有参加本次周赛，只是赛后将题目拿出来看一看，做一做。

3028. 边界上的蚂蚁

蚂蚁在边界上，题目给出一个非零整数数组nums，蚂蚁从第一个元素开始按照nums[i]进行移动，nums[i] > 0 向右移动nums[i], nums[i]<0向左移动-nums[i]，求蚂蚁返回边界的次数。

这个题目，蚂蚁在边界上，向左向右移动，我们只需要求得蚂蚁向右移动的补数加上向左移动的步数等于0，就表示蚂蚁返回了边界。

Java

class Solution {
    public int returnToBoundaryCount(int[] nums) {
        int walk = 0, ans =  0;
        for(int i: nums){
            walk += i;
            if(walk == 0){
                ans++;
            }
        }
        return ans;
    }
}

Python3

class Solution:
    def returnToBoundaryCount(self, nums: List[int]) -> int:
        side, count = 0, 0  # 初始化边界的位置，以及返回的次数
        for i in nums:
            # 表示回到了有边界
            if side + i == 0:   # 向右移动加上向左移动等于0，就表示返回到边界一次
                count += 1
            side += i  
        return count

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var returnToBoundaryCount = function(nums) {
    var ans = 0, sum=0;
    for(var i of nums){
        sum += i;
        if(sum === 0){
            ans++;
        }
    }
    return ans;
};

JavaScript知识点

1、js中的foreach语法是for(var i of nums){}，连接词是of，不想java、python中是in

Changelog

Last Updated: View All Changelog

3d2e0-
feat(wiki): algo: 算法总结
On 3/30/25

力扣2024周赛题题解

第402场周赛（20240616考）

第401场周赛（20240609考）

第 400 场周赛 （20240602考）

100230. 修改矩阵 （2 分）

100186. 匹配模式数组的子数组数目 I （4 分）

100219. 回文字符串的最大数量（5 分）

3036. 匹配模式数组的子数组数目 II（6 分）

求求了，快滚去学习！！！

第 400 场周赛（20240602考）

100230. 修改矩阵（2 分）