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

zltzlt

今天的题目：

假设有一个带有四个圆形拨轮的转盘锁。每个拨轮都有 10 个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。

每个拨轮可以自由旋转，例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000'，一个代表四个拨轮的数字的字符串。

给定列表 deadnums 和 字符串 target 。

deadnums 包含一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表目标数字，返回旋转到 target 需要的最小的旋转次数。

如果无论如何都不能旋转到 target，返回 -1。

说明：target 有可能是 deadnum 中的数字。

示例 1：

输入：deadnums = ['0201', '0101', '0102', '1212', '2002'], target = "0202"
输出：6
解释：可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2：

输入：deadnums = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可，"0000" -> "0009"。

示例 3：

输入：deadnums = ['8887', '8889', '8878', '8898', '8788', '8988', '7888', '9888'], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。

示例 4：

输入：deadnums = ["0000"], target = "8888"
输出：-1

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-4-8 18:47:13

有奖励动力还是比较大的，不会都不行

def f370(deadends, target):
    if "0000" in deadends: return -1
    direction=[[1,0,0,0,1],[-1,0,0,0,1],[0,1,0,0,1],[0,-1,0,0,1],[0,0,1,0,1],[0,0,-1,0,1],[0,0,0,1,1],[0,0,0,-1,1]]
    position=[[0,0,0,0,0]]
    dead=set(deadends)
    while len(position)>0:
        for dire in direction:
            p=[(x+y)%10 for x,y in zip(dire,position[0])]
            p[4]=dire[4]+position[0][4]
            p_str="".join(list(map(str,p[:-1])))
            if p_str==target:
                return p[4]
            elif p_str not in dead:
                position.append(p)
                dead.add(p_str)
        position.pop(0)
    return -1

跳转到最佳答案楼层

kinkon

有奖励动力还是比较大的，不会都不行

def f370(deadends, target):
    if "0000" in deadends: return -1
    direction=[[1,0,0,0,1],[-1,0,0,0,1],[0,1,0,0,1],[0,-1,0,0,1],[0,0,1,0,1],[0,0,-1,0,1],[0,0,0,1,1],[0,0,0,-1,1]]
    position=[[0,0,0,0,0]]
    dead=set(deadends)
    while len(position)>0:
        for dire in direction:
            p=[(x+y)%10 for x,y in zip(dire,position[0])]
            p[4]=dire[4]+position[0][4]
            p_str="".join(list(map(str,p[:-1])))
            if p_str==target:
                return p[4]
            elif p_str not in dead:
                position.append(p)
                dead.add(p_str)
        position.pop(0)
    return -1

永恒的蓝色梦想

前排

kkk999de

理解个题目都要半天，做不起做不起

kylin121380

刷到过类似的词梯
def main(deadnum ,target):
    if '0000' in deadnum or '0000' == target:
        return -1
    my = ['0000']
    step = 0   
    while my:  
        step += 1
        length = len(my)
        for _ in range(length):
            elem = my.pop(0)  
            for i in range(4):  
                for j in [-1,1]:
                    elem_list = [m for m in elem]
                    elem_list[i] = str((int(elem_list[i]) + j) % 10)
                    elem_list = ''.join(elem_list)
                    if elem_list == target:
                        return step
                    if elem_list in deadnum:
                        continue
                    my.append(elem_list)
    return -1

TJBEST

@zltzlt  我来了 转发至此

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

March2615

上次看到大佬说用BFS，就去临时抱佛脚了
看着挺容易想的，结果写起来那么难

def daily370(deadnums: list, target: str) -> int:
    # 解题思路
    # 如果没有deadnums
    # '0000' -> 'abcd' --> sum(min(int(i), 10 - int(i)) for i in code)
    # 此时有deadnums -> ? -> BFS(大佬提醒) 

    # https://blog.csdn.net/weixin_40953222/article/details/80544928(BFS图解)
    # https://blog.csdn.net/g11d111/article/details/76169861(BFS图解+代码示例)
    # 转换deadnums思路：走到deadnums即为锁死 -> 不能走 -> 搜索时当成已经走过了

    def next_code(code: str) -> list:  # 移动一次获得的所有可能值
        n_code = []
        for i in range(4):
            list_code = list(code)
            n = int(list_code[i])
            for d in (-1, 1):
                new_n = (n + d) % 10
                list_code[i] = str(new_n)
                n_code.append(''.join(list_code))
        return n_code

    if target in deadnums or '0000' in deadnums:
        return -1

    if target == '0000':
        return 0

    start = ['0000']  # 起始状态
    queue = [('0000', 0)]  # 据说可以用hash set(?)  TODO
    visited = start + deadnums
    while queue:
        n_code = next_code(queue[0][0])  # 每次找队头的下一个点
        step_count = queue[0][1] + 1
        for i in range(len(n_code)):
            if n_code[i] == target:
                return step_count
            elif n_code[i] in visited:
                continue
            else:
                visited.append(n_code[i])
            if n_code[i] not in queue:
                queue.append((n_code[i], step_count))
        queue.pop(0)
    return -1


if __name__ == '__main__':
    deadnums = ['0000']
    target = "0009"
    r = daily370(deadnums, target)
    print(r)

跑的好慢老是以为哪里没注意造成死循环了
而且visited越到后面越大
测试用例好像是没有问题，不知道能不能通过其他的测试用例

扁扁

逻辑跟不上

wdek263

新手看了头好晕，还有得学

编程鱼C

订正

陈尚涵

不懂什么意思

冰河星云

public static int openLock(String[] deadends,String target){

    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    Set<String> visited = new HashSet<>();
    String init = "0000";
    if (dead.contains(init) || dead.contains(target)) {
        return -1;
    }

    if (target.equals(init)) {
        return 0;
    }

    Set<String> set1 = new HashSet<>();
    set1.add(init);
    Set<String> set2 = new HashSet<>();
    set2.add(target);
    int count=0;
    while (!set1.isEmpty() && !set2.isEmpty()) {
        //将最小的集合遍历
        if (set1.size() > set2.size()) {
            Set<String> temp = set1;
            set1 = set2;
            set2 = temp;
        }
        Set<String> set3 = new HashSet<>();
        for (String curLock : set1) {
            List<String> neibors=findNeibors(curLock);
            for (String nextLock : neibors) {
                //如果set2中包含了这个Lock,则表示初试和目标在途中相遇到了
                if(set2.contains(nextLock)) {
                    return count+1;
                }
                if (!dead.contains(nextLock) && !visited.contains(nextLock)) {
                    visited.add(nextLock);
                    set3.add(nextLock);
                }
            }
        }
        count++;
        set1 = set3;
    }
    return -1;
}

/**
 *  找当前锁相邻的锁
 */
public static List<String> findNeibors(String currLock){
    int size = currLock.length();
    List<String> result = new ArrayList<String>();
    //对锁的4位数分别处理
    for(int i=0;i<size;i++){
        String temp = currLock;
        char[] cs = temp.toCharArray();
        if(cs[i]=='9'){
            cs[i]= '0';
        }else{
            cs[i] = (char)(cs[i] +1);
        }
        temp = new String(cs);
        result.add(temp);

        //执行-1操作
        temp = currLock;
        cs = temp.toCharArray();
        if(cs[i] =='0'){
            cs[i] = '9';
        }else{
            cs[i]=(char)(cs[i]-1);
        }
        temp = new String(cs);
        result.add(temp);
    }
    return result;
}

zltzlt

编程鱼C 发表于 2020-4-9 08:50

https://www.cnblogs.com/libbin/p/openLock.html

请不要抄袭！

编程鱼C

zltzlt 发表于 2020-4-9 12:49
https://www.cnblogs.com/libbin/p/openLock.html

请不要抄袭！

好吧。。。。我改了

阴阳神万物主

嗯？！之前的回复不见了？啥情况？
分割是什么操作？

阴阳神万物主

难度评级：普通
要素分析：模拟 规划 逻辑
写得很复杂，但是应该算快，不确定寻找最少次数的方法是否能适应所有情况，但是我有信心大部分情况都好使。
随机输入生成器，送给有需要的人：

import random
def gent(m:'死亡数字的数量上限'=4,n:'生成数量'=10)->tuple:
    for i in range(n):
        deadnums = [''.join([random.choice('0123456789') for j in range(4)])for i in range(random.randint(0,m))]
        target = ''.join([random.choice('0123456789') for j in range(4)])
        yield deadnums,target

解题代码：

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,i):#校准方向
            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):#尝试解锁
            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,0,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+1)%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)
    return l.trying()

if __name__ == '__main__':
    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

kylin121380 发表于 2020-4-8 20:12
刷到过类似的词梯
def main(deadnum ,target):
    if '0000' in deadnum or '0000' == target ...

输入以下数据超时：

deadnums = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"]
target = "8888"

zltzlt

TJBEST 发表于 2020-4-8 20:42
@zltzlt  我来了 转发至此

3916 ms

zltzlt

kinkon 发表于 2020-4-8 21:05
有奖励动力还是比较大的，不会都不行

1700 ms

zltzlt

March2615 发表于 2020-4-8 22:12
上次看到大佬说用BFS，就去临时抱佛脚了
看着挺容易想的，结果写起来那么难

输入以下数据超时：

deadnums = ["8430","5911","4486","7174","9772","0731","9550","3449","4437","3837","1870","5798","9583","9512","5686","5131","0736","3051","2141","2989","6368","2004","1012","8736","0363","3589","8568","6457","3467","1967","1055","6637","1951","0575","4603","2606","0710","4169","7009","6554","6128","2876","8151","4423","0727","8130","3571","4801","8968","6084","3156","3087","0594","9811","3902","4690","6468","2743","8560","9064","4231","6056","2551","8556","2541","5460","5657","1151","5123","3521","2200","9333","9685","4871","9138","5807","2191","2601","1792","3470","9096","0185","0367","6862","1757","6904","4485","7973","7201","2571","3829","0868","4632","6975","2026","3463","2341","4647","3680","3282","3761","4410","3397","3357","4038","6505","1655","3812","3558","4759","1112","8836","5348","9113","1627","3249","0537","4227","7952","8855","3592","2054","3175","6665","4088","9959","3809","7379","6949","8063","3686","8078","0925","5167","2075","4665","2628","8242","9831","1397","5547","9449","6512","6083","9682","2215","3236","2457","6211","5536","8674","2647","9752","5433","0186","5904","1526","5347","1387","3153","1353","6069","9995","9496","0003","3400","1692","6870","4445","3063","0708","3278","6961","3063","0249","0375","1763","1804","4695","6493","7573","9977","1108","0856","5631","4799","4164","0844","2600","1785","1587","4510","9012","7497","4923","2560","0338","3839","5624","1980","1514","4634","2855","7012","3626","7032","6145","5663","4395","0724","4711","1573","6904","8100","2649","3890","8110","8067","1460","0186","6098","2459","6991","9372","8539","8418","7944","0499","9276","1525","1281","8738","5054","7869","6599","8018","7530","2327","3681","5248","4291","7300","8854","2591","8744","3052","6369","3669","8501","8455","5726","1211","8793","6889","9315","0738","6805","5980","7485","2333","0140","4708","9558","9026","4349","5978","4989","5238","3217","5938","9660","5858","2118","7657","5896","3195","8997","1688","2863","9356","4208","5438","2642","4138","7466","6154","0926","2556","9574","4497","9633","0585","1390","5093","3047","0430","7482","0750","6229","8714","4765","0941","1780","6262","0925","5631","9167","0885","7713","5576","3775","9652","0733","7467","5301","9365","7978","4736","3309","6965","4703","5897","8460","9619","0572","6297","7701","7554","8669","5426","6474","5540","5038","3880","1657","7574","1108","4369","7782","9742","5301","6984","3158","2869","0599","2147","6962","9722","3597","9015","3115","9051","8269","6967","5392","4401","6579","8997","8933","9297","0151","8820","3297","6723","1755","1163","8896","7122","4859","5504","0857","4682","8177","8702","9167","9410","0130","2789","7492","5938","3012","4137","3414","2245","4292","6945","5446","6614","2977","8640","9242","7603","8349","9420","0538","4222","0599","8459","8738","4764","6717","7575","5965","9816","9975","4994","2612","0344","6450","9088","4898","6379","4127","1574","9044","0434","5928","6679","1753","8940","7563","0545","4575","6407","6213","8327","3978","9187","2996","1956","8819","9591","7802","4747","9094","0179","0806","2509","4026","4850","2495","3945","4994","5971","3401","0218","6584","7688","6138","7047","9456","0173","1406","1564","3055","8725","4835","4737","6279","5291","0145","0002","1263","9518","1251","8224","6779","4113","8680","2946","1685","2057","9520","4099","7785","1134","2152","4719","6038","1599","6750","9273","7755","3134","2345","8208","5750","5850","2019","0350","9013","6911","6095","6843","3157","9049","0801","2739","9691","3511"]
target = "2248"