初级入门
https://leetcode.com/problems/minimum-path-sum/
求一个方格，左上角到右下角的最短距离
动态规划的经典题型
/**
* @param Integer[][] $grid
* @return Integer
* @brief https://leetcode.com/problems/minimum-path-sum/
*/
function minPathSum($grid) {
$dp = [[]];
$dp[0][0] = $grid[0][0];
for ($i = 1; $i < count($grid); $i++) {
$dp[$i][0] = $grid[$i][0] + $dp[$i - 1][0];
}
for ($i = 1; $i < count($grid[0]); $i++) {
$dp[0][$i] = $grid[0][$i] + $dp[0][$i - 1];
}
for ($i = 1; $i < count($grid); $i++) {
for ($j = 1; $j < count($grid[0]); $j++) {
$dp[$i][$j] = min($dp[$i - 1][$j], $dp[$i][$j - 1]) + $grid[$i][$j];
}
}
return $dp[count($grid) -1][count($grid[0]) - 1];
}
不同路径，机器人走路
https://leetcode.com/problems/unique-paths/
给定一个矩阵，一个机器人从左上角到右下角，求它最多有几种走法,每次只能往右或者往下走动
其中dp[i][j]表示到当前位置不同的走法的个数，然后可以得到递推式为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
/**
* @param Integer $m
* @param Integer $n
* @return Integer
*/
function uniquePaths($m, $n) {
$res = [];
//对于第一列，每个点都只能有一种走法
for ($i = 0; $i < $m; $i++) {
$res[$i][0] = 1;
}
//对于第一行，每个点也只能有一种走法
for ($j = 0; $j < $n; $j++) {
$res[0][$j] = 1;
}
//对于任意一点(i,j)，走法为(i-1,j) + (i,j-1),因为只有这两个点能走到(i,j)这个点
for ($i = 1; $i < $m; $i++) {
for ($j = 1; $j < $n; $j++) {
$res[$i][$j] = $res[$i - 1][$j] + $res[$i][$j - 1];
}
}
return $res[$m - 1][$n - 1];
}
机器人走路加障碍
https://leetcode.com/problems/unique-paths-ii/
这个相对于机器人走路，增加了一个点，在方格中可能存在障碍物，有了障碍物表明机器人无法走到该方格
- 这题看起来没什么，但是暗藏玄机
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] grid = new int[obstacleGrid.length][obstacleGrid[0].length];
//临界条件，在第一个点如果有障碍，其他的格子都走不到了
if (obstacleGrid[0][0] == 1) {
return 0;
}
grid[0][0] = 1;
for (int i = 1; i < grid[0].length; i++) {
if (obstacleGrid[0][i] == 1) {
grid[0][i] = 0;
} else {
//第一行和第一列是依赖上一个格子的走法的
//举一个例子: m = [[0,0,0],[1,0,0],[0,0,0]],此时m[2][0]这个点是一定走不到的，因为m[1][0]有障碍
grid[0][i] = grid[0][i - 1];
}
}
for (int j = 1; j < grid.length; j++) {
if (obstacleGrid[j][0] == 1) {
grid[j][0] = 0;
} else {
grid[j][0] = grid[j - 1][0];
}
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
if (obstacleGrid[i][j] == 1) {
grid[i][j] = 0;
} else {
grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
}
}
}
return grid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
}
Edit Distance
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
1.insert
2.Remove
3.Replace
Examples:
Input: str1 = "geek", str2 = "gesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.
Input: str1 = "cat", str2 = "cut"
Output: 1
We can convert str1 into str2 by replacing 'a' with 'u'.
Input: str1 = "sunday", str2 = "saturday"
Output: 3
Last three and first characters are same. We basically
need to convert "un" to "atur". This can be done using
below three operations.
Replace 'n' with 'r', insert t, insert a
/**
* editDist
* @param $str1
* @param $str2
* @param $m str1的长度
* @param $n str2的长度
* @return int|mixed
*/
function editDist($str1, $str2, $m, $n) {
if ($m == 0) {
return $n;
}
if ($n == 0) {
return $m;
}
if ($str1[$m - 1] == $str2[$n - 1]) {
return $this->editDist($str1, $str2, $m - 1, $n - 1);
}
return 1 + min($this->editDist($str1, $str2, $m, $n - 1), $this->editDist($str1, $str2, $m - 1, $n), $this->editDist($str1, $str2, $m - 1, $n - 1));
}
Trapping Rain Water 收集雨水
https://leetcode.com/problems/trapping-rain-water/submissions/
image.png
两个数组，分别记录i处的左边最高柱子，和右边最高柱子，根据柱子高度和i处的柱子高度来计算盛水容量
public int trap(int[] height) {
int[] leftM = new int[height.length];
int[] rightM = new int[height.length];
int max = 0;
//leftM为当前i的左边最高柱形
for (int i = 0; i < height.length; i++) {
if (max < height[i]) {
max = height[i];
}
leftM[i] = max;
}
//rightM为当前i的右边最高柱形
max = 0;
for (int i = height.length - 1; i >= 0; i--) {
if (max < height[i]) {
max = height[i];
}
rightM[i] = max;
}
int res = 0;
//根据左右的长度，与i出的柱形长度比较，如果能盛水，则加上
for (int i = 0; i < height.length; i++) {
int minL = Math.min(leftM[i], rightM[i]);
if (height[i] > minL) {
continue;
}
res += minL - height[i];
}
return res;
}
word Break
https://leetcode.com/problems/word-break/
给定一个String，和一个Dict，Dict中包含些许英文单词，求这个String是否能被这个Dict中的所有单词拼接起来，即这个String的子串都在这个Dict中
注意，Dict中的单词没有重复，且Dict中的单词可以被重复利用（即:String="applepenapple",Dict=['apple','pen'] 是符合需求的）
example：
String=“leetcode”，Dict=["leet","code"]; return true
网友评论