寒武紀(jì)2018筆試編程題:已知字符串S丘跌,求最小字符串A

同學(xué)報(bào)考的袭景,職位貌似是算法工程師?要求C++語(yǔ)言闭树、數(shù)據(jù)結(jié)構(gòu)耸棒、算法等基礎(chǔ)知識(shí)。
我不會(huì)C++报辱,所以本文嘗試用Python解決問(wèn)題与殃。

題目要求:

對(duì)于字符串A、B碍现,定義以下操作:

  1. 比較大蟹邸:按字典順序比較兩個(gè)字符串大小。(前一道編程題已引入此概念昼接,兩道題都強(qiáng)調(diào)對(duì)于字母組成相同的兩個(gè)字符串的比較爽篷,如'abcd' < 'abdc' < 'cbda' < 'dcba'龙宏,而暫不考慮'abcd''baef'的大小關(guān)系)
  2. 反轉(zhuǎn)操作reverse(A)介袜,例如reverse('abcd') == 'dcba'狮鸭。
  3. 亂序輸出shuffle(A)钮莲,例如'bacd', 'cadb', 'abdc'等都是shuffle('abcd')可能的輸出結(jié)果。
  4. 合并操作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'

解題思路:

  1. 統(tǒng)計(jì)S的字母出現(xiàn)頻率育八,每個(gè)字母的出現(xiàn)頻率減半,生成reverse(A)的字母出現(xiàn)頻率赦邻。
  2. 根據(jù)字母出現(xiàn)頻率髓棋,由大到小生成reverse(A),并驗(yàn)證reverse(A)是否為S的子字符串(并保持順序)。如果是的話按声,從S中剔除reverse(A)貢獻(xiàn)的字母膳犹,剩下的字符串一定是shuffle(A)可能的輸出結(jié)果。
  3. 將找到的首個(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)化的位置包括:

  1. 數(shù)據(jù)結(jié)構(gòu)的使用族阅。permutate(...)每次都要構(gòu)造O(factorial(n))個(gè)新字典,手動(dòng)捂臉膝捞。
  2. 邊生成排列邊驗(yàn)證坦刀,把permutate(...)改寫成非遞歸的,再令其返回一個(gè)全排列的生成器绑警。
  3. 算法復(fù)雜度還是相當(dāng)高的求泰,不知道有沒(méi)有低一點(diǎn)的算法。1核有難7核15線程圍觀還是挺尷尬的计盒,單純改寫成多線程并發(fā)也有點(diǎn)尷尬渴频。

2019-08-21更新:

  1. 今天發(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)化卜朗。
  2. 但是itertools.permutations(iterable, r=None)不支持reverse之類的參數(shù)。咕村。场钉。解決方法一是事先將iterable做reverse,二是
    懈涛。
    逛万。

    仔細(xì)讀題批钠。宇植。。發(fā)現(xiàn)題目中給出的reversemerge有下列性質(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()
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市缭付,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌陷猫,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,627評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件烙丛,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡羔味,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門钠右,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)赋元,“玉大人,你說(shuō)我怎么就攤上這事「橥梗” “怎么了媚值?”我有些...
    開(kāi)封第一講書人閱讀 169,346評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)护糖。 經(jīng)常有香客問(wèn)我褥芒,道長(zhǎng),這世上最難降的妖魔是什么嫡良? 我笑而不...
    開(kāi)封第一講書人閱讀 60,097評(píng)論 1 300
  • 正文 為了忘掉前任锰扶,我火速辦了婚禮,結(jié)果婚禮上寝受,老公的妹妹穿的比我還像新娘坷牛。我一直安慰自己,他們只是感情好很澄,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,100評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布京闰。 她就那樣靜靜地躺著,像睡著了一般甩苛。 火紅的嫁衣襯著肌膚如雪蹂楣。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書人閱讀 52,696評(píng)論 1 312
  • 那天讯蒲,我揣著相機(jī)與錄音痊土,去河邊找鬼。 笑死爱葵,一個(gè)胖子當(dāng)著我的面吹牛施戴,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播萌丈,決...
    沈念sama閱讀 41,165評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼赞哗,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了辆雾?” 一聲冷哼從身側(cè)響起肪笋,我...
    開(kāi)封第一講書人閱讀 40,108評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎度迂,沒(méi)想到半個(gè)月后藤乙,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,646評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡惭墓,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,709評(píng)論 3 342
  • 正文 我和宋清朗相戀三年坛梁,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片腊凶。...
    茶點(diǎn)故事閱讀 40,861評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡拴念,死狀恐怖褐缠,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情公般,我是刑警寧澤胡桨,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布登失,位于F島的核電站,受9級(jí)特大地震影響状婶,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜膛虫,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,196評(píng)論 3 336
  • 文/蒙蒙 一稍刀、第九天 我趴在偏房一處隱蔽的房頂上張望敞曹。 院中可真熱鬧,春花似錦局齿、人聲如沸橄登。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,698評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)蹋半。三九已至充坑,卻和暖如春闻蛀,著一層夾襖步出監(jiān)牢的瞬間您市,已是汗流浹背茵休。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,804評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工榕莺, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留棵介,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,287評(píng)論 3 379
  • 正文 我出身青樓唠雕,卻偏偏與公主長(zhǎng)得像吨述,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子捕儒,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,860評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 前言 最先接觸編程的知識(shí)是在大學(xué)里面,大學(xué)里面學(xué)了一些基礎(chǔ)的知識(shí)蒲拉,c語(yǔ)言痴腌,java語(yǔ)言,單片機(jī)的匯編語(yǔ)言等锦援;大學(xué)畢...
    oceanfive閱讀 3,095評(píng)論 0 7
  • Spring Cloud為開(kāi)發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具(例如配置管理剥悟,服務(wù)發(fā)現(xiàn)曼库,斷路器毁枯,智...
    卡卡羅2017閱讀 134,716評(píng)論 18 139
  • pyspark.sql模塊 模塊上下文 Spark SQL和DataFrames的重要類: pyspark.sql...
    mpro閱讀 9,464評(píng)論 0 13
  • 魚兒出生那月谴古,陰歷陽(yáng)歷日子重合 她一出生,我就覺(jué)得與眾不同 魚兒圓乎可耐讥电,個(gè)高還懂事。 一見(jiàn)到我就手舞足蹈 變著花...
    吾聞聽(tīng)閱讀 620評(píng)論 0 9
  • 本文參加#感悟三下鄉(xiāng)瞬测,青春筑夢(mèng)行#活動(dòng)月趟,本人承諾,文章內(nèi)容為原創(chuàng)孝宗,且未在其他平臺(tái)發(fā)表過(guò)耕肩。 檸檬香茅草,可泡茶飲及用...
    病友_2704閱讀 338評(píng)論 0 0