KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1


Example 2:

Input: coins = [2], amount = 3
Output: -1


Example 3:

Input: coins = [1], amount = 0
Output: 0


Example 4:

Input: coins = [1], amount = 1
Output: 1


Example 5:

Input: coins = [1], amount = 2
Output: 2


Constraints:

1 <= coins.length <= 12 1 <= coins[i] <= 2<sup>31</sup> - 1
* 0 <= amount <= 10<sup>4</sup>

题目大意：

求兑换硬币的最小个数

解题思路：

用数值->个数DP模板

注意事项：

  1. amount为0时候，返回0，表示不用coin也能满足，属于合法情况, dp[0] = 0(第二步)
  2. 返回值，若dp[-1]为初始值，表示无解，返回-1(第5步)
  3. 实现中dp[i] = min(dp[i], dp[i - j] + 1), +1在min内而不是min外。
  4. 此题内外循环顺序不重要，跟LeetCode 518 Coin Change 2有区别

Python代码：

1
2
3
4
5
6
7
8
9
def coinChange(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for coin in coins:
		for i in range(len(dp)):
			if i + coin <= amount:
				dp[i + coin] = min(dp[i + coin], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

算法分析：

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

Posted on Edited on Disqus:

LeetCode 239 Sliding Window Maximum



You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position                Max
—————               —–
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7


Example 2:

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


Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
* 1 <= k <= nums.length

算法思路：

LL + 递减栈
难点是什么时候输出结果，并不是出栈时候，而是每轮遍历时，就可以计算当轮的最大值，也就是当前的队首

注意事项：

  1. 每轮遍历时，计算当轮的最大值就是当前的队首
  2. 注意程序顺序，先递减栈模板，在计算结果，最后移出越界元素。如例子[876], i = 2, 窗口大小满足了，计算结果为8,8在下一轮会越界，所以移除。
  3. 结果数小于数组大小，注意line 8的条件

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	queue, res = collections.deque(), []
	for i in range(len(nums)):
		while queue and nums[i] > nums[queue[-1]]:
			queue.pop()
		queue.append(i)

		if i + 1 >= k:
			res.append(nums[queue[0]])
		if i - queue[0] + 1 >= k:
			queue.popleft()
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example 1:



Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.


Example 2:

Input: root = [1], target = 1, k = 3
Output: []


Constraints:

The number of nodes in the tree is in the range [1, 500]. 0 <= Node.val <= 500
All the values Node.val are unique. target is the value of one of the nodes in the tree.
* 0 <= k <= 1000

算法思路：

有三种情况，都容易忽略： 1. 儿子节点 2. 所有父节点路劲上 3. 兄弟节点路径上。而第三种情况要搜另一边的儿子节点（左右不确定）要用visited记录，而且不一定是父亲的兄弟节点，可能爷爷的非父亲的儿子节点。
既然不是单向搜索，不妨转换为图，然后用计算距离BFS模板，只要用map来记录某节点的父亲节点或者增加一个域。BFS中for neighbor in [node.left, node, right, node.parent]

注意事项：

  1. root的parent是None，所以从root去赋值parent，而不是从parent root给儿子赋parent
  2. Line 13 node.left, node.right, node.parent都可能为None，所以Line14要加not neighbor
  3. BFS从target开始而不是root

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
	if not root:
		return []
	self.dfs(root, None)
	queue, visited, distance_to_tgt,  = collections.deque([target]), set([target]), collections.defaultdict(int)
	distance_to_tgt[target], res = 0, []
	while queue:
		node = queue.popleft()
		if distance_to_tgt[node] == k:
			res.append(node.val)
		if distance_to_tgt[node] > k:
			break
		for neighbor in [node.left, node.right, node.parent]:
			if not neighbor or neighbor in visited:  # remember not neighbor
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance_to_tgt[neighbor] = distance_to_tgt[node] + 1
	return res

def dfs(self, root, parent):
	if not root:
		return None
	root.parent = parent
	'''if root.left:
		root.left.parent = root
	if root.right:
		root.right.parent = root'''
	self.dfs(root.left, root)  # remember to pass parent
	self.dfs(root.right, root)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3. For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Example 1:

Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0


Constraints: -10<sup>5</sup> <= num <= 10<sup>5</sup>
There will be at least one element in the data structure before calling findMedian. At most 5 * 10<sup>4</sup> calls will be made to addNum and findMedian.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

题目大意：

求动态中位数

算法思路：

用max_heap, min_heap, 保证min_heap个数永远等于max_heap或多一个。插入元素先进max_heap, 再heappop将堆顶元素加入min_heap, 若此时比max_heap多2个，就再heappop加入到max_heap.

注意事项：

  1. 中位数有1-2个
  2. Python中的max_heap用负数实现，入堆出堆都要取反

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder(TestCases):

    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)
        max_value = -heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap, max_value)
        if len(self.min_heap) - len(self.max_heap) >= 2:
            min_value = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -min_value)

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “3+22”
Output: 7


Example 2:

Input: s = “ 3/2 “
Output: 1


Example 3:

Input: s = “ 3+5 / 2 “
Output: 5


Constraints: 1 <= s.length <= 3 * 10<sup>5</sup>
s consists of integers and operators `(‘+’, ‘-‘, ‘‘, ‘/‘)separated by some number of spaces. *srepresents **a valid expression**. * All the integers in the expression are non-negative integers in the range[0, 231 - 1]`.
The answer is guaranteed to fit in a *32-bit integer.

题目大意：

实现字符串加减乘除，但无括号。

算法思路：

逆波兰式的实现用Stack。Stack只存数，而且只存加号操作符的数，也就是说，
如果是减，就将-num入栈，
如果是乘除，立刻计算stack[-1]乘除num的结果再压入栈，因为乘除是最高优先级可以直接计算，而加减不可以。
所以用一个stack

代码中含三种情况：空格，运算符，数字

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

此题没有括号，不能用模板，要借用op来记录前一个操作符

  1. op记录前一个运算符，char为运算符或当前字符。计算时候根据op，因为char(+)只是第二个操作数(1-2+)的终结字符，此时表明操作数stack[-1], num以及操作符op均已完成，可以计算
  2. 最容易错的是向下取整Line 18, 题目返回要求整数。所以要除法后取整int(prev / num)
  3. s末尾加入加号，方便parse最后一个num

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def calculate(self, s: str) -> int:
	s += '+'
	res, num, stack, op = 0, 0, [], '+'
	for char in s:
		if char == ' ':
			continue
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char
    return sum(stack)

算法分析：

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

Free mock interview