KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10<sup>9</sup>.

Example 1:



Input: m = 3, n = 7
Output: 28


Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down


Constraints:

* 1 <= m, n <= 100

题目大意：

求矩阵路径总数

解题思路：

求个数用DP，递归式：

1
dp[i][j] = dp[i-1][j] + dp[i][j-1]

解题步骤：

N/A

注意事项：

  1. 初始值dp[1] = 1而不是dp[0] = 1因为第二行的第一格不能加左边的虚拟格=1
  2. range(m)不是range(len(m))
  3. 优化空间用一维

Python代码：

1
2
3
4
5
6
7
def uniquePaths(self, m: int, n: int) -> int:
	dp = [0] * (n + 1)
	dp[1] = 1 # remember not dp[0] = 1
	for i in range(m): # remember no len(m)
		for j in range(1, len(dp)):
			dp[j] += dp[j - 1]
	return dp[-1]

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Posted on Edited on Disqus:

LeetCode



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).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Example 1:



Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right


Example 2:



Input: obstacleGrid = [[0,1],[0,0]]
Output: 1


Constraints:

m == obstacleGrid.length n == obstacleGrid[i].length
1 <= m, n <= 100 obstacleGrid[i][j] is 0 or 1.

题目大意：

求矩阵路径总数。有障碍

解题思路：

求个数用DP，递归式：

1
2
dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacle[i][j-1] == 0
         = 0                       if obstacle[i][j-1] == 1

解题步骤：

N/A

注意事项：

  1. obstacleGrid[i][j-1], j-1因为dp从1开始, 但i不是，因为dp不含i。

Python代码：

1
2
3
4
5
6
7
8
9
10
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
	dp = [0] * (len(obstacleGrid[0]) + 1)
	dp[1] = 1
	for i in range(len(obstacleGrid)):
		for j in range(1, len(dp)):
			if obstacleGrid[i][j - 1] == 0:
				dp[j] += dp[j - 1]
			else:
				dp[j] = 0
	return dp[-1]

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Posted on Edited on Disqus:

LeetCode



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.

Example 1:



Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.


Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12


Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 200 0 <= grid[i][j] <= 100

题目大意：

求矩阵最短路径和。只能向下向右走。

解题思路：

递归式：

1
dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + grid[i - 1][j - 1]

解题步骤：

N/A

注意事项：

  1. 初始值为最大值，dp[0][1] = dp[1][0] = 0确保左上格正确。
  2. 模板四点注意事项

Python代码：

1
2
3
4
5
6
7
8
# dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + grid[i - 1][j - 1]
def minPathSum(self, grid: List[List[int]]) -> int:
	dp = [[float('inf') for _ in range(len(grid[0]) + 1)] for _ in range(len(grid) + 1)]
	dp[0][1] = dp[1][0] = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
	return dp[-1][-1]

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Posted on Edited on Disqus:

LeetCode



Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


Example 2:

Input: nums = [0,0,0], target = 1
Output: 0


Constraints:

3 <= nums.length <= 1000 -1000 <= nums[i] <= 1000
* -10<sup>4</sup> <= target <= 10<sup>4</sup>

题目大意：

三数和最接近target

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 此题不需去重，若等于target可直接返回

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def threeSumClosest(self, nums: List[int], target: int) -> int:
	nums.sort()
	res = float('inf')
	for i in range(len(nums)):
		left, right = i + 1, len(nums) - 1
		while left < right:
			temp = nums[i] + nums[left] + nums[right]
			if abs(temp - target) < abs(res - target):
				res = temp
			if temp < target:
				left += 1
			elif temp > target:
				right -= 1
			else:
				return target
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode



You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.


Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].


Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.


Constraints:

nums1.length == m + n nums2.length == n
0 <= m, n <= 200 1 <= m + n <= 200
-10<sup>9</sup> <= nums1[i], nums2[j] <= 10<sup>9</sup>

*Follow up: Can you come up with an algorithm that runs in O(m + n) time?

题目大意：

合并两有序数组，最后结果储存在第一个数组

解题思路：

从后往前合并

解题步骤：

N/A

注意事项：

  1. i从m - 1而不是len(nums1) - 1开始，m和n是数组实际长度。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
	i, j, k = m - 1, n - 1, len(nums1) - 1
	while i >= 0 and j >= 0:
		if nums1[i] > nums2[j]:
			nums1[k] = nums1[i]
			k -= 1
			i -= 1
		else:
			nums1[k] = nums2[j]
			k -= 1
			j -= 1
	while i >= 0:
		nums1[k] = nums1[i]
		k -= 1
		i -= 1
	while j >= 0:
		nums1[k] = nums2[j]
		k -= 1
		j -= 1

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1)

Free mock interview