Python：每日一题 370
今天的题目：假设有一个带有四个圆形拨轮的转盘锁。每个拨轮都有 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
{:10_298:}欢迎大家一起答题！{:10_298:} 有奖励动力还是比较大的，不会都不行
def f370(deadends, target):
if "0000" in deadends: return -1
direction=[,[-1,0,0,0,1],,,,,,]
position=[]
dead=set(deadends)
while len(position)>0:
for dire in direction:
p=[(x+y)%10 for x,y in zip(dire,position)]
p=dire+position
p_str="".join(list(map(str,p[:-1])))
if p_str==target:
return p
elif p_str not in dead:
position.append(p)
dead.add(p_str)
position.pop(0)
return -1
前排 理解个题目都要半天，做不起做不起{:10_266:} 刷到过类似的词梯{:10_254:}
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 =
elem_list = str((int(elem_list) + 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 @zltzlt我来了 转发至此
def fun370(deadnums,target):
def get8Str(string):
result = []
for index in range(0,4):
num = int(string)
result.append(string+ str((num+1)%10) +string[(index+1):])
result.append(string+ 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 于 2020-4-9 13:27 编辑
上次看到大佬说用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)
for d in (-1, 1):
new_n = (n + d) % 10
list_code = 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)# 每次找队头的下一个点
step_count = queue + 1
for i in range(len(n_code)):
if n_code == target:
return step_count
elif n_code in visited:
continue
else:
visited.append(n_code)
if n_code not in queue:
queue.append((n_code, step_count))
queue.pop(0)
return -1
if __name__ == '__main__':
deadnums = ['0000']
target = "0009"
r = daily370(deadnums, target)
print(r)
跑的好慢{:10_285:}老是以为哪里没注意造成死循环了
而且visited越到后面越大
测试用例好像是没有问题，不知道能不能通过其他的测试用例 {:5_107:}逻辑跟不上 {:10_249:}{:10_249:}新手看了头好晕，还有得学 本帖最后由 编程鱼C 于 2020-4-9 13:33 编辑
订正 不懂什么意思 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=='9'){
cs= '0';
}else{
cs = (char)(cs +1);
}
temp = new String(cs);
result.add(temp);
//执行-1操作
temp = currLock;
cs = temp.toCharArray();
if(cs =='0'){
cs = '9';
}else{
cs=(char)(cs-1);
}
temp = new String(cs);
result.add(temp);
}
return result;
}
编程鱼C 发表于 2020-4-9 08:50
https://www.cnblogs.com/libbin/p/openLock.html
请不要抄袭！ zltzlt 发表于 2020-4-9 12:49
https://www.cnblogs.com/libbin/p/openLock.html
请不要抄袭！
好吧。。。。我改了 嗯？！之前的回复不见了？啥情况？
分割是什么操作？ 本帖最后由 阴阳神万物主 于 2020-4-9 15:55 编辑
难度评级：普通
要素分析：模拟 规划 逻辑
写得很复杂，但是应该算快，不确定寻找最少次数的方法是否能适应所有情况，但是我有信心大部分情况都好使。
随机输入生成器，送给有需要的人：
import random
def gent(m:'死亡数字的数量上限'=4,n:'生成数量'=10)->tuple:
for i in range(n):
deadnums = [''.join()for i in range(random.randint(0,m))]
target = ''.join()
yield deadnums,target
解题代码：
def solve(deadnums:list,target:str)->int:
class Lock:
def __init__(self,dn:list,tg:str):
self.now =
self.target =
self.denger = dict()
for each in dn:
d = self.denger
for i in each[:-1]:
i = int(i)
if i not in d:d = dict()
d = d
else:
i = int(each[-1])
if i not in d:d = 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
return True
except KeyError:return False
def dd(self,i):#校准方向
self.direction = 0 if self.target==self.nowelse 1 if (self.target-self.now)%10<(self.now-self.target)%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 += 1
b -= 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:
ne = (ne+self.direction)%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 = ]
for n in range(1,10):
for j in ins:
ne = self.now[:]
ne = (ne+n)%10
if not self.check(ne):
ne = (ne+self.direction)%10
if not self.check(ne):
c += n+1
break
ne = (self.now - n)%10
if not self.check(ne):
ne = self.now
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"))
思路解说：
既然这题目说的是锁的事情，那么为什么不造一把锁呢？
我构思了锁的概念模型，有四个轮盘的电子锁，当数字的排列满足死亡数字时，锁死的控制电路开关被接上，通电引起锁死。
既然已经有锁了，那么按照解锁的套路来，先在不锁死的前提下尽可能地靠近目标，在更进一步就会锁死的情况下稍微远离，进行迂回，然后再尝试接近，这样基本上就是最少的旋转次数了。
当然，我并不确定这是否能够适配所有情况，只敢肯定大部分如此
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" TJBEST 发表于 2020-4-8 20:42
@zltzlt我来了 转发至此
3916 ms kinkon 发表于 2020-4-8 21:05
有奖励动力还是比较大的，不会都不行
1700 ms 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"
页:
[1]
2