KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u<sub>1</sub>, v<sub>1</sub>), (u<sub>2</sub>, v<sub>2</sub>), ..., (u<sub>k</sub>, v<sub>k</sub>) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]


Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]


Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]


Constraints:

1 <= nums1.length, nums2.length <= 10<sup>5</sup> -10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup>
nums1 and nums2 both are sorted in ascending order. 1 <= k <= 1000

注意事项：

  1. 类似于BFS模板，只不过是将queue换成heap。
  2. 将两数和加入到heap中，而不是下标的和(粗心)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
OFFSET = [(0, 1), (1, 0)]
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
	heap, res = [(nums1[0] + nums2[0], 0, 0)], []
	visited = set([0, 0])
	while heap:
		node = heapq.heappop(heap)
		res.append([nums1[node[1]], nums2[node[2]]])
		if len(res) == k:
			break
		for _dx, _dy in OFFSET:
			_x, _y = node[1] + _dx, node[2] + _dy
			if _x < len(nums1) and _y < len(nums2) and (_x, _y) not in visited:
				heapq.heappush(heap, (nums1[_x] + nums2[_y], _x, _y))
				visited.add((_x, _y))
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

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


Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]


Constraints: 1 <= nums.length <= 200
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup> -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求四数和等于target。这些数值结果排序后不能重复。

解题思路：

类似于3sum，但需要更加一般化。用递归。不能用求所有笛卡尔积版的Two sum，会TLE。

解题步骤：

N/A

注意事项：

  1. k_sum接口含k_sum(nums, target, k), 基础case为two_sum, 遍历nums每个元素，若重复跳过，将(子数组，target-nums[i], k-1)递归，返回结果拼接
  2. two_sum也是遇到重复元素跳过，若等于target，要左右指针均移动

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
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
	nums.sort()
	return self.k_sum(nums, target, 4)

def k_sum(self, nums, target, k):
	if k == 2:
		return self.two_sum(nums, target)
	# assume 3 sum
	res = []
	for i in range(len(nums)):
		if i >= 1 and nums[i - 1] == nums[i]: # remember
			continue
		sub_res = self.k_sum(nums[i + 1:], target - nums[i], k - 1)
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, target):
	i, j, res = 0, len(nums) - 1, []
	while i < j:
		if (i >= 1 and nums[i - 1] == nums[i]) or nums[i] + nums[j] < target:
			i += 1
		elif (j + 1 < len(nums) and nums[j] == nums[j + 1]) or nums[i] + nums[j] > target:
			j -= 1
		else:
			res.append([nums[i], nums[j]]) # remember to use list rather than tuple
			i += 1 # remember
			j -= 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example 1:



Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.


Example 2:

Input: root = [1], target = 1, k = 3
Output: []


Constraints:

The number of nodes in the tree is in the range [1, 500]. 0 <= Node.val <= 500
All the values Node.val are unique. target is the value of one of the nodes in the tree.
* 0 <= k <= 1000

算法思路：

有三种情况，都容易忽略： 1. 儿子节点 2. 所有父节点路劲上 3. 兄弟节点路径上。而第三种情况要搜另一边的儿子节点（左右不确定）要用visited记录，而且不一定是父亲的兄弟节点，可能爷爷的非父亲的儿子节点。
既然不是单向搜索，不妨转换为图，然后用计算距离BFS模板，只要用map来记录某节点的父亲节点或者增加一个域。BFS中for neighbor in [node.left, node, right, node.parent]

注意事项：

  1. root的parent是None，所以从root去赋值parent，而不是从parent root给儿子赋parent
  2. Line 13 node.left, node.right, node.parent都可能为None，所以Line14要加not neighbor
  3. BFS从target开始而不是root

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
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
	if not root:
		return []
	self.dfs(root, None)
	queue, visited, distance_to_tgt,  = collections.deque([target]), set([target]), collections.defaultdict(int)
	distance_to_tgt[target], res = 0, []
	while queue:
		node = queue.popleft()
		if distance_to_tgt[node] == k:
			res.append(node.val)
		if distance_to_tgt[node] > k:
			break
		for neighbor in [node.left, node.right, node.parent]:
			if not neighbor or neighbor in visited:  # remember not neighbor
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance_to_tgt[neighbor] = distance_to_tgt[node] + 1
	return res

def dfs(self, root, parent):
	if not root:
		return None
	root.parent = parent
	'''if root.left:
		root.left.parent = root
	if root.right:
		root.right.parent = root'''
	self.dfs(root.left, root)  # remember to pass parent
	self.dfs(root.right, root)

算法分析：

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

Posted on Edited on Disqus:

LeetCode 003 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.

Example 2:

**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.

Example 3:

**Input:** s = "pwwkew"
**Output:** 3
**Explanation:** The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

**Input:** s = ""
**Output:** 0

Constraints:

  • 0 <= s.length <= 5 * 10<sup>4</sup>
  • s consists of English letters, digits, symbols and spaces.

题目大意：

求最长不重复子串。

解题思路：

HashMap和滑动窗口法，利用HashMap来记录这个窗口中所有字符的下标，该窗口中所有字符都不重复。
start_idx表示窗口的左界，而i是右界。左界=上次一次出现该字符的下标和目前左界的较大值，
因为Map中的某些字符可能已经不在窗口中，我没有把它从窗口中去掉，而是用start_idx来限制。

要计算长度就要先计算start_idx，步骤：

  1. 计算start_idx
  2. 计算长度

注意事项：

  1. start_idx和前值比较，且只有当字符在map中才更新start_idx

Python代码：

1
2
3
4
5
6
7
8
9
def lengthOfLongestSubstring(self, s: str) -> int:
	start_idx, max_len = 0, 0
	char_map = {}
	for i in range(len(s)):
		if s[i] in char_map:
			start_idx = max(start_idx, char_map[s[i]] + 1)
		max_len = max(max_len, i - start_idx + 1)
		char_map[s[i]] = i
	return max_len

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]


Example 2:

Input: nums = []
Output: []


Example 3:

Input: nums = [0]
Output: []


Constraints:

0 <= nums.length <= 3000 -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

算法思路：

N/A

注意事项：

  1. 先排序
  2. 结果要去重，用i, j, k指针比较前一个元素，若相等指针移动跳过，k是比较后一个元素
  3. 注意指针移动，等于target两指针都要移动，若与前一元素相等，相应指针移一位，要避免死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSum(self, nums: List[int]) -> List[List[int]]:
	nums.sort()
	res = []
	for i in range(len(nums)):
		if i > 0 and nums[i] == nums[i - 1]:
			continue
		sub_res = self.two_sum(nums, i + 1, -nums[i])
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, start, target):
	j, k, res = start, len(nums) - 1, []
	while j < k:
		if (j > start and nums[j] == nums[j - 1]) or nums[j] + nums[k] < target:
			j += 1
		elif (k < len(nums) - 1 and nums[k] == nums[k + 1]) or nums[j] + nums[k] > target:
			k -= 1
		elif nums[j] + nums[k] == target:
			res.append([nums[j], nums[k]])
			j += 1
			k -= 1
	return res

Java代码：

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
public List<List<Integer>> threeSum2(int[] nums) {
	List<List<Integer>> re = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return re;
	Arrays.sort(nums);
	for(int i = 0; i < nums.length - 2; i++) {
		if(i > 0 && nums[i] == nums[i-1])
			continue;
		twoPointers(nums, i + 1, nums.length - 1, -nums[i], re);
	}
	return re;
}

void twoPointers(int[] nums, int left, int right, int target, List<List<Integer>> re) {
	int leftOri = left, rightOri = right;
	while(left < right) {
		if(left > leftOri && nums[left] == nums[left-1]) {
			left++;
			continue;
		}
		if(right < rightOri && nums[right] == nums[right + 1]) {
			right--;
			continue;
		}
		
		if(nums[left] + nums[right] == target) 
			re.add(Arrays.asList(-target, nums[left++], nums[right--]));
		else if(nums[left] + nums[right] < target)
			left++;
		else 
			right--;
	}
}

算法分析：

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

Free mock interview