KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

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


Example 2:

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


Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]


Example 4:

Input: nums = [1]
Output: [1]


Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 100

题目大意：

下一个全排列数

解题思路：

N/A

解题步骤：

  1. 找到从后往前升序的第一个非升序数，如135864的5
  2. 找到从后往前比步骤1中大的数，调换，如6，变成136854
  3. 后边部分按升序排列或者做reverse(更高效)

注意事项：

  1. Python语法问题： reverse子列表，跟倒序遍历数组一样，要指明前后边界，前面边界值更大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 135864 -> 136854 -> 136458
# 1355864 -> 1356458
# 99
def nextPermutation(self, nums: List[int]) -> None:
	to_be_swapped_index, greater_index = -1, -1
	for i in range(len(nums) - 2, -1, -1):
		if nums[i] < nums[i + 1]: # 5 < 8
			to_be_swapped_index = i # 2
			break
	if to_be_swapped_index == -1:
		nums.sort()
		return nums
	for i in range(len(nums) - 1, to_be_swapped_index, -1): #
		if nums[to_be_swapped_index] < nums[i]: # 5 < 6
			greater_index = i # 4
			break # 136854
	nums[to_be_swapped_index], nums[greater_index] = nums[greater_index], nums[to_be_swapped_index]
	# nums[to_be_swapped_index + 1:] = sorted(nums[to_be_swapped_index + 1:]) # 136458
	nums[to_be_swapped_index + 1:] = nums[:to_be_swapped_index:-1]
	return nums

算法分析：

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

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是单词长度

Free mock interview