寻找小码的路 | 「青训营 X 码上掘金」主题创作

简介: 寻找小码的路 | 「青训营 X 码上掘金」主题创作

前言

能加入到这届的青训营我十分的开心,更希望自己不仅能通过这次的青训营之旅丰富自己的阅历之余,还能够认识到更多的学习伙伴。最后通过快乐写码分享讲解我创作灵感和过程的同时,也希望大家可以及时纠正我的错误,伴我学习。

任务介绍

小青要找小码去玩,他们的家在一条直线上,当前小青在地点 N ,小码在地点 K (0≤N , K≤100 000),并且小码在自己家原地不动等待小青。小青有两种交通方式可选:步行和公交。 步行:小青可以在一分钟内从任意节点 X 移动到节点 X-1 或 X+1 公交:小青可以在一分钟内从任意节点 X 移动到节点 2×X (公交不可以向后走)

请帮助小青通知小码,小青最快到达时间是多久? 输入: 两个整数 N 和 K 输出: 小青到小码家所需的最短时间(以分钟为单位)

任务分析

通过对题目的解读,不难看出这是一个求从起点N到终点K的最短路径的问题,可以使用宽度优先搜索算法BFS进行解题。

宽度优先搜索算法的搜索步骤一般是:

(1)从队列头取出一个结点,检查它按照扩展规则是否能够扩展,如果能则产生一个新结点。

(2)检查新生成的结点,看它是否已在队列中存在,如果新结点已经在队列中出现过,就放弃这个结点,然后回到第(1)步。否则,如果新结点未曾在队列中出现过,则将它加入到队列尾。

(3)检查新结点是否目标结点。如果新结点是目标结点,则搜索成功,程序结束;若新结点不是目标结点,则回到第(1)步,再从队列头取出结点进行扩展。

任务设计

假设小青起点N为节点N,并使用一个双端队列来实现宽度优先搜索算法,接着使用一个set来记录已经访问过的节点,这样就可以避免重复访问已经访问过的节点,由此来提高效率。

在这里,我假设小青和小码的位置关系为 N < K,代码中的边界条件也是基于此假设而设置的。如果你需要处理 N > K 的情况,需要对代码进行相应的修改。

另外,在这个问题中,如果起点和终点之间不存在路径,则返回 -1。

最后,这段代码的复杂度为 O(K),因为只需要遍历K个节点即可找到终点,并且由于使用了set来判重,所以不存在重复便利相同节点的情况。

from collections import deque
def shortest_path(N, K):
    queue = deque([(N, 0)])
    visited = set()
    while queue:
        node, step = queue.popleft()
        if node == K:
            return step
        if node not in visited:
            visited.add(node)
            if node - 1 >= 0:
                queue.append((node - 1, step + 1))
            if node + 1 <= K:
                queue.append((node + 1, step + 1))
            if node * 2 <= K:
                queue.append((node * 2, step + 1))
    return -1
if __name__ == '__main__':
   n, k = map(int, input("请输入小青和小码的位置:").split())
   print("最短时间是:",shortest_path(n, k),"分钟")


总结

通过这次的解题,我认为这道题目也可以使用递归来实现宽度优先搜索算法,每一层的递归可以看作为一层的BFS,但考虑到递归是一种比较耗费时间的算法,对于量较大的数据,可能会导致超时,所以我暂时没用尝试使用递归进行解题。

写文章不易,如果你觉得文章对你有帮助,麻烦点一下点赞、收藏,你的支持是我写文章的最大动力!

最后,希望通过这次的讲解创作灵感和过程,能让掘友们看到对于这个主题的不一样的解法,也希望掘友们可以及时纠正我的错误。


目录
打赏
0
0
0
0
8
分享
相关文章
【我的创作之路】CSDN陪我走过的256个日夜
【我的创作之路】CSDN陪我走过的256个日夜
178 0
2024 乘风者计划全新启航!快来加入吧!
 2021年,阿里云开发者社区焕新升级,重磅推出“乘风者计划”!诚邀四海技术博主入驻社区,泼墨云间,书写天地。入驻社区,即可享丰厚权益! 新的一年,乘风者计划重磅升级!
250697 81
2024 乘风者计划全新启航!快来加入吧!
DayDayUp:7月25日,如何打造技术品牌影响力?顶级大咖独家传授—阿里云乘风者计划专家博主&CSDN TOP1“一个处女座程序猿”《我是如何通过写作成为百万粉丝博主的?》演讲全文回顾
DayDayUp:7月25日,如何打造技术品牌影响力?顶级大咖独家传授—阿里云乘风者计划专家博主&CSDN TOP1“一个处女座程序猿”《我是如何通过写作成为百万粉丝博主的?》演讲全文回顾 目录 个人简介 一、什么内容是受欢迎的写作内容? 1.1、学生(计算机相关)群体 1.2、同行(开发者)群体 1.3、好内容的特点 二、一些经典的技术文章逻辑框架设计 2.1、从写作逻辑和结构角度考虑 (1)、对于bug类型的文章——通过分析刨根问底 (2)、对于学习类型的文章—通过案例学以致用 (3)、对于总结类型的文章—通过思考产生共鸣 2.2、从写作技巧考虑 (1)、题目和摘要必须简单、清晰明了且定位
DayDayUp:7月25日,如何打造技术品牌影响力?顶级大咖独家传授—阿里云乘风者计划专家博主&CSDN TOP1“一个处女座程序猿”《我是如何通过写作成为百万粉丝博主的?》演讲全文回顾
涨粉写作经验分享(一) - 写作技巧
为什么感觉自己的文章写的不错却没有流量推送,为什么别人一篇文章却能吸引这么多人访问,关注?你是否有过这些疑问,来看看怎么解决他们吧。
225 0
阿里技术人和开发者朋友们的私藏书单
在快速变化、充满不确定的时代大背景下,拥抱变化成为常态。该如何应对、如何破局? 通过读书持续学习、持续精进,可能是其中成本最低、最高效的一种方式。
阿里技术人和开发者朋友们的私藏书单
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等