KK's blog

每天积累多一些

0%

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 the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:



Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.


Example 2:



Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.


Constraints: The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9 The depth of the tree will not exceed 10.

题目大意：

由root到叶子节点的数字组成多位数的数，求这些数的总和

解题思路：

题目提到叶子节点，所以DFS中要含叶子节点的情况

解题步骤：

N/A

注意事项：

  1. 题目提到叶子节点，所以DFS中要含叶子节点的情况。当然还要有root为空的情况，这样root.left和root.right不用非空检查，代码更简洁

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def sumNumbers(self, root: TreeNode) -> int:
	return self.dfs(root, 0)

def dfs(self, root, path):
	if not root:
		return 0
	current = path * 10 + root.val
	if not root.left and not root.right:
		return current
	#if root.left #if root.right:
	return self.dfs(root.left, current) + self.dfs(root.right, current)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, “/leetcode" and “/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn’t exist. int get(string path) Returns the value associated with path or returns -1 if the path doesn’t exist.

Example 1:

Input:
[“FileSystem”,”createPath”,”get”]
[[],[“/a”,1],[“/a”]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/a”, 1); // return true
fileSystem.get(“/a”); // return 1


Example 2:

Input:
[“FileSystem”,”createPath”,”createPath”,”get”,”createPath”,”get”]
[[],[“/leet”,1],[“/leet/code”,2],[“/leet/code”],[“/c/d”,1],[“/c”]]
Output:
[null,true,true,2,false,-1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/leet”, 1); // return true
fileSystem.createPath(“/leet/code”, 2); // return true
fileSystem.get(“/leet/code”); // return 2
fileSystem.createPath(“/c/d”, 1); // return false because the parent path “/c” doesn’t exist.
fileSystem.get(“/c”); // return -1 because this path doesn’t exist.


Constraints:

The number of calls to the two functions is less than or equal to 10<sup>4</sup> in total. 2 <= path.length <= 100
* 1 <= value <= 10<sup>9</sup>

题目大意：

设计文件系统，支持创建路径，路径含key, value

Trie解题思路：

用Trie, is_end变成key, value

解题步骤：

N/A

注意事项：

  1. 遍历用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
33
34
35
36
37
38
39
class FileSystem(TestCases):

    def __init__(self):
        self.head = TrieNode('')

    def createPath(self, path: str, value: int) -> bool:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                if i == len(segments) - 1: # match all the previous segments
                    it.children[segment] = TrieNode(segment)
                else:
                    return False
            it = it.children[segment]
        if it.value != -1: # exists
            return False
        it.value = value
        return True

    def get(self, path: str) -> int:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                return -1
            it = it.children[segment]
        return it.value

class TrieNode:

    def __init__(self, name):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.name = name
        self.value = -1

算法分析：

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

算法II HashMap解题思路：

用前缀法

Python代码：

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

    def __init__(self):
        self.path_to_val = defaultdict()

    def createPath(self, path: str, value: int) -> bool:

        if path == "/" or len(path) == 0 or path in self.path_to_val:
            return False

        # search from the right
        parent = path[:path.rfind('/')]
        if len(parent) > 1 and parent not in self.path_to_val:
            return False

        self.path_to_val[path] = value
        return True

    def get(self, path: str) -> int:
        return self.path_to_val.get(path, -1)

算法分析：

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

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



Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.


Example 2:

Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.


Example 3:

Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints: 1 <= text1.length, text2.length <= 1000
* text1 and text2 consist of only lowercase English characters.

题目大意：

求两字符串的最大公共字符序列，不一定需要连续

解题思路：

两字符串最值问题用DP
dp[i][j]为最大公共字符序列，最后一位不需要相等。递归式为:

1
2
dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = max(dp[i - 1][j], dp[i][j - 1])

解题步骤：

DP五点注意事项

注意事项：

  1. 不相等时候不需要dp[i - 1][j - 1]，因为已经包含在dp[i - 1][j]或dp[i][j - 1]中, DP属于累计DP

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # no dp[i - 1][j - 1] but no impact
	return dp[-1][-1]

打印路径

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1
return res[::-1]

算法分析：

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

Free mock interview