编辑距离

坐标 72. Edit Distance ，这一题要计算两个字符串的编辑距离，通俗来讲就是字符串“abc”编辑成字符串“abb”至少所需要的操作次数，显然来看这里需要将字符c转化为字符b，也就是一次编辑次数。

这里直接使用动态规划分析，通过建模令计算数组dp[i][j]，表示字符串A从0到i的子串和字符串B从0到j的子串的编辑距离。

使用上述例子分析A="abc",B="abb"。

i=0,j=0 ; A="",B=""，编辑距离为0

i=1,j=0；A="a",B=""，编辑距离为1

i=0,j=1；A="",B="a"，编辑距离为1

i=1,j=1；A="a",B="a",编辑距离为0

....

i=2,j=2；A="ab",B="ab",编辑距离为0

i=2,j=3；A=“ab",B="abb",编辑距离为1

i=3,j=2；A="abc",B="ab",编辑距离为1

i=3,j=3；A="abc",B="abb",编辑距离为1

由此我们可以总结，如果一个字符串A->B，它所需要的最小编辑距离应该为:

f[i][j] = 1+min{f[i-1][j],f[i][j-1],f[i-1][j-1]} 当A[i] != B[j]的时候

f[i][j] = f[i-1][j-1] 当A[i] == B[j]的时候

/**
 * 72. Edit Distance hard
 *
 * Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
 *
 * You have the following 3 operations permitted on a word:
 *
 * Insert a character
 * Delete a character
 * Replace a character
 */
public class EditDistance {
    /**
     * Example :
     * Input: word1 = "horse", word2 = "ros"
     * Output: 3
     * Explanation:
     * horse -> rorse (replace 'h' with 'r')
     * rorse -> rose (remove 'r')
     * rose -> ros (remove 'e')
     */
    public void test(){
        String s1 = "horse";
        String t1 = "ros";
        // 3
        System.out.println(minDistance(s1,t1));
    }


    /**
     * dp[i][j] for s[0:i] t[0:j]
     *
     * Dp("horse","ros")
     *  = 1 + min{Dp("horse","ro"),Dp("hors","ros"),Dp("hors","ro")}
     *        = 1+ min{Dp("horse","r"),Dp("hors","ro"),Dp("hors","r")} ||
     *        1+ min{Dp("hors","ro"),Dp("hor","ros"),Dp("hors","ro")} ||
     *        1+ min{Dp("hors","r"),Dp("hor","ro"),Dp("hor","r")}
     *        ...
     * dp[i][j] = dp[i-1][j-1] , s[i]==t[j]
     * dp[i][j] = min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]} + 1
     */
    public int minDistance(String s, String t) {
        int[][] dp = new int[s.length()+1][t.length()+1];
        for(int i=0;i<s.length()+1;i++)
            dp[i][0] = i;
        for(int j=0;j<t.length()+1;j++)
            dp[0][j] = j;
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[i].length;j++){
                dp[i][j] = s.charAt(i-1)==t.charAt(j-1)?dp[i-1][j-1]:1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
            }
        }
        return dp[s.length()][t.length()];
    }
}

子段回文

坐标 131. Palindrome Partitioning
将字符串所有回文切分输出。
很显然，这里是排列的一种，需要使用递归进行切分。

/**
 * 回文子串切分
 * 131. Palindrome Partitioning
 * Given a string s, partition s such that every substring of the partition is a palindrome.

 * Return all possible palindrome partitioning of s.

 * Input: "aab"
 * Output:
 * [
 * ["aa","b"],
 * ["a","a","b"]
 * ]
 * Created by MacBook on 2019/12/14.
 */
public class PalindromePartitioning {
    public void test() {
        System.out.println(partition("aab"));
        System.out.println(partition("a"));
        System.out.println(partition("bb"));
        System.out.println(partition("cdd"));
    }
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.isEmpty()){
            return result;
        }
        recursion(s,new ArrayList<>(),result);
        return result;
    }
    private void recursion(String s,List<String> each,List<List<String>> result){
        if(s.isEmpty()){
            result.add(new ArrayList<>(each));
        }else {
            for(int i=1;i<=s.length();i++){
                String sub = s.substring(0,i);
                if(!validPalindrome(sub)){
                    continue;
                }
                each.add(sub);
                recursion(s.substring(i),each,result);
                each.remove(each.size()-1);
            }
        }
    }
    private boolean validPalindrome(String s){
        int i=0;
        int j=s.length()-1;
        while (i<j) {
            if (s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}

最大直方图

坐标 84. Largest Rectangle in Histogram
计算直方图中围成的最大矩形
使用一种非常有意思的方法，单调栈法
维护一个单调递增的栈，直到得到比栈顶元素更小的输入，就会处理栈中的数据；当栈为空时候，说明弹出元素是(0,i)中的最矮矩阵，所以是乘以i，当栈不为空时候，需要计算从i到弹出下标的横向长度乘以弹出元素高度（heights[cur]*(i-stack.peek()-1)）。

    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0){
            return 0;
        }
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=0;i<heights.length;i++){
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int cur = stack.pop();
                maxArea = Math.max(maxArea,heights[cur]*(stack.isEmpty()?i:i-stack.peek()-1));
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int area = heights[stack.pop()] * (stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);

        }
        return maxArea;
    }