链接：LeetCode

[Leetcode]2325. 解密消息

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
2. 将替换表与普通英文字母表对齐，形成对照表。
3. 按照对照表 替换 message 中的每个字母。
4. 空格 ' ' 保持不变。

• 例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。
  返回解密后的消息。

模拟遍历即可。

class Solution {
    public String decodeMessage(String key, String message) {
        char start = 'a';
        HashMap<Character, Character> hash = new HashMap<>();
        for(char keyChar:key.toCharArray()) {
            if(keyChar == ' ') continue;
            else if(hash.containsKey(keyChar)) continue;
            else {
                hash.put(keyChar, start);
                start = (char)(start + 1);
            }
        }
        String res = "";
        for(var keyChar:message.toCharArray()) {
            if(keyChar == ' ') res += ' ';
            else res += hash.get(keyChar);
        }
        return res;
    }
}

[Leetcode]2326. 螺旋矩阵 IV

给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。

模拟遍历即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[][] spiralMatrix(int n, int m, ListNode head) {
        int[][] res = new int[n][m];
        HashSet<String> set = new HashSet<>();
        int state = 1;
        int i=0,j=0;
        for(int ind=0; ind< n*m ; ind ++){
            if( head!=null) {
                res[i][j] = head.val;
                head = head.next;
            }
            else {
                res[i][j] = -1;
            }
            set.add(""+i+"_"+j);
            if(state == 1 && (j == m-1 || set.contains(""+i+"_"+(j+1)))) state ++;
            if(state == 2 && (i==n-1 || set.contains(""+(i+1)+"_"+j))) state ++;
            if(state == 3 && (j == 0 || set.contains(""+i+"_"+(j-1)))) state ++;
            if(state == 4 && (i == 0 || set.contains(""+(i-1)+"_"+j))) state = 1;
            if(state == 1) j++;
            else if(state == 2) i++;
            else if(state == 3) j--;
            else i--;
        }
        return res;
    }
}

[Leetcode]2327. 知道秘密的人数

在第 1 天，有一个人发现了一个秘密。
给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 \(10^9 + 7\) 取余 后返回。

动态规划。
只需要统计第i天新增的人数就好了，然后知道秘密的总人数其实就等于从最后一天往前推forget天的人数和。
每一个第i天知道秘密的人，都对[i+delay,i+forget)这个区间有贡献，从前往后推即可,时间复杂度\(O（n^2）\)。
可以采用前缀和优化时间，最终时间复杂度\(O（n）\)

class Solution1 {
    private static final int MOD = (int)1E9+7;
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n+1];
        dp[1] = 1;
        for(int i=1;i<n+1;++i) {
            for(int j=i+delay; j<Math.min(i+forget,n+1); ++j) {
                dp[j] += dp[i]%MOD;
            }
        }
        long res = 0;
        for(int i=0;i<forget;++i) {
            res += dp[n-i];
        }
        return (int)(res%MOD);
    }

    public int peopleAwareOfSecret2(int n, int delay, int forget) {
        long[] dp = new long[n+1];
        long[] diff = new long[n+1];
        dp[0] = 0;
        diff[1] = 1;
        diff[2] = -1;
        for(int i=1;i<n+1;++i) {
            dp[i] = dp[i-1] + diff[i];
            if(i+delay < n+1) diff[i+delay] += dp[i]%MOD;
            if(i+forget < n+1) diff[i+forget] -=  dp[i]%MOD;
        }
        long res = 0;
        for(int i=0;i<forget;++i) {
            res += dp[n-i] % MOD;
        }
        return (int)(res%MOD);
    }
}

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

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。
请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 \(10^9 + 7\) 取余 后返回。
如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

记忆化搜索。我们可以遍历每个格子，以这个格子为起点，往上下左右四个方向前进，如果下一个格子的值比当前格子的值大，则可以前进。定义 \(f[i][j]\) 表示以第 i 行第 j 列的格子为起点的路径数。由于路径中的数字严格递增，状态无后效性，可以用动态规划解决。
我们把四个方向可以走的格子所对应的状态 \(f[i'][j']\) 累加起来，再加上 1，即当前格子组成的长度为 1 的路径，即为 \(f[i][j]\)。
另外，利用java PriorityQueue的特性，我们也可以从小到大出发,查找每个点周围有多少个点比当前点小。

class Solution {
    final static int MOD = (int)1E9 + 7;
    final static int[][] directions = new int[][] {{1,0},{-1,0},{0,1},{0,-1}};
    public int countPaths(int[][] grid) {
        int res = 0, n = grid.length, m = grid[0].length;
        int[][] memo = new int[n][m];
        for(int i=0;i<n;++i) Arrays.fill(memo[i], -1);

        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                res = (res + dfs(grid, memo, i, j)) % MOD;
            }
        }
        return res % MOD;
    }

    public int dfs(int[][] grid, int[][] memo, int i, int j) {
        if(memo[i][j] != -1) return memo[i][j];
        int res = 0, n = grid.length, m = grid[0].length;
        memo[i][j] = 1;
        for(var dir:directions) {
            int inext = i+dir[0], jnext = j+dir[1];
            if(inext<0 || jnext<0 || inext>n-1 || jnext>m-1 || grid[inext][jnext] <= grid[i][j]) continue;
            memo[i][j] = (memo[i][j]+dfs(grid, memo, inext, jnext)) % MOD;
        }
        return memo[i][j]% MOD;
    }

    // DP
    public int countPaths2(int[][] grid) {
        int res = 0, n = grid.length, m = grid[0].length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->b[2]-a[2]);
        int[][] dp = new int[n][m];
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                queue.add(new int[]{i,j,grid[i][j]});
            }
        }
        while(!queue.isEmpty()) {
            int[] popVal = queue.poll();
            int i = popVal[0],j=popVal[1],val=popVal[2];
            dp[i][j] = 1;
            for(var dir:directions) {
                int inext = i+dir[0], jnext=j+dir[1];
                if(inext<0 || jnext<0 || inext>n-1 || jnext>m-1 || grid[inext][jnext] <= grid[i][j]) continue;
                dp[i][j] = (dp[i][j] + dp[inext][jnext]) % MOD;
            }
            res = (res+dp[i][j]) % MOD;
        }
        return res;
    }
}

参考：LeetCode