The 300th weekly match of leetcode (20220703)

6108. Decrypt the message

https://leetcode.cn/problems/decode-the-message/

Ideas ： Simple simulation questions , First, according to the string key Create a comparison table , Then replace according to the comparison table message The characters in the , about key Each character in , It is only added to the comparison table when it is first visited , You can set the initial value to -1 Indicates that it has not been updated

class Solution {
    
    public String decodeMessage(String key, String message) {
    
		 int[] table=new int[26];
		 Arrays.fill(table, -1);
		 int index=0;
		 for(int i=0;i<key.length();i++) {
    
			 if(key.charAt(i)==' ') {
    // Space skipping 
				 continue;
			 }
			 int ascii=key.charAt(i)-'a';// The current character ch Of ascii Code value 
			 if(table[ascii]!=-1) {
    //ch Has joined in table It's in   skip 
				 continue;
			 }
			 table[ascii]=index;// Update cross reference table 
			 index++;
		 }
		 char[] ch=message.toCharArray();
		 for(int i=0;i<ch.length;i++) {
    
			 if(ch[i]==' ') {
    
				 continue;
			 }
			 ch[i]=(char) (table[ch[i]-'a']+'a');// Update according to the comparison table 
		 }
		 return new String(ch);
	 }
}

6111. Spiral matrix IV

https://leetcode.cn/problems/spiral-matrix-iv/

Ideas ： The key point is how to traverse a matrix counterclockwise , Specific ideas can be referred to 59. Spiral matrix II
Put 1-n^2 Replace the data in the linked list with the data in the linked list

/** * 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 m, int n, ListNode head) {
    
		 	int[][] matrix=new int[m][n];
	        int top=0,bottom=m-1,left=0,right=n-1;
	        ListNode cur=head;
	        while(true)
	        {
    
	        	
	            for(int i=left;i<=right;i++) {
    // From left to right 
	            	if(cur!=null) {
    
	            		matrix[top][i]=cur.val;
	            		cur=cur.next;
	            	}else {
    
	            		matrix[top][i]=-1;
	            	}
	            }
	            top++;
	            if(top>bottom)
	                break;
	            for(int i=top;i<=bottom;i++) {
    // From top to bottom 
	            	if(cur!=null) {
    
	            		matrix[i][right]=cur.val;
	            		cur=cur.next;
	            	}else {
    
	            		matrix[i][right]=-1;
	            	}
	            }
	                
	            right--;
	            if(right<left)
	                break;
	            for(int i=right;i>=left;i--) {
    // From right to left 
	            	if(cur!=null) {
    
	            		matrix[bottom][i]=cur.val;
	            		cur=cur.next;
	            	}else {
    
	            		matrix[bottom][i]=-1;
	            	}
	            }
	              
	            bottom--;
	            if(bottom<top)
	                break;
	            for(int i=bottom;i>=top;i--) {
    // From bottom to top 
	            	if(cur!=null) {
    
	            		matrix[i][left]=cur.val;
	            		cur=cur.next;
	            	}else {
    
	            		matrix[i][left]=-1;
	            	}
	            }
	                
	            left++;
	            if(left>right)
	                break;
	        }
	        return matrix;
	  }
	
}

6109. Number of people who know the secret

https://leetcode.cn/problems/number-of-people-aware-of-a-secret/

Ideas ：
Write it down as dp[i] It means the first one i Tianxin knows the number of Secrets , Be careful , It's the new number , Not the total number , When we count the number of new people we know every day , Last statistical interval [n-forget+1,n] The sum of the number of people who newly know the secret in the interval , That is, the total number of people who know the secret , Because other people who know the secret have forgotten

class Solution {
    
    public int peopleAwareOfSecret(int n, int delay, int forget) {
    
        int[] dp=new int[n+1];
        dp[1]=1;
        int mod=(int)(1e9+7);
        for(int i=1;i<=n;i++){
    
            for(int j=1;j<i;j++){
    
                // The first i Tianxin knows that people can be divided into sections [i-forget+1,i-delay] God knows who will tell  
               if(i>=j+delay&&i<j+forget){
    // The first j Tianxin knows that people can tell the first i Man of heaven   You can tell && I haven't forgotten 
                    dp[i]+=dp[j];
                    dp[i]%=mod;
               }
            }
        }
        long ans=0;
        for(int i=n-forget+1;i<=n;i++){
    //[i-forget+1,n] New people in the day n Days have not forgotten 
            ans+=dp[i];
            ans%=mod;
        }
        return (int)ans;
    }
}

6110. The number of incremental paths in the grid graph

https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/

Ideas ： Dynamic programming is also used here , But in general dp It solves problems from the bottom up , Here is top-down problem solving , Recursive solution , Top down dp A memo is usually added , Prevent double counting . Concrete ,dp[i][j] It is expressed as a cell (i,j) The number of paths that meet the increment condition at the end , When calculating in cells (i,j) When the number of paths at the end that meet the increment condition , If you find a cell (i,j) Up, down, left and right of a grid (x,y) The value is less than grid[i][j] Value , explain (i,j) The position can be transferred from this position , So add cells (x,y) The number of paths at the end dp[x][y]

class Solution {
    
    int m,n;
    int[][] grid;
    int[][] memo;
    int[][] dirs={
    {
    0,-1},{
    0,1},{
    -1,0},{
    1,0}};
    int mod=(int)(1e9+7);
    public int countPaths(int[][] grid) {
    
        int ans=0;
        this.grid=grid;
        this.m=grid.length;
        this.n=grid[0].length;
        memo=new int[m][n];
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                ans+=dp(i,j);
                ans%=mod;
            }
        }
        return ans;

    }
    public int dp(int i,int j){
    
        if(memo[i][j]!=0){
    // By location (i,j) The number of paths at the end has been calculated 
            return memo[i][j];
        }
        long ans=1L;// The initial value is 1  because 1 Lattice (i,j) It is also a qualified path 
        for(int[] dir:dirs){
    
            int x=i+dir[0],y=j+dir[1];
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]<grid[i][j]){
    
                ans+=dp(x,y);//(x,y)->(i,j)
                ans%=mod;
            }
        }
        memo[i][j]=(int)ans;
        return memo[i][j];
    }
}
//O(mn)
//O(mn)