KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0. void set(index, val) sets the element at the given index to be equal to val.
int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1. int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: [“SnapshotArray”,”set”,”snap”,”set”,”get”]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5


Constraints:

1 <= length <= 50000 At most 50000 calls will be made to set, snap, and get.
0 <= index < length 0 <= snap_id <(the total number of times we call snap())
* 0 <= val <= 10^9

题目大意：

设计一个数据结构支持数组的快照

Binary Search解题思路(推荐)：

暴力法是每次快照时候，将当时的数组的所有值存入dict中，key为(snap_id, index), value为数组值，得到MLE
后来考虑用二分法优化snap，将数值跟前值不同才存入历史记录，但得到TLE，应该是因为snap时间太长，因为要遍历整个数组
所以应该将存入历史这一步放在set中，每次值改变才存入历史记录，虽然一个snap_id可能会存入多值，大部分是不需要，因为同一个snap_id应该取最新值，但这样设计费了空间，省了时间。

解题步骤：

N/A

注意事项：

  1. 历史记录为3d数组，第一维为数组index, 第二维为所有历史记录，第三维为每一个记录为[snap_id, value]。由于数组初始值为0，所以初始历史记录为[-1, 0]
  2. snap_id和题目要求的id差1，比如第一次call snap为0，但是之前的snap应该为-1
  3. 最容易错的在于二分法，要先将snap_id + 1，比如[-1, 0], [0, 5], [0, 6], [0, 2], [1, 1], [1, 4]…找snap_id = 0的值也就是要找最后的，所以先加1，找到[1, 1]再下标减1

Python代码：

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

    def __init__(self, length: int):
        self.snap_id = 0
        self.history = [[[-1, 0]] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.history[index].append([self.snap_id, val])

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        last_snap_id = bisect.bisect(self.history[index], [snap_id + 1]) - 1 # remember snap + 1
        return self.history[index][last_snap_id][1]

算法分析：

get时间复杂度为O(logn)，空间复杂度O(n), 数组某值n更改次数

暴力法算法II解题思路(不推荐)：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self, length: int):
	self.ary = [0] * length
	self.snap_id = -1
	self.idx_snap_to_val = {}

def set(self, index: int, val: int) -> None:
	self.ary[index] = val

def snap(self) -> int:
	self.snap_id += 1
	for i, n in enumerate(self.ary):
		self.idx_snap_to_val[(i, self.snap_id)] = self.ary[i]
	return self.snap_id

def get(self, index: int, snap_id: int) -> int:
	return self.idx_snap_to_val[(index, snap_id)]

Posted on Edited on Disqus:

LeetCode



You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:



Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).


Example 2:



Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.


Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 40 1 <= k <= m * n
grid[i][j] is either 0 or 1. grid[0][0] == grid[m - 1][n - 1] == 0

题目大意：

矩阵从左上走到右下，但含障碍，现在可以移除k个，使得路径最短，求最短路径

解题思路：

求最短路径用BFS，但此题难点在于distance跟路径有关，比如某一格可能属于不同的路径，此时它的distance会不同，所以distance不能global，必须作为state传到下一个迭代
同样的情况也在visited中存在，visited跟路径相关，而这一格跟k相关，这一格可以被属于不同的k的路径访问，所以visited应该加入k

解题步骤：

N/A

注意事项：

  1. visited是(x, y, k), queue是(x, y, k, dis)
  2. (x, y, k - 1)跟visited比较，而不是(x, y, k)。下一个节点的条件为eleminatios >= 0
  3. 若k过多会LTE, 因为广度会过大。这是用曼哈顿距离来剪枝。左上到右下距离为m - n + 2这肯定是最短距离，若k大于等于这个数，也就是可以移除曼哈顿路径上的所有障碍。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shortestPath(self, grid: List[List[int]], k: int) -> int:
	m, n = len(grid), len(grid[0])
	if k >= m + n - 2: # TLE
		return m + n - 2

	queue = collections.deque([(0, 0, k, 0)]) # x, y, k, distance
	visited = set([(0, 0, k)]) # include k
	while queue:
		_x, _y, _k, _dis = queue.popleft()
		if _x == m - 1 and _y == n - 1:
			return _dis
		for _dx, _dy in OFFSET:
			x, y = _x + _dx, _y + _dy
			if x < 0 or x >= m or y < 0 or y >= n:
				continue
			eliminations = _k - 1 if grid[x][y] == 1 else _k
			if (x, y, eliminations) not in visited and eliminations >= 0:
				queue.append((x, y, eliminations, _dis + 1))
				visited.add((x, y, eliminations))
	return -1

算法分析：

时间复杂度为O(nmk)，空间复杂度O(mnk), 某个cell都可能被访问k次，因为最多有k条路径

Posted on Edited on Disqus:

LeetCode



You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c<sub>1</sub>) and (r + 1, c<sub>2</sub>) will subtract abs(c<sub>1</sub> - c<sub>2</sub>) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

x for x >= 0. -x for x < 0.

Example 1:



Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.


Example 2:



Input: points = [[1,5],[2,3],[4,2]]
Output: 11
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.


Constraints:

m == points.length n == points[r].length
1 <= m, n <= 10<sup>5</sup> 1 <= m * n <= 10<sup>5</sup>
* 0 <= points[r][c] <= 10<sup>5</sup>

题目大意：

矩阵中含点数，每行取一个cell上的点数，但若两行之间的cell的列不同，要扣去列下标差，求最大点数

优化DP解题思路(推荐)：

求数值的最大值，容易想到用DP，dp[i][j]定义为每个cell的累计最大点数，递归式为

1
dp[i][j] = max(dp[i - 1][k] - abs(j - k)) + points[i][j], k = 0..len(dp[0])

复杂度为n立方。

如果没有扣除的规则，其实就是找上一行的最大值，但要考虑下标，考虑怎么移除这个限制，若将上一个某个cell搬到跟目前列，就是dp[i - 1][k] - (j - k), 所以可以提前计算，
而且有绝对值，所以类似于LeetCode 042 Trapping Rain Water拆分为向左向右最大值：
left[i]是该行第i个cell，上一行在该列左边的cell的累计最大点数(已扣除)，同理
right[i]是该行第i个cell，上一行在该列右边的cell的累计最大点数(已扣除)

最后，上一行的最大值只能在左边或右边

1
dp[i][j] = max(left[j], right[j]) + points[i][j], k = 0..len(dp[0])

解题步骤：

N/A

注意事项：

  1. left[j], right[j]的引入

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxPoints(self, points: List[List[int]]) -> int:
	m, n = len(points), len(points[0])
	dp = [[0 for _ in range(n)] for _ in range(m)]
	for j in range(n):
		dp[0][j] = points[0][j]
	for i in range(1, m):
		left, right = [0] * n, [0] * n
		left[0], right[-1] = dp[i - 1][0], dp[i - 1][-1]
		for j in range(1, n):
			left[j] = max(dp[i - 1][j], left[j - 1] - 1)
		for j in range(n - 2, -1, -1):
			right[j] = max(dp[i - 1][j], right[j + 1] - 1)
		for j in range(n):
			dp[i][j] = points[i][j] + max(left[j], right[j])
	return max(dp[-1])

算法分析：

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

暴力DP算法II解题思路(不推荐)：

Python代码：

1
2
3
4
5
6
7
8
9
def maxPoints2(self, points: List[List[int]]) -> int:
	dp = [[0 for _ in range(len(points[0]))] for _ in range(len(points))]
	for j in range(len(dp[0])):
		dp[0][j] = points[0][j]
	for i in range(1, len(dp)):
		for j in range(len(dp[0])):
			for k in range(len(dp[0])):
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + points[i][j] - abs(j - k))
	return max(dp[-1])

算法分析：

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

Posted on Edited on Disqus:

LeetCode



An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1  2 = 2.
- Twice the value of 3 is 3  2 = 6.
- Twice the value of 4 is 4  2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].


Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.


Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.


Constraints: 1 <= changed.length <= 10<sup>5</sup>
* 0 <= changed[i] <= 10<sup>5</sup>

题目大意：

给定一个数组，求这个数组是否可以分成两部分，后一部分的每个元素是否前一部分某元素的两倍

解题思路：

由最大值容易确定它的一半是否在数组中。所以排序后由大到小遍历。注意数组元素可能相等，所以不能用visited set来记录已用过的数，val_to_index也不支持重复，只有val_to_count支持

解题步骤：

N/A

注意事项：

  1. 用val_to_count，注意遍历时候就要减去，不要进入if才减去

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findOriginalArray(self, changed: List[int]) -> List[int]:
	if len(changed) % 2 == 1:
		return []
	changed.sort()
	res = []
	val_to_count = collections.Counter(changed)
	for i in reversed(range(len(changed))):
		if val_to_count[changed[i]] == 0:
			continue
		val_to_count[changed[i]] -= 1 # not in  if statement
		if changed[i] / 2 in val_to_count and val_to_count[changed[i] / 2] > 0:
			val_to_count[changed[i] / 2] -= 1
			res.append(int(changed[i] / 2))
	return [] if len(res) * 2 != len(changed) else res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.

Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.

Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp. Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records. Finds the minimum price the stock has been based on the current records.

Implement the StockPrice class:

StockPrice() Initializes the object with no price records. void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock. int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.

Example 1:

Input
[“StockPrice”, “update”, “update”, “current”, “maximum”, “update”, “maximum”, “update”, “minimum”]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]

Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5);  // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current();     // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum();     // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3);  // The previous timestamp 1 had the wrong price, so it is updated to 3.
                          // Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum();     // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2);  // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum();     // return 2, the minimum price is 2 at timestamp 4.


Constraints: 1 <= timestamp, price <= 10<sup>9</sup>
At most 10<sup>5</sup> calls will be made in total to update, current, maximum, and minimum. current, maximum, and minimum will be called only after update has been called at least once.

题目大意：

实现一个关于股票的数据结构，可以更新时间点对应的股价，最大最小值，最新价格

解题思路：

求最大最小值容易想到用heap，但heap不支持更新，难点是怎么支持更新股价。
仍然(price, timestamp)加入到heap中，在出堆时验证

解题步骤：

N/A

注意事项：

  1. 验证堆顶： 若股价和时间不匹配(用time_to_price验证)，表示这是stale股价，不断去掉，直到验证成功为止，最后加入到堆中

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
class StockPrice(TestCases):

    def __init__(self):
        self.time_to_price = {}
        self.cur_time = 0
        self.min_heap = []
        self.max_heap = []

    def update(self, timestamp: int, price: int) -> None:
        self.time_to_price[timestamp] = price
        self.cur_time = max(self.cur_time, timestamp)
        heapq.heappush(self.min_heap, (price, timestamp))
        heapq.heappush(self.max_heap, (-price, timestamp))

    def current(self) -> int:
        return self.time_to_price[self.cur_time]

    def maximum(self) -> int:
        price, timestamp = heapq.heappop(self.max_heap)
        while -price != self.time_to_price[timestamp]:
            price, timestamp = heapq.heappop(self.max_heap)
        heapq.heappush(self.max_heap, (price, timestamp))
        return -price

    def minimum(self) -> int:
        price, timestamp = heapq.heappop(self.min_heap)
        while price != self.time_to_price[timestamp]:
            price, timestamp = heapq.heappop(self.min_heap)
        heapq.heappush(self.min_heap, (price, timestamp))
        return price

算法分析：

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

Free mock interview