Python – 列表上的简单算法任务(求职面试的标准问题)

发布时间：2020-12-20 12:36:31 所属栏目：Python 来源：网络整理

导读：有2个输入列表L和M,例如： L = ['a','ab','bba']M = ['baa','aa','bb'] 如何获得2个非空输出列表U和V,以便： ”.join(U)==”.join(V))为True, U的每个元素都在L中,V的每个元素都在M中？例如,上面两个输入列表的一种可能解决方案是： U=['bba','bba','a']V=[

有2个输入列表L和M,例如：

L =  ['a','ab','bba']
M = ['baa','aa','bb']

如何获得2个非空输出列表U和V,以便：
”.join(U)==”.join(V))为True,
U的每个元素都在L中,V的每个元素都在M中？

例如,上面两个输入列表的一种可能解决方案是：

U=['bba','bba','a']
V=['bb','bb','baa']

因为

'bbaabbbaa' == 'bbaabbbaa' is True

并且[‘bba’,’ab’,’bba’,’a’]的每个元素都在[‘a’,’bba’]中

并且[‘bb’,’aa’,’bb’,’baa’]的每个元素都在[‘baa’,’bb’]中

1)创建一个算法,找到至少一个解(U和V).

2)它可以在O(n)中求解,其中n = len(L M)？

：WQ

解决方法

你在寻找什么 – 所有(可数无数)可能的解决方案？ “最短”(通过某种程度)非空解决方案,或一组等于最短的解决方案,或……？

因为,如果有任何解决方案,将U和V都设置为[]符合所有规定的条件,并且是O(1)启动;-).

编辑：好的,所以,开玩笑,这是一个很好的对称解决方案,打印前十个可数无限的非空解决方案：

import itertools as it
import collections

L = ['a','bb']

def cmbs(L=L,M=M):
  Ucans = collections.defaultdict(list)
  Vcans = collections.defaultdict(list)
  sides = (L,Vcans,Ucans),(M,Ucans,Vcans)
  for i in it.count(1):
    for k,(G,Ocans,Tcans) in enumerate(sides):
      for u in it.product(G,repeat=i):
        j = ''.join(u)
        if j in Ocans:
          for samp in Ocans[j]:
            result = samp,u
            yield result[1-k],result[k]
        Tcans[j].append(u)

if __name__ == '__main__':
  for x,y in it.islice(cmbs(),10):
    print x,y,''.join(x),''.join(y)

发出的

('a','a') ('aa',) aa aa
('bba','a') ('bb','aa') bbaa bbaa
('a','a','aa') aaaa aaaa
('a','aa') aabbaa aabbaa
('a','baa') aabaa aabaa
('a','baa') aabbbaa aabbbaa
('bba','aa') bbaaaa bbaaaa
('bba','baa') bbaabaa bbaabaa
('bba','baa') bbaabbbaa bbaabbbaa
('bba','aa') bbaabbaa bbaabbaa

我不确定O(N)在可数无限解决问题的背景下是什么意思 – N应该在这里是什么？！ – )

编辑2：更改为使用(默认)列表的序列,以确保即使在>中可以创建相同的连接字符串时它也能找到所有解决方案来自其中一个输入集合的1种方式(样本输入中未出现的条件,因此样本输出不受影响);例如,如果L是[‘a’,’aa’],那么显然任何连接的字符串都带有> 1a可以以多种方式制作 – 当这样的连接字符串匹配为M制作的字符串时,当前解决方案将发出所有这些多种方式,而前一个字符串只发出其中一个.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!