[已解决]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

def f372(bottom,allowed):
    n=len(bottom)
    d={}
    for e in allowed:
        d[e[:-1]]=d.get(e[:-1],[])+[e[-1]]
    def dp(n,now):
        if n==1:
            return True
        else:
            t=['']
            for i in range(n-1):
                a=now[i:i+2]
                if a in d:
                    nt=[]
                    for e in d[a]:
                        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)

先写个蠢得

跳转到最佳答案楼层

永恒的蓝色梦想

前排~

TJBEST

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

FHR

前排

塔利班

def f372(bottom,allowed):
    n=len(bottom)
    d={}
    for e in allowed:
        d[e[:-1]]=d.get(e[:-1],[])+[e[-1]]
    def dp(n,now):
        if n==1:
            return True
        else:
            t=['']
            for i in range(n-1):
                a=now[i:i+2]
                if a in d:
                    nt=[]
                    for e in d[a]:
                        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

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

解答错误

输入：

bottom = "DB"
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  写完了 见三楼

风魔孤行者

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[each:each+2] == n[:2]:
                    list2.append(n[2])
            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[0]
        del list1[0]
        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

阴阳神万物主

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

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 = [0]*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[i] += 1
                if self.indexs[i]<self.limit[i]:return False
                self.indexs[i] = 0
            else:return True
            
    class Space:
        def __init__(self,bottom:str,allowed:'list of str'):
            self.pyramid = [[Foots(bottom[i:i+2])for i in range(len(bottom)-1)]]
            Space.blocks = [Block(each) for each in set(allowed)]
            self.hight = 1
        def build(self,floor=0):
            choices = Nlist()
            for each in self.pyramid[floor]:
                choices.append([b for b in Space.blocks if b==each])
            if 0 in choices.limit:return False#缺少必要组件
            if (l := len(choices))==1:
                self.pyramid.append(choices[0][0].top)
                return True
            while 1:
                n = [choices[i][choices.indexs[i]]+choices[(j := i+1)][choices.indexs[j]]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[i],str):
                    s += self.pyramid[i]
                else:
                    for j in range(len(self.pyramid[i])):
                        s += self.pyramid[i][j].left+ ' '
                    else:s += self.pyramid[i][-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

import collections
import itertools


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

    # 将allowed转化为字典
    allowed_dict = collections.defaultdict(list)
    for allow in allowed:
        allowed_dict[allow[:-1]].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[i] = allowed_dict.get(b[i:i + 2], '')
        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

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

76 ms

zltzlt

风魔孤行者 发表于 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-12 01:52
难度评级：普通
要素分析：模拟
敲代码感受：一定要勤打注释，不然自己不专心的话完全反应不过来自己写到 ...

84 ms

zltzlt

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

48 ms