記錄七月在線：
解題套路：
1.找出遞推關(guān)系式
2.初始值
3.優(yōu)化空間復(fù)雜度:主要是每行或每列進行更新，所以可將二維數(shù)組轉(zhuǎn)換為以為數(shù)組重復(fù)利用。

leetcode 64

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

思路：
根據(jù)描述可建立遞推關(guān)鍵式：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
解題code：

public class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        //節(jié)約內(nèi)存目的是為了得出最后一個dp[n-1],重復(fù)空間可復(fù)用
        int[] dp = new int[n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i==0){
                    if(j==0)
                    dp[j]=grid[i][j];
                    else
                    dp[j]=dp[j-1]+grid[i][j];
                }else if(j==0){
                    dp[j]=dp[j]+grid[i][j];
                }else{
                    dp[j]=Math.min(dp[j],dp[j-1])+grid[i][j];
                }
            }
        }
        return dp[n-1];
    }
}

leetcode 53

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4]
,the contiguous subarray [4,-1,2,1]
has the largest sum = 6
找出數(shù)組中的最大子數(shù)組的值。
思路：dp[i]=max(dp[i-1]+a[i],a[i]);
解題code：

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int max = dp[0];
        int last = dp[0];
        for(int i = 1;i < nums.length;i++){
            int current=Math.max(last+nums[i],nums[i]);
            last = current;
            if(max < current)
                max = current;
        }
        return max;
    }
}

leetcode 53

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a characterb) Delete a characterc) Replace a character
找出數(shù)組中的最大子數(shù)組的值。
思路:抽象出dp[i][j]表示word1 第i個字符與word2 第j個字符
推出遞推式
dp[i][j]=min(dp[i-1][j-1]+isSame(a[i-1],b[j-1]),dp[i][j-1]+1,dp[i-1][j]+1);
dp[i-1][j-1]+isSame(a[i-1],b[j-1]):如果將i,j對應(yīng)，如果值不同用replace操作
dp[i][j-1]+1：將i+1與j對應(yīng)，在word1 中remove操作（相當(dāng)于在word2 j下標(biāo)前 insert）
dp[i-1][j]+1：將i與j+1對應(yīng)，在word1 i前insert操作
解題code：

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

空間復(fù)雜度優(yōu)化后:

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

leetcode 84

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Paste_Image.png

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]

The largest rectangle is shown in the shaded area, which has area = 10
unit.

For example,Given heights = [2,1,5,6,2,3],return 10
思路：對應(yīng)每個item的高度，計算出與周邊矩形能圍成的最大矩形，于是問題轉(zhuǎn)化為對應(yīng)每一個item，找出左右兩邊連續(xù)的不小于item高度的矩形塊數(shù)，最后算出每一個item可圍成的最大矩形。
簡化：將對應(yīng)item的向左向右遍歷簡化為一個棧，棧內(nèi)元素是高度遞增矩形的item，一旦新入棧的item高度小于棧內(nèi)item，則棧內(nèi)item出棧。
推導(dǎo)：棧內(nèi)兩個item之間的item高度大于兩個item的高度。

解題code：

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length==0)
            return 0;
        int i = 0;
        Stack<Integer> stack = new Stack();
        int max = 0;
        while (i<=heights.length){
            if(stack.isEmpty()||heights[stack.peek()]<=heights[i]){
                stack.push(i);
                i++;
            }else{
                int j = stack.pop();
                max = Math.max(max,heights[j]*(stack.empty() ? i : i - stack.peek()-1));
            }
        }
        if(!stack.isEmpty()){
            int last = stack.peek();
            while(!stack.isEmpty()){
                int j = stack.pop();
                max = Math.max(max,heights[j]*(stack.empty() ? last+1 : last - stack.peek()));
            }
        }
    
        return max;
    }
}

參考

更多 91 97 120 131 132 139 140 152