KK's blog

LeetCode

<div>

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

<pre>Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 </pre>

Example 2:

<pre>Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 </pre>

Example 3:

<pre>Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 </pre>

Constraints:

• 1 <= tokens.length <= 10<sup>4</sup>
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

</div>

题目大意：

求逆波兰式计算结果

解题思路：

逆波兰式用Stack

解题步骤：

N/A

注意事项：

1. 左右操作数是有区别的，所以stack先出栈的为右操作数，后出栈的为左操作数
2. 最容易错的是向下取整, 题目返回要求整数。所以要除法后取整int(prev / num)。这点和LeetCode 227 Basic Calculator II一样。也是和Java一致，用类型转化来实现，而//是比它小的整数如-2.8就是-3，只在负数是有区别

Python代码：

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

def evalRPN(self, tokens: List[str]) -> int:
	stack = []
	for token in tokens:
		if token in '+-*/':
			operand_right = stack.pop() # remember
			operand_left = stack.pop()
			if token == '+':
				stack.append(operand_left + operand_right)
			elif token == '-':
				stack.append(operand_left - operand_right)
			elif token == '*':
				stack.append(operand_left * operand_right)
			else:
				stack.append(int(operand_left / operand_right)) # remember
		else:
			stack.append(int(token))
	return stack[-1]

算法分析：

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

LeetCode

<div>

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

<pre>Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. </pre>

Example 2:

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

Constraints:

• 1 <= nums.length <= 2 * 10<sup>4</sup>
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

</div>

题目大意：

求子数组最大积

解题思路：

类似于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

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

Example 3:

<pre>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. </pre>

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?</div>

题目大意：

求两LL的相交点

解题思路：

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

解题步骤：

N/A

注意事项：

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

<div>

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

• "a->b" if a != b
• "a" if a == b

Example 1:

<pre>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" </pre>

Example 2:

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

Constraints:

• -10<sup>9</sup> <= lower <= upper <= 10<sup>9</sup>
• 0 <= nums.length <= 100
• lower <= nums[i] <= upper
• All the values of nums are unique.

</div>

题目大意：

给定一个范围[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

<div>

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

<pre>Input: nums = [3,2,3] Output: 3 </pre>

Example 2:

<pre>Input: nums = [2,2,1,1,1,2,2] Output: 2 </pre>

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10<sup>4</sup>
• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

Follow-up: Could you solve the problem in linear time and in O(1) space?</div>

题目大意：

求数组中的众数

解题思路：

编程之美的水王法

解题步骤：

N/A

注意事项：

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)