KK's blog

LeetCode 078 Subsets

Posted on 2022-01-14 Edited on 2022-02-02 Disqus:

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

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

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10
All the numbers of nums are *unique.

题目大意：

求所有子集

解题思路：

组合知识点

解题步骤：

N/A

注意事项：

题目要求结果含空集

Python代码：

def subsets(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

时间复杂度为O(nx2ⁿ)，空间复杂度O(n)

LeetCode 065 Valid Number

Posted on 2022-01-13 Edited on 2022-01-31 Disqus:

LeetCode

A valid number can be split up into these components (in order):

1. A decimal number or an integer.
2. (Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

1. (Optional) A sign character (either '+' or '-').
2. One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = “0”
Output: true

Example 2:

Input: s = “e”
Output: false

Example 3:

Input: s = “.”
Output: false

Constraints:

1 <= s.length <= 20 s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

题目大意：

求合法小数指数形式

类括号法解题思路(推荐)：

有四种symbol，要保证先后关系。

解题步骤：

先写基本框架：

def isNumber(self, s: str) -> bool:
	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
	for char in s:
		if char = '+-':
			if seen_sign:
				return False
			seen_sign = True
		elif char.isdigit():

			seen_num = True
		elif char in 'eE':
			if seen_exp:
				return False
			seen_exp = True
		elif char == '.':
			if seen_dot:
				return False
			seen_dot = True
		else:
			return False
	return True

if语句加入前面字符不能出现什么，每种其他字符过一遍。还有字符必须出现什么，此情况只有一种： e字符前必须有数字
for循环后return语句检查单个字符

注意事项：

有四种symbol：符号，数字，dot，exp。保证先后关系。exp的前后部分是独立的，唯一区别是后部分不能有dot，如1e2.2
实现类似于括号题用if语句来分别处理每种symbol：前面不能出现什么符号(e后面不能出现小数，也就是小数前面不能出现e)，或必须出现什么符号(仅一种情况：e前面必须出现数字)，如1e2. 然后该符号赋True
for循环后检查单个字符且不含数字情况
见解题步骤

Python代码：

def isNumber(self, s: str) -> bool:
	seen_sign, seen_num, seen_exp, seen_dot = False, False, False, False
	for char in s:
		if char in '+-':
			if seen_sign or seen_num or seen_dot:
				return False
			seen_sign = True
		elif char.isdigit():
			seen_num = True
		elif char in 'eE':
			if seen_exp or not seen_num:
				return False
			seen_exp = True
			seen_sign = False
			seen_num = False
			seen_dot = False
		elif char == '.':
			if seen_dot or seen_exp:
				return False
			seen_dot = True
		else:
			return False
	return False if (seen_sign or seen_exp or seen_dot) and not seen_num else True

算法分析：

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

DFA算法II解题思路(不推荐)：

Deterministic Finite Automaton (DFA)状态机，也就是将状态写入一个map中作为config，代码较简洁，但很难想。

算法分析：

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

LeetCode 063 Unique Paths II

Posted on 2022-01-05 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

注意事项：

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

Python代码：

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(n²)，空间复杂度O(n²)

LeetCode 062 Unique Paths

Posted on 2022-01-05 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

注意事项：

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

Python代码：

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(n²)，空间复杂度O(n²)

LeetCode 064 Minimum Path Sum

Posted on 2022-01-05 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

注意事项：

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

Python代码：

# 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(n²)，空间复杂度O(n²)