KK's blog

LeetCode

<div>

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

<pre>Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. </pre>

Example 2:

<pre>Input: num = 9973 Output: 9973 Explanation: No swap. </pre>

Constraints:

• 0 <= num <= 10<sup>8</sup>

</div>

题目大意：

给定一个数，最多交换一位，使得这个数尽可能最大

解题思路：

类似于LeetCode 854 K-Similar Strings, 如2736， 求2后面最大的数为7，和7交换即为所求。这里有两个问题：

1. 第一位可能已经是最大的数位，这样需要遍历每个数位，找到能交换的数位，若这个位在倒序排序后位置一样，表明此位不能交换。所以排序法的算法复杂度为n平方
2. 若要优化就要采用bucket sort，因为数位是有限的。若后续数位有一个数比自己大，表示可交换。所以只要记录每个数位的位置，贪心法从9(最大)遍历到自己，若该位位置在自己之后，可交换
3. 若不同数位上数值相同，应该记录其最后的位置，因为交换时候将小的尽量往后交换，越好越不重要，如2949, 2和最后的9交换得到最大的数

解题步骤：

N/A

注意事项：

1. 内循环从9遍历到该位数值(不包括)
2. buckets的key为字符串，注意整数和字符串互换，如buckets[str(j)], int(digits[i])

Python代码：

1
2
3
4
5
6
7
8
9

def maximumSwap(self, num: int) -> int:
	digits, buckets = str(num), collections.defaultdict(int)
	for i, digit in enumerate(digits):
		buckets[digit] = i # use last position for same char
	for i in range(len(digits)):
		for j in range(9, int(digits[i]), -1): # remember to use int(digits[i]) not i
			if buckets[str(j)] > i: # 2736, i = (2), j = (7) # remember to use str j
				return int(digits[:i] + digits[buckets[str(j)]] + digits[i + 1:buckets[str(j)]] + digits[i] + digits[buckets[str(j)] + 1:])
	return num

算法分析：

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

LeetCode

<div>

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

Example 1:

<pre>Input: strs = ["tars","rats","arts","star"] Output: 2 </pre>

Example 2:

<pre>Input: strs = ["omv","ovm"] Output: 1 </pre>

Constraints:

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only.
• All words in strs have the same length and are anagrams of each other.

</div>

题目大意：

单词列表中，可以分成多少组，每组里面的单词互相之间至少有一对可以通过交换一个位置变成另一个单词

解题思路：

典型求连通集个数，类似于Num of island，用BFS。难点在于怎么找到neighbor，用遍历每一个单词的方式

解题步骤：

N/A

注意事项：

1. 难点在于怎么找到neighbor，用遍历每一个单词的方式，判断是否buddyStrings Leetcode 0859

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

def numSimilarGroups(self, strs: List[str]) -> int:
	if not strs:
		return 0
	visited, groups, word_set = set(), 0, set(strs)
	for s in strs:
		if s in visited:
			continue
		self.bfs(word_set, s, visited)
		groups += 1
	return groups

def bfs(self, word_set, start, visited):
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		for s in word_set:
			if s in visited:
				continue
			if node == s or not self.buddyStrings(node, s):
				continue
			queue.append(s)
			visited.add(s)

def buddyStrings(self, s: str, goal: str) -> bool:
	if len(s) != len(goal):
		return False
	if s == goal and len(set(s)) < len(goal):  # any dups
		return True
	diff = [(a, b) for a, b in zip(s, goal) if a != b]
	return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False

算法分析：

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

LeetCode

<div>

Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

Example 1:

<pre>Input: s1 = "ab", s2 = "ba" Output: 1 </pre>

Example 2:

<pre>Input: s1 = "abc", s2 = "bca" Output: 2 </pre>

Constraints:

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
• s2 is an anagram of s1.

</div>

题目大意：

两字符，交换两个位置，使得他们相等，求最小交换次数

解题思路：

最值考虑用BFS，难点在于生成neighbor，见注意事项

解题步骤：

N/A

注意事项：

1. 用例子写程序node = abc s2 = cba, 先找到第一个不同位i，然后找下一个不同位j，这个不同位node[j]需要与目标s2[i]相同，贪心法
2. 倒数第二行要break，否则TLE，因为只要找到一位可以交换这一层的BFS算是结束

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def kSimilarity(self, s1: str, s2: str) -> int:
	queue = collections.deque([s1])
	visited = set([s1])
	distance = {s1: 0}
	while queue:
		node = queue.popleft()
		if node == s2:
			return distance[node]
		for i in range(len(node)): # abc, cba
			if node[i] == s2[i]:
				continue
			for j in range(i + 1, len(node)):
				if node[j] == s2[j]:
					continue
				if node[j] == s2[i]:
					ss = node[:i] + node[j] + node[i + 1:j] + node[i] + node[j + 1:]
					if ss in visited:
						continue
					queue.append(ss)
					visited.add(ss)
					distance[ss] = distance[node] + 1
			break # remember
	return -1

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小)

LeetCode

<div>

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

• For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

<pre>Input: s = "ab", goal = "ba" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal. </pre>

Example 2:

<pre>Input: s = "ab", goal = "ab" Output: false Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal. </pre>

Example 3:

<pre>Input: s = "aa", goal = "aa" Output: true Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal. </pre>

Constraints:

• 1 <= s.length, goal.length <= 2 * 10<sup>4</sup>
• s and goal consist of lowercase letters.

</div>

题目大意：

给定两字符串，交换一次使得他们相等

解题思路：

三种情况： 长度不等，完全相等（若至少有一个重复，即满足题意），两次不同

解题步骤：

N/A

注意事项：

1. 三种情况： 长度不等，完全相等，两次不同

Python代码：

1
2
3
4
5
6
7

def buddyStrings(self, s: str, goal: str) -> bool:
	if len(s) != len(goal):
		return False
	if s == goal and len(set(s)) < len(goal): # any dups
		return True
	diff = [(a, b) for a, b in zip(s, goal) if a != b]
	return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False

算法分析：

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

A change for two N-children tree contains:

1. key is different
2. value is different
3. delete a node
4. add a node

Problem: how many changes to convert tree A to tree B

题目大意：

DD的面经题，多少个改动可以使得existingTree变成newTree

解题思路：

DFS, 比较children，三种情况。若其中一方没有节点，就是计算节点数

解题步骤：

N/A

注意事项：

1. 比较children，三种情况。若其中一方没有节点，就是计算节点数

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

def changeNodes(self, existingTree, newTree) -> int:
	if not existingTree and not newTree:
		return 0
	if not existingTree or not newTree:
		return self.count(existingTree) + self.count(newTree)
	res = 0 if existingTree.key == newTree.key and existingTree.val == newTree.val else 1
	existing_children_dict = self.get_children_dict(existingTree.children)
	new_tree_children_dict = self.get_children_dict(newTree.children)
	for key in existing_children_dict.keys() & new_tree_children_dict.keys(): # in both
		res += self.changeNodes(existing_children_dict[key], new_tree_children_dict[key])
	for key in existing_children_dict.keys() - new_tree_children_dict.keys(): # in existing tree not in new tree
		res += self.count(existing_children_dict[key])
	for key in new_tree_children_dict.keys() - existing_children_dict.keys():  # in new tree not in existing tree
		res += self.count(new_tree_children_dict[key])
	return res

def count(self, root):
	if not root:
		return 0
	res = 0
	for child in root.children:
		res += self.count(child)
	return 1 + res

def get_children_dict(self, children):
	key_to_node = {}
	for child in children:
		key_to_node[child.key] = child
	return key_to_node

算法分析：

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