Python：每日一题 372,Python交流,编程语言专区,鱼C论坛

zltzlt 发表于 2020-4-10 13:26:37

Python：每日一题 372

今天的题目：

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

给定金字塔的基层 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

{:10_298:}欢迎大家一起答题！{:10_298:}

永恒的蓝色梦想 发表于 2020-4-10 13:57:31

前排~

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

本帖最后由 TJBEST 于 2020-4-11 21:09 编辑

def fun372(bottom,allowed):
dictionary = {}
for each in allowed:
   try:
         dictionary[(each,each)].append(each)
   except:
         dictionary[(each,each)] = ]
def inner(bottom):
   outer = ['']#记录每一个组合
   M = len(bottom)
   for index in range(1,M):
         try:
            maybe = dictionary[(bottom,bottom)]
         except:
            return False
         N = len(maybe)
         L = len(outer)
         outer = outer * N
         for count in range(0,N):
            for position in range(0,L):
               outer += maybe
   for each in outer:
         if len(each) == 1:
            return True
         if inner(each):
            return True
   return False
return inner(bottom)

FHR 发表于 2020-4-10 15:19:04

前排

塔利班 发表于 2020-4-10 15:28:13

本帖最后由塔利班于 2020-4-10 15:29 编辑

def f372(bottom,allowed):
n=len(bottom)
d={}
for e in allowed:
   d]=d.get(e[:-1],[])+]
def dp(n,now):
   if n==1:
         return True
   else:
         t=['']
         for i in range(n-1):
            a=now
            if a in d:
               nt=[]
               for e in d:
                     for et in t:
                        nt.append(et+e)
               t=nt
            else:
               return False
         for e in t:
            if dp(n-1,e):
               return True
         return False
return dp(len(bottom),bottom)
先写个蠢得

Joy187 发表于 2020-4-10 23:05:15

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-11 18:50:16

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

48 ms

zltzlt 发表于 2020-4-11 18:51:09

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

解答错误

输入：bottom = "DB"
allowed = ['BDD', 'ACA', 'CBA', 'BDC', 'AAC', 'DCB', 'ABC', 'DDA', 'CCB']
输出：True
预期结果：False

zltzlt 发表于 2020-4-11 18:54:00

大家快来答题呀~

March2615 发表于 2020-4-11 19:03:23

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

zltzlt 发表于 2020-4-11 19:06:10

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

可以

TJBEST 发表于 2020-4-11 21:09:53

@zltzlt写完了见三楼

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

def f(bottom,allowed):
if len(bottom) == 1:
   return True
else:
   list1 = []
   list2 = []
   for each in range(len(bottom)-1):
         for n in allowed:
            if bottom == n[:2]:
               list2.append(n)
         if list2 == []:
            return False
         else:
            list1.append(list2)
            list2 = []
   def f1(list1,list2):
         list3 = []
         for each in list1:
            for n in list2:
               list3.append(each+n)
         return list3
   list3 = list1
   del list1
   for each in list1:
         list3 = f1(list3,each)
   count = 0
   for each in list3:
         count += f(each,allowed)
   if count>0:
         return True
   else:
         return False

阴阳神万物主 发表于 2020-4-12 01:52:42

难度评级：普通
要素分析：模拟
敲代码感受：一定要勤打注释，不然自己不专心的话完全反应不过来自己写到什么程度了(我沉浸在音乐中的同时敲的代码，敲一段，停几分钟，然后再看就不记得写到哪里了……)
def solve(bottom:str,allowed:'list of str',show:'是否显示金字塔'=False)->bool:
class Foots:
   def __init__(self,how:str):
         self.left,self.right = how
   def __add__(self,other):
         if self.right == other.left:
            return True
         else:
            return False
   def __eq__(self,other):
         if isinstance(other,Foots):return self.left==other.left and self.right==other.right
         elif isinstance(other,Block):return self == other.foots
   def __hash__(self):
         return hash(self.left+self.right)

class Block:
   def __init__(self,shap:str):
         self.top,self.foots = shap[-1],Foots(shap[:-1])
   def __add__(self,other):
         if self.foots + other.foots:
            t = Foots(self.top+other.top)
            if t in Space.blocks:return t
         else:return False
   def __eq__(self,other):
         if isinstance(other,Foots):return self.foots == other
         elif isinstance(other,Block):return self.top==other.top and self.foots==other.foots

class Nlist(list):
   def __init__(self,iterable=()):
         super().__init__(iterable)
         self.limit = *len(self)
         self.indexs = self.limit[:]
   def append(self,obj):
         super().append(obj)
         self.limit.append(len(obj))
         self.indexs.append(0)
   def up(self):
         for i in range(-1,-len(self)-1,-1):
            self.indexs += 1
            if self.indexs<self.limit:return False
            self.indexs = 0
         else:return True

class Space:
   def __init__(self,bottom:str,allowed:'list of str'):
         self.pyramid = [)for i in range(len(bottom)-1)]]
         Space.blocks =
         self.hight = 1
   def build(self,floor=0):
         choices = Nlist()
         for each in self.pyramid:
            choices.append()
         if 0 in choices.limit:return False#缺少必要组件
         if (l := len(choices))==1:
            self.pyramid.append(choices.top)
            return True
         while 1:
            n = ]+choices[(j := i+1)]]for i in range(l-1)]
            if False not in n:
               self.pyramid.append(n)
               ok = self.build(floor+1)
               if ok:return ok
               self.pyramid.pop()
            if choices.up():return False#没有多余的可选方案
   def __str__(self):
         s = ''
         l = len(self.pyramid)
         for i in range(-1,-l-1,-1):
            s += ' '*(l+i)
            if isinstance(self.pyramid,str):
               s += self.pyramid
            else:
               for j in range(len(self.pyramid)):
                     s += self.pyramid.left+ ' '
               else:s += self.pyramid[-1].right
            s += '\n'
         return s
ready = Space(bottom,allowed)
del bottom,allowed
res = ready.build()
if show:print(ready)
return res

if __name__ == '__main__':
print('示例1 输出：',solve(bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"],show=1))
print('示例2 输出：',solve(bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]))

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

March2615 发表于 2020-4-12 19:56:23

import collections
import itertools

def daily372(bottom: str, allowed: list) -> bool:
# 解题思路
# 使用递归 -> 读取有可能的下一层状态(更新bottom)

# 将allowed转化为字典
allowed_dict = collections.defaultdict(list)
for allow in allowed:
   allowed_dict].append(allow[-1])

def getNextBottom(b: str):# 获得下一层所有可能的bottom
   n = len(b)
   possible_bottom = ['' for _ in range(n - 1)]
   if n == 1:
         return b
   for i in range(n - 1):
         possible_bottom = allowed_dict.get(b, '')
   n_bottom = itertools.product(*possible_bottom)# 拆包操作
   return n_bottom

def built_bottom(b):
   if len(b) == 1:
         return True
   for each in getNextBottom(b):
         if built_bottom(''.join(each)):
            return True
   return False

return built_bottom(bottom)

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

zltzlt 发表于 2020-4-13 13:22:27

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

76 ms

zltzlt 发表于 2020-4-13 13:23:41

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

输入以下数据超时：

mottom = "BDBBAA"
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-13 13:25:11

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

84 ms

zltzlt 发表于 2020-4-13 13:26:42

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

48 ms

页: [1]

鱼C论坛's Archiver

Python：每日一题 372