记录七月在线：
解题套路：
1.找出递推关系式
2.初始值
3.优化空间复杂度:主要是每行或每列进行更新，所以可将二维数组转换为以为数组重复利用。
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.
思路：
根据描述可建立递推关键式：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;
//节约内存目的是为了得出最后一个dp[n-1],重复空间可复用
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
找出数组中的最大子数组的值。
思路：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
找出数组中的最大子数组的值。
思路:抽象出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对应，如果值不同用replace操作
dp[i][j-1]+1：将i+1与j对应，在word1 中remove操作（相当于在word2 j下标前 insert）
dp[i-1][j]+1：将i与j+1对应，在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];
}
}
空间复杂度优化后:
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
思路：对应每个item的高度，计算出与周边矩形能围成的最大矩形，于是问题转化为对应每一个item，找出左右两边连续的不小于item高度的矩形块数，最后算出每一个item可围成的最大矩形。
简化：将对应item的向左向右遍历简化为一个栈，栈内元素是高度递增矩形的item，一旦新入栈的item高度小于栈内item，则栈内item出栈。
推导：栈内两个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
网友评论