KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [[“John”,”johnsmith@mail.com”,”john_newyork@mail.com”],[“John”,”johnsmith@mail.com”,”john00@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]
Output: [[“John”,”john00@mail.com”,”john_newyork@mail.com”,”johnsmith@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]
Explanation:
The first and second John’s are the same person as they have the common email “johnsmith@mail.com”.
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’],
[‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.


Example 2:

Input: accounts = [[“Gabe”,”Gabe0@m.co”,”Gabe3@m.co”,”Gabe1@m.co”],[“Kevin”,”Kevin3@m.co”,”Kevin5@m.co”,”Kevin0@m.co”],[“Ethan”,”Ethan5@m.co”,”Ethan4@m.co”,”Ethan0@m.co”],[“Hanzo”,”Hanzo3@m.co”,”Hanzo1@m.co”,”Hanzo0@m.co”],[“Fern”,”Fern5@m.co”,”Fern1@m.co”,”Fern0@m.co”]]
Output: [[“Ethan”,”Ethan0@m.co”,”Ethan4@m.co”,”Ethan5@m.co”],[“Gabe”,”Gabe0@m.co”,”Gabe1@m.co”,”Gabe3@m.co”],[“Hanzo”,”Hanzo0@m.co”,”Hanzo1@m.co”,”Hanzo3@m.co”],[“Kevin”,”Kevin0@m.co”,”Kevin3@m.co”,”Kevin5@m.co”],[“Fern”,”Fern0@m.co”,”Fern1@m.co”,”Fern5@m.co”]]


Constraints:

1 <= accounts.length <= 1000 2 <= accounts[i].length <= 10
1 <= accounts[i][j] <= 30 accounts[i][0] consists of English letters.
* accounts[i][j] (for j > 0) is a valid email.

题目大意：

每个人都有一堆邮件，根据邮件是否相同判断是否同一个人，合并同一个人的所有邮件。

BFS解题思路(推荐)：

根据输入建图，然后类似于Num of island从某一个邮件出发用BFS找连通的所有邮件，迭代所有邮件，全局visited来记录访问过的，这点跟Num of island一样。

解题步骤：

N/A

注意事项：

  1. 图的初始化，要记得没有边的图要加入到邻接表中，注意不存在的时候才加入，否则会覆盖现有的邻接表Line 8 - 9
  2. 处理名字(第一个元素)，名字对确定是否连通没有任何作用，只需要加入到最后结果即可
  3. 有重复邮件，所以一开始去重。结果按同一账号内按字母排序

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
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
	for li in accounts:
		li[:] = [li[0]] + list(set(li[1:]))
	graph = collections.defaultdict(list)
	name_dict = collections.defaultdict(str)
	for li in accounts:
		name_dict[li[1]] = li[0]
		if li[1] not in graph:
			graph[li[1]] = [] # remember single email
		for i in range(2, len(li)):
			graph[li[1]].append(li[i])
			graph[li[i]].append(li[1])
	res, visited = [], set()
	for email in graph.keys():
		sub_res = self.bfs(graph, email, visited, name_dict)
		if sub_res:
			res.append(sub_res)
	return res

def bfs(self, graph, start, visited, name_dict):
	if start in visited:
		return
	res, name = [], ''
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		res.append(node)
		if node in name_dict:
			name = name_dict[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
	res.sort()
	res.insert(0, name)
	return res

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数, 因为结果需要按字母排序

UnionFind算法II解题思路(不推荐)：

这题很容易想到用连通集做，但其实连通集应用条件为动态求连通集个数。这题是静态求连通数，所以类似于L200 Num of island可以用DFS或者BFS。

注意事项：

  1. union只做每个list里面的，而list之间相同的邮件不用做union，因为既然相同自动做了
  2. 模板的问题，见UnionFind里的注意事项： if self.parent[email] != email, self.parent[parent] = parent2
  3. 处理名字
  4. 有重复邮件

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
class Solution(TestCases):

    def accountsMerge2(self, accounts: List[List[str]]) -> List[List[str]]:
        for li in accounts:
            li[::] = [li[0]] + list(set(li[1:]))
        uf = UnionFind(accounts)

        for li in accounts:
            for i in range(2, len(li)):
                uf.union(li[i - 1], li[i])

        visited = set()
        res = collections.defaultdict(list)
        name_dict = collections.defaultdict(str)
        for li in accounts:
            name_dict[uf.find(li[1])] = li[0]
            for email in li[1:]:
                if email in visited:  # remember
                    continue
                res[uf.find(email)].append(email)
                visited.add(email)
        for _id, li in res.items():
            li.sort()
            li.insert(0, name_dict[_id])
        return list(res.values())

class UnionFind:

    def __init__(self, email_list):
        self.parent = collections.defaultdict(str)
        for i, li in enumerate(email_list):
            for email in li[1:]:
                self.parent[email] = email

    def find(self, email):
        if self.parent[email] != email:  # if statement
            self.parent[email] = self.find(self.parent[email])
        return self.parent[email]

    def union(self, email, email2):
        parent = self.find(email)
        parent2 = self.find(email2)
        if parent != parent2:
            self.parent[parent] = parent2 # remember not self.parent[email] = email2

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数

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



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



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), 因为同一列同一行节点要排序

Free mock interview