面试准备：优化 swapLexOrder
interview prep: optimizing swapLexOrder
面试关于代码打架的哈希图问题，需要帮助优化我的暴力解决方案。这是问题所在：
给定字符串 str 和指示可以交换字符串中的哪些索引的对数组，return 执行允许的交换后产生的字典序最大的字符串。您可以多次交换索引。
例子
For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
swapLexOrder(str, pairs) = "dbca".
通过交换给定的索引，您可以得到字符串："cbda"、"cbad"、"dbac"、"dbca"。此列表中字典序最大的字符串是 "dbca".
我目前的解决方案
通过不断添加所有可能性直到没有新的解决方案来进行暴力破解。这对于 swapLexOrder('dznsxamwoj',[[1,2],[3,4],[6,5],[8,10]]) 来说太慢了，无法在我的机器上完成。任何优化提示？一个更容易通过的测试用例是 swapLexOrder('abdc,[[1,4],[3,4]])= dbca
def swapLexOrder(str, pairs):
d = {}
d[str]=True
while True:
oldlen=len(d)
for x,y in pairs:
for s in d.keys():
d[swp(s,x,y)]=True
if len(d) == oldlen:
#no more new combinations.
return sorted(d)[-1]
def swp(str,x,y):
x=x-1
y=y-1
a=str[x]
b=str[y]
return str[0:x]+b+str[x+1:y]+a+str[y+1:]
我建议的解决方案是首先尝试 'link' 尽可能多的对以形成可以互换的索引集 - 例如，在您的第一个示例中，[[1, 4], [3, 4]] 可以变成 [[1, 3, 4]].然后可以按字典顺序对这些索引的每个子集进行排序以形成输出。实现是这样的：
def build_permitted_subs(pairs):
perm = []
for a, b in pairs:
merged = False
for ind, sub_perm in enumerate(perm):
if a in sub_perm or b in sub_perm:
sub_perm.add(a)
sub_perm.add(b)
merged = True
break
else:
perm.append(set([a, b]))
if merged:
for merge_perm_ind in reversed(range(ind + 1, len(perm))):
if perm[merge_perm_ind] & sub_perm:
sub_perm.update(perm[merge_perm_ind])
perm.pop(merge_perm_ind)
return list(map(sorted, perm))
def swap_lex_order(swap_str, _pairs):
pairs = [[a - 1, b - 1] for a, b in _pairs]
out = list(swap_str)
perm = build_permitted_subs(pairs)
for sub_perm in perm:
sorted_subset = sorted(sub_perm, key=lambda ind: swap_str[ind], reverse=True)
for sort, targ in zip(sorted_subset, sub_perm):
out[targ] = swap_str[sort]
return "".join(out)
print(swap_lex_order("dznsxamwoj", [[1, 2], [3, 4], [6, 5], [8, 10]]))
print(swap_lex_order("abdc", [[1, 4], [3, 4]]))
print(swap_lex_order("acxrabdz",[[1,3], [6,8], [3,8], [2,7]]))
输出：
zdsnxamwoj
dbca
zdxrabca
我还重命名了您的参数以不使用 str，这已经是一个非常基本的 Python 内置。请注意，我的代码可能没有尽可能 Pythonic，但我认为它足以很好地说明算法，并且没有受到任何重大性能影响。我怀疑这种方法的复杂性很低——它通常是 'intelligent'，因为它不会暴力破解任何东西，并且使用 O(n log n) 排序。第一个例子似乎是正确的。请注意，这会将每对转换为基于 0 的，因为这对于 Python.
来说要容易得多
这有点依赖于能够从相邻排列（交换对）中形成任何排列（对链接对进行排序）。这可能不完全直观，但它可能有助于认识到您可以仅使用列表中的相邻交换来有效地执行插入（通过在元素移动的方向上不断交换元素）。使用相邻交换排列列表的一个示例是冒泡排序，您可能会意识到，如果可以对任何排列进行冒泡排序，则意味着所有排列都可以通过冒泡排序实现。
如果您有任何疑问，或有任何问题，请告诉我，我会开始 elaborating/debugging。 （截至格林威治标准时间 19:28，我已经注意到一个错误并已将其编辑掉 : )。 Bug #2（在测试用例 3 中有重复的 z）也应该被修复。
关于 bug #1 的更多信息：
我没有对 build_permitted_subs 返回的索引进行排序，因此无法参考 swap_str.
对它们进行正确排序
有关错误 #2 的更多信息：
build_permitted_subs 功能没有正常工作 - 具体来说，如果它遇到一对可以分成两个组，这意味着这些组也应该加入在一起，这没有发生，现在会有是两个不应该分开的团体。这导致 z 重复，因为两个组都可以从 z 中提取。我草率地用一个标志和一个可追溯的 for 循环修复了这个问题。
这个也许效果更好。
def swapLexOrder(str_, pairs):
n = len(str_)
str_ = list(str_)
corr = [set() for _ in range(n)]
nodes = set()
for a, b in pairs:
corr[a-1].add(b-1)
corr[b-1].add(a-1)
nodes.add(a-1)
nodes.add(b-1)
while nodes:
active = {nodes.pop()}
group = set()
while active:
group |= active
nodes -= active
active = {y for x in active for y in corr[x] if y in nodes}
chars = iter(sorted((str_[i] for i in group), reverse=True))
for i in sorted(group):
str_[i] = next(chars)
return "".join(str_)
def swapLexOrder(str, pairs):
if not str or not pairs:
return ('', str)[not pairs]
lst = [''] + list(str)
setted_pairs = list(map(set, pairs))
while setted_pairs:
path = setted_pairs.pop(0)
while True:
path1 = path.copy()
for pair in setted_pairs:
if path1 & pair:
path |= pair
setted_pairs.remove(pair)
if path == path1:
break
optimal = sorted(lst[i] for i in path)
for i, v in enumerate(sorted(path, reverse=True)):
lst[v] = optimal[i]
return ''.join(lst[1:])
我的首选解决方案是使用不相交集来解决此问题。关键思想是建立一个类似于链表的对的连接图。这表示由对连接的子串。一旦弄清楚连接的内容，就可以对子字符串进行排序，然后在构建字符串时从子字符串中挑选出最字典序的字符。
不相交集在这里有很大帮助，因为它可以让我们以极快的速度找出连接的东西。它实际上比 log 快，它是 log*。我建议阅读 Wikipedia page 以获得解释。通过使用 union 函数，我们可以从给定的对构建“链表”。
import collections
class DisjointSet:
def __init__(self, string, pairs):
self.parent = [i for i in range(len(string))]
self.size = [1] * len(string)
for a, b in pairs:
self.union(a-1, b-1)
def find_parent(self, idx):
# O(log*(n))
if self.parent[idx] == idx:
return idx
self.parent[idx] = self.find_parent(self.parent[idx])
return self.parent[idx]
def union(self, a, b):
# O(log*(n))
x = self.find_parent(a)
y = self.find_parent(b)
if x == y:
return
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] = self.size[x] + self.size[y]
def swapLexOrder(string, pairs):
# O(nlogn) + O(nlog*(n))
string = list(string)
# Build the disjoint set to figure out what pairs are connected
disjoint = DisjointSet(string, pairs)
graph = collections.defaultdict(list)
# With the disjoint set, build the substrings connected by the pairs
for i, c in enumerate(string):
graph[disjoint.find_parent(i)].append(c)
# Sort the substrings
for i in range(len(string)):
graph[i].sort()
# Build the answer by picking the most lexicographic out of the substrings
for i in range(len(string)):
parent = disjoint.find_parent(i)
string[i] = graph[parent][-1]
graph[parent].pop()
return "".join(string
我找到了 idea here。我刚刚在 Python 中实现了它并添加了评论。
面试关于代码打架的哈希图问题，需要帮助优化我的暴力解决方案。这是问题所在：
给定字符串 str 和指示可以交换字符串中的哪些索引的对数组，return 执行允许的交换后产生的字典序最大的字符串。您可以多次交换索引。
例子
For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
swapLexOrder(str, pairs) = "dbca".
通过交换给定的索引，您可以得到字符串："cbda"、"cbad"、"dbac"、"dbca"。此列表中字典序最大的字符串是 "dbca".
我目前的解决方案
通过不断添加所有可能性直到没有新的解决方案来进行暴力破解。这对于 swapLexOrder('dznsxamwoj',[[1,2],[3,4],[6,5],[8,10]]) 来说太慢了，无法在我的机器上完成。任何优化提示？一个更容易通过的测试用例是 swapLexOrder('abdc,[[1,4],[3,4]])= dbca
def swapLexOrder(str, pairs):
d = {}
d[str]=True
while True:
oldlen=len(d)
for x,y in pairs:
for s in d.keys():
d[swp(s,x,y)]=True
if len(d) == oldlen:
#no more new combinations.
return sorted(d)[-1]
def swp(str,x,y):
x=x-1
y=y-1
a=str[x]
b=str[y]
return str[0:x]+b+str[x+1:y]+a+str[y+1:]
我建议的解决方案是首先尝试 'link' 尽可能多的对以形成可以互换的索引集 - 例如，在您的第一个示例中，[[1, 4], [3, 4]] 可以变成 [[1, 3, 4]].然后可以按字典顺序对这些索引的每个子集进行排序以形成输出。实现是这样的：
def build_permitted_subs(pairs):
perm = []
for a, b in pairs:
merged = False
for ind, sub_perm in enumerate(perm):
if a in sub_perm or b in sub_perm:
sub_perm.add(a)
sub_perm.add(b)
merged = True
break
else:
perm.append(set([a, b]))
if merged:
for merge_perm_ind in reversed(range(ind + 1, len(perm))):
if perm[merge_perm_ind] & sub_perm:
sub_perm.update(perm[merge_perm_ind])
perm.pop(merge_perm_ind)
return list(map(sorted, perm))
def swap_lex_order(swap_str, _pairs):
pairs = [[a - 1, b - 1] for a, b in _pairs]
out = list(swap_str)
perm = build_permitted_subs(pairs)
for sub_perm in perm:
sorted_subset = sorted(sub_perm, key=lambda ind: swap_str[ind], reverse=True)
for sort, targ in zip(sorted_subset, sub_perm):
out[targ] = swap_str[sort]
return "".join(out)
print(swap_lex_order("dznsxamwoj", [[1, 2], [3, 4], [6, 5], [8, 10]]))
print(swap_lex_order("abdc", [[1, 4], [3, 4]]))
print(swap_lex_order("acxrabdz",[[1,3], [6,8], [3,8], [2,7]]))
输出：
zdsnxamwoj
dbca
zdxrabca
我还重命名了您的参数以不使用 str，这已经是一个非常基本的 Python 内置。请注意，我的代码可能没有尽可能 Pythonic，但我认为它足以很好地说明算法，并且没有受到任何重大性能影响。我怀疑这种方法的复杂性很低——它通常是 'intelligent'，因为它不会暴力破解任何东西，并且使用 O(n log n) 排序。第一个例子似乎是正确的。请注意，这会将每对转换为基于 0 的，因为这对于 Python.
这有点依赖于能够从相邻排列（交换对）中形成任何排列（对链接对进行排序）。这可能不完全直观，但它可能有助于认识到您可以仅使用列表中的相邻交换来有效地执行插入（通过在元素移动的方向上不断交换元素）。使用相邻交换排列列表的一个示例是冒泡排序，您可能会意识到，如果可以对任何排列进行冒泡排序，则意味着所有排列都可以通过冒泡排序实现。
如果您有任何疑问，或有任何问题，请告诉我，我会开始 elaborating/debugging。 （截至格林威治标准时间 19:28，我已经注意到一个错误并已将其编辑掉 : )。 Bug #2（在测试用例 3 中有重复的 z）也应该被修复。
关于 bug #1 的更多信息：
我没有对 build_permitted_subs 返回的索引进行排序，因此无法参考 swap_str.
有关错误 #2 的更多信息：
build_permitted_subs 功能没有正常工作 - 具体来说，如果它遇到一对可以分成两个组，这意味着这些组也应该加入在一起，这没有发生，现在会有是两个不应该分开的团体。这导致 z 重复，因为两个组都可以从 z 中提取。我草率地用一个标志和一个可追溯的 for 循环修复了这个问题。
这个也许效果更好。
def swapLexOrder(str_, pairs):
n = len(str_)
str_ = list(str_)
corr = [set() for _ in range(n)]
nodes = set()
for a, b in pairs:
corr[a-1].add(b-1)
corr[b-1].add(a-1)
nodes.add(a-1)
nodes.add(b-1)
while nodes:
active = {nodes.pop()}
group = set()
while active:
group |= active
nodes -= active
active = {y for x in active for y in corr[x] if y in nodes}
chars = iter(sorted((str_[i] for i in group), reverse=True))
for i in sorted(group):
str_[i] = next(chars)
return "".join(str_)
def swapLexOrder(str, pairs):
if not str or not pairs:
return ('', str)[not pairs]
lst = [''] + list(str)
setted_pairs = list(map(set, pairs))
while setted_pairs:
path = setted_pairs.pop(0)
while True:
path1 = path.copy()
for pair in setted_pairs:
if path1 & pair:
path |= pair
setted_pairs.remove(pair)
if path == path1:
break
optimal = sorted(lst[i] for i in path)
for i, v in enumerate(sorted(path, reverse=True)):
lst[v] = optimal[i]
return ''.join(lst[1:])
我的首选解决方案是使用不相交集来解决此问题。关键思想是建立一个类似于链表的对的连接图。这表示由对连接的子串。一旦弄清楚连接的内容，就可以对子字符串进行排序，然后在构建字符串时从子字符串中挑选出最字典序的字符。
不相交集在这里有很大帮助，因为它可以让我们以极快的速度找出连接的东西。它实际上比 log 快，它是 log*。我建议阅读 Wikipedia page 以获得解释。通过使用 union 函数，我们可以从给定的对构建“链表”。
import collections
class DisjointSet:
def __init__(self, string, pairs):
self.parent = [i for i in range(len(string))]
self.size = [1] * len(string)
for a, b in pairs:
self.union(a-1, b-1)
def find_parent(self, idx):
# O(log*(n))
if self.parent[idx] == idx:
return idx
self.parent[idx] = self.find_parent(self.parent[idx])
return self.parent[idx]
def union(self, a, b):
# O(log*(n))
x = self.find_parent(a)
y = self.find_parent(b)
if x == y:
return
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] = self.size[x] + self.size[y]
def swapLexOrder(string, pairs):
# O(nlogn) + O(nlog*(n))
string = list(string)
# Build the disjoint set to figure out what pairs are connected
disjoint = DisjointSet(string, pairs)
graph = collections.defaultdict(list)
# With the disjoint set, build the substrings connected by the pairs
for i, c in enumerate(string):
graph[disjoint.find_parent(i)].append(c)
# Sort the substrings
for i in range(len(string)):
graph[i].sort()
# Build the answer by picking the most lexicographic out of the substrings
for i in range(len(string)):
parent = disjoint.find_parent(i)
string[i] = graph[parent][-1]
graph[parent].pop()
return "".join(string
我找到了 idea here。我刚刚在 Python 中实现了它并添加了评论。