Kata: 從隨機的三字符列表組中恢復秘密字符串

zgbgx 發布于2019-07-30 14:49 / 1715人閱讀

摘要：題目從給定字符串中隨機出的三字符列表的集合中，恢復原始字符串，并且三字符列表按字符在字符串中出現順序排列。作為簡化，假設秘密字符串中不會有重復字母。從原始集合中去掉找出的第一個字母，并在除去字母的該行末尾添加，以保持三元素列表。

題目：從給定字符串中隨機出的三字符列表的集合中，恢復原始字符串，并且三字符列表按字符在字符串中出現順序排列。作為簡化，假設秘密字符串中不會有重復字母。如下：

secret = "whatisup"
triplets = [
    ["t", "u", "p"],
    ["w", "h", "i"],
    ["t", "s", "u"],
    ["a", "t", "s"],
    ["h", "a", "p"],
    ["t", "i", "s"],
    ["w", "h", "s"]
]

我想了許久，有這么一個思路：

分別提取集合triplets中列表第一、第二和第三項組成集合。

字符串中第一個字母只會在第一集合中出現，排除得出第一個字母。

從原始集合triplets中去掉找出的第一個字母，并在除去字母的該行末尾添加0，以保持三元素列表。

重復上述動作，直到triplets變成只包含0。

按上述思路，確實能夠寫出答案，但結果無比丑陋：

    def recoverSecret(triplets):
        res = []
        while triplets:
            t = list(zip(*triplets))
            big = list(set(t[0]) - set(t[1] + t[2]))
            if not big:
                break
            res.extend(big)
            for item in triplets:
                if big[0] == item[0]:
                    item.pop(0)
                    item.append(0)
        return "".join(res)

感覺要瞎了。看了下大神的代碼，思路是這樣的：

根據triplets生成原字符串的字符列表t，無重復，但非按順序。

循環遍歷triplets，每次循環按三字符列表中的順序調整上一步的t中字符順序。

結果如下：

    def recoverSecret(triplets):
      r = list({i for t in triplets for i in t})
      for t in triplets:
        fix(r, t[1], t[2])
        fix(r, t[0], t[1])
      return "".join(r)
      
    def fix(t, a, b):
       if t.index(a) > t.index(b):
           t.remove(a)
           t.insert(t.index(b), a)

但上面的算法有問題，比如下面這個例子：

triplets = [
    ["w", "h", "p"],
    ["t", "u", "p"],
    ["w", "h", "t"],
    ["t", "s", "u"],
    ["a", "t", "s"],
    ["h", "a", "p"],
    ["t", "i", "s"]
]

當我確定了w, h兩個的位置后，又要確認h, a的位置，此時a在h前面，所以把h的位置前提，但因為初始a在w前面，那h就位置放錯了，后面又不再有w, h的位置調整，最后的結果當然是錯的。

當然，解決方式也很簡單，多循環一遍triplets：

for t in triplets * 2

以我的智商暫時就只能想到這里，如有更好的方法，請不吝賜教。

GPU云服務器云服務器 php的字符連接符 C 從 UTF-8 流中讀取字符串的正確恢復從秘密的爬蟲類

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40939.html

【學習筆記】用python做些事

摘要：并返回合理錯誤提示。如果不在則再輸入密碼，成功則增加用戶信息到文件中，密碼進行加密處理。作業增加用戶名，密碼的合法化判斷和錯誤提示。課時5：字符串-基礎切片，索引 s = use python do somenthing s[1],s[-1],s[1:3],s[1:6:2],s[1:],s[:-1],s[:] spilt,join,[start:stop:step] 常用方法集...

wdzgege 2019-07-24 18:37 評論0 收藏0
Spring Cloud 參考文檔（Spring Cloud Config Server）

摘要：，這是標記配置文件集版本化的服務器端特性。要配置對稱密鑰，需要將設置為秘密字符串或使用環境變量將其排除在純文本配置文件之外。 Spring Cloud Config Server Spring Cloud Config Server為外部配置提供基于HTTP資源的API（名稱—值對或等效的YAML內容），通過使用@EnableConfigServer注解，服務器可嵌入Spring Bo...

harryhappy 2019-08-16 16:39 評論0 收藏0
Python基礎-列表、元組、字典、字符串

摘要：多維數組一維數組二維數組一二三四五三維數組一二三四維數組二五五中可以放不同類型的值，的下標從開始。多維數組 nums1 = [1,2,3] #一維數組 nums2 = [1,2,3,[4,56]] #二維數組 nums3 = [1,2,3,4,[a,b,c,d,e,[一,二,三]],[四,五]] #三維數組 nums4 = [1,2,3,4,[a,b,c,d,e,[一,二,三,[1,...

zhangrxiang 2019-07-31 10:19 評論0 收藏0