动态规划与最短路径算法
最近在leetcode看到了一道题,很有意思,可以用动态规划解,也可以用Dijkstra算法来解,这道题最大的启发就是:
动态规划的每个节点就是图中的节点,状态转移方程其实就是两个节点之间的连线,我们可以用Dijkstra算法求解从开始节点到目标结点的最短路径。
白话Docker容器基础
最近在极客时间上买了一个关于K8S的课程,第一个部分讲的是Docker容器的基本原理,简单总结一下。
如何将解决vditor中katex未定义的问题
最近在项目中使用了vditor但是它的数学公式,流程图,脑图等都没法用,看了它的源码后,找到了解决方案,这里记录下。
使用Eva+MatterJS实现一个2D版推金币Demo
最近拼多多的推金币比较火,就尝试想用一下2D的游戏引擎试一下效果,做了一个简单的Demo。
引擎选择的是Eva,采用这个引擎是因为它基于ECS的微内核架构,让扩展非常方便,同时也提供了几个官方的插件,足以支持大部分需求,它的渲染引擎插件是基于PixiJS,物理引擎插件是基于MatterJS,它的插件所依赖的版本比较低了,对于我来说还够用,如果有需要完全可以自己实现。
Floyd-Warshall 多源最短路径算法
单源最短路径算法和多源最短路径算法的区别在于它们解决的问题不同。
单源最短路径算法是指在给定一个起点,计算该起点到图中其他所有顶点的最短路径。其中最著名的算法是Dijkstra算法和Bellman-Ford算法。Dijkstra算法适用于有向图中没有负权边的情况,而Bellman-Ford算法可以处理有负权边的情况。
多源最短路径算法是指计算图中任意两个顶点之间的最短路径。其中最著名的算法是Floyd-Warshall算法。Floyd-Warshall算法通过动态规划的方式计算任意两个顶点之间的最短路径,可以处理有向图和负权边的情况。
总结起来,单源最短路径算法解决的是从一个起点到其他所有顶点的最短路径问题,而多源最短路径算法解决的是任意两个顶点之间的最短路径问题。
Bellman-Ford算法
贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离,是一种单源最短路径算法,支持存在负权重的情况
计算二叉树堂兄弟节点的和
这是一道leetcode的中等难度的题目,代码不算复杂,但还是有一点可以记录下来举一反三。
贪心算法:不要同时贪多个维度
最近在通过《代码随想录》训练关于贪心算法方面的题目,有了一个新的心得体会,在这里摘抄一下,就是,如果一道题目有多个维度,那先不要上来就尝试在多个维度同时做贪心,那大概率会让给自己的思路陷入混乱。
从几个贪心算法的问题体会如何通过问题等价来简化问题
算法学习的路线,个人体验,首先是学习基本的数据结构和算法,通晓每种数据结构适合存储什么类型的信息,然后了解通用的算法思想,比如贪心,双指针,单调栈,回溯等。第三步就是学会抽象,或者说等价,将具体的问题等价为简单的问题,然后用通用的算法去解决。第四步,就是有的算法只存在理论上的可行性,实际由于各种原因,如何去工程上的近似,或者有些问题不存在理论上的解法,只存在工程上的解法。
基本的数据结构,其实就是栈,队列,数组,链表,哈希,树,图之类的,其他的复杂数据结构都是再基本数据结构基础上组合出来的,比如跳表。
这次我们就从几个贪心算法体验问题等价能够带来的问题简化。