KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u<sub>1</sub>, v<sub>1</sub>), (u<sub>2</sub>, v<sub>2</sub>), ..., (u<sub>k</sub>, v<sub>k</sub>) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]


Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]


Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]


Constraints:

1 <= nums1.length, nums2.length <= 10<sup>5</sup> -10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup>
nums1 and nums2 both are sorted in ascending order. 1 <= k <= 1000

注意事项：

  1. 类似于BFS模板，只不过是将queue换成heap。
  2. 将两数和加入到heap中，而不是下标的和(粗心)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
OFFSET = [(0, 1), (1, 0)]
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
	heap, res = [(nums1[0] + nums2[0], 0, 0)], []
	visited = set([0, 0])
	while heap:
		node = heapq.heappop(heap)
		res.append([nums1[node[1]], nums2[node[2]]])
		if len(res) == k:
			break
		for _dx, _dy in OFFSET:
			_x, _y = node[1] + _dx, node[2] + _dy
			if _x < len(nums1) and _y < len(nums2) and (_x, _y) not in visited:
				heapq.heappush(heap, (nums1[_x] + nums2[_y], _x, _y))
				visited.add((_x, _y))
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:



Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.


Example 2:



Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1


Constraints:

The number of nodes in the tree is in the range [2, 10<sup>5</sup>]. -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
All Node.val are unique. p != q
* p and q will exist in the tree.

题目大意：

二叉树中求给定的两节点的最低共同父亲节点

解题思路：

DFS

解题步骤：

N/A

注意事项：

  1. pq一定存在，所以有**三种情况： 1) p或q是root，另一是其子孙。 2) p，q分列root两边。 3) p，q在root的一边

Python代码：

1
2
3
4
5
6
7
8
9
10
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root:
		return None
	if root == p or root == q:
		return root
	left = self.lowestCommonAncestor(root.left, p, q)
	right = self.lowestCommonAncestor(root.right, p, q)
	if left and right:
		return root
	return left if left else right

算法分析：

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

算法II解题思路：

BFS遍历树（可以找到就停止），然后记录子节点到父节点的映射，将所有父节点放到set中，同样查找另一个节点的父节点们，找到第一个在set中的节点。

Posted on Edited on Disqus:

LeetCode



Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = “abab”, s = “redblueredblue”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “red”
‘b’ -> “blue”


Example 2:

Input: pattern = “aaaa”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “asd”


Example 3:

Input: pattern = “abab”, s = “asdasdasdasd”
Output: true
Explanation: One possible mapping is as follows:
‘a’ -> “a”
‘b’ -> “sdasd”
Note that ‘a’ and ‘b’ cannot both map to “asd” since the mapping is a bijection.


Example 4:

Input: pattern = “aabb”, s = “xyzabcxzyabc”
Output: false


Constraints:

1 <= pattern.length, s.length <= 20 pattern and s consist of only lower-case English letters.

算法思路：

类似于word break，但由于要存储处理过map和set，DP不能处理，所以只能用DFS

注意事项：

  1. 比较映射，用Map比较A->B的映射，如已有a->dog, 另一对映射a->cat通过查找Map知道不合法。B->A的映射可通过将map的所有value存到一个set中知道。如a->dog, b->dog. b不在Map中但b对应的dog在set中，不合法。
    DFS的API为dfs(pattern, word, pattern_to_word, used_set)
  2. 若pattern的字母出现过，如aba，不应进入循环，更不应该加入到map和set中，应该用startswith比较word判断是否合法，若是，直接下一轮DFS(Line 11 -15)
  3. 1中的两情况的第一种情况以及第二种情况的前半部分(b不在map中)在2中已经处理，所以只要在循环中处理第二种情况后半部分(b对应的dog在set中)即可(Line 22 - 23)

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 wordPatternMatch(self, pattern: str, s: str) -> bool:
	if not pattern or not s:
		return False
	return self.dfs(pattern, s, 0, 0, {}, set())

def dfs(self, pattern, s, start_p, start_s, pattern_to_s, s_set):
	if start_p >= len(pattern) and start_s >= len(s):
		return True
	if start_p >= len(pattern) or start_s >= len(s):
		return False
	char = pattern[start_p]
	if char in pattern_to_s:
		word = pattern_to_s[char]
		if not s[start_s:].startswith(word):
			return False
		return self.dfs(pattern, s, start_p + 1, start_s + len(word), pattern_to_s, s_set)
		
	for j in range(start_s, len(s)):
		matched_word = s[start_s:j + 1]
		'''if char in pattern_to_s and pattern_to_s[char] != matched_word:
			continue
		if char not in pattern_to_s and matched_word in s_set:  # remembers
			continue'''
		if matched_word in s_set:
			continue
		pattern_to_s[char] = matched_word
		s_set.add(matched_word)
		if self.dfs(pattern, s, start_p + 1, j + 1, pattern_to_s, s_set):
			return True
		s_set.remove(matched_word)
		pattern_to_s.pop(char)
	return False

算法分析：

时间复杂度为O(解大小)，空间复杂度为O(解大小)。

Posted on Edited on Disqus:

LeetCode



Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:



Input: board = [[“o”,”a”,”a”,”n”],[“e”,”t”,”a”,”e”],[“i”,”h”,”k”,”r”],[“i”,”f”,”l”,”v”]], words = [“oath”,”pea”,”eat”,”rain”]
Output: [“eat”,”oath”]


Example 2:



Input: board = [[“a”,”b”],[“c”,”d”]], words = [“abcb”]
Output: []


Constraints:

m == board.length n == board[i].length
1 <= m, n <= 12 board[i][j] is a lowercase English letter.
`1 <= words.length <= 3 104*1 <= words[i].length <= 10*words[i]consists of lowercase English letters. * All the strings ofwords` are unique.

算法思路：

N/A

注意事项：

  1. 用Trie来保存单词列表，这样每次DFS的每一步都可以O(1)时间知道是否和单词吻合，而不是O(n)
  2. 难点1: Trie的接口有startswith, search, insert，仅insert可以用，其他两个不支持与DFS同步搜索。所以要写一个新函数：其实修改startsWith将for循环去掉当然DFS的API也要改，去掉word, word_index加入trie, trie_node, path, res
  3. TLE错误，因为比如矩阵为[abc]，单词列表为abc, abc, abc，这样abc加入到结果后就不应该再搜abc，因为结果不能重且效率大打折扣。如果找到了单词，就应该将它从Trie中去掉，避免无谓的搜索，条件是该节点children长度为0，就父节点就将key删除。如果还有儿子节点只能标记is_end为False。Line 29 - 31和35 - 36

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
OFFSETS = [(0, 1), (1, 0), (-1, 0), (0, -1)]
class Solution(TestCases):

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0] or not words:
            return []
        trie, res = Trie(), []
        for word in words:
            trie.insert(word)

        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, i, j, visited, trie, trie.get_head(), '', res)
        return list(res)

    def dfs(self, board, start_x, start_y, visited, trie, trie_node, path, res):
        if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
            return
        if visited[start_x][start_y]:
            return
        trie_child = trie.search_one_node(board[start_x][start_y], trie_node)
        if not trie_child:
            return
        visited[start_x][start_y] = True
        path += board[start_x][start_y]
        if trie_child.is_end:
            res.append(path)
            trie_child.is_end = False
            if len(trie_child.children) == 0 and board[start_x][start_y] in trie_node.children:
                trie_node.children.pop(board[start_x][start_y])
        for dx, dy in OFFSETS:
            self.dfs(board, start_x + dx, start_y + dy, visited, trie, trie_child, path, res)
        path = path[:-1]
        visited[start_x][start_y] = False
        if len(trie_child.children) == 0 and board[start_x][start_y] in trie_node.children:
            trie_node.children.pop(board[start_x][start_y])


class Trie:
    def __init__(self):
        self.head = TrieNode()

    def insert(self, word: str) -> None:
        if not word:
            return
        it = self.head
        for i in range(len(word)):
            it = it.children[word[i]]
        it.is_end = True

    def search_one_node(self, c: str, trie_node):
        if c not in trie_node.children:
            return None
        else:
            return trie_node.children[c]

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

上述代码比较复杂，可以先写这个LTE版本, 它在最后结果去重，但是对于重复单词会LTE，如[‘a’, … ‘a’]. 所以演变成最优版本，需要删除Trie的节点

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
	...
	return list(set(res))

def dfs(self, board, start_x, start_y, visited, trie, trie_node, path, res):
	if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
		return
	if visited[start_x][start_y]:
		return
	trie_child = trie.search_one_node(board[start_x][start_y], trie_node)
	if not trie_child:
		return
	visited[start_x][start_y] = True
	path += board[start_x][start_y]
	if trie_child.is_end:
		res.append(path)
	for dx, dy in OFFSETS:
		self.dfs(board, start_x + dx, start_y + dy, visited, trie, trie_child, path, res)
	path = path[:-1]
	visited[start_x][start_y] = False

算法分析：

时间复杂度为O(n2*4*3L-1)，空间复杂度O(n2), n是矩阵长度，L是最大单词长度.
3是因为访问过的节点不合法，也就是来的节点不能再走一次，所以只能3个方向,第一个可以4个方向，其他步是3个方向

有一个方法是不用Trie而是将单词所有prefix放入到set中，但会TLE，因为时间复杂度为O(n23n*n)，它不会剪枝，从顶点出发，最差情况是z型走完board，此时路径长度为n*n.

Posted on Edited on Disqus:

LeetCode



Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
Output: true


Example 2:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
Output: true


Example 3:



Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
Output: false


Constraints:

m == board.length n = board[i].length
1 <= m, n <= 6 1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

*Follow up: Could you use search pruning to make your solution faster with a larger board?

算法思路：

N/A

注意事项：

  1. 难点在于判断不合法情况的顺序，比DFS模板稍复杂。这些语句都在for循环外，按此顺序： word_index和(start_x, start_y)不合法，该点访问过(模板)，字母不等。
    然后visited为True，循环后visited为False
    根据DFS模板visited紧接在return之后(当然先确保不越界)，visited赋值一定要在所有不合法情况之后，不能紧跟visited比较

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
OFFSETS = [(0, 1), (1, 0), (-1, 0), (0, -1)]
class Solution(TestCases):

    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0] or not word:
            return False
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, i, j, word, 0, visited):
                    return True
        return False

    def dfs(self, board, start_x, start_y, word, word_index, visited):
        if word_index >= len(word):
            return True
        if start_x < 0 or start_x >= len(board) or start_y < 0 or start_y >= len(board[0]):
            return False
        if visited[start_x][start_y]:
            return False
        if board[start_x][start_y] != word[word_index]:
            return False
        visited[start_x][start_y] = True
        for dx, dy in OFFSETS:
            if self.dfs(board, start_x + dx, start_y + dy, word, word_index + 1, visited):
                return True
        visited[start_x][start_y] = False
        return False

算法分析：

时间复杂度为O(n2*3L)，空间复杂度O(n2), n是矩阵长度，L是最大单词长度.
3是因为访问过的节点不合法，也就是来的节点不能再走一次，所以只能3个方向

Free mock interview