Leetcode7 DFS + dynamic programming + double pointer

DFS 

Ideas ： Traverse the two-dimensional array of Islands , If the current number is 1, Then enter the infection function and count the number of Islands +1

Infection function ： In fact, it is a recursive annotation process , It will connect all connected 1 All marked as 2. Why label ？ This avoids repeated counting during traversal , All of an island 1 All become 2 after , When traversing, there will be no repeated traversal . Suggest students who don't understand draw a picture to see .

class Solution {
    public int numIslands(char[][]grid){
        int islandNum=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
               // There is a position of 1 That's the island dfs Judge 
                if(grid[i][j]=='1'){
                    // recursive 
                    dfs(grid,i,j);
                    islandNum++;
                }
            }
        }
        return islandNum;
    }
    // Recursive function 
    public void dfs(char[][]grid,int i,int j){
        //1. The end condition 
        if(i<0||i>= grid.length||j<0||j>=grid[0].length||grid[i][j]!='1'){
            return;
        }
        
        //2. If the conditions are met, change the number to 2
        grid[i][j]='2';
        //3. recursive 
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}

Dynamic programming

class Solution {
    // The sliding window 
    public int fib(int n) {
     if(n<2) return n;
     int a=0,b=1,c=0;
     for(int i=1;i<n;i++){
       c=a+b;
       a=b;
       b=c;
     }
      return c;
    }
}

The recursive method ：

class Solution {
    public int fib(int n) {
      if(n<2){
          return n;
      }
      return fib(n-1)+fib(n-2);
    }
}

Dynamic programming ：

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

Double pointer （ This problem is not completely understood ,mad Since I can tear this question half a year ago , Now it turns out that the same solution has not been written ） 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        int[] c1 = new int[26], c2 = new int[26];
        for (int i = 0; i < m; i++) c2[p.charAt(i) - 'a']++;
        for (int l = 0, r = 0; r < n; r++) {
            c1[s.charAt(r) - 'a']++;
            if (r - l + 1 > m) c1[s.charAt(l++) - 'a']--;
            if (check(c1, c2)) ans.add(l);
        }
        return ans;
    }
    boolean check(int[] c1, int[] c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}

  Dynamic programming ：
 

class Solution {
    // Dynamic programming , That's sliding the window 
    public int climbStairs(int n) {
    if(n<=2){
      return n;
    }
    //1 and 2 floor 
    int a=1;
    int b=2;
    for(int i=3;i<=n;i++){
       int temp=a+b;
       a=b;
       b=temp;
    }
    return b;
 }
}