KK's blog

LeetCode 1146 Snapshot Array

Posted on 2022-02-16 Disqus:

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

注意事项：

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

Python代码：

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代码：

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)]

LeetCode 1937 Maximum Number of Points with Cost

Posted on 2022-02-16 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, c1) and (r + 1, c2) will subtract abs(c1 - c2) 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 <= 105 1 <= m * n <= 105
* 0 <= points[r][c] <= 105

题目大意：

矩阵中含点数，每行取一个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

注意事项：

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

Python代码：

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(n²)，空间复杂度O(n²)

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

Python代码：

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(n³)，空间复杂度O(n²)

LeetCode 1293 Shortest Path in a Grid with Obstacles Elimination

Posted on 2022-02-16 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

注意事项：

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

Python代码：

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条路径

LeetCode 670 Maximum Swap

Posted on 2022-02-15 Disqus:

LeetCode

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

* 0 <= num <= 108

题目大意：

给定一个数，最多交换一位，使得这个数尽可能最大

解题思路：

类似于LeetCode 854 K-Similar Strings, 如2736，求2后面最大的数为7，和7交换即为所求。这里有两个问题：

第一位可能已经是最大的数位，这样需要遍历每个数位，找到能交换的数位，若这个位在倒序排序后位置一样，表明此位不能交换。所以排序法的算法复杂度为n平方
若要优化就要采用bucket sort，因为数位是有限的。若后续数位有一个数比自己大，表示可交换。所以只要记录每个数位的位置，贪心法从9(最大)遍历到自己，若该位位置在自己之后，可交换
若不同数位上数值相同，应该记录其最后的位置，因为交换时候将小的尽量往后交换，越好越不重要，如2949, 2和最后的9交换得到最大的数

解题步骤：

N/A

注意事项：

内循环从9遍历到该位数值(不包括)
buckets的key为字符串，注意整数和字符串互换，如buckets[str(j)], int(digits[i])

Python代码：

def maximumSwap(self, num: int) -> int:
	digits, buckets = str(num), collections.defaultdict(int)
	for i, digit in enumerate(digits):
		buckets[digit] = i # use last position for same char
	for i in range(len(digits)):
		for j in range(9, int(digits[i]), -1): # remember to use int(digits[i]) not i
			if buckets[str(j)] > i: # 2736, i = (2), j = (7) # remember to use str j
				return int(digits[:i] + digits[buckets[str(j)]] + digits[i + 1:buckets[str(j)]] + digits[i] + digits[buckets[str(j)] + 1:])
	return num

算法分析：

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

LeetCode 567 Permutation in String

Posted on 2022-02-15 Disqus:

LeetCode

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1‘s permutations is the substring of s2.

Example 1:

Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input: s1 = “ab”, s2 = “eidboaoo”
Output: false

Constraints:

1 <= s1.length, s2.length <= 104 s1 and s2 consist of lowercase English letters.

题目大意：

求字符串s2中是否含s1的anagram

解题思路：

类似于LeetCode 438 Find All Anagrams in a String, 唯一区别是substr_win == char_to_count_p时返回而不是加入到res

解题步骤：

N/A

注意事项：

Python代码：

def checkInclusion(self, s1: str, s2: str) -> bool:
	char_to_count_p = collections.Counter(s1)
	substr_win = collections.defaultdict(int)
	for i, char in enumerate(s2):
		substr_win[s2[i]] += 1
		# window: [i - len(p) + 1, i]
		if i >= len(s1):
			substr_win[s2[i - len(s1)]] -= 1
			if substr_win[s2[i - len(s1)]] == 0:
				substr_win.pop(s2[i - len(s1)])
		if substr_win == char_to_count_p:
			return True
	return False

算法分析：

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