leetcode

今天刷了7道力扣，总结一下

动态规划： 

(26条消息) 告别动态规划，连刷40道动规算法题，我总结了动规的套路_Hollis Chuang的博客-CSDN博客 3个步骤——>

意思就是定义历史记录，记录我们曾经的计算，这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤。

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

class Solution {
     /**
     * 单词转换
     */
    public int minDistance(String word1, String word2) {
        //1.先初始化得到一个word1->word2的一个数组存放最少操作次数
        int n=word1.length();
        int m=word2.length();
        int [][]dp=new int[n+1][m+1];
 
        //2.然后初始化单词转换最局部的情况,0->1=之前00的转换次数+1
        for (int i = 1; i <= m; i++) {
            dp[0][i]=dp[0][i-1]+1;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0]=dp[i-1][0]+1;
        }
 
        //3.然后找规律，求dp[n][m]
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                /**
                 * 此时i-1，j-1位置上的两个word相等时，ij就是i-1 j-1的情况
                 */
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    //所有的情况都是基于i-1,j-1开始进行考虑的
                    dp[i][j]=Math.min(Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1),dp[i][j-1]+1);
                }
            }
        }
        return dp[n][m];
    }
}

class Solution {
    /**
     * 青蛙跳台
     * 利用递归的局部分割思想，大->小，以至划分慢慢求出局部最大
     */
    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 1000_000_007;
        }
        return dp[n];
    }
 
}

class Solution {
       public int uniquePaths(int m, int n) {
        //1.先特殊条件判断
        if (m<=0||n<=0){
            return 0;
        }
        //2.初始化记录
        int[][] dp = new int[m][n];
        
        //3.对1行1列初始化
        for (int i = 0; i < m; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i]=1;
        }  
        
        //4.对dp[m][n]进行推到
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
      return dp[m-1][n-1];    
    }
 
}

练习题

1.合并两个有序数组

class Solution {
     public static void merge(int[] nums1, int m, int[] nums2, int n) {
            int p1 = 0, p2 = 0;
            int[] sorted = new int[m + n];
            int cur;
           while(p1<m||p2<m){
             if(p1==m){
               cur=nums2[p2++];
             }
             if(p2==n){
               cur=nums1[p1++];
             }
             if(nums1[p1]<nums2[p2]){
               cur=nums1[p1];
             }
             if(nums1[p1]>nums2[p2]){
               cur=nums2[p2]; 
             }
 
           }
              for (int i = 0; i != m + n; ++i) {
                nums1[i] = sorted[i];
            }
        }
}

2.判断是否属于子序列

class Solution {
     /**双指针
     * 判断是否为子序列
     */
    public static boolean isSubsequence(String s, String t) {
       int n=s.length(),m=t.length();
       //定义两指针的路程
        int i=0,j=0;
        //进行遍历匹配
        while(i<n&&j<m){
            if(s.charAt(i)==t.charAt(j)){
                i++;
            }
            j++;
        }
        return i==n;
    }
}

 3.同构字符串，判断两个字符串能否通过某种关系得到彼此

public static boolean JudgeEqual(String s,String b){
        for (int i = 0; i < s.length(); i++) {
            //进行判断，看s和t的下标是否相等,用indexOf得到字符第一次出现的位置，不等于就说明不能映射
            if(s.indexOf(s.charAt(i))!=b.indexOf(b.charAt(i))){
                //当两个字符位置不相等说明为false
                return false;
            }
 
        }
       return true;
    }
 
    public boolean isIsomorphic2(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
 
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }