KK's blog

每天积累多一些

0%

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

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

用排序作为id

注意事项：

  1. sorted(word)返回的是排好序的字母列表，要用join转回单词
  2. list(anagrams_dict.values())要转成list

Python代码：

1
2
3
4
5
6
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
	anagrams_dict = collections.defaultdict(list)
	for word in strs:
		_id = "".join(sorted(word))
		anagrams_dict[_id].append(word)
	return list(anagrams_dict.values())

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)

Posted on Edited on Disqus:

LeetCode



There are n gas stations along a circular route, where the amount of gas at the i<sup>th</sup> station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i<sup>th</sup> station to its next (i + 1)<sup>th</sup> station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.


Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.


Constraints:

gas.length == n cost.length == n
1 <= n <= 10<sup>5</sup> 0 <= gas[i], cost[i] <= 10<sup>4</sup>

题目大意：

N/A

算法思路：

只要总gas >= 总cost，就总有一个点满足gas-cost为非负

注意事项：

  1. 先判断不合法的情况sum(gas) < sum(cost)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
	if sum(gas) < sum(cost):
		return -1
	sum_gas, sum_cost, pos = 0, 0, 0
	for i in range(len(gas)):
		sum_gas += gas[i]
		sum_cost += cost[i]
		if sum_gas < sum_cost:
			pos = i + 1
			sum_gas = 0
			sum_cost = 0
	return pos

算法分析：

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

Free mock interview