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

zltzlt

冰河星云 发表于 2020-4-9 12:02

要用 Python 写哦

zltzlt

阴阳神万物主 发表于 2020-4-9 14:17
嗯？！之前的回复不见了？啥情况？
分割是什么操作？

本来想着将原贴中的回复合并到这个帖子下的，但是合并不了……

冰河星云

zltzlt 发表于 2020-4-9 17:44
要用 Python 写哦

为什么？总得给点安慰奖吧（求安慰奖）

冰河星云

zltzlt 发表于 2020-4-9 17:44
要用 Python 写哦

谢谢！

March2615

zltzlt 发表于 2020-4-9 17:44
输入以下数据超时：

但是我输入这两个参数是可以得到答案的啊
答案是10

zltzlt

阴阳神万物主 发表于 2020-4-9 15:31
难度评级：普通
要素分析：模拟 规划 逻辑
写得很复杂，但是应该算快，不确定寻找最少次数的方法是否能适 ...

解答错误

输入：

deadnums = ['0033', '3201', '0321', '0122', '3032', '2120', '1230', '2303', '2111', '2030']
target = '0123'

输出：8
预期结果：6

zltzlt

March2615 发表于 2020-4-10 10:30
但是我输入这两个参数是可以得到答案的啊
答案是10

用时比较长，效率有待提升

阴阳神万物主

zltzlt 发表于 2020-4-10 12:57
解答错误

输入：

时间复杂度加倍，但是这个错误被纠正了。

def solve(deadnums:list,target:str)->int:
    class Lock:
        def __init__(self,dn:list,tg:str):
            self.now = [0,0,0,0]
            self.target = [int(i) for i in tg]
            self.denger = dict()
            for each in dn:
                d = self.denger
                for i in each[:-1]:
                    i = int(i)
                    if i not in d:d[i] = dict()
                    d = d[i]
                else:
                    i = int(each[-1])
                    if i not in d:d[i] = 1
            self.direction = [((1 if n<10-n else -1)if n else 0)for n in self.target]
        def check(self,lst)->bool:#检查是否死线
            a,b,c,d = lst
            try:
                self.denger[a][b][c][d]
                return True
            except KeyError:return False
        def dd(self,*j):#校准方向
            for i in j:
                self.direction[i] = 0 if self.target[i]==self.now[i]else 1 if (self.target[i]-self.now[i])%10<(self.now[i]-self.target[i])%10 else -1
        def trying(self,m=0,d=1):#尝试解锁
            if self.check(self.now):#初始锁死
                return -1
            c = 0
            for i in range(4):#必然有一位不可能达到目标
                a,b = self.target[:],self.target[:]
                a[i] += 1
                b[i] -= 1
                if self.check(a) and self.check(b):c+=1
            if c == 4:
                return -1
            c,i,flg,t =0,m,1,0
            while self.now != self.target:#一定可以解锁
                ne = self.now[:]
                #print('ts',ne,self.direction,i,flg)
                if flg:#靠近目标
                    if self.direction[i]:
                        ne[i] = (ne[i]+self.direction[i])%10
                        if ne == self.target:return c+1
                        #print('ts',ne)
                        if self.check(ne):
                            if self.direction.count(0) == 3:
                                flg = 0
                                continue
                            else:
                                i = (i+d)%4
                                t += 1
                        else:
                            c += 1
                            self.now = ne
                            self.dd(i)
                            t = 0
                    else:
                        i = (i+1)%4
                        t += 1
                        if t == 4:
                            t,flg = 0,0
                else:#尽可能少地远离目标
                    ins = [q for q in range(4)if not self.direction[q]]
                    for n in range(1,10):
                        for j in ins:
                            ne = self.now[:]
                            ne[j] = (ne[j]+n)%10
                            if not self.check(ne):
                                ne[i] = (ne[i]+self.direction[i])%10
                                if not self.check(ne):
                                    c += n+1
                                    break
                            ne[j] = (self.now[j] - n)%10
                            if not self.check(ne):
                                ne[i] = self.now[i]
                                if not self.check(ne):
                                    c += n
                                    break
                        else:
                            continue
                        self.now = ne
                        self.dd(j)
                        self.dd(i)
                        flg = 1
                        break
            return c
    l = Lock(deadnums,target)
    a = l.trying()
    l.now = [0,0,0,0]
    l.dd(0,1,2,3)
    b = l.trying(-1,-1)
    return min(a,b)

if __name__ == '__main__':
    print('之前错的：',solve(deadnums = ['0033', '3201', '0321', '0122', '3032', '2120', '1230', '2303', '2111', '2030'], target = '0123'))
    print('示例1 输出：',solve(deadnums = ['0201', '0101', '0102', '1212', '2002'], target = "0202"))
    print('示例2 输出：',solve(deadnums = ["8888"], target = "0009"))
    print('示例3 输出：',solve(deadnums = ['8887', '8889', '8878', '8898', '8788', '8988', '7888', '9888'], target = "8888"))
    print('示例4 输出：',solve(deadnums = ["0000"], target = "8888"))

zltzlt

阴阳神万物主 发表于 2020-4-10 13:25
时间复杂度加倍，但是这个错误被纠正了。

解答错误

输入：

deadnums = ["7887","7876","8677","7667","8686","6688","6777","8687","8877","8668","6676","7778","7788","6766","7687","6688","6867","8866","7878","6776","6888","7888","6767","8787","6876","8788","6767","7667","8768","8877","6786","7878","6888","8786","7866","8887","8866","8788","6787","7676","7766","7867","7687","6676","6776","6878","7876","7888","8877","7788","7876","8687","8866","8776","7666","7887","7787","6768","7876","8776","6877","8666","8868","8876","8868","6778","7887","6787","7878","7766","6887","7776","7867","6677","8788","7778","7878","8786","6667","7776","7687","6888","7776","6887","6788","7768","6767","7886","6787","7876","8678","7677","8776","7866","6777","6778","8788","8766","8768","8867","6876","7876","6766","6786","7786","7888","8868","8688","8788","6666","6788","6688","8887","7866","7878","6777","6786","7688","7677","7777","6767","6877","7677","6888","7668","8677","7668","8788","7666","7688","7688","7887","8877","7687","6868","6687","6668","6667","6886","6888","7676","7867","8786","7686","8666","7668","6766","7877","6667","7886","8786","6866","7788","6877","8878","7767","7766","7786","8788","7888","7778","8876","8778","6786","8786","8777","6667","8687","6776","8788","6878","8678","6887","8788","7676","8888","6788","7878","7878","8867","6767","8688","7888","6877","7866","7678","8878","8786","7887","6866","8668","7868","6887","6688","7686","6876","7677","7868","6876","6877","7678","7766","8787","6676","8776","6767","8877","6868","8786","8887","8776","7867","7678","8868","8887","6767","8778","7768","7666","7876","8686","7868","6777","8877","8888","6686","8768","6768","6768","8686","7776","7877","8887","6677","8878","8678","6677","7678","7768","6868","7867","7888","6788","6886","8677","8667","8788","7677","8678","8766","7686","8888","7666","7678","6676","8776","6668","8867","8668","8776","8687","8888","7778","6878","7678","6686","8667","8786","8877","7768","7666","8777","7878","8888","7787","7666","8676","6666","8778","6767","8886","7877","8787","7666","8868","7868","8887","8667","6787","7776","7778","6677","6877","6668","6767","8788","8866","8787","8676","6878","8787","6668","8776","8877","8778","8887","8887","7688","7886","7766","7887","7888","8866","6876","6868","6786","6788","8777","7668","6686","6867","7777","8678","6688","6878","8778","8877","6776","8776","7768","6678","8866","8677","8667","6667","6786","8867","6776","6787","7787","7777","6668","6777","6777","8778","6866","7786","7777","6866","8776","7666","8777","8876","7667","8678","8778","7776","6877","6787","7767","7777","6787","6678","6868","7886","6688","6888","6877","8887","6786","6876","7688","7686","8677","7766","7667","7676","6867","7666","8778","6786","7676","8777","8786","6687","7867","6788","6868","6868","7887","8778","7778","6777","8678","7876","8888","8687","6686","7887","8677","6688","7788","7776","7766","7768","6866","7666","7778","6676","6677","8776","8676","6866","8666","7787","7687","8676","7766","7777","8686","7888","7676","6666","7667","6886","6678","6888","8788","7867","8776","7768","7767","8778","7666","8667","7876","8868","6678","6766","6888","7678","6678","8878","7678","7876","7768","8678","6866","6787","6868","8778","8688","8688","8666","7776","7686","8876","6786","7878","8777","6766","7676","7686","8677","6768","8886","6766","8678","7878","8788","7688","7766","7677","7668","7678","8686","6888","8868","7887","8766","8678","6767","7877","6888","7666","8787","7767","6766","8677","7868","6778","7687","7766","6768","6786","8886","6688","8678","7778","6777"]
target = "8767"

输出：14
预期结果：12

阴阳神万物主

zltzlt 发表于 2020-4-10 13:28
解答错误

输入：

那我是想不到另外的解锁套路了。

BXQXX

每次连题目都看不懂
坐等大神解释

KKL123

def fun370(deadnums,target):
    def get8Str(string):
        result = []
        for index in range(0,4):
            num = int(string[index])
            result.append(string[0:index]+ str((num+1)%10) +string[(index+1):])
            result.append(string[0:index]+ str((num+9)%10) +string[(index+1):])
        return set(result)
   
    if target == '0000':
        return 0
    elif '0000' in deadnums:
        return -1
    Search = {'0000'}
    Last = {'0000'}
    Dead = set(deadnums)
    page = 1
    while True:
        Temp = set()
        for eachStr in Last:
            Temp = Temp | get8Str(eachStr)
        Temp = Temp - Search
        if target in Temp:
            return page
        Search = Search | Temp
        Last = Temp - Dead
        if Last == set():
            return -1
        page += 1

爱叫什么叫什么

我还是新手,还是个宝宝,宝宝表示看不懂