KK's blog

每天积累多一些

0%

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



Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:



Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.


Example 2:



Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.


Example 3:



Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.


Constraints:

The number of the nodes in the list is in the range [0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
pos is -1 or a valid index in the linked-list.

*Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意：

求LL是否存在循环，若存在返回循环起点

解题思路：

先用快慢指针找到相遇点，然后将slow指针移回fake_head起点，同速度移动直到相遇即为所求

证明：

A为起点，B为快慢指针相遇点，假设长度分别为z, y, x

1
2
3
4
5
fast在相遇时走过的距离为: z + x + y + y, 比slow多走一圈  
slow在相遇时走过的距离为: z + y  
由于fast速度是slow的两倍，所以相遇时，同一时间内，走过的距离也是两倍。
z + x + y + y = 2 * (z + y)
x = z得证

解题步骤：

N/A

注意事项：

  1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。
  2. 循环可能不存在，此时返回None

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def detectCycle(self, head: ListNode) -> ListNode:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			break
	if not fast or not fast.next:
		return None # remember
	slow = head
	while fast != slow:
		fast, slow = fast.next, slow.next
	return fast

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:



Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).


Example 2:



Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.


Example 3:



Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.


Constraints:

The number of the nodes in the list is in the range [0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
pos is -1 or a valid index in the linked-list.

*Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意：

求LL是否存在循环

解题思路：

快慢指针。若存在循环就一定会相遇，这是显然的。

解题步骤：

N/A

注意事项：

  1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。

Python代码：

1
2
3
4
5
6
7
def hasCycle(self, head: ListNode) -> bool:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			return True
	return False

算法分析：

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

Posted on Disqus:

LeetCode



Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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


Example 2:

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


Example 3:

Input: nums = [1]
Output: 1


Constraints:

`1 <= nums.length <= 3 104*-3 104 <= nums[i] <= 3 104`
* Each element in the array appears twice except for one element which appears only once.

题目大意：

数列中，所有数都出现两次除了一个数，求这一个数

异或解题思路(推荐)：

Easy题

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    def singleNumber(self, nums: List[int]) -> int:
    	res = 0
    	for n in nums:
    		res ^= n
    	return res

算法分析：

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

HashMap算法II解题思路：

记录频数，最直观解法

Python代码：

1
2
3
def singleNumber2(self, nums: List[int]) -> int:
	num_to_count = collections.Counter(nums)
	return [n for n, count in num_to_count.items() if count == 1][0]

算法分析：

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

Math算法III解题思路：

用set求单一元素和乘以2减去原数组的和

Python代码：

1
2
def singleNumber3(self, nums: List[int]) -> int:
	return 2 * sum(set(nums)) - sum(nums)

算法分析：

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

Free mock interview