KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:



Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.


Example 2:



Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
          1 is at the top, so it comes first.
          5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.


Example 3:



Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.


Constraints:

The number of nodes in the tree is in the range [1, 1000]. 0 <= Node.val <= 1000

题目大意：

按列顺序打印二叉树，若列号同，同一行的节点按值排序

解题思路：

与LeetCode 314 Binary Tree Vertical Order Traversal类似，用BFS

LeetCode 314 Binary Tree Vertical Order Traversal 同一列，从上到下，从左到右排序
LeetCode 987 Vertical Order Traversal of a Binary Tree 同一列，从上到下，同一行值从小到大排序

解题步骤：

N/A

注意事项：

与LeetCode 314实现的区别

  1. 一开始以为同一列的同一行的节点在queue是一个紧接一个出列。但同一行节点可能先出列col=3, col=4， col=3。而且同一列同一行的节点有多个，不止两个。所以将row_id也加入到queue节点和map中
  2. 遍历结果时，map中的value排序**, value是先row_id再node.val，所以直接可以排序，最后直接取出第二维度

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
	if not root:
		return []
	col_to_node_list = collections.defaultdict(list)
	min_col, max_col = float('inf'), float('-inf')
	queue = collections.deque([(root, 0, 0)])
	while queue:
		node, row_id, col_id = queue.popleft()
		col_to_node_list[col_id].append((row_id, node.val))
		min_col, max_col = min(min_col, col_id), max(max_col, col_id)
		if node.left:
			queue.append((node.left, row_id + 1, col_id - 1))
		if node.right:
			queue.append((node.right, row_id + 1, col_id + 1))
	res = []
	for i in range(min_col, max_col + 1):
		col_to_node_list[i].sort()
		res.append([_[1] for _ in col_to_node_list[i]])
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)，稍大于O(n), 因为同一列同一行节点要排序

Posted on Edited on Disqus:

LeetCode



Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation: Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]


Example 2:

Input: nums = [1,1,1]
Output: 0


Constraints:

n == nums.length 1 <= nums.length <= 10<sup>5</sup>
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup> The answer is guaranteed to fit in a 32-bit integer.

题目大意：

求最小移动步数使得数组所有数相等。每次移动是将n-1个元素加1

解题思路：

最小值考虑用DP。但比较难写递归式，以[1, 2, 3]为例，值为3，现在是[1, 2, 3, 6]，由于dp[3]的最终状态为[4, 4, 4], 而最终状态加上新元素为[4, 4, 4, 9], 由6变成9是因为dp[3] = 3，表示移动了3步，新元素6，移动的3步全部参与了，所以变成9
由[4, 4, 4, 9], 4变9，需要5步，所以结果dp[4] = dp[3] + 5 = 8

公式为

1
2
dp[i + 1] = dp[i] + (nums[i] + dp[i] - equal_num)  
equal_num = nums[i] + dp[i]

解题步骤：

N/A

注意事项：

  1. 数组要排序
  2. equal_num初始值为nums[0]

Python代码：

1
2
3
4
5
6
def minMoves(self, nums: List[int]) -> int:
	nums.sort()
	dp, equal_num = 0, nums[0]
	for n in nums:
		dp, equal_num = dp + (n + dp - equal_num), n + dp # 2
	return dp

算法分析：

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

Posted on Edited on Disqus:

LeetCode



A binary string is monotone increasing if it consists of some number of 0‘s (possibly none), followed by some number of 1‘s (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

Example 1:

Input: s = “00110”
Output: 1
Explanation: We flip the last digit to get 00111.


Example 2:

Input: s = “010110”
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.


Example 3:

Input: s = “00011000”
Output: 2
Explanation: We flip to get 00000000.


Constraints:

1 <= s.length <= 10<sup>5</sup> s[i] is either '0' or '1'.

题目大意：

01字符串中Flip其中一些将它变成00111,0和1的个数是任意。

DP解题思路(推荐)：

求最小值考虑用BFS或者DP。BFS的复杂度可能比较大，DP定义为以s[i]为结尾的最小flip数，但由于不知道具体排列(末状态)是什么或者结尾是什么，所以比较难从子问题推导出来。
不妨用两个dp来计算，
dp为以0为结尾的最小flip数
dp2为以1为结尾的最小flip数

1
2
3
4
5
dp = dp     if s[i] = '0'
   = dp + 1 if s[i] = '1'
   
dp2 = min(dp2 + 1, dp + 1)     if s[i] = '0'
    = min(dp2, dp)             if s[i] = '1'

公式不是对称，因为题意是先0再1。

解题步骤：

N/A

注意事项：

  1. 用Python的dp和dp2同时由前状态赋值，这样避免用临时变量

Python代码：

1
2
3
4
5
6
7
8
def minFlipsMonoIncr(self, s: str) -> int:
	dp, dp2 = 0, 0
	for i in range(len(s)):
		if s[i] == '0':
			dp, dp2 = dp, min(dp, dp2) + 1
		else:
			dp, dp2 = dp + 1, min(dp2, dp)
	return min(dp, dp2)

算法分析：

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

presum算法II解题思路：

统计1的个数，若是0同时统计从0 flip到1的个数，取两者较小为新flip数。较难理解，不推荐

Python代码：

1
2
3
4
5
6
7
8
9
def minFlipsMonoIncr2(self, s: str) -> int:
	ones, flips = 0, 0
	for c in s:
		if c == '1':
			ones += 1
		else:
			flips += 1
		flips = min(ones, flips)
	return flips

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.

For example if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

Example 1:

Input: s = “ABC”
Output: 10
Explanation: All possible substrings are: “A”,”B”,”C”,”AB”,”BC” and “ABC”.
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10


Example 2:

Input: s = “ABA”
Output: 8
Explanation: The same as example 1, except countUniqueChars(“ABA”) = 1.


Example 3:

Input: s = “LEETCODE”
Output: 92


Constraints: 1 <= s.length <= 105
* s consists of uppercase English letters only.

题目大意：

求所有子串的唯一字符的个数的总和

解题思路：

暴力法是所有子串O(n^2)，统计唯一字符个数O(n), 复杂度为O(n^3). 尝试优化统计那一步，用presum map来详见可以O(1)求得，但内存过大，仍然TLE。
求个个数且是字符串题，考虑用DP。此题还有点似Leetcode 003 Longest Substring Without Repeating Characters。

写几个找规律且从简单开始，也就是没有重复

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
A: 1
AB: 1                + 2 + 1 = 4, 1是dp[1], 2是以B结尾的2个子串有两个B，最后一个1表示AB串中有一个A  
       B
      AB        
ABC： 4           + 3 + 2 + 1 = 10， 4是dp[2], 2是以C结尾的3个子串有三个C，2个B，1个A. Delta = 6  
        C
       BC
      ABC  
ABCB:10      + 2 + 3 + 0 + 1 = 16, 同理是上一个DP结果和从后往前每个字母在新子串中的唯一数。由于出现重复，B从4个变成2个，前一个B变成0个，其他加法项是不变的。Delta = 6 + 4 - 2 x 2 = 6 公式为Delta = Delta + 当前长度 - (i - 上一个重复元素下标) x 2    
         B
        CB
       BCB
      ABCB  
ABCBA:16 + 4 + 2 + 3 + 0 + 0 = 25 = 16 + delta 验证公式delta = 6 + 5 - 1 x 2 = 9    
          A 
         BA
        CBA
       BCBA
      ABCBA 
ABCBAC:25 + 3 + 4 + 2 + 0 + 0 + 0 = 34 = 25 + delta 验证公式delta = 9 + 6 - (6 - 3) x 2 = 9    
           C 
          AC 
         BAC
        CBAC
       BCBAC
      ABCBAC 
ABCBACA:34 + 2 + 3 + 0 + 2 + 0 + 0 + 0 = 41 = 34 + delta 验证公式delta = 9 + 7 - (7 - 2) x 2 = 6不匹配，新A本来是7个变成2个，而次新A上一轮有4个最多减4个并不能减5个，所以x 2是不对的。      
            A 
           CA 
          ACA 
         BACA
        CBACA
       BCBACA
      ABCBACA

公式为：

1
2
Delta = Delta + 当前下标 - 上一个重复元素下标 - (上一个重复元素下标 - 上个重复元素对应的下标)
Res += Delta

公式解释：
delta是每增加一个字符的增量。若每一个字符都不重复，Delta = Delta + 当前长度表示增加了最后一个字符的数量如AB -> ABC
若有重复，就只增加遇到前一个重复前的个数，如ABCB -> ABCBA的4个
若前面重复有2个，就还要减去在算前一个重复时的增量如上图ABCBACA中BACA和CBACA中在BA和CBA时候当时A没有重复，计算了2个

解题步骤：

delta_sum为上一轮的增加的唯一元素个数
delta[i]为下标为i的元素的唯一个数的增量

注意事项：

  1. 公式中减去重复个数不能乘以2，因为上一个重复元素的增量可能不够减

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def uniqueLetterString(self, s: str) -> int:
	res, delta_sum, delta, char_to_index = 0, 0, [0] * len(s), collections.defaultdict(lambda: -1)
	for i in range(len(s)):
		cur_len = i + 1
		delta[i] = cur_len
		if s[i] in char_to_index:
			delta[i] -= char_to_index[s[i]] + 1
			delta_sum += delta[i] - delta[char_to_index[s[i]]]
			delta[char_to_index[s[i]]] = 0
		else:
			delta_sum += delta[i]
		res += delta_sum
		char_to_index[s[i]] = i
	return res

算法分析：

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

两个Map算法II解题思路(推荐)：

公式中上个重复元素对应的加法项也就是上个重复元素与上上个重复元素的距离，所以引入另一个map来记录，避免用delta[i]，算法更加简单。

Python代码：

1
2
3
4
5
6
7
8
9
10
def uniqueLetterString(self, s: str) -> int:
	last_char_to_index = collections.defaultdict(lambda: -1)
	last_last_char_to_index = collections.defaultdict(lambda: -1)
	res, delta = 0, 0
	for i, c in enumerate(s):
		delta += i - last_char_to_index[c] - (last_char_to_index[c] - last_last_char_to_index[c])
		last_last_char_to_index[c] = last_char_to_index[c]
		last_char_to_index[c] = i
		res += delta
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

The path starts with a single slash '/'. Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'. The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

Input: path = “/home/“
Output: “/home”
Explanation: Note that there is no trailing slash after the last directory name.


Example 2:

Input: path = “/../“
Output: “/“
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.


Example 3:

Input: path = “/home//foo/“
Output: “/home/foo”
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.


Constraints:

1 <= path.length <= 3000 path consists of English letters, digits, period '.', slash '/' or '_'.
* path is a valid absolute Unix path.

题目大意：

简化路径，遇.表示当前目录不做事，遇..表示到上一个目录

解题思路：

路径类似于括号题，利用括号题模板

解题步骤：

N/A

注意事项：

  1. edge case /../ 表示若stack为空，就不pop。if stack不能加到elif token == ‘..’中
  2. 遇到..返回到上层目录

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def simplifyPath(self, path: str) -> str:
	path += '/'
	token, stack = '', []
	for c in path:
		if c == '/':
			if token == '.':
				pass
			elif token == '..':
				if stack: # remember
					stack.pop()
			elif token:
				stack.append(token)
			token = ''
		else:
			token += c
	return '/' + '/'.join(stack)

算法分析：

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

Free mock interview