KK's blog

每天积累多一些

0%

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)

Posted on Edited on Disqus:

LeetCode



Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'. Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'. The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

Input: path = “/home/“
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.


Example 2:

Input: path = “/../“
Output: “/“
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.


Example 3:

Input: path = “/home//foo/“
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.


Constraints:

1 <= path.length <= 3000 path consists of English letters, digits, period '.', slash '/' or '_'.
* path is a valid absolute Unix path.

题目大意：

简化路径，遇.表示当前目录不做事，遇..表示到上一个目录

解题思路：

路径类似于括号题，利用括号题模板

解题步骤：

N/A

注意事项：

  1. edge case /../ 表示若stack为空，就不pop。if stack不能加到elif token == ‘..’中
  2. 遇到..返回到上层目录

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def simplifyPath(self, path: str) -> str:
	path += '/'
	token, stack = '', []
	for c in path:
		if c == '/':
			if token == '.':
				pass
			elif token == '..':
				if stack: # remember
					stack.pop()
			elif token:
				stack.append(token)
			token = ''
		else:
			token += c
	return '/' + '/'.join(stack)

算法分析：

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

Free mock interview