KK's blog

LeetCode

<div>

You are given a 0-indexed integer array nums and a target element target.

A target index is an index i such that nums[i] == target.

Return a list of the target indices of nums after sorting nums in non-decreasing order. If there are no target indices, return an empty list. The returned list must be sorted in increasing order.

Example 1:

<pre>Input: nums = [1,2,5,2,3], target = 2 Output: [1,2] Explanation: After sorting, nums is [1,<u>2</u>,<u>2</u>,3,5]. The indices where nums[i] == 2 are 1 and 2. </pre>

Example 2:

<pre>Input: nums = [1,2,5,2,3], target = 3 Output: [3] Explanation: After sorting, nums is [1,2,2,<u>3</u>,5]. The index where nums[i] == 3 is 3. </pre>

Example 3:

<pre>Input: nums = [1,2,5,2,3], target = 5 Output: [4] Explanation: After sorting, nums is [1,2,2,3,<u>5</u>]. The index where nums[i] == 5 is 4. </pre>

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i], target <= 100

</div>

题目大意：

如果数组已排序，求target对应的所有下标。

解题思路：

这道题是Easy题，也是Q&A中被问到的，Binary Search不是最优解，但是可以用它作为解法研究。

解题步骤：

标准binary search

注意事项：

N/A

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
29
30
31
32

def targetIndices(self, nums: List[int], target: int) -> List[int]:
	sorted_nums = sorted(nums)
	target_index = self.binary_search(sorted_nums, target)
	res = []
	print(target_index)

	for i in range(target_index - 1, -1, -1):
		if sorted_nums[i] == target:
			res.append(i)
	res = res[::-1]
	for i in range(target_index, len(sorted_nums)):
		if sorted_nums[i] == target:
			res.append(i)
	return res

def binary_search(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		else:
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

算法II解题思路：

first_postition & last position

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def targetIndices(self, nums: List[int], target: int) -> List[int]:
	sorted_nums = sorted(nums)
	target_upper_index = self.last_position(sorted_nums, target)
	target_lower_index = self.first_position(sorted_nums, target)
	res = [i for i in range(target_lower_index, target_upper_index + 1)]
	return [] if target_upper_index == -1 else res

def first_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid

	if nums[start] == target:
		return start
	elif nums[end] == target:
		return end
	else:
		return -1

def last_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:  # Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

算法分析：

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

LeetCode

<div>

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

Example 1:

<pre>Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.</pre>

Example 2:

<pre>Input: nums = [1,2,1,3,5,6,4] Output: 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.</pre>

Constraints:

• 1 <= nums.length <= 1000
• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
• nums[i] != nums[i + 1] for all valid i.

</div>

题目大意：

找数组极大值

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. mid - 1 >= 0

Python代码：

1
2
3
4
5
6
7
8
9

def findPeakElement(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid >= 1 and nums[mid - 1] < nums[mid]:
			start = mid
		else:
			end = mid
	return start if nums[start] > nums[end] else end

1
2
3
4
5
6
7
8
9

def findValleyElement(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid >= 1 and nums[mid - 1] >= nums[mid]:
			start = mid
		else:
			end = mid
	return start if nums[start] <= nums[end] else end

算法分析：

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

LeetCode

<div>

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

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

Example 1:

<pre>Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] </pre>

Example 2:

<pre>Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] </pre>

Example 3:

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

Constraints:

• 0 <= nums.length <= 10<sup>5</sup>
• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
• nums is a non-decreasing array.
• -10<sup>9</sup> <= target <= 10<sup>9</sup>

</div>

题目大意：

求有序数列中元素等于target的第一个和最后一个下标

解题思路：

用模板

解题步骤：

N/A

注意事项：

1. 数组为空的情况要返回-1

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
29
30
31
32
33
34
35
36
37
38
39
40

def searchRange(self, nums: List[int], target: int) -> List[int]:
	first = self.first_position(nums, target)
	last = self.last_position(nums, target)
	return [first, last]

def last_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			start = mid
	if nums[end] == target:
		return end
	if nums[start] == target:
		return start
	return -1

def first_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start+ (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1

算法分析：

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

LeetCode

<div>

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring_, return the empty string_ "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

<pre>Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. </pre>

Example 2:

<pre>Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. </pre>

Example 3:

<pre>Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string. </pre>

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10<sup>5</sup>
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?</div>

题目大意：

最短摘要：给定s和t两个字符串，求在s中包含所有t的字符的最短子串。这个结果可以包含不在t的字符，某个字符数量也可以多于t中的字符但不能少于。

解题思路：

提到window substring就用滑动窗口或者同向双指针。

解题步骤：

N/A

注意事项：

1. 用同向双指针模板。用map来统计t的字符频率，用unique_count统计满足条件唯一字符个数。while的条件为unique_count达到了map的大小。
2. while里面的统计与while外面的统计本质一样，但相反。若s中某字符多于s中的，map为负值，left指针右移时，负值会变回正值。

Python代码：

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

def minWindow(self, s: str, t: str) -> str:
	t_char_to_count = collections.Counter(t)
	left, unique_count, min_len, res = 0, 0, float('inf'), ''
	for i in range(len(s)):
		if s[i] in t_char_to_count:
			t_char_to_count[s[i]] -= 1
			if t_char_to_count[s[i]] == 0:
				unique_count += 1
		while unique_count == len(t_char_to_count):
			if i - left + 1 < min_len:
				min_len = i - left + 1
				res = s[left:i + 1]
			if s[left] in t_char_to_count:
				t_char_to_count[s[left]] += 1
				if t_char_to_count[s[left]] == 1:
					unique_count -= 1
			left += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(m), n和m分别为s和t的长度

LeetCode

<div>

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

• "s10n" ("s <u>ubstitutio</u> n")
• "sub4u4" ("sub <u>stit</u> u <u>tion</u>")
• "12" ("<u>substitution</u>")
• "su3i1u2on" ("su <u>bst</u> i <u>t</u> u <u>ti</u> on")
• "substitution" (no substrings replaced)

The following are not valid abbreviations:

• "s55n" ("s <u>ubsti</u> <u>tutio</u> n", the replaced substrings are adjacent)
• "s010n" (has leading zeros)
• "s0ubstitution" (replaces an empty substring)

Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

<pre>Input: word = "internationalization", abbr = "i12iz4n" Output: true Explanation: The word "internationalization" can be abbreviated as "i12iz4n" ("i <u>nternational</u> iz <u>atio</u> n"). </pre>

Example 2:

<pre>Input: word = "apple", abbr = "a2e" Output: false Explanation: The word "apple" cannot be abbreviated as "a2e". </pre>

Constraints:

• 1 <= word.length <= 20
• word consists of only lowercase English letters.
• 1 <= abbr.length <= 10
• abbr consists of lowercase English letters and digits.
• All the integers in abbr will fit in a 32-bit integer.

</div>

题目大意：

验证第二字符串是否第一字符串的一个种简写形式，用数字代替字符串部分长度

解题思路：

Easy题

解题步骤：

注意事项：

1. 用内外while循环如quicksort的不推荐的算法，内循环的条件一定要复制外循环的条件j < len(abbr)
2. 题目条件不能含前缀0，包括0本身，若数字第一位为0，就返回False

Python代码：

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

def validWordAbbreviation(self, word: str, abbr: str) -> bool:
	i, j, num = 0, 0, 0
	while i < len(word) and j < len(abbr):
		num_str = ''
		while j < len(abbr) and abbr[j].isdigit(): # remember j < len(abbr)
			num_str += abbr[j]
			j += 1
		if num_str:
			if num_str[0] == '0': # remember
				return False
			i += int(num_str)
		elif word[i] != abbr[j]:
			return False
		else:
			i += 1
			j += 1
	return False if i != len(word) or j != len(abbr) else True

算法分析：

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