KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:



Input: points = [[1,1],[2,2],[3,3]]
Output: 3


Example 2:



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


Constraints:

1 <= points.length <= 300 points[i].length == 2
-10<sup>4</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup> All the points are unique.

题目大意：

求在同一直线上的点的最大个数

解题思路：

固定一个点，求其与其他点的斜率是否相同，记录在map中。通过同一个点，若斜率相同，肯定在同一直线上。这是几何题。

解题步骤：

N/A

注意事项：

  1. 两重循环，外循环为每个点，内循环为该点和其他的点的斜率。斜率可以为无穷大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxPoints(self, points: List[List[int]]) -> int:
	res = 0
	for i in range(len(points)):
		slope_to_count = collections.defaultdict(int)
		max_p = 0
		for j in range(i + 1, len(points)):
			slope = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]) \
				if points[j][0] - points[i][0] != 0 else float('inf') # remember line is y-axis
			slope_to_count[slope] += 1
			max_p = max(max_p, slope_to_count[slope])
		res = max(res, max_p + 1)
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:

Input: tokens = [“2”,”1”,”+”,”3”,”“]
Output: 9
Explanation: ((2 + 1)  3) = 9


Example 2:

Input: tokens = [“4”,”13”,”5”,”/“,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6


Example 3:

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


Constraints:

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

题目大意：

求逆波兰式计算结果

解题思路：

逆波兰式用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)

Posted on Edited on Disqus:

LeetCode



Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

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


Example 2:

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


Example 3:

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.


Constraints:

1 <= s.length <= 10<sup>4</sup> s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it *in-place with O(1) extra space?

题目大意：

反转字符串中的单词顺序

解题思路：

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)

Posted on Edited on Disqus:

LeetCode



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:

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


Example 2:

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


Constraints:

`1 <= nums.length <= 2 104*-10 <= nums[i] <= 10* The product of any prefix or suffix ofnums` is guaranteed to fit in a 32-bit integer.

题目大意：

求子数组最大积

解题思路：

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

Posted on Edited on Disqus:

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)

Free mock interview