[已解决]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
难度评级：普通
要素分析：模拟 规划 逻辑
写得很复杂，但是应该算快，不确定寻找最少次数的方法是否能适 ...

解答错误

输入：

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

复制代码

输出：8
预期结果：6

zltzlt

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

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

阴阳神万物主

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

输入：

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

1. def solve(deadnums:list,target:str)->int:
   
2.     class Lock:
   
3.         def __init__(self,dn:list,tg:str):
   
4.             self.now = [0,0,0,0]
   
5.             self.target = [int(i) for i in tg]
   
6.             self.denger = dict()
   
7.             for each in dn:
   
8.                 d = self.denger
   
9.                 for i in each[:-1]:
   
10.                     i = int(i)
    
11.                     if i not in d:d[i] = dict()
    
12.                     d = d[i]
    
13.                 else:
    
14.                     i = int(each[-1])
    
15.                     if i not in d:d[i] = 1
    
16.             self.direction = [((1 if n<10-n else -1)if n else 0)for n in self.target]
    
17.         def check(self,lst)->bool:#检查是否死线
    
18.             a,b,c,d = lst
    
19.             try:
    
20.                 self.denger[a][b][c][d]
    
21.                 return True
    
22.             except KeyError:return False
    
23.         def dd(self,*j):#校准方向
    
24.             for i in j:
    
25.                 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
    
26.         def trying(self,m=0,d=1):#尝试解锁
    
27.             if self.check(self.now):#初始锁死
    
28.                 return -1
    
29.             c = 0
    
30.             for i in range(4):#必然有一位不可能达到目标
    
31.                 a,b = self.target[:],self.target[:]
    
32.                 a[i] += 1
    
33.                 b[i] -= 1
    
34.                 if self.check(a) and self.check(b):c+=1
    
35.             if c == 4:
    
36.                 return -1
    
37.             c,i,flg,t =0,m,1,0
    
38.             while self.now != self.target:#一定可以解锁
    
39.                 ne = self.now[:]
    
40.                 #print('ts',ne,self.direction,i,flg)
    
41.                 if flg:#靠近目标
    
42.                     if self.direction[i]:
    
43.                         ne[i] = (ne[i]+self.direction[i])%10
    
44.                         if ne == self.target:return c+1
    
45.                         #print('ts',ne)
    
46.                         if self.check(ne):
    
47.                             if self.direction.count(0) == 3:
    
48.                                 flg = 0
    
49.                                 continue
    
50.                             else:
    
51.                                 i = (i+d)%4
    
52.                                 t += 1
    
53.                         else:
    
54.                             c += 1
    
55.                             self.now = ne
    
56.                             self.dd(i)
    
57.                             t = 0
    
58.                     else:
    
59.                         i = (i+1)%4
    
60.                         t += 1
    
61.                         if t == 4:
    
62.                             t,flg = 0,0
    
63.                 else:#尽可能少地远离目标
    
64.                     ins = [q for q in range(4)if not self.direction[q]]
    
65.                     for n in range(1,10):
    
66.                         for j in ins:
    
67.                             ne = self.now[:]
    
68.                             ne[j] = (ne[j]+n)%10
    
69.                             if not self.check(ne):
    
70.                                 ne[i] = (ne[i]+self.direction[i])%10
    
71.                                 if not self.check(ne):
    
72.                                     c += n+1
    
73.                                     break
    
74.                             ne[j] = (self.now[j] - n)%10
    
75.                             if not self.check(ne):
    
76.                                 ne[i] = self.now[i]
    
77.                                 if not self.check(ne):
    
78.                                     c += n
    
79.                                     break
    
80.                         else:
    
81.                             continue
    
82.                         self.now = ne
    
83.                         self.dd(j)
    
84.                         self.dd(i)
    
85.                         flg = 1
    
86.                         break
    
87.             return c
    
88.     l = Lock(deadnums,target)
    
89.     a = l.trying()
    
90.     l.now = [0,0,0,0]
    
91.     l.dd(0,1,2,3)
    
92.     b = l.trying(-1,-1)
    
93.     return min(a,b)
    
94. 
    
95. if __name__ == '__main__':
    
96.     print('之前错的：',solve(deadnums = ['0033', '3201', '0321', '0122', '3032', '2120', '1230', '2303', '2111', '2030'], target = '0123'))
    
97.     print('示例1 输出：',solve(deadnums = ['0201', '0101', '0102', '1212', '2002'], target = "0202"))
    
98.     print('示例2 输出：',solve(deadnums = ["8888"], target = "0009"))
    
99.     print('示例3 输出：',solve(deadnums = ['8887', '8889', '8878', '8898', '8788', '8988', '7888', '9888'], target = "8888"))
    
100.     print('示例4 输出：',solve(deadnums = ["0000"], target = "8888"))

复制代码

zltzlt

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

解答错误

输入：

1. 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"]
   
2. 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

爱叫什么叫什么

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