KK's blog

LeetCode

<div>

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

<pre>Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 </pre>

Example 2:

<pre>Input: coins = [2], amount = 3 Output: -1 </pre>

Example 3:

<pre>Input: coins = [1], amount = 0 Output: 0 </pre>

Example 4:

<pre>Input: coins = [1], amount = 1 Output: 1 </pre>

Example 5:

<pre>Input: coins = [1], amount = 2 Output: 2 </pre>

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2<sup>31</sup> - 1
• 0 <= amount <= 10<sup>4</sup>

</div>

题目大意：

求兑换硬币的最小个数

解题思路：

用数值->个数DP模板

注意事项：

1. amount为0时候，返回0，表示不用coin也能满足，属于合法情况, dp[0] = 0(第二步)
2. 返回值，若dp[-1]为初始值，表示无解，返回-1(第5步)
3. 实现中dp[i] = min(dp[i], dp[i - j] + 1), +1在min内而不是min外。
4. 此题内外循环顺序不重要，跟LeetCode 518 Coin Change 2有区别

Python代码：

1
2
3
4
5
6
7
8
9

def coinChange(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(len(dp)):
			if i + coin <= amount:
				dp[i + coin] = min(dp[i + coin], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

算法分析：

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

LeetCode

<div>Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order. Example 1:

<pre>Input: s = "owoztneoer" Output: "012" </pre>

Example 2:

<pre>Input: s = "fviefuro" Output: "45" </pre>

Constraints: * 1 <= s.length <= 10<sup>5</sup> * s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]. * s is guaranteed to be valid.</div>

题目大意：

数字用英语单词表示如12 -> onetwo, 但打乱顺序otwone. 求如何获得原数字

算法思路：

统计每个字母的个数，根据个数来决定数字
规律见代码： 有些字母但唯一的，如two，w可以知道数字含2
但有些字母是多个数字的和如s，six和seven都含有s，减去用上述的six的个数就知道seven的个数

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
27
28

def originalDigits(self, s: str) -> str:
	char_to_num = {
		'z': '0',
		'w': '2',
		'u': '4',
		'x': '6',
		'g': '8',
		'o': '1',  # decided by previous keys
		'h': '3',  # decided by previous keys
		'f': '5',  # decided by previous keys
		's': '7',  # decided by previous keys
		'i': '9',  # decided by previous keys
	}
	res = []
	char_to_freq = collections.defaultdict(int)
	for char in s:
		char_to_freq[char] += 1
	char_to_freq['o'] -= char_to_freq['z'] + char_to_freq['w'] + char_to_freq['u']
	char_to_freq['h'] -= char_to_freq['g']
	char_to_freq['f'] -= char_to_freq['u']
	char_to_freq['s'] -= char_to_freq['x']
	char_to_freq['i'] -= char_to_freq['x'] + char_to_freq['g'] + char_to_freq['f']
	for char, num in char_to_num.items():
		if char in char_to_freq and char_to_freq[char] > 0:
			for _ in range(char_to_freq[char]):
				res.append(num)
	res.sort()
	return ''.join(res)   

算法分析：

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

LeetCode

<div>

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

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

Example 2:

<pre>Input: nums = [1,2,3], k = 3 Output: 2 </pre>

Constraints:

• 1 <= nums.length <= 2 * 10<sup>4</sup>
• -1000 <= nums[i] <= 1000
• -10<sup>7</sup> <= k <= 10<sup>7</sup>

</div>

题目大意：

子数组和等于k的个数

解题思路：

子数组和第一时间想到presum，而数组元素之间关系也应该想到two sum

解题步骤：

N/A

注意事项：

1. 加0到presum中或者加0到sum_to_idx字典中，确保presum本身可以等于k
2. 数组含负数，也即是presum中可以含有多个相同的值，所以sum_to_idx要转成频数而不是下标。如[-1, 1, -1, 1], k=0结果为4，而不是3, 容易漏整个数组和

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# presum = [0, 1, 2, 3], target = presum[i] - k = presum[j]
# add 0 to presum so that presum[i] = k
# [0, -1, 0, -1, 0]
# [0, 1]
def subarraySum(self, nums: List[int], k: int) -> int:
	presum, res = [0], 0 #
	for n in nums:
		presum.append(presum[-1] + n) # 0, 1, 2, 3
	sum_to_idx = collections.defaultdict(int)
	for i in range(len(presum)): #
		if presum[i] - k in sum_to_idx: # 1-1
			res += sum_to_idx[presum[i] - k] #4
		sum_to_idx[presum[i]] += 1 # {0:2, -1:2, 2:2}
	return res

算法分析：

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

LeetCode

<div>

Sometimes people repeat letters to represent extra feeling. For example:

• "hello" -> "heeellooo"
• "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

• For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

Example 1:

<pre>Input: s = "heeellooo", words = ["hello", "hi", "helo"] Output: 1 Explanation: We can extend "e" and "o" in the word "hello" to get "heeellooo". We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more. </pre>

Example 2:

<pre>Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output: 3 </pre>

Constraints:

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s and words[i] consist of lowercase letters.

</div>

题目大意：

Cisco常考题
定义了一种富于表现力的单词，就是说某个字母可以重复三次或以上，叫stretchy
找给定的单词列表中的单词可以成为stretchy单词的个数

解题思路：

统计每个字符的个数，然后比较对应每个字符个数

解题步骤：

N/A

注意事项：

1. Line 13的条件，若个数不等，word的字符个数大于stretchy的字符个数(word不能删除字符)，或者stretchy的个数小于3，就不满足

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
27

def expressiveWords(self, s: str, words: List[str]) -> int:
	res = 0
	s_count = self.get_consecutive_count(s)
	for word in words:
		char_count = self.get_consecutive_count(word)
		if len(char_count) != len(s_count):
			continue
		for i in range(len(s_count)):
			char_s, count_s = s_count[i]
			char_w, count_w = char_count[i]
			if char_w != char_s:
				break
			if count_s != count_w and (count_w > count_s or count_s < 3): # remember
				break
			if i == len(s_count) - 1:
				res += 1
	return res

def get_consecutive_count(self, s):
	s += ' '
	s_count, count = [], 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			s_count.append((s[i - 1], count))
			count = 0
		count += 1
	return s_count

算法分析：

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

LeetCode

<div>

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example 1:

<pre>Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3] </pre>

Example 2:

<pre>Input: nums = [], target = 0 Output: 0 </pre>

Example 3:

<pre>Input: nums = [0], target = 0 Output: 0 </pre>

Constraints:

• n == nums.length
• 0 <= n <= 3500
• -100 <= nums[i] <= 100
• -100 <= target <= 100

</div>

题目大意：

找三数和小于target的组合个数

解题思路：

类似于三数和等于target，但当小于target时，直接求个数，类似于LeetCode 315 Count of Smaller Numbers After Self。

解题步骤：

N/A

注意事项：

1. res不是+1而是right - left

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def threeSumSmaller(self, nums: List[int], target: int) -> int:
	if len(nums) < 3:
		return 0
	nums.sort()
	res = 0
	for i in range(len(nums) - 2):
		left, right = i + 1, len(nums) - 1
		while left < right:
			if nums[i] + nums[left] + nums[right] < target:
				res += right - left # remember
				left += 1
			else:
				right -= 1
	return res

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度O(1)