KK's blog

LeetCode 2079 Watering Plants

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i<sup>th</sup> plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

• Water the plants in order from left to right.
• After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
• You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i<sup>th</sup> plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

**Input:** plants = [2,2,3,3], capacity = 5
**Output:** 14
**Explanation:** Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

**Input:** plants = [1,1,1,4,2,3], capacity = 4
**Output:** 30
**Explanation:** Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

**Input:** plants = [7,7,7,7,7,7,7], capacity = 8
**Output:** 49
**Explanation:** You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

• n == plants.length
• 1 <= n <= 1000
• 1 <= plants[i] <= 10<sup>6</sup>
• max(plants[i]) <= capacity <= 10<sup>9</sup>

题目大意：

x坐标上分别是浇每棵植物需要的水量，用数组plants表示，-1上为河水可以打水，capacity是容器大小。若发现水不够，就要回到河里将容器打满水。问浇完所有植物的总步数

解题思路：

此题类似于Leetcode 2073，可以按部就班按每个plant计算，但是为了提高效率，一般采取归结为更高一层次计算。
这题更高层次是每次去洒水再回去河边作为一个循环。最后一个循环不用回河边所以是单程。

解题步骤：

1. 计算一次来回的距离，条件为剩余的水不够浇该次的植物
2. 退出循环后，计算单程距离

注意事项：

1. 如果满足capacity也要递归到下一轮再计算，也就是Line 5取等号

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def wateringPlants(self, plants: List[int], capacity: int) -> int:
	sum, steps = 0, 0
	for i, n in enumerate(plants):
		sum += plants[i]
		if sum <= capacity:
			continue
		steps += i * 2  # back to river
		sum = plants[i]
	if sum > 0:
		steps += len(plants)
	return steps

算法分析：

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

算法思路：

递归分前半和后半排序然后合并。

应用：

1. 排序
2. 求逆序数

注意事项：

1. merge函数中更改输入nums。
2. line 15的等号决定是否stable sort。

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

def merge_sort(self, nums: List[int]):
	self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.m_sort(nums, start, mid)
	self.m_sort(nums, mid + 1, end)
	self.merge(nums, start, mid, end)

def merge(self, nums: List[int], start: int, mid: int, end: int):
	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:  # = decides if it is stable sort
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

算法思路：

最小堆可以维持堆顶元素为最小值。

应用：

1. 求数组第k个大的数

Python代码：

1
2
3
4
5
6
7
8
9
10

from heapq import heapreplace, heappush
def min_heap(self, nums: List[int], k: int) -> List[int]:
	res = []
	for i in range(len(nums)):
		if i < k:
			heappush(res, nums[i])
		elif nums[i] > res[0]:
			heapreplace(res, nums[i])

	return res

max heap的话，入堆的数转负数，跟堆顶比较的大于号不变，出堆后转为整数
注意第6行res[0]并没有负号，因为res已经是负数

1
2
3
4
5
6
7
8
9

def max_heap(self, nums: List[int], k: int) -> List[int]:
	res = []
	for i in range(len(nums)):
		if i < k:
			heappush(res, -nums[i])
		elif -nums[i] > res[0]:
			heapreplace(res, -nums[i])
	res = [-n for n in res]
	return res

BFS + Heap

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

def bfs(self, nums, start, k) -> List[int]:
	heap, res = ([start])), []
	visited.add(start)
	while heap:
		node = heapq.heappop(heap)
		res.append(node)
		if len(res) == k:
			break
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			heap.append(neighbor)
			visited.add(neighbor)
	return res

算法分析：

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

LeetCode 378 Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k<sup>th</sup> smallest element in the matrix.

Note that it is the k<sup>th</sup> smallest element in the sorted order, not the k<sup>th</sup> distinct element.

You must find a solution with complexity better than O(n<sup>2</sup>).

Example 1:

**Input:** matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
**Output:** 13
**Explanation:** The elements in the matrix are [1,5,9,10,11,12,13,**13**,15], and the 8th smallest number is 13

Example 2:

**Input:** matrix = [[-5]], k = 1
**Output:** -5

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup>
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n<sup>2</sup>

Follow up: Could you solve the problem in O(n) time complexity?

题目大意：

按行按列有序矩阵中，找第k大的数。

Heap解题思路(推荐)：

见Heap知识点。 分别将(value, i, j)放入heap中，取出堆顶元素后，去(i, j)相邻右和下节点放入堆中。这个方法容易实现，所以推荐。

LeetCode 074 Search a 2D Matrix 每一行有序，下一行的首元素大于上一行的尾元素 + 找target
LeetCode 240 Search a 2D Matrix II 按行按列有序 + 找target
LeetCode 378 Kth Smallest Element in a Sorted Matrix 按行按列有序 + 找第k大
矩阵结构方面，第一道每一行都是独立，所以可以独立地按行按列做二分法
后两道，矩阵二维连续，所以解法都是类BFS，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

注意事项：

1. 将(value, i, j)放入heap中

Python代码：

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

def kthSmallest4(self, matrix: List[List[int]], k: int) -> int:
	OFFSETS = [(0, 1), (1, 0)]
	heap = [(matrix[0][0], 0, 0)]
	visited = set([(0, 0)])
	while heap:
		node = heapq.heappop(heap)
		k -= 1
		if k == 0:
			return node[0]
		for _dx, _dy in OFFSETS:
			x, y = node[1] + _dx, node[2] + _dy
			if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]) or (x, y) in visited:
				continue
			heapq.heappush(heap, (matrix[x][y], x, y))
			visited.add((x, y))
	return -1

算法分析：

for循环是k个，每次循环理论上产生2个节点，所以总共是2^k个，复杂度为O(klog(2k), 也就是O(k2)
由于矩阵最多n^2个元素，所以复杂度为O(klog(n2)
所以时间复杂度为O(klogn)，空间复杂度O(n2)。

数值二分法算法II解题思路：

第k的数运用数值二分法

解题步骤：

1. 数值二分法
2. 难点在于统计小于mid的个数。若遍历全矩阵比较慢，采用按行遍历，每行再用二分法找到小于mid的数的个数，再求和。

注意事项：

1. 注意k–, k从1开始
2. 每行统计小于mid个数用find smaller的模板。返回值要加1，因为下标转换成个数。

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
31
32

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
	k -= 1
	if not matrix or not matrix[0]:
		return -1
	N, M = len(matrix), len(matrix[0])
	start, end, epsilon = matrix[0][0], matrix[N - 1][M - 1], 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = sum([self.get_count(matrix[i], mid) for i in range(N)])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

def get_count(self, nums: List[int], target: float) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			end = mid
	if nums[end] < target:
		return end + 1
	if nums[start] < target:
		return start + 1
	return 0

用bisect优化

Python代码：

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

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
	k -= 1
	if not matrix or not matrix[0]:
		return -1
	N, M = len(matrix), len(matrix[0])
	start, end, epsilon = matrix[0][0], matrix[N - 1][M - 1], 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = sum([bisect.bisect(matrix[i], mid) + 1 for i in range(N)])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

算法分析：

while循环有log[(max - min)/epsilon]个，假设数字平均分布，复杂度是log(n), 每个循环按每行(n行)统计小于mid的个数，
每次统计调用get_count用了log(n)，
所以总时间复杂度为O(log(n) * nlogn)，空间复杂度O(1)。

LeetCode 2073 Time Needed to Buy Tickets

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

题目大意：

排队买票，每个人都有不同的票数需求。每人每次只能买一张，买完后重新排队。买一张票需要1秒，求第k个人买票的总时间。

解题思路：

一开始按照题目要求老老实实每个元素减一，按照流程计算，但效率较低。考虑若所有人票数大于0，每轮计算结果是一样的：
当前排队人数乘以排队的人中的最小票数。当最小票数人离队后，公式会改变。如此循环直到第k个人票数也变成0为止。

解题步骤：

1. 求最小值
2. 计算票数
3. 更新人数，继续循环
4. 结果减去排在第k个人后的人数

注意事项：

1. 结果要减去排在第k个人后的还在排队的人数（tickets数不为负数，可以等于0，因为是同时在同一轮买到足够票）。

Python代码：

1
2
3
4
5
6
7
8
9
10

def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
	sum, ppl, min_tickets = 0, len(tickets), 0
	while tickets[k] > 0:
		min_tickets = min(t for t in tickets if t > 0)
		sum += min_tickets * ppl
		tickets = [t - min_tickets for t in tickets]
		ppl -= tickets.count(0)

	after_k = [i for i in range(k + 1, len(tickets)) if tickets[i] >= 0]
	return sum - len(after_k)

算法分析：

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