同学报考的，职位貌似是算法工程师？要求C++语言、数据结构、算法等基础知识。
我不会C++，所以本文尝试用Python解决问题。
题目要求：
对于字符串A、B，定义以下操作：
- 比较大小：按字典顺序比较两个字符串大小。（前一道编程题已引入此概念，两道题都强调对于字母组成相同的两个字符串的比较，如
'abcd' < 'abdc' < 'cbda' < 'dcba'，而暂不考虑'abcd'和'baef'的大小关系）- 反转操作
reverse(A)，例如reverse('abcd') == 'dcba'。- 乱序输出
shuffle(A)，例如'bacd', 'cadb', 'abdc'等都是shuffle('abcd')可能的输出结果。- 合并操作
merge(A,B)：合并的结果保持A、B各自字符的顺序，但每一位从哪个字符串取值则是随机的。例如'aebcfghd', 'abefcgdh'等都是merge('abcd', 'efgh')可能的输出结果。对于某个完全由小写字母组成的字符串A，计算
S = merge(reverse(A), shuffle(A))，如果S是已知的，求能够算出S的最小的字符串A。
后面有一个例子我没记，下文用程序生成了一个例子：
一开始生成的
a = 'ixsrqolpuq'
计算reverse(a) == 'quploqrsxi'
以及shuffle(a) == 'orulxqipsq'
s == 'oqurulxpqlioqprsxisq'作为程序输入
通过程序求出的a == 'isrpqolqxu'
解题思路：
- 统计S的字母出现频率，每个字母的出现频率减半，生成
reverse(A)的字母出现频率。 - 根据字母出现频率，由大到小生成
reverse(A)，并验证reverse(A)是否为S的子字符串（并保持顺序）。如果是的话，从S中剔除reverse(A)贡献的字母，剩下的字符串一定是shuffle(A)可能的输出结果。 - 将找到的首个（最大的）
reverse(A)反转，得到最小的A。
代码如下：
#!/usr/bin/env python
# find smallest A in S == merge(reverse(A), shuffle(A))
import random
TEST = True
def generic_get_inputs(echo=False):
n = raw_input('')
data = []
for i in xrange(n):
buf = raw_input('')
data.append(buf)
return data # or (n, data) if needed
# Methods generating S from A
def reverse(a_in=''):
return a_in[::-1]
def shuffle(a_in=''):
a_seq = list(a_in)
random.shuffle(a_seq)
ret = ''.join(a_seq)
return ret
def random_merge(a_in='', b_in=''):
l_a = len(a_in)
l_b = len(b_in)
i = 0
j = 0
ret = []
while True:
if i < l_a:
if j < l_b:
choice = random.choice([0,1])
if choice:
ret.append(b_in[j])
j += 1
else:
ret.append(a_in[i])
i += 1
else: # b_in finished
ret.append(a_in[i])
i += 1
else: # a_in finished
if j < l_b:
ret.append(b_in[j])
j += 1
else:
break
ret = ''.join(ret)
return ret
# Method for generating A and S for testing
def generate_test_case(l=10):
alphabet = 'abcdefghijklmnopqrstuvwxyz'
a_seq = [random.choice(alphabet) for i in range(l)]
a_in = ''.join(a_seq)
a_reverse = reverse(a_in)
a_shuffle = shuffle(a_in)
s_in = random_merge(a_reverse, a_shuffle)
if TEST:
print a_in
print a_reverse
print a_shuffle
print s_in
return s_in
# Methods for solving the problem
def stat_s(s_in=''):
ret = {}
for i in s_in:
if i in ret:
ret[i] += 1
else:
# creating entry
ret[i] = 1
return ret
def stat_a(s_in='', s_stat={}):
if not s_stat:
s_stat = stat_s(s_in)
ret = {}
for key,val in s_stat.items():
if val % 2 != 0:
raise "Input has {val} {key} 's, which is illegal".format(key=key, val=val)
ret[key] = val / 2
return ret
def permutate(stat={}, reverse=False):
ret = []
for key in sorted(stat.keys(), reverse=reverse):
val = stat[key]
substat = {}
for key1,val1 in stat.items():
if key1 != key:
substat[key1] = val1
elif val1 > 1:
substat[key1] = val1 - 1
#else:
# Do not create "substat[key1] = 0"
remaining_keys = substat.keys()
if len(remaining_keys) == 0:
return [key]
perm = permutate(stat=substat, reverse=reverse)
ret += [(key + i) for i in perm]
return ret #or [''] # how permutate({}) is treated
def substr(child, parent):
if child == '':
return True
l_child = len(child)
l_parent = len(parent)
if l_child > l_parent:
return False
i = 0
j = 0
while i < l_child:
if child[i] == parent[j]:
i += 1
#else:
# keep i
if i == l_child:
# all child[i] found in parent in corresponding order
return True
j += 1 # no matter what
if j == l_parent:
# all parent[j] used up but some child[i] not found in corresponding order
return False
#assert i == l_child
# all child[i] found in parent in corresponding order
return True
def main():
ret = 'No answer'
if TEST:
s_in = generate_test_case(l=10)
else:
s_in = raw_input('')
print '================'
a_stat = stat_a(s_in)
print a_stat
for i in permutate(a_stat, reverse=True):
if substr(i, s_in):
print i, 'yes!'
ret = i[::-1]
break
#print i, 'no...'
print ret
if __name__ == '__main__':
main()
在AMD Ryzen 7 1700X，Win7 x64，Python 2.7.14下，光是构造一个10位字母的全排列就要消耗10多秒，之后的搜索也需要数秒。（题目对C/C++以外语言的要求是2秒以内）
目前想到可以优化的位置包括：
- 数据结构的使用。
permutate(...)每次都要构造O(factorial(n))个新字典，手动捂脸。 - 边生成排列边验证，把
permutate(...)改写成非递归的，再令其返回一个全排列的生成器。 - 算法复杂度还是相当高的，不知道有没有低一点的算法。1核有难7核15线程围观还是挺尴尬的，单纯改写成多线程并发也有点尴尬。
网友评论