KK's blog

LeetCode

<div>

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:

<pre>Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] </pre>

Example 2:

<pre>Input: strs = [""] Output: [[""]] </pre>

Example 3:

<pre>Input: strs = ["a"] Output: [["a"]] </pre>

Constraints:

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

</div>

题目大意：

对同字母不同序单词分组

算法思路：

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

LeetCode

<div>

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:

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

Example 2:

<pre>Input: nums = [1] Output: 1 </pre>

Example 3:

<pre>Input: nums = [5,4,-1,7,8] Output: 23 </pre>

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.

</div>

题目大意：

最大子数组和

算法思路：

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)

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

Constraints:

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

</div>

题目大意：

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)

LeetCode

<div>

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

<pre>Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. </pre>

Example 2:

<pre>Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. </pre>

Constraints:

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

</div>

算法思路：

N/A

第二刷: f(n) = max{f(n-2)+nums[n-1], f(n-3)+nums[n-1]}, f(n)是以nums[n-1]为结尾必偷的房子，可以选择偷隔一个或隔两个。

Python代码：

1
2
3
4
5
6
7
8
9

def rob(self, nums: List[int]) -> int:
	if len(nums) <= 2:
		return max(nums)
	n = len(nums)
	dp = [0] * (n + 1)
	dp[1], dp[2] = nums[0], nums[1]
	for i in range(3, len(dp)):
		dp[i] = max((dp[i-2]), dp[i-3]) + nums[i-1]
	return max(dp[n], dp[n-1])

初刷: f(n)是以nums[n-1]为结尾不必偷的房子，可以选择偷隔一个或隔两个

注意事项：

1. 循环不是模板中的1开始，而是从2开始，因为i-2>=0

Python代码：

1
2
3
4
5
6

def rob(self, nums: List[int]) -> int:
	dp = [0] * (len(nums) + 1)
	dp[1] = nums[0]
	for i in range(2, len(dp)):
		dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
	return dp[-1]

算法分析：

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

LeetCode

<div>

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

<pre>Input: nums = [1,2,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.</pre>

Example 2:

<pre>Input: nums = [1,3,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [3], range = 3 - 3 = 0 [3], range = 3 - 3 = 0 [1,3], range = 3 - 1 = 2 [3,3], range = 3 - 3 = 0 [1,3,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4. </pre>

Example 3:

<pre>Input: nums = [4,-2,-3,4,1] Output: 59 Explanation: The sum of all subarray ranges of nums is 59. </pre>

Constraints:

• 1 <= nums.length <= 1000
• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

</div>

题目大意：

求所有子数组的最大值最小值之差的和

Stack算法思路：

参考Leetcode 907，分别求子数组最小值的相反数，子数组的最大值，这两个值的和即为所求

注意事项：

1. 最小值用递增栈，最大值用递减栈

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def subArrayRanges(self, nums: List[int]) -> int:
	arr = list(nums)
	arr.insert(0, -sys.maxsize)
	arr.append(-sys.maxsize)
	stack, res, = [], 0
	for i in range(len(arr)):
		while stack and arr[i] < arr[stack[-1]]:
			prev_idx = stack.pop()
			res -= arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
		stack.append(i)

	arr = list(nums)
	arr.insert(0, sys.maxsize)
	arr.append(sys.maxsize)

	for i in range(len(arr)):
		while stack and arr[i] > arr[stack[-1]]:
			prev_idx = stack.pop()
			res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
		stack.append(i)
	return res

算法分析：

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

累计和算法II解题思路：

比暴力法稍优，两重循环覆盖所有子数组[i, j]，每轮循环得到最大最小值，然后O(1)内求该区间内所有最大最小值差值和。

Python代码：

1
2
3
4
5
6
7
8
9

def subArrayRanges(self, nums: List[int]) -> int:
	sum = 0
	for i in range(len(nums) - 1):
		min_value, max_value = nums[i], nums[i]
		for j in range(i + 1, len(nums)):
			min_value = min(min_value, nums[j])
			max_value = max(max_value, nums[j])
			sum += max_value - min_value
	return sum

算法分析：

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