KK's blog

LeetCode 2089 Find Target Indices After Sorting Array

Posted on 2022-10-02 Disqus:

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:

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

Example 2:

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

Example 3:

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

Constraints:

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

题目大意：

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

解题思路：

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

解题步骤：

标准binary search

注意事项：

N/A

Python代码：

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代码：

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 791 Custom Sort String

Posted on 2022-03-19 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

注意事项：

Python代码：

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)

LeetCode 426 Convert Binary Search Tree to Sorted Doubly Linked List

Posted on 2022-03-19 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

注意事项：

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

Python代码：

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)

LeetCode 408 Valid Word Abbreviation

Posted on 2022-03-19 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 ubstitutio n") "sub4u4" ("sub stit u tion")
"12" ("substitution") "su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)

The following are not valid abbreviations: "s55n" ("s ubsti tutio 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题

解题步骤：

注意事项：

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

Python代码：

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)

LeetCode 921 Minimum Add to Make Parentheses Valid

Posted on 2022-03-16 Disqus:

LeetCode

A parentheses string is valid if and only if:

It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(**(**)))" or a closing parenthesis to be "())**)**)".

Return the minimum number of moves required to make s valid.

Example 1:

Input: s = “())”
Output: 1

Example 2:

Input: s = “(((“
Output: 3

Constraints:

1 <= s.length <= 1000 s[i] is either '(' or ')'.

题目大意：

最小加括号数使得配对

Stack解题思路(推荐)：

跟Leetcode 1249一样。括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

解题步骤：

注意事项：

Python代码：

def minAddToMakeValid(self, s: str) -> int:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	return len(stack)

算法分析：

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

统计算法II解题思路：

类似于Leetcode 032 Longest Valid Parentheses的统计算法。用这两种情况来写即可： ()), )(. 若左括号数left出现负数，根据第一个规律，重设left，计入res

Python代码：

def minAddToMakeValid2(self, s: str) -> int:
	left, res = 0, 0
	for char in s:
		if char == '(':
			left += 1
		else:
			left -= 1
			if left < 0:
				res += 1
				left = 0
	return res + abs(left)

算法分析：

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