宽度优先搜索法

class Solution:def openLock(self, deadends: List[str], target: str) -> int:# 目的地在死亡数组里if target in deadends:return -1# 起点在死亡数字里if '0000' in deadends:return -1# 起点就是目标字符串if '0000' == target:return 0# 定义前向函数def prev(num):return str(int(num)-1) if num != '0' else '9'# 定义后向函数def after(num):return str(int(num)+1) if num != '9' else '0'# 该字符串下一个搜索集合def get(str_):# 依次对四个数字进行尝试arr = list(str_)for i in range(4):num = arr[i]# 前向查询arr[i] = prev(num)yield (''.join(arr))# 后向查询arr[i] = after(num)yield (''.join(arr))arr[i] = num# 初始化队列q = collections.deque([('0000', 0)])# 初始化访问数组，避免死循环seen = set(['0000'])# 广度优先搜索寻找路径while q:# 出队操作top = q.popleft()str_, step = topprint(str_)for s in get(str_):# 判断是否为目标if s == target:return step + 1# 是否在访问数组中或者死亡数组中if s not in seen and s not in deadends:q.append((s, step + 1))# 添加访问数组seen.add(s)return -1

A*算法寻路

# 定义A*算法类
class AStar(object):def __init__(self, status, target, g):self.status = statusself.g = gself.h = AStar.getH(status, target)self.f = self.g + self.h @staticmethoddef getH(status, target):sum_ = 0# 对四个字符分别求曼哈顿距离for i in range(4):dis = abs(int(status[i]) - int(target[i]))sum_ += min(dis, 10 - dis)return sum_# 排序def __lt__(self, other):return self.f < other.f
class Solution:def openLock(self, deadends: List[str], target: str) -> int:# 起点或终点在死亡数组里if '0000' in deadends or target in deadends:return -1# 起点就是终点if '0000' == target:return 0# 获取向右拨动的字符def forward(c):return str(int(c) + 1) if c != '9' else '0'# 获取向左拨动的字符def pre(c):return str(int(c) - 1) if c != '0' else '9'# 获得孩子结点的状态def get(str_):arr = list(str_)for i in range(4):c = arr[i]# 右拨动arr[i] = forward(c)yield ''.join(arr)# 左拨动arr[i] = pre(c)yield ''.join(arr)arr[i] = c# 初始化优先队列q = [AStar('0000', target, 0)]# 初始化访问数组seen = {'0000'}# 遍历优先队列while q:# 出队操作top = heapq.heappop(q)# 获取结点属性g = top.gf = top.fstatus = top.statusfor str_ in get(status):if str_ == target:return g + 1if str_ not in seen and str_ not in deadends:seen.add(str_)heapq.heappush(q, AStar(str_, target, g + 1))return -1

小黑生活

去笔试去的路上

吃份烤冷面

收到笔试通知

回学校开就业中心证明

开完证明做一小时足疗+半小时按摩

终于习惯了坐地铁上不戴口罩啦

跟尚香的疯狂星期四

去喝茶百道，热爱并记录生活的小黑黑

去尚香自习室转转，感受一下学习氛围

小跑着回家啦，准备第二天实习

报名个中级软考

去交材料啦，临走时主任送我一杯咖啡，开心啦～

午餐牛肉堡

吃完饭喝个茶

晚餐造一造，来个豪华麻辣香锅

收到笔试通知

跟导师监考蓝桥杯

午饭学校吃个烤冷面+蟹黄面+百香果茶

回宿舍尝一尝老黑们昨天的剩饭

马拉松前一天小造一下

去领马拉松参赛物资啦

坐地铁去副中心

跑崩了，不过坚持下来了，遇见了好久不见的本科同学

照片传过来了，人生不求一直奔跑，要跑跑停停一直向前

回家从五点睡到了晚上12点，吃个牛排

早餐宇飞牛肉面

来个太平洋咖啡桃花美式

证书出来了

午餐鳕鱼堡套餐

实习终于有了方向，尽可能多接触实际的东西，花絮：看到了有人摸鱼哈哈哈哈

晚餐蹄筋面套餐

开启小汤3，练完琴发现沙尘暴太大了

回家喝点儿“石榴酒”

早起去面试，虽然竞争很大，但小黑也要积极面对毕业季

午饭牛肉双拼外卖

午后太平洋咖啡来杯香草咖啡，下午继续努力！