KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

<pre>Input: num = "123", target = 6 Output: ["123","1+2+3"] Explanation: Both "123" and "1+2+3" evaluate to 6. </pre>

Example 2:

<pre>Input: num = "232", target = 8 Output: ["23+2","2+32"] Explanation: Both "23+2" and "2+32" evaluate to 8. </pre>

Example 3:

<pre>Input: num = "3456237490", target = 9191 Output: [] Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191. </pre>

Constraints:

  • 1 <= num.length <= 10
  • num consists of only digits.
  • -2<sup>31</sup> <= target <= 2<sup>31</sup> - 1

</div>

题目大意：

求一串数字加入加减乘能得到target的所有可能性

解题思路：

求所有可能用DFS。属于分割型DFS，在数位之间加符号，数位可以是1个到多个。
一轮递归分割出符号 + 数字 另一种选择是数字 + 符号，但需要额外变量sign，因为不能立刻计算到结果。也不符合正常逻辑。所以选择前者。

由于运算都是二元，也就是用上述分割法，第一个数要特别处理。所以DFS中要特别处理第一个数。这样可以开始写加减。引入prev_res作为DFS参数，这样只要prev_res 加减 该轮数字即可得到该轮结果。用DFS模板5个标准参数外加prev_res： 

1
def dfs(self, num, st, target, prev_res, path, res):
这样只处理加减的DFS比较容易实现

最大难点在于乘法，参考LeetCode 227 Basic Calculator II，加减和乘除属于两层计算需要分别处理，所以引入新参数prev_multi_res，用于保存乘法结果，而刚才的命名为prev_add_res保存加减乘的全部结果

1
def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
举例2+3*4，按照原来的逻辑会计算到2+3=5，但此时如果遇到乘号，就要重新计算加法结果，先减去乘法结果，退回到2，再计算3*4=12这是乘法结果，再加回2得到新加法结果。进一步理解prev_multi_res，如果该轮是加减法，仍要将该轮的数作为prev_multi_res传到下轮DFS，因为如果下一轮是乘法，它就是第一个乘法的数。

解题步骤：

  1. 先实现加减法
  2. 再实现乘法

注意事项：

  1. 分割型DFS，选择每轮递归分割符号 + 数字。由于运算都是二元，特别处理第一个数
  2. 引入参数prev_add_res, prev_multi_res. prev_multi_res若是加减，用(+/-)cur_num, 否则用乘法结果prev_multi_res * cur_num。注意若是减法cur_num用负号
  3. 分割时数字不能有前缀0
  4. prev_res不用恢复状态因为是标量

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def addOperators(self, num: str, target: int) -> List[str]:
	res = []
	self.dfs(num, 0, target, 0, 0, '', res)
	return res

def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
	if st == len(num):
		if target == prev_add_res:
			res.append(path)
		return
	for i in range(st, len(num)):
		if i > st and num[st] == '0': # remember
			continue
		cur_num = int(num[st:i + 1])
		if not path: # remember
		    # first number, same as + case
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, str(cur_num), res)
		else:
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, path + '+' + str(cur_num), res) # use cur_num rather than cur
			self.dfs(num, i + 1, target, prev_add_res - cur_num, -cur_num, path + '-' + str(cur_num), res) # -cur_num rather than cur_num
			self.dfs(num, i + 1, target, (prev_add_res - prev_multi_res) + prev_multi_res * cur_num, prev_multi_res * cur_num, path + '*' + str(cur_num), res) # prev_multi_res * cur_num not cur_num

算法分析：

时间复杂度为<code>O(4<sup>n</sup>)</code>，空间复杂度O(n), 因为每个字符之间都有不加操作符，加3个操作符，所以是4，有n-1个间隔

Posted on Edited on Disqus:

LeetCode

<div>

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

<pre>Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. </pre>

Example 2:

<pre>Input: nums = [-1] Output: [0] </pre>

Example 3:

<pre>Input: nums = [-1,-1] Output: [0,0] </pre>

Constraints:

  • 1 <= nums.length <= 10<sup>5</sup>
  • -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

</div>

题目大意：

数组中，统计每一位比自己小的数。

解题思路：

一开始考虑用递减栈。但不可行, 因为这是统计题，而不是求比自己大的一个数LeetCode 503 Next Greater Element II。类似于merge sort，考虑统计逆序数

解题步骤：

N/A

注意事项：

  1. 由于mergesort会改变数组顺序，所以统计数组count也要对应的数也会变，所以将原数组变成(数值, 下标)对，count就可以统计原数组
  2. 计算逆序对时候，放在nums[i][0] <= nums[j][0]中，核心在count[nums[i][1]] += j - mid - 1

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
def countSmaller(self, nums: List[int]) -> List[int]:
	count = [0] * len(nums)
	num_with_idx = [(n, i) for i, n in enumerate(nums)]
	self.merge_sort(num_with_idx, 0, len(nums) - 1, count)
	return count

def merge_sort(self, nums, start, end, count):
	if start >= end:
		return
	mid = start + (end - start) // 2
	self.merge_sort(nums, start, mid, count)
	self.merge_sort(nums, mid + 1, end, count)
	self.merge(nums, start, mid, end, count)

def merge(self, nums, start, mid, end, count):
	i, j = start, mid + 1
	res = []
	while i <= mid and j <= end:
		if nums[i][0] <= nums[j][0]:
			res.append(nums[i])
			count[nums[i][1]] += j - mid - 1
			i += 1
		else:
			res.append(nums[j])
			j += 1
	while i <= mid:
		res.append(nums[i])
		count[nums[i][1]] += j - mid - 1
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1
	nums[start:end + 1] = res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

<pre>Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 </pre>

Example 2:

<pre>Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. </pre>

Example 3:

<pre>Input: amount = 10, coins = [10] Output: 1 </pre>

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000

</div>

题目大意：

求兑换硬币的种数

解题思路：

类似于LeetCode 322 Coin Change，那题求最小个数，此题求总数，也是用DP。
递归式： 

1
dp[i] = sum(dp[j]), i = j + coins[i]

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列 LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题步骤：

递归5部曲

注意事项：

  1. for循环顺序不能错，先coin再dp，否则会有重复计算，如dp[3] = 2 + 1和1 + 2. 字面上理解也是可以知道重复。但如果coin先的话，就只能用1的硬币，第二轮是只能用2的硬币，如此类推，显然不会重复，dp[3] = dp[2] + 1(只用硬币1), dp[1] + 2(只用硬币2)

Python代码：

1
2
3
4
5
6
7
8
9
# dp[i] = dp[j], i = j + coins[i]
def change(self, amount: int, coins: List[int]) -> int:
	dp = [0] * (amount + 1)
	dp[0] = 1
	for coin in coins:
		for i in range(len(dp)): # [0, 0]
			if i + coin <= amount:
				dp[i + coin] += dp[i]
	return dp[-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

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

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.

</div>

题目大意：

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

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

<div>

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:

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

Example 2:

<pre>Input: nums = [1,1,1] Output: 0 </pre>

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.

</div>

题目大意：

求最小移动步数使得数组所有数相等。每次移动是将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)

Free mock interview