Kata: 从随机的三字符列表组中恢复秘密字符串

zgbgx 发布于2019-07-30 14:49 / 1713人阅读

摘要：题目从给定字符串中随机出的三字符列表的集合中，恢复原始字符串，并且三字符列表按字符在字符串中出现顺序排列。作为简化，假设秘密字符串中不会有重复字母。从原始集合中去掉找出的第一个字母，并在除去字母的该行末尾添加，以保持三元素列表。

题目：从给定字符串中随机出的三字符列表的集合中，恢复原始字符串，并且三字符列表按字符在字符串中出现顺序排列。作为简化，假设秘密字符串中不会有重复字母。如下：

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

以我的智商暂时就只能想到这里，如有更好的方法，请不吝赐教。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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