[已解决]Python：每日一题 372

zltzlt

今天的题目：

假设我们现在在用一些方块来堆砌一个金字塔，每个方块用一个字母表示。

给定金字塔的基层 bottom（用一个字符串表示）和一个三元组列表 allowed（每个三元组用一个长度为 3 的字符串表示）。

对于三元组 (A, B, C) ，“C” 为顶层方块，方块 “A”、“B” 分别作为方块 “C” 下一层的的左、右子块。

当且仅当三元组 (A, B, C) 存在于 allowed，我们才可以将其堆砌上。

返回是否可以由基层一直堆到塔尖。

注意：允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组，其中 C != D。

示例 1：

输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
输出：True
解释：可以堆砌成这样的金字塔。

示例 2：

输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
输出：False

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

塔利班

2020-4-10 15:28:13

1. def f372(bottom,allowed):
   
2.     n=len(bottom)
   
3.     d={}
   
4.     for e in allowed:
   
5.         d[e[:-1]]=d.get(e[:-1],[])+[e[-1]]
   
6.     def dp(n,now):
   
7.         if n==1:
   
8.             return True
   
9.         else:
   
10.             t=['']
    
11.             for i in range(n-1):
    
12.                 a=now[i:i+2]
    
13.                 if a in d:
    
14.                     nt=[]
    
15.                     for e in d[a]:
    
16.                         for et in t:
    
17.                             nt.append(et+e)
    
18.                     t=nt
    
19.                 else:
    
20.                     return False
    
21.             for e in t:
    
22.                 if dp(n-1,e):
    
23.                     return True
    
24.             return False
    
25.     return dp(len(bottom),bottom)

复制代码

先写个蠢得

跳转到最佳答案楼层

永恒的蓝色梦想

前排~

TJBEST

1. def fun372(bottom,allowed):
   
2.     dictionary = {}
   
3.     for each in allowed:
   
4.         try:
   
5.             dictionary[(each[0],each[1])].append(each[2])
   
6.         except:
   
7.             dictionary[(each[0],each[1])] = [each[2]]
   
8.     def inner(bottom):
   
9.         outer = ['']#记录每一个组合
   
10.         M = len(bottom)
    
11.         for index in range(1,M):
    
12.             try:
    
13.                 maybe = dictionary[(bottom[index-1],bottom[index])]
    
14.             except:
    
15.                 return False
    
16.             N = len(maybe)
    
17.             L = len(outer)
    
18.             outer = outer * N
    
19.             for count in range(0,N):
    
20.                 for position in range(0,L):
    
21.                     outer[count*L + position] += maybe[count]
    
22.         for each in outer:
    
23.             if len(each) == 1:
    
24.                 return True
    
25.             if inner(each):
    
26.                 return True
    
27.         return False
    
28.     return inner(bottom)
    

复制代码

FHR

前排

塔利班

1. def f372(bottom,allowed):
   
2.     n=len(bottom)
   
3.     d={}
   
4.     for e in allowed:
   
5.         d[e[:-1]]=d.get(e[:-1],[])+[e[-1]]
   
6.     def dp(n,now):
   
7.         if n==1:
   
8.             return True
   
9.         else:
   
10.             t=['']
    
11.             for i in range(n-1):
    
12.                 a=now[i:i+2]
    
13.                 if a in d:
    
14.                     nt=[]
    
15.                     for e in d[a]:
    
16.                         for et in t:
    
17.                             nt.append(et+e)
    
18.                     t=nt
    
19.                 else:
    
20.                     return False
    
21.             for e in t:
    
22.                 if dp(n-1,e):
    
23.                     return True
    
24.             return False
    
25.     return dp(len(bottom),bottom)

复制代码

先写个蠢得

Joy187

def Judge(bottom,allowed):
    co=len(allowed)
    x=len(bottom)*(len(bottom)-1)//2
    while True:
        for i in allowed:
            for j in i:
                if bottom.find(j)!=-1 :
                    i=i.replace(j,"")
        bottom = bottom.replace(bottom,"")
        for i in allowed:
            if(len(i)==1):
                bottom+=i
                allowed=allowed.remove(i)
                co+=1
        if(len(bottom)==0 and co>=x):
            return True
            break
        else:
            return False
            break

zltzlt

塔利班 发表于 2020-4-10 15:28
先写个蠢得

48 ms

zltzlt

Joy187 发表于 2020-4-10 23:05
def Judge(bottom,allowed):
    co=len(allowed)
    x=len(bottom)*(len(bottom)-1)//2

解答错误

输入：

1. bottom = "DB"
   
2. allowed = ['BDD', 'ACA', 'CBA', 'BDC', 'AAC', 'DCB', 'ABC', 'DDA', 'CCB']

复制代码

输出：True
预期结果：False

zltzlt

大家快来答题呀~

March2615

又是过了一天才看到
问一个问题：allowed里的元素可以重复用吗

zltzlt

March2615 发表于 2020-4-11 19:03
又是过了一天才看到
问一个问题：allowed里的元素可以重复用吗

可以

TJBEST

@zltzlt  写完了 见三楼

风魔孤行者

1. def f(bottom,allowed):
   
2.     if len(bottom) == 1:
   
3.         return True
   
4.     else:
   
5.         list1 = []
   
6.         list2 = []
   
7.         for each in range(len(bottom)-1):
   
8.             for n in allowed:
   
9.                 if bottom[each:each+2] == n[:2]:
   
10.                     list2.append(n[2])
    
11.             if list2 == []:
    
12.                 return False
    
13.             else:
    
14.                 list1.append(list2)
    
15.                 list2 = []
    
16.         def f1(list1,list2):
    
17.             list3 = []
    
18.             for each in list1:
    
19.                 for n in list2:
    
20.                     list3.append(each+n)
    
21.             return list3
    
22.         list3 = list1[0]
    
23.         del list1[0]
    
24.         for each in list1:
    
25.             list3 = f1(list3,each)
    
26.         count = 0
    
27.         for each in list3:
    
28.             count += f(each,allowed)
    
29.         if count>0:
    
30.             return True
    
31.         else:
    
32.             return False

复制代码

阴阳神万物主

难度评级：普通
要素分析：模拟
敲代码感受：一定要勤打注释，不然自己不专心的话完全反应不过来自己写到什么程度了(我沉浸在音乐中的同时敲的代码，敲一段，停几分钟，然后再看就不记得写到哪里了……)

1. def solve(bottom:str,allowed:'list of str',show:'是否显示金字塔'=False)->bool:
   
2.     class Foots:
   
3.         def __init__(self,how:str):
   
4.             self.left,self.right = how
   
5.         def __add__(self,other):
   
6.             if self.right == other.left:
   
7.                 return True
   
8.             else:
   
9.                 return False
   
10.         def __eq__(self,other):
    
11.             if isinstance(other,Foots):return self.left==other.left and self.right==other.right
    
12.             elif isinstance(other,Block):return self == other.foots
    
13.         def __hash__(self):
    
14.             return hash(self.left+self.right)
    
15.         
    
16.     class Block:
    
17.         def __init__(self,shap:str):
    
18.             self.top,self.foots = shap[-1],Foots(shap[:-1])
    
19.         def __add__(self,other):
    
20.             if self.foots + other.foots:
    
21.                 t = Foots(self.top+other.top)
    
22.                 if t in Space.blocks:return t
    
23.             else:return False
    
24.         def __eq__(self,other):
    
25.             if isinstance(other,Foots):return self.foots == other
    
26.             elif isinstance(other,Block):return self.top==other.top and self.foots==other.foots
    
27.         
    
28.     class Nlist(list):
    
29.         def __init__(self,iterable=()):
    
30.             super().__init__(iterable)
    
31.             self.limit = [0]*len(self)
    
32.             self.indexs = self.limit[:]
    
33.         def append(self,obj):
    
34.             super().append(obj)
    
35.             self.limit.append(len(obj))
    
36.             self.indexs.append(0)
    
37.         def up(self):
    
38.             for i in range(-1,-len(self)-1,-1):
    
39.                 self.indexs[i] += 1
    
40.                 if self.indexs[i]<self.limit[i]:return False
    
41.                 self.indexs[i] = 0
    
42.             else:return True
    
43.             
    
44.     class Space:
    
45.         def __init__(self,bottom:str,allowed:'list of str'):
    
46.             self.pyramid = [[Foots(bottom[i:i+2])for i in range(len(bottom)-1)]]
    
47.             Space.blocks = [Block(each) for each in set(allowed)]
    
48.             self.hight = 1
    
49.         def build(self,floor=0):
    
50.             choices = Nlist()
    
51.             for each in self.pyramid[floor]:
    
52.                 choices.append([b for b in Space.blocks if b==each])
    
53.             if 0 in choices.limit:return False#缺少必要组件
    
54.             if (l := len(choices))==1:
    
55.                 self.pyramid.append(choices[0][0].top)
    
56.                 return True
    
57.             while 1:
    
58.                 n = [choices[i][choices.indexs[i]]+choices[(j := i+1)][choices.indexs[j]]for i in range(l-1)]
    
59.                 if False not in n:
    
60.                     self.pyramid.append(n)
    
61.                     ok = self.build(floor+1)
    
62.                     if ok:return ok
    
63.                     self.pyramid.pop()
    
64.                 if choices.up():return False#没有多余的可选方案
    
65.         def __str__(self):
    
66.             s = ''
    
67.             l = len(self.pyramid)
    
68.             for i in range(-1,-l-1,-1):
    
69.                 s += ' '*(l+i)
    
70.                 if isinstance(self.pyramid[i],str):
    
71.                     s += self.pyramid[i]
    
72.                 else:
    
73.                     for j in range(len(self.pyramid[i])):
    
74.                         s += self.pyramid[i][j].left+ ' '
    
75.                     else:s += self.pyramid[i][-1].right
    
76.                 s += '\n'
    
77.             return s
    
78.     ready = Space(bottom,allowed)
    
79.     del bottom,allowed
    
80.     res = ready.build()
    
81.     if show:print(ready)
    
82.     return res
    
83. 
    
84. if __name__ == '__main__':
    
85.     print('示例1 输出：',solve(bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"],show=1))
    
86.     print('示例2 输出：',solve(bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]))
    

复制代码

唉，难度比简单难一些的时候，我的代码总是这么长……

March2615

1. import collections
   
2. import itertools
   
3. 
   
4. 
   
5. def daily372(bottom: str, allowed: list) -> bool:
   
6.     # 解题思路
   
7.     # 使用递归 -> 读取有可能的下一层状态(更新bottom)
   
8. 
   
9.     # 将allowed转化为字典
   
10.     allowed_dict = collections.defaultdict(list)
    
11.     for allow in allowed:
    
12.         allowed_dict[allow[:-1]].append(allow[-1])
    
13. 
    
14.     def getNextBottom(b: str):  # 获得下一层所有可能的bottom
    
15.         n = len(b)
    
16.         possible_bottom = ['' for _ in range(n - 1)]
    
17.         if n == 1:
    
18.             return b
    
19.         for i in range(n - 1):
    
20.             possible_bottom[i] = allowed_dict.get(b[i:i + 2], '')
    
21.         n_bottom = itertools.product(*possible_bottom)  # 拆包操作
    
22.         return n_bottom
    
23. 
    
24.     def built_bottom(b):
    
25.         if len(b) == 1:
    
26.             return True
    
27.         for each in getNextBottom(b):
    
28.             if built_bottom(''.join(each)):
    
29.                 return True
    
30.         return False
    
31. 
    
32.     return built_bottom(bottom)

复制代码

隔夜题做吐了，递归调用也不是很清楚，不过好歹通过了测试用例
学到了很多新知识，果然做题才是学习最好的方法

zltzlt

TJBEST 发表于 2020-4-10 14:02

76 ms

zltzlt

风魔孤行者 发表于 2020-4-11 21:57

输入以下数据超时：

1. mottom = "BDBBAA"
   
2. allowed = ["ACB","ACA","AAA","ACD","BCD","BAA","BCB","BCC","BAD","BAB","BAC","CAB","CCD","CAA","CCA","CCC","CAD","DAD","DAA","DAC","DCD","DCC","DCA","DDD","BDD","ABB","ABC","ABD","BDB","BBD","BBC","BBA","ADD","ADC","ADA","DDC","DDB","DDA","CDA","CDD","CBA","CDB","CBD","DBA","DBC","DBD","BDA"]

复制代码

zltzlt

阴阳神万物主 发表于 2020-4-12 01:52
难度评级：普通
要素分析：模拟
敲代码感受：一定要勤打注释，不然自己不专心的话完全反应不过来自己写到 ...

84 ms

zltzlt

March2615 发表于 2020-4-12 19:56
隔夜题做吐了，递归调用也不是很清楚，不过好歹通过了测试用例
学到了很多新知识，果然做题才是学习最 ...

48 ms