KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

<pre>Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. </pre>

Example 2:

<pre>Input: root = [1,2] Output: 1 </pre>

Constraints:

  • The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
  • -100 <= Node.val <= 100

</div>

题目大意：

求树的直径：任何两个节点的最大距离

解题思路：

DFS

解题步骤：

N/A

注意事项：

  1. 三种情况：自己+左，自己+右，左+右，不要漏掉最后一种
  2. 用nonlocal就不用定义self.max_len的全局变量

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def diameterOfBinaryTree(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		left = dfs(root.left) + 1
		right = dfs(root.right) + 1
		res = max(left, right)
		total = left + right - 1
		max_len = max(res, total, max_len)
		return res

	dfs(root)
	return max_len - 1

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given two integers a and b, return any string s such that:

  • s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters,
  • The substring 'aaa' does not occur in s, and
  • The substring 'bbb' does not occur in s.

Example 1:

<pre>Input: a = 1, b = 2 Output: "abb" Explanation: "abb", "bab" and "bba" are all correct answers. </pre>

Example 2:

<pre>Input: a = 4, b = 1 Output: "aabaa" </pre>

Constraints:

  • 0 <= a, b <= 100
  • It is guaranteed such an s exists for the given a and b.

</div>

题目大意：

给定两个整数代表ab的个数，生成一个字符串，字符串ab频数不能超过这2个数，不能有连续的aaa, bbb, 求此种字符串的最大长度

解题思路：

参考LeetCode 1405 Longest Happy String, 此题不用heap因为只有两种字符

解题步骤：

N/A

注意事项：

  1. 不能连续的处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def strWithout3a3b(self, a: int, b: int) -> str:
	res = ''
	while a > 0 or b > 0:
		if a > b:
			if len(res) > 1 and res[-2] == res[-1] == 'a':
				res += 'b'
				b -= 1
			else:
				res += 'a'
				a -= 1
		else:
			if len(res) > 1 and res[-2] == res[-1] == 'b':
				res += 'a'
				a -= 1
			else:
				res += 'b'
				b -= 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true </pre>

Example 2:

<pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true </pre>

Example 3:

<pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false </pre>

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?

</div>

算法思路：

LeetCode 211 若多个单词用Trie，一个单词就只需要DFS

注意事项：

  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

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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"] </pre>

Example 2:

<pre>Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: [] </pre>

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 10<sup>4</sup>
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

</div>

算法思路：

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

算法分析：

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

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

Posted on Edited on Disqus:

LeetCode

<div>

A website domain "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

A count-paired domain is a domain that has one of the two formats "rep d1.d2.d3" or "rep d1.d2" where rep is the number of visits to the domain and d1.d2.d3 is the domain itself.

  • For example, "9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com was visited 9001 times.

Given an array of count-paired domains cpdomains, return an array of the count-paired domains of each subdomain in the input. You may return the answer in any order.

Example 1:

<pre>Input: cpdomains = ["9001 discuss.leetcode.com"] Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"] Explanation: We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times. </pre>

Example 2:

<pre>Input: cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"] Output: ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"] Explanation: We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times. </pre>

Constraints:

  • 1 <= cpdomain.length <= 100
  • 1 <= cpdomain[i].length <= 100
  • cpdomain[i] follows either the "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>.d3<sub>i</sub>" format or the "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>" format.
  • rep<sub>i</sub> is an integer in the range [1, 10<sup>4</sup>].
  • d1<sub>i</sub>, d2<sub>i</sub>, and d3<sub>i</sub> consist of lowercase English letters.

</div>

题目大意：

统计所以domain和子域名个数

解题思路：

遍历每个domain，将domain和个数存入dict，再对domain按点号break，将每个sub-domain存入dict

解题步骤：

N/A

注意事项：

  1. Line 64根据题意倒转统计，Line 65记得非空时候加点号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
	domain_to_count = collections.defaultdict(int)
	for pair_str in cpdomains:
		pair = pair_str.split(' ')
		count = int(pair[0])
		domain = pair[1]
		subdomain = ''
		for segment in domain.split('.')[::-1]:
			subdomain = segment + ('.' + subdomain if subdomain else '')
			domain_to_count[subdomain] += count
	return ['{} {}'.format(_count, _domain) for _domain, _count in domain_to_count.items()]

算法分析：

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

Free mock interview