LeetCode解題鏈接
LeetCode 二叉樹(shù) 題目分類匯總
干貨东跪！LeetCode 題解匯總
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
思路
定義一個(gè) m * n 的矩陣 dp，其中dp[m-1][n-1]代表從出發(fā)點(diǎn)(0, 0)→點(diǎn)(m, n)的路徑個(gè)數(shù)。
- dp[i][0] = 1 (i∈[0, m))
- dp[0][j] = 1 (j∈[0, n))
- dp[m][n] = dp[m][n-1] + dp[m-1][n] (m > 0, n > 0)
優(yōu)化
- 在使用遞歸計(jì)算時(shí)虽填，如果dp[m][n]計(jì)算過(guò)丁恭，就應(yīng)該直接取出結(jié)果，而不是再次計(jì)算斋日。實(shí)際中牲览，可以將dp二維數(shù)組的初始值設(shè)置為-1，如果遞歸過(guò)程中恶守，dp[m][n]!=-1第献，則表示計(jì)算過(guò)對(duì)應(yīng)點(diǎn)的路徑個(gè)數(shù)，直接返回結(jié)果兔港。
- 既然每一行庸毫，計(jì)算一次就沒(méi)有用了，那么是否可以將空間復(fù)雜度降低衫樊？定義dp[m][n]的空間復(fù)雜度是
m * n飒赃，如果只定義一個(gè)dp[m]，則可以將空間復(fù)雜度降低至m科侈。
代碼
利用遞歸载佳，空間復(fù)雜度m * n：
public class Solution {
public int robot(int m, int n, int[][] dp) {
if(m == 0 || n == 0) {
return 1;
}
if(dp[m][n] != -1) {
return dp[m][n];
}
dp[m][n] = robot(m - 1, n, dp) + robot(m, n - 1, dp);
return dp[m][n];
}
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return robot(m - 1, n - 1, dp);
}
}
迭代，空間復(fù)雜度m * n：
public int uniquePaths(int m, int n) {
int[][] grid = new int[m][n];
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(i==0||j==0)
grid[i][j] = 1;
else
grid[i][j] = grid[i][j-1] + grid[i-1][j];
}
}
return grid[m-1][n-1];
}
進(jìn)一步優(yōu)化兑徘，空間復(fù)雜度m：
public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 || j == 0)
dp[j] = 1;
else if(j > 0)
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}
63. Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
思路
和上一題很像刚盈，只不過(guò)增加了一個(gè)限制條件：有些點(diǎn)可能不能走。不能走的點(diǎn)挂脑，dp變成0就好了藕漱。
代碼
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int width = obstacleGrid[0].length;
int[] dp = new int[width];
dp[0] = 1;
for(int[] row : obstacleGrid) {
for(int j = 0; j < width; j++) {
if(row[j] == 1)
dp[j] = 0;
else if(j > 0)
dp[j] += dp[j - 1];
}
}
return dp[width - 1];
}
}
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.
思路
定義一個(gè)二維數(shù)組sum[m][n]，表示從(0, 0)到(m - 1, n - 1)的最小的和崭闲。所以可以得出公式：
- sum[0][n] =
grid[0][0] + grid[0][4] ... + grid[0][n] - sum[m][0] =
grid[0][0] + grid[1][0] ... + grid[m][0] - sum[m][n] = min(sum[m - 1][n], sum[m][n - 1]) + grid[m][n]
sum[m - 1][n - 1] 即為最終結(jié)果肋联。
代碼
public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] sum = new int[m][n];
sum[0][0] = grid[0][0];
for(int i = 1; i < m; i++) {
sum[i][0] += sum[i - 1][0] + grid[i][0];
}
for(int j = 1; j < n; j++) {
sum[0][j] += sum[0][j - 1] + grid[0][j];
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
sum[i][j] += Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
}
}
return sum[m - 1][n - 1];
}
}
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ù)組sum[i]，其中sum[i]表示包括nums[i]的刁俭，nums數(shù)組從0~i的最大連續(xù)和橄仍。
- sum[i] = max(nums[i], sum[i - 1] + nums[i])
- max = max(sum[i], max)
以題干中的數(shù)組[-2,1,-3,4,-1,2,1,-5,4]為例，sum數(shù)組為：
[-2, 1, -2, 4, 3, 5, 6, 1, 5]
- 當(dāng)i=0時(shí)牍戚，sum[0] = -2
- 當(dāng)i=1時(shí)侮繁，sum1 = max(nums1, sum[0] + nums1) = max(1, -2 + 1) = 1
- ……
優(yōu)化
sum[i]中的每一個(gè)數(shù)，都只會(huì)用到一次如孝。所以可以將sum[i]數(shù)組宪哩，變成1個(gè)變量sum即可，sum的含義與sum[i]相同第晰。
代碼
public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) return 0;
int sum = nums[0], max = nums[0];
for(int i = 1; i < nums.length; i++) {
sum = Math.max(nums[i], sum + nums[i]);
max = Math.max(sum, max);
}
return max;
}
}
總結(jié)
對(duì)于動(dòng)態(tài)規(guī)劃的題目锁孟，最重要的一步就是寫(xiě)明遞推公式和初始公式彬祖，緩存計(jì)算的中間結(jié)果，以獲取效率品抽。
