专栏首页架构说【LeetCode】数据结构与算法 最短路径

【LeetCode】数据结构与算法 最短路径

Happy coding! Enjoy Algorithms.

【LeetCode】数据结构与算法 第一期 图的最短路径问题

如何刷题:表达+熟练+重复5遍

  1. 刷题不需要刷那么多!!不需要那么多!!不需要辣么多!!刷熟常用300题,刷5遍,效果 >>>>>(远好于) 我这样刷到900+题。
  2. 个人感觉:熟练度 >>>>> (远重要于)抖小聪明。流畅的表达,简介明了的思路远好于在白板上磨磨蹭蹭的推导。这也回到第一点,反复刷同样的题非常重要。

其实,8-10遍高频效果是最好的,这基本就是到另一个境界了。当然,大家没有那么多时间,3-5遍也可以去面试了。

  1. Talk out loud,这个不仅仅是说在面试的时候你要说出你的思路。

刷题的时候也是!你第一遍可以不开口,但后面几遍,一定要开口说话!!

刷题是为了面试,面试第一看的是communication skill! 不在刷题的时候开口,到面试的时候才意识到沟通不畅就太晚了。

  1. 关于具体刷题,我只说第一遍,我是怎么刷的。

前500题:抄。就是直接看答案抄!完美解决没基础看不懂,不会做,做题枯燥等种种问题。其实,我觉得,在刚开始的时候完全没必要思考,做题。因为初学者啥也不会。自己拼命想,写两题就被劝退不想再做了。

  1. https://afteracademy.com/tech-interview/ds-algo-concepts 题目总结和这个对比起来。

优先级队列使用场景和 课后作业

  • CPU Scheduling
  • Event-driven Simulation.
  • A* search algorithm in AI.
  • Data compression using Huffman coding.【tree】
  • Statistics (maintain the largest M values in a sequence).

Suggested Problems to Solve in Heaps

  • K Pairs with Smallest Sums
  • Sliding window maximum
  • Merge K sorted list
  • Convert a min heap to max heap

题目

【LeetCode】Daily Coding Challenge 124. 二叉树中的最大路径和

分析:

  • 假如给我一个二叉树root, 利用已有掌握知识,(数学几何都是利用已知识信息 推到更复杂信息) 我能计算出roo为根节点高度/深度/路径。最大路径。9 -10 20 15组成的链表(类比hegiht)

不一定经过root节点。因为每个节点值不一定,可能需要计算每个node, 每个node就是一个tree

  • 难点1 如何:二叉树的每个节点都计算执行一遍(从上到下看) 变成遍历一边(从下到上)

【万变不离其宗还是利用 遍历,但是返回值 不是最大路径,二是最深路径,需要2个返回值】

  • 难点2 :负数一定舍去吧?如果叶子节点肯定删除,如果中间的,看sum结果。

###【LeetCode】Daily Coding Challenge 54. 螺旋矩阵

分析

  • 从一个位置到另外一个位置,只有一个路径。该怎么遍历?
  • 【100%确定事情】 按照行列遍历线型方式肯定不行。
  • 【100%确定事情】 这里不需要回溯。

如何判断一个图是否有环?207. 课程表

  • 【你知道,大家都知道知识】 无论怎么遍历,最终收回输出一个顺序。
  • 定义:遍历顺序 开始位置 = 结束位置。
  • 一个节点被访问2次 一定是环吗?
  • 0为一次dfs遍历 入口节点,这个节点被访问2次,说明存在环。
  • 说明 如果 3也被访问2次,这个不是环

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法——图最短路径

    最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。关于求解图的最短路径方法也层出不穷,本篇文章将详细讲解图的最短路...

    五分钟学算法
  • 数据结构——最短路径Dijkstra算法

    在上一篇博文里,我记录了最小生成树的算法实现,而在这篇里,我们来讲讲查找最短路径的算法,Dijkstra算法。

    Originalee
  • 数据结构(十三):最短路径(Floyd算法)

    Floyd-Warshall 算法使用动态规划策略计算图中每两个顶点间的最短路径,算法中通过调整路径中经过的中间顶点来缩小路径权值,最终得到每对顶点间的最短路径...

    zhipingChen
  • 数据结构(十二):最短路径(Dijkstra算法)

    Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

    zhipingChen
  • 数据结构(十一):最短路径(Bellman-Ford算法)

    最短路径是指连接图中两个顶点的路径中,所有边构成的权值之和最小的路径。之前提到的广度优先遍历图结构,其实也是一种计算最短路径的方式,只不过广度遍历中,边的长度都...

    zhipingChen
  • 数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩...

    越陌度阡
  • 算法与数据结构(六) 迪杰斯特拉算法的最短路径(Swift版)

    上篇博客我们详细的介绍了两种经典的最小生成树的算法,本篇博客我们就来详细的讲一下最短路径的经典算法----迪杰斯特拉算法。首先我们先聊一下什么是最短路径,这个还...

    lizelu
  • 数据结构与算法–关键路径

    关键路径与无环加权有向图的最长路径 现在考虑一个这样的问题:你今天事情比较多,要洗衣服、做作业还要烧水洗澡,之后出去找朋友玩。假设洗衣服要20分钟,烧水要30分...

    小莹莹
  • PHP数据结构-图的应用:最短路径

    上篇文章的最小生成树有没有意犹未尽的感觉呀?不知道大家掌握得怎么样,是不是搞清楚了普里姆和克鲁斯卡尔这两种算法的原理了呢?面试的时候如果你写不出,至少得说出个大...

    硬核项目经理
  • 数据结构和算法——用动态规划求解最短路径问题

    一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

    zhaozhiyong
  • 数据结构和算法——用动态规划求解最短路径问题

        在利用动态规划求解的过程中值得注意的就是是否包含最优子结构,简单来讲就是一个问题的最优解是不是包含着子问题的最优解。利用求解子问题的最优解最后得到整个问...

    zhaozhiyong
  • 数据结构基础温故-5.图(下):最短路径

    图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径。例如在交通网络中经常会遇到这样的问题:两地之间是否有公路可通;在有多条公路可通的情况下,哪一条路径是...

    Edison Zhou
  • 算法与数据结构(八) AOV网的关键路径(Swift版)

    上篇博客我们介绍了AOV网的拓扑序列,请参考《数据结构(七) AOV网的拓扑排序(Swift面向对象版)》。拓扑序列中包括项目的每个结点,沿着拓扑序列将项目进行...

    lizelu
  • 【数据结构与算法面试题】二叉树路径查找

    问题分析:核心是树的遍历,注意题目中“路径”的定义,是从根节点到叶子节点。先序遍历正好是从根节点开始,因此可以利用先序遍历的过程来实现这个过程。

    zhaozhiyong
  • 最短路问题与标号算法(label correcting algorithm)研究(2) - 最短路径问题简介

    在开始介绍最短路问题之前我们先来简单讨论网络流问题(network flow problems)

    用户1621951
  • 力扣 (LeetCode)-最大子序和,JavaScript数据结构与算法(数组)

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • 数据结构 第15讲 一场说走就走的旅行——最短路径

    本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

    rainchxy
  • 算法与数据结构

    七月半夏
  • 数据结构与算法

    树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

    不作声

扫码关注云+社区

领取腾讯云代金券