同學(xué)報(bào)考的袭景，職位貌似是算法工程師？要求C++語(yǔ)言闭树、數(shù)據(jù)結(jié)構(gòu)耸棒、算法等基礎(chǔ)知識(shí)。
我不會(huì)C++报辱，所以本文嘗試用Python解決問(wèn)題与殃。
題目要求：
對(duì)于字符串A、B碍现，定義以下操作：
- 比較大蟹邸：按字典順序比較兩個(gè)字符串大小。（前一道編程題已引入此概念昼接，兩道題都強(qiáng)調(diào)對(duì)于字母組成相同的兩個(gè)字符串的比較爽篷，如
'abcd' < 'abdc' < 'cbda' < 'dcba'龙宏，而暫不考慮'abcd'和'baef'的大小關(guān)系）- 反轉(zhuǎn)操作
reverse(A)介袜，例如reverse('abcd') == 'dcba'狮鸭。- 亂序輸出
shuffle(A)钮莲，例如'bacd', 'cadb', 'abdc'等都是shuffle('abcd')可能的輸出結(jié)果。- 合并操作
merge(A,B)：合并的結(jié)果保持A厅翔、B各自字符的順序俱尼，但每一位從哪個(gè)字符串取值則是隨機(jī)的薄榛。例如'aebcfghd', 'abefcgdh'等都是merge('abcd', 'efgh')可能的輸出結(jié)果者吁。對(duì)于某個(gè)完全由小寫字母組成的字符串A，計(jì)算
S = merge(reverse(A), shuffle(A))饲帅，如果S是已知的复凳，求能夠算出S的最小的字符串A。
后面有一個(gè)例子我沒(méi)記灶泵，下文用程序生成了一個(gè)例子：
一開(kāi)始生成的
a = 'ixsrqolpuq'
計(jì)算reverse(a) == 'quploqrsxi'
以及shuffle(a) == 'orulxqipsq'
s == 'oqurulxpqlioqprsxisq'作為程序輸入
通過(guò)程序求出的a == 'isrpqolqxu'
解題思路：
- 統(tǒng)計(jì)S的字母出現(xiàn)頻率育八，每個(gè)字母的出現(xiàn)頻率減半，生成
reverse(A)的字母出現(xiàn)頻率赦邻。 - 根據(jù)字母出現(xiàn)頻率髓棋，由大到小生成
reverse(A)，并驗(yàn)證reverse(A)是否為S的子字符串（并保持順序）。如果是的話按声，從S中剔除reverse(A)貢獻(xiàn)的字母膳犹，剩下的字符串一定是shuffle(A)可能的輸出結(jié)果。 - 將找到的首個(gè)（最大的）
reverse(A)反轉(zhuǎn)签则，得到最小的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下豺旬，光是構(gòu)造一個(gè)10位字母的全排列就要消耗10多秒，之后的搜索也需要數(shù)秒柒凉。（題目對(duì)C/C++以外語(yǔ)言的要求是2秒以內(nèi)）
目前想到可以優(yōu)化的位置包括：
- 數(shù)據(jù)結(jié)構(gòu)的使用族阅。
permutate(...)每次都要構(gòu)造O(factorial(n))個(gè)新字典，手動(dòng)捂臉膝捞。 - 邊生成排列邊驗(yàn)證坦刀，把
permutate(...)改寫成非遞歸的，再令其返回一個(gè)全排列的生成器绑警。 - 算法復(fù)雜度還是相當(dāng)高的求泰，不知道有沒(méi)有低一點(diǎn)的算法。1核有難7核15線程圍觀還是挺尷尬的计盒，單純改寫成多線程并發(fā)也有點(diǎn)尷尬渴频。
2019-08-21更新：
- 今天發(fā)現(xiàn)Python的
itertools.permutations(iterable, r=None)（Py3文檔 Py2文檔）就已經(jīng)實(shí)現(xiàn)了一個(gè)全排列的生成器，也就是上面的第2項(xiàng)優(yōu)化北启，并且很可能也包含第1項(xiàng)優(yōu)化卜朗。 - 但是
itertools.permutations(iterable, r=None)不支持reverse之類的參數(shù)。咕村。场钉。解決方法一是事先將iterable做reverse，二是
懈涛。
逛万。
。
仔細(xì)讀題批钠。宇植。。發(fā)現(xiàn)題目中給出的reverse和merge有下列性質(zhì)：
a.merge交換律：當(dāng)A埋心、B任意指定時(shí)指郁，merge(A, B)和merge(B, A)的解集相等。
b.merge“分配”律：reverse(merge(A, B))和merge(reverse(A), reverse(B))的解集也相等拷呆。
所以闲坎，可以事先將S做reverse疫粥，之后驗(yàn)證A是否為reverse(S)的子字符串（并保持順序）。算法更直觀了腰懂，而且真要回到C/C++的話梗逮，前一題要做的next(A)也用上了，手動(dòng)滑稽悯恍。
2020-3-2更新：
https://www.hackerrank.com/challenges/reverse-shuffle-merge/forum
最高贊答案的前兩條不難想到库糠，第三條中的“倒序”在上次更新的時(shí)候也考慮到了，但是“逐個(gè)字符查找”和后面4--7條（貪心算法）是我始終沒(méi)有想到的涮毫，這樣一來(lái)就可以完全拋棄permutation了瞬欧，而且預(yù)計(jì)性能也不會(huì)太差。
2020-4-4更新：
上一題：next(A)的實(shí)現(xiàn)
在定義完字符串大小的概念后艘虎，對(duì)任意字符串A，找出大于A的最小字符串咒吐，如不存在則提示“不存在”。
直接解決的話恬叹，可以寫出下列代碼，期望的時(shí)間復(fù)雜度為O(n)绽昼。但是這個(gè)算法不容易與下一題結(jié)合，除非一開(kāi)始就想到下一題用“貪心算法”而不復(fù)用本題的代碼硅确。
#!/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()
