leetcode 2325 解密消息
    (哈希表) O(n+m)

    • 遍历 key 字符串，使用哈希表记录映射关系。
    • 遍历 message 字符串，使用哈希表解密字符串。

    时间复杂度

    • 遍历 key 和 message 字符串各一次，故时间复杂度为 O(n+m)。

    需要额外空间存储哈希表。（注意代码风格）

    1. class Solution {
    2.     public String decodeMessage(String key, String message) {
    3.         StringBuilder result = new StringBuilder();
    4.         char [] chs = key.toCharArray();
    5.         HashMap<Character,Character> map = new HashMap<>();
    6.         int mod = 0;
    7.         for (char ch:chs ){
    8.             if (ch!=' '&& !map.containsKey(ch)){
    9.                 map.put(ch, (char) ('a'+mod++));
    10.             }
    11.         }
    12.         char []chw = message.toCharArray();
    13.         for (int i = 0; i < chw.length; i++) {
    14.             if (chw[i]!=' '){
    15.                 result.append(map.get(chw[i]));
    16.             }else{
    17.                 result.append(" ");
    18.             }
    19.         }
    20.         return result.toString();
    21.     }
    22. }

    leetcode 2326 螺旋矩阵 IV
    参考螺旋打印矩阵题目，
    (模拟) O(mn)

    • 螺旋遍历矩阵，遍历过程中同时移动当前访问链表的指针，并填充数字。

    时间复杂度

    • 遍历数组一次，遍历链表一次，故总时间复杂度为 O(mn)

    空间复杂度

    • 需要 O(mn)的额外空间存储答案。

      1. /**
      2. * Definition for singly-linked list.
      3. * public class ListNode {
      4. *     int val;
      5. *     ListNode next;
      6. *     ListNode() {}
      7. *     ListNode(int val) { this.val = val; }
      8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      9. * }
      10. */
      11. class Solution {
      12.   public int[][] spiralMatrix(int m, int n, ListNode head) {
      13.       int[][] result = new int[m][n];
      14.       if(n == 0 || m==0) return result;
      15.       for (int i = 0; i <m ; i++) {
      16.           for (int j =0;j<n;j++){
      17.               result[i][j] = -1;
      18.           }
      19.       }
      21.       // 定义四个偏移量
      22.       int[] dx = {0,1,0,-1},dy = {1,0,-1,0};
      23.       boolean[][] st = new boolean[m][n];
      24.       for(int i = 0,x = 0,y = 0,d = 0;i < n*m;i++){
      25.           result[x][y] = head.val;
      26.           st[x][y] = true;
      27.           int a = x + dx[d],b = y + dy[d];
      28.           if(a < 0 || a >= m || b < 0 || b >= n || st[a][b] == true){
      29.               d = (d + 1) % 4; // 使d在0 1 2 3间循环
      30.               a = x + dx[d];
      31.               b = y + dy[d];
      32.           }
      33.           x = a;
      34.           y = b;
      35.           head =head.next;
      36.           if (head==null){
      37.               break;
      38.           }
      39.       }
      40.       return result;
      41.   }
      42. }

      leetcode 2327 知道秘密的人数
      思路：(动态规划) O(n)

    • 设 f(i)表示第 i天 新增知道秘密人数。

    • 初始时，f(1)=1，其余为 0待定。
    • 转移时，对于 f(i)，新增的人数为第 [i−forget+1,i−delay]区间内知道秘密的人数的和。
    • 最终答案为[n−forget+1,n] 区间内知道秘密的人数的和。
    • 为了降低时间复杂度，可以考虑使用前缀和数组快速求出区间和。不妨令 f(i) 重新表示为第 1 天到第 i天 新增 知道秘密人数的前缀和，则转移时，仅需要 f(i)=f(i−1)+f(i−delay)−f(i−forget)。最终答案为 f(n)−f(n−forget)。

    时间复杂度

    • 状态数为 O(n)，转移时间为常数，故时间复杂度为 O(n)。

    空间复杂度

    • 需要 O(n) 的额外空间存储状态。

    知识点：DP+前缀和+区间和

    1. class Solution {
    2.     static int mod = 1000000000+7;
    3.     public int peopleAwareOfSecret(int n, int delay, int forget) {
    4.         int f[] = new int[n+1];
    5.         f[0]=0;
    6.         f[1]=1;
    7.         for(int i =2;i<=n;i++){
    8.             f[i] = f[i-1];
    9.             f[i] =(f[i]+ (i>delay?f[i-delay]:0))%mod;
    10.             f[i] = (f[i]-(i>forget?f[i-forget]:0))%mod;
    11.         }
    12.         return ((f[n]-f[n-forget])%mod+mod)%mod;
    13.     }
    14. }

    leetcode 2328 网格图中递增路径的数目 （我当然不会了）
    (记忆化搜索) O(mn)

    • 设状态 f(x,y)表示以 (x,y)为终点的路径个数。由于拓扑关系比较复杂，所以需要通过记忆化搜索的方式遍历状态。
    • 初始时，所有点都可以直接作为终点，故f(x,y)=1。
    • 转移时，对于 (x,y)，枚举其四个方向，如果存在合法的前驱方向 (tx,ty)（不越界且满足 grid(x,y)>grid(tx,ty)），递归处理 (tx,ty)后，转移 f(x,y)=f(x,y)+f(tx,ty)。
    • 最终答案为 ∑f(x,y)。

    时间复杂度

    • 状态数共 O(mn)，转移时间为常数，故总时间复杂度为 O(mn)。

    空间复杂度

    • 需要 O(mn)的额外空间存储状态数和递归调用的系统栈。

      1. class Solution {
      2.   static int mod = 1000000000+7;
      3.   static int[] dx = {0,1,0,-1};
      4.   static int[] dy = {1,0,-1,0};
      5.   int m,n;
      6.   int [][] res;
      7.   public int countPaths(int[][] grid) {
      8.       m = grid.length;
      9.       n = grid[0].length;
      10.       res = new int[m][n];
      11.       for(int i = 0; i < m; i++) {
      12.           for(int j = 0; j < n; j++) {
      13.               res[i][j] = -1;
      14.           }
      15.       }
      16.       int ans = 0;
      17.       for(int i =0;i<m;i++){
      18.           for(int j = 0;j<n;j++){
      19.               ans = (ans+dp(i,j,grid))%mod;
      20.           }
      21.       }
      22.       return ans;
      23.   }
      25.   public int dp(int x,int y ,int[][] grid){
      26.       if(res[x][y]!=-1){
      27.           return res[x][y];
      28.       }
      29.       int r = 1;
      30.       for(int i =0;i<4;i++){
      31.           int tx = x+dx[i];
      32.           int ty = y+dy[i];
      33.           if(tx<0||tx>=m||ty<0||ty>=n){
      34.               continue;
      35.           }
      36.           if(grid[tx][ty]>=grid[x][y]){
      37.               continue;
      38.           }
      39.           r=(r+dp(tx,ty,grid))%mod;
      40.       }
      41.       res[x][y]=r
      42.       return r;
      43.   }
      44. }