KK's blog

LeetCode

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:



The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node. listA - The first linked list.
listB - The second linked list. skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at ‘8’
Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at ‘2’
Explanation: The intersected node’s value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints: The number of nodes of listA is in the m.
The number of nodes of listB is in the n. 1 <= m, n <= 3 * 10<sup>4</sup>
1 <= Node.val <= 10<sup>5</sup> 0 <= skipA < m
0 <= skipB < n intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

*Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

题目大意：

求两LL的相交点

解题思路：

类似于LeetCode 1650 Lowest Common Ancestor of a Binary Tree III.

解题步骤：

N/A

注意事项：

1. Python代码：

   1 2 3 4 5 6 7 8 9 10 11 12

   def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: a_set = set() it = headA while it: a_set.add(it) it = it.next it = headB while it: if it in a_set: return it it = it.next return None

算法分析：

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

LeetCode

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [“2”,”4->49”,”51->74”,”76->99”]
Explanation: The ranges are:
[2,2] –> “2”
[4,49] –> “4->49”
[51,74] –> “51->74”
[76,99] –> “76->99”

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

题目大意：

给定一个范围[lower, upper]和数组表示这个范围有的数，求缺失数范围

解题思路：

简单题。也是数学题
公式为:

1

[nums[i-1] + 1, nums[i] - 1]

解题步骤：

N/A

注意事项：

1. 缺失数范围公式为[nums[i-1] + 1, nums[i] - 1], 需要一个函数来处理若范围内仅含一个数或多个数的情况
2. 题目条件lower, upper在数组范围之外，所以不妨将lower, upper加到数组中，同一处理，但是由于lower和upper表示缺失数，而数组表示含有数。所以将lower - 1和upper + 1加到数组
3. 数组可能为空，要特别处理Line 3

Python代码：

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

def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
	if not nums: # remember
		return [self.get_missing_str(lower, upper)]
	res = []
	nums.insert(0, lower - 1)
	nums.append(upper + 1)
	for i in range(1, len(nums)):
		# [nums[i-1] + 1, n - 1]
		if nums[i - 1] + 1 <= nums[i] - 1:
			res.append(self.get_missing_str(nums[i - 1] + 1, nums[i] - 1))
	return res
	
def get_missing_str(self, start, end):
	if start == end:
		return str(start)
	else:
		return str(start) + '->' + str(end)

算法分析：

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

LeetCode

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

题目大意：

求数组中的众数

解题思路：

编程之美的水王法

解题步骤：

N/A

注意事项：

1. Python代码：

   1 2 3 4 5 6 7 8 9 10 11 12

   def majorityElement(self, nums: List[int]) -> int: candidate, count = 0, 0 for i in range(len(nums)): if count == 0: candidate = nums[i] count += 1 continue if nums[i] == candidate: count += 1 else: count -= 1 return candidate

算法分析：

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

LeetCode

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one ‘1’ bit.

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one ‘1’ bits.

题目大意：

求二进制上1的个数

解题思路：

用n & n - 1来去掉最左的1

解题步骤：

N/A

注意事项：

1. 用n & n - 1来去掉最左的1

Python代码：

1
2
3
4
5
6

def hammingWeight(self, n: int) -> int:
	count = 0
	while n:
		n = n & (n - 1)
		count += 1
	return count

算法分析：

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

LeetCode

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

题目大意：

二叉树从右看的节点列表。

解题思路：

BFS按层访问的最后一个

解题步骤：

N/A

注意事项：

1. 需要知道最后一个，所以引入i，不能用enumerate，只能用len
2. deque([root])不是deque(root)

Python代码：

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

def rightSideView(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res = []
	queue = collections.deque([root])
	while queue:
		i, len_q = 0, len(queue) # remember
		for _ in range(len_q):
			node = queue.popleft()
			if i == len_q - 1:
				res.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			i += 1
	return res

算法分析：

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