KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, return the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).

Example 1:



Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.


Example 2:



Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.


Constraints:

The number of nodes in the tree is in the range `[1, 3 104]. *-3 104 <= Node.val <= 3 104`

题目大意：

求从父到子的最长连续数列的长度(由小到大)

解题思路：

DFS

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大
LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

解题步骤：

N/A

注意事项：

  1. 题意是从父到儿子的有小到大数列，而不是儿子到父亲
  2. 以root为起点的最长数列，若root不符合条件，不加入left或right的长度
  3. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有三种情况：自己，自己+左，自己+右

Python代码：

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

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:  # remember not ==
			lpath += left
		if root.right and root.val + 1 == root.right.val:
			rpath += right
		res = max(lpath, rpath)
		max_len = max(res, max_len)
		return res

	dfs(root)
	return max_len

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:



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


Example 2:

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


Constraints:

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

题目大意：

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

解题思路：

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



Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:



Input: root = [1,2,3]
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].


Example 2:



Input: root = [2,1,3]
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].


Constraints: The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
`-3 104 <= Node.val <= 3 * 104`

题目大意：

求任意节点到另一个节点的最长连续数列的长度(由小到大)

解题思路：

类似于LeetCode 298 Binary Tree Longest Consecutive Sequence，不过由于父亲到儿子可能递增或递减，所以DFS返回值也返回递增和递减的长度

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大
LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

解题步骤：

N/A

注意事项：

  1. DFS返回值也返回递增和递减的长度
  2. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

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
def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0, 0  # (increasing, decreasing) from root
		nonlocal max_len
		inc = desc = 1
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:
			lpath += left[0]
		if root.right and root.val + 1 == root.right.val:
			rpath += right[0]
		inc = max(1, lpath, rpath)

		lpath = rpath = 1
		if root.left and root.val - 1 == root.left.val:
			lpath += left[1]
		if root.right and root.val - 1 == root.right.val:
			rpath += right[1]
		desc = max(1, lpath, rpath)

		total = inc + desc - 1
		max_len = max(inc, desc, total, max_len)
		return inc, desc

	dfs(root)
	return max_len

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:

Input: a = 1, b = 2
Output: “abb”
Explanation: “abb”, “bab” and “bba” are all correct answers.


Example 2:

Input: a = 4, b = 1
Output: “aabaa”


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

题目大意：

给定两个整数代表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



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?

算法思路：

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

算法分析：

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

Free mock interview