KK's blog

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: 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

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 = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

题目大意：

求子数组最大积

解题思路：

类似于LeetCode 053 Maximum Subarray求子数组最大和，用DP。

递归式； dp为以某个数为结尾的最大子数组积，dp2为以某个数为结尾的最小子数组积

1
2

dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])

解题步骤：

N/A

注意事项：

1. 由于负负得正，所以是多状态DP。需要同时赋值

Python代码：

1
2
3
4
5
6
7
8
9

# dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
# dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
def maxProduct(self, nums: List[int]) -> int:
	max_p, min_p, res = 1, 1, float('-inf')
	for n in nums:
		# remember assign same time
		max_p, min_p = max(n, max_p * n, min_p * n), min(n, max_p * n, min_p * n) # 4, -48 | 4, -8, -48
		res = max(res, max_p) # 6
	return res

算法分析：

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

LeetCode

Input: s = “the sky is blue”
Output: “blue is sky the”

Input: s = “  hello world  “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Input: s = “a good   example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

题目大意：

反转字符串中的单词顺序

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. word不能为空，单词之间可能含多个空格

Python代码：

1
2
3
4

def reverseWords(self, s: str) -> str:
	words = s.split(' ')
	words_without_space = [word for word in words if word]
	return ' '.join(words_without_space[::-1])

算法分析：

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