KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



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:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]


Example 2:

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


Example 3:

Input: nums = [], target = 0
Output: [-1,-1]


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>

题目大意：

求有序数列中元素等于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)

Posted on Edited on Disqus:

LeetCode



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:

Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.


Example 2:

Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.


Example 3:

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.


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?

题目大意：

最短摘要：给定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的长度

Posted on Edited on Disqus:

LeetCode



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:

Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Explanation: The word “internationalization” can be abbreviated as “i12iz4n” (“i nternational iz atio n”).


Example 2:

Input: word = “apple”, abbr = “a2e”
Output: false
Explanation: The word “apple” cannot be abbreviated as “a2e”.


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.

题目大意：

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

解题思路：

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)

Posted on Edited on Disqus:

LeetCode



Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Example 1:



Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.



Example 2:

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


Constraints:

The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000
All the values of the tree are *unique.

题目大意：

将二叉树变成双向链表，left为父节点，right为儿子节点

解题思路：

类似于LeetCode 114 Flatten Binary Tree to Linked List，先假设左右儿子，已经是双向LL，下面就是将root这个节点插入到两个LL之间其将它们首尾相连

解题步骤：

N/A

注意事项：

  1. 要将左右儿子节点的LL，首尾相连。首尾节点获得要在if语句前，因为右儿子的left会连到root，就找不到它的尾部。首尾相连要发生在最后。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def treeToDoublyList(self, root: 'Node') -> 'Node':
	if not root:
		return None
	if not root.left and not root.right:
		root.left, root.right = root, root
		return root
	left_head = self.treeToDoublyList(root.left)
	right_head = self.treeToDoublyList(root.right)
	# remember this part and order, can't be placed after ifs
	new_head = left_head if left_head else root
	new_tail = right_head.left if right_head else root
	if left_head:
		left_head.left.right, root.left = root, left_head.left
	if right_head:
		root.right, right_head.left = right_head, root
	new_head.left, new_tail.right = new_tail, new_head
	return new_head

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = “cba”, s = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in order, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in order, it can be at any position in the returned string. “dcba”, “cdba”, “cbda” are also valid outputs.


Example 2:

Input: order = “cbafg”, s = “abcd”
Output: “cbad”


Constraints:

1 <= order.length <= 26 1 <= s.length <= 200
order and s consist of lowercase English letters. All the characters of order are unique.

题目大意：

给一个字符串，求这个字符串的一个排列，使得字母顺序按照另一个给定字符串order的顺序。

解题思路：

由限制条件知道，order字母是唯一的，order字母可以重复。所以只要统计s频率，然后按照字母顺序开始重写

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def customSortString(self, order: str, s: str) -> str:
    	char_to_count = collections.Counter(s)
    	res = ''
    	for c in order:
    		if c in char_to_count:
    			res += c * char_to_count[c]
    			char_to_count.pop(c)
    	for c, count in char_to_count.items():
    		res += c * count
    	return res

算法分析：

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

Free mock interview