Leetcode Hot100 76-80

细节：

递推公式：
增：dp[i] = dp[i-1][j]+1
删：dp[i] = dp[i][j-1]+1
改：dp[i] = dp[i-1][j-1]+1

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if(m==0)return n;
        if(n==0)return m;
        int dp[][] = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        return dp[m][n];
    }
}

思想：每次在上次能跳到的范围内选择一个能跳的最远的位置作为下次的起跳点

需要边界和最大值两个变量

public int jump(int[] nums) {
        int maxright = 0;//最大可达位置
        int bianjie = 0;//边界
        int times = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //记录该轮能到达的最长位置
            maxright = Math.max(maxright,nums[i]+i);
            //若到达边界，则需要跳下一次，该位置为maxright
            if(i==bianjie){
                bianjie = maxright;
                times++;
            }
        }
        return times;
    }

记录每个字母的最远距离，如果这一串单词的最远距离都在一个right内，就把它加入到list种

class Solution {
    public List<Integer> partitionLabels(String s) {
        int index[] = new int[27];
        //会自动记录字母最远距离
        for (int i = 0; i < s.length(); i++) {
            index[s.charAt(i)-'a'] = i;
        }
        List<Integer> list = new LinkedList<>();
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            right = Math.max(right,index[s.charAt(i)-'a']);
            if(i==right){
                list.add(right-left+1);
                left = right+1;
                right = left;
            }
        }
        return list;
    }
}