同学报考的，职位貌似是算法工程师？要求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线程围观还是挺尴尬的，单纯改写成多线程并发也有点尴尬。
2019-08-21更新：
- 今天发现Python的
itertools.permutations(iterable, r=None)（Py3文档 Py2文档）就已经实现了一个全排列的生成器，也就是上面的第2项优化，并且很可能也包含第1项优化。 - 但是
itertools.permutations(iterable, r=None)不支持reverse之类的参数。。。解决方法一是事先将iterable做reverse，二是
。
。
。
仔细读题。。。发现题目中给出的reverse和merge有下列性质：
a.merge交换律：当A、B任意指定时，merge(A, B)和merge(B, A)的解集相等。
b.merge“分配”律：reverse(merge(A, B))和merge(reverse(A), reverse(B))的解集也相等。
所以，可以事先将S做reverse，之后验证A是否为reverse(S)的子字符串（并保持顺序）。算法更直观了，而且真要回到C/C++的话，前一题要做的next(A)也用上了，手动滑稽。
2020-3-2更新：
https://www.hackerrank.com/challenges/reverse-shuffle-merge/forum
最高赞答案的前两条不难想到，第三条中的“倒序”在上次更新的时候也考虑到了，但是“逐个字符查找”和后面4--7条（贪心算法）是我始终没有想到的，这样一来就可以完全抛弃permutation了，而且预计性能也不会太差。
2020-4-4更新：
上一题：next(A)的实现
在定义完字符串大小的概念后，对任意字符串A，找出大于A的最小字符串，如不存在则提示“不存在”。
直接解决的话，可以写出下列代码，期望的时间复杂度为O(n)。但是这个算法不容易与下一题结合，除非一开始就想到下一题用“贪心算法”而不复用本题的代码。
#!/bin/python3
import math
import os
import random
import re
import sys
def binary_search_first_next(ls, item):
NOT_FOUND = -1
low = 0
high = len(ls)
if high == 0:
return NOT_FOUND
elif high == 1:
return (0 if ls[0] > item else NOT_FOUND)
else:
while high > low + 1:
mid = (low + high) // 2
if ls[mid] <= item:
low = mid
elif mid == low + 1:
return (low if ls[low] > item else mid)
else:
high = mid + 1
return NOT_FOUND
# Complete the biggerIsGreater function below.
def biggerIsGreater(w):
if len(w) >= 2:
last_char = w[-1]
for (i, c) in list(enumerate(w[:-1]))[::-1]:
if c >= last_char:
# still descending
last_char = c
else:
last_chars = list(w[:i:-1]) # must be ascending
j = binary_search_first_next(last_chars, c)
if j >= 0:
(c, last_chars[j]) = (last_chars[j], c)
# last_chars must still be ascending
return w[:i] + c + (''.join(last_chars))
#else:
# you shouldn't be here
#if not returned:
#else: # if len(w) < 2:
# automatically no answer
return "no answer"
if __name__ == '__main__':
if 'OUTPUT_PATH' not in os.environ:
os.environ['OUTPUT_PATH'] = r'C:\test\hackerrank\out.txt'
fptr = open(os.environ['OUTPUT_PATH'], 'w')
T = int(input())
for T_itr in range(T):
w = input()
result = biggerIsGreater(w)
fptr.write(result + '\n')
fptr.close()
