竞赛题 2022-6-26

6104. 统计星号

class Solution:
    def countAsterisks(self, s: str) -> int:

        return "".join(s.split("|")[::2]).count("*")

        flag, ans = 1, 0
        for c in s:
            if c == "*": ans += flag
            elif c == "|": flag = 1 - flag
        return ans
        
        a = s.split('|')
        return sum(a[i].count("*") for i in range(0, len(a), 2))

6107. 不同骰子序列的数目

第 i 次扔骰子的结果受第 (i - 1) 次和第 (i - 2) 次结果的限制。因此我们维护 f(i, a, b) 表示第 i 次扔骰子的结果为 a，第 (i - 1)次的结果为 b 的方案数。

为了转移，我们枚举第 (i - 2) 次的结果 c。根据题意，a，b，c 需要满足以下要求：

三个数互不相等；
gcd(a, b) = gcd(b, c) = 1。
只要同时满足这两个条件，f(i - 1, b, c) 就能转移给 f(i, a, b)。

第 300 场周赛

2325. 解密消息

class Solution {
    
    public String decodeMessage(String key, String message) {
    
        Map<Character, Character> map = new HashMap<>();
        int i = 97;
        for(char c : key.toCharArray()){
    
            if(c == ' ') continue;
            if(!map.containsKey(c)) map.put(c, (char)(i++));
        }
        map.put(' ', ' ');
        StringBuilder sb = new StringBuilder();
        for(char c : message.toCharArray()){
    
            sb.append(map.get(c));
        }
        return sb.toString();
    }
}

2326. 螺旋矩阵 IV

class Solution {
    
    public int[][] spiralMatrix(int m, int n, ListNode head) {
    
        int[][] ans = new int[m][n];
        for(int[] row : ans) Arrays.fill(row, -1);
        int up = 0, down = m - 1, left = 0, right = n - 1;
        while(head != null){
    
            for(int j = left; head != null && j <= right; j++){
    
                ans[up][j] = head.val;
                head = head.next;
            }
            up++;
            for(int i = up; head != null && i <= down; i++){
    
                ans[i][right] = head.val;
                head = head.next;
            }
            right--;
            for(int j = right; head != null && j >= left; j--){
    
                ans[down][j] = head.val;
                head = head.next;               
            }
            down--;
            for(int i = down; head != null && i >= up; i--){
    
                ans[i][left] = head.val;
                head = head.next;
            }
            left++;
        }
        return ans;        
    }
}

2327. 知道秘密的人数

f[i] 表示第 i 天新知道秘密的人数。

class Solution {
    
    public int peopleAwareOfSecret(int n, int delay, int forget) {
    
        int mod = 1000000007; 
        long s = 0;
        long[] f = new long[n + 1];
        f[1] = 1;
        for(int i = 2; i <= n; i++){
    
            if(i > delay) s += f[i-delay];
            if(i > forget) s -= f[i-forget];
            f[i] = s % mod;
        }
        long sum = 0;
        for(int i = 0; i < forget; i++){
    
            sum = (sum + f[n - i]) % mod;
        }
        return (int)sum;
    }
}

2328. 网格图中递增路径的数目