KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]


Example 2:

Input: n = 1
Output: [“()”]


Constraints:

* 1 <= n <= 8

题目大意：

产生n对括号的所有可能

算法思路：

DFS填位法，运用括号定律1： 左括号数 >= 右括号数，也就是左括号剩余数 < 右括号剩余数

注意事项：

  1. 复杂度的计算

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def generateParenthesis(self, n: int) -> List[str]:
	res = []
	self.dfs(n, n, '', res)
	return res

def dfs(self, left_paren_left, right_paren_left, path, res):
	if left_paren_left == 0 and right_paren_left == 0:
		res.append(path)
		return
	if left_paren_left > 0:
		path += '('
		self.dfs(left_paren_left - 1, right_paren_left, path, res)
		path = path[:-1]
	if right_paren_left > 0 and left_paren_left < right_paren_left:
		path += ')'
		self.dfs(left_paren_left, right_paren_left - 1, path, res)
		path = path[:-1]

算法分析：

n个括号，有2n位，时间复杂度为Catalan数O[C(n,2n)/n+1]，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode



Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.


Example 2:

Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.


Example 3:

Input: s = “”
Output: 0


Constraints:

`0 <= s.length <= 3 104*s[i]is‘(‘, or‘)’`.

题目大意：

最长括号对数。

Stack算法思路(推荐)：

括号题优先考虑用Stack。由于只有单种括号，只需考虑两种不合法情况。
三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空)
难点： 1. 用下标存于stack，方便计算长度。不合法的保留栈中，这样不合法之间的距离-1就是合法的长度

注意事项：

  1. Stack存了左右括号，不只存左括号，所以Line 7要验证栈顶为左括号
  2. 循环后头尾加-1和s长度，方便头尾计算

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestValidParentheses(self, s: str) -> int:
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		if s[i] == ')':
			if stack and s[stack[-1]] == '(':  # remember
				stack.pop()
			else:
				stack.append(i)

	# ())(()) # ())
	stack.insert(0, -1)
	stack.append(len(s))
	max_len = 0
	while len(stack) > 1:
		index = stack.pop()
		max_len = max(max_len, index - stack[-1] - 1)
	return max_len

算法分析：

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

DP算法II解题思路：

注意事项：

  1. 答案用max_len
  2. 条件s[i - 1 - dp[i - 1] - 1]和递归式dp[i - dp[i - 1] - 2]不能越界
  3. 递归式要加dp[i - dp[i - 1] - 2]，dp[..]”(“dp..[]”)” 就是第一个递归式，容易忽略

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# dp[i] = max -> dp[i-2] + 2 if s[i-2:i] == ()
#             -> dp[i-1] + 2 + dp[i-1-dp[i-1]-2] if s[i-1-dp[i-1]-1]== ( and s[i-1] == )
def longestValidParentheses2(self, s: str) -> int:
	dp = [0] * (len(s) + 1)
	max_len = 0  # remember
	for i in range(2, len(dp)):
		dp[i] = max(dp[i], dp[i - 2] + 2 if s[i - 2:i] == '()' else 0)
		prev_dp = 0  # remember
		if i - dp[i - 1] - 2 >= 0:
			prev_dp = dp[i - dp[i - 1] - 2]
		# remember i - 1 - dp[i - 1] - 1 >= 0
		dp[i] = max(dp[i], dp[i - 1] + 2 + prev_dp if i - 1 - dp[i - 1] - 1 >= 0 and s[i - 1 - dp[i - 1] - 1] == '(' and s[i - 1] == ')' else 0)
		max_len = max(max_len, dp[i])
	return max_len

算法分析：

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

统计算法III解题思路：

括号题另一个常用思路是用统计左右括号数。维护四个变量left, right, res, max_len
当左括号小于右括号数（第一个规律）：重设全部变量
当左括号等于右括号数（第二个规律）：满足两个条件，可以计算res。重设left，right，准备计算下一轮res。不重设res，因为可以连续如()()

注意事项：

  1. 上述情况只覆盖了()),不能覆盖((), 因为左括号数在每一位永远都不会等于右括号数。所以旋转180度再做一次。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def longestValidParentheses3(self, s: str) -> int:
	max_len = self.get_max_len(s)
	res = []
	PARENTHESES_DICT = {'(': ')', ')': '('}
	for char in s:
		res.append(PARENTHESES_DICT[char])
	max_len = max(max_len, self.get_max_len(res[::-1]))
	return max_len

def get_max_len(self, s: str) -> int:
	max_len = res = left = right = 0
	for char in s:
		if char == '(':
			left += 1
		if char == ')':
			right += 1
			if left < right:
				left = 0
				right = 0
				res = 0
			if left == right:  # (())), ()()
				res += left * 2
				max_len = max(max_len, res)
				left = 0
				right = 0
	return max_len

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4


Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1


Example 3:

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


Constraints:

1 <= nums.length <= 5000 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
All values of nums are unique. nums is an ascending array that is possibly rotated.
* -10<sup>4</sup> <= target <= 10<sup>4</sup>

题目大意：

有序数组旋转了几位，求target的下标

算法思路：

N/A

注意事项：

  1. 四种情况： 左半有序且target在这个有序区间内，左边有序的所有其他情况，右半有序且target在这个有序区间，右半有序的所有其他情况

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def search(self, nums: List[int], target: int) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if nums[start] < nums[mid] and nums[start] <= target <= nums[mid]:  # remember
			end = mid
		elif nums[start] < nums[mid]:
			start = mid
		elif nums[mid] < nums[end] and nums[mid] <= target <= nums[end]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int search(int[] nums, int target) {
	if(nums == null || nums.length == 0)
		return -1;
	
	int start = 0, end = nums.length - 1;
	while(start + 1 < end) {
		int mid = start + (end - start) / 2;
		if(nums[mid] > nums[start]) { // the left segment is increasing
			// pay attention to equal 
			if(nums[start] <= target && target <= nums[mid]) //the [start, mid] is increasing
				end = mid;
			else
				start = mid;
		} 
		else { 
			if(nums[mid] <= target && target <= nums[end]) // the [mid, end] is increasing
				start = mid;
			else
				end = mid;
		}
	}
	
	if(nums[start] == target)
		return start;
	if(nums[end] == target)
		return end;
	
	return -1;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]


Example 2:

Input: strs = [“”]
Output: [[“”]]


Example 3:

Input: strs = [“a”]
Output: [[“a”]]


Constraints:

1 <= strs.length <= 10<sup>4</sup> 0 <= strs[i].length <= 100
* strs[i] consists of lowercase English letters.

题目大意：

对同字母不同序单词分组

算法思路：

N/A

注意事项：

  1. list(id_to_words.values())要转成list

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
	id_to_words = collections.defaultdict(list)
	for word in strs:
		id_to_words[self.get_id(word)].append(word)
	return list(id_to_words.values())  # remember to convert it to list

def get_id(self, word):
	char_to_freq = collections.Counter(word)
	res = ''
	for c in string.ascii_lowercase:
		if c in char_to_freq:
			res += c + str(char_to_freq[c])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(n+m). n是单词个数，m是单词长度

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


Example 2:

Input: nums = [1]
Output: 1


Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23


Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题目大意：

最大子数组和

算法思路：

dp[i] = max(dp[i-1] + nums[i], nums[i])

注意事项：

  1. 引入全局最大的res，因为递归式是以末位为结尾的最大和

Python代码：

1
2
3
4
5
6
7
8
9
10
# dp[i] = max(dp[i-1] + nums[i], nums[i])
def maxSubArray(self, nums: List[int]) -> int:
	sum, res = -sys.maxsize, -sys.maxsize
	for num in nums:
		if sum > 0:
			sum += num
		else:
			sum = num
		res = max(sum, res)
	return res

算法分析：

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

Free mock interview