Monthly Archives: February 2021
如何写Dijkistra与A*算法
Dijkistra’s 我们需要维护两个set： Set A: Vertices that are included in the shortest-path tree. Set B: Vertices that are not yet included in the shortest-path tree. At every step of the algorithm, 我们从set B中取走一个vertice，放到set A里。 至于取走哪个vertice, 我们将set B里的vertices进行了排序，priority就是谁离start node距离最短，就先谁。 所以最开始set A是空的，而set B是包含了所有的vertices，但是我们还不知道每个vertice到底离source node多远，于是我们就默认设置为无穷大。由于source node与自己的距离为0，所以最先从set B中取出，放到set A里。我们找到source node的adjacent nodes，由于我们知道它与它的adjacent nodes的距离，于是我们就可以将这几个nodes的（离source node多远）信息进行update，从无穷大更新到真实的。于是我们就可以从刚刚更新的几个source node的adjacent nodes中取个最小的，进行新一轮的计算。即找到最新取出的这个node U的adjacent nodes, 然后对于将U的邻近node，我们计算一下node U到source node的距离+node…
Coding interview的patterns
[latexpage]本文基于 [1] Grokking the Coding Interview: Patterns for Coding Questions [2] The Ultimate Strategy to Preparing for the Coding Interview 如何解决算法问题的5个步骤How To Approach Any Algorithm Interview Without Panicking： Step 1: Rephrase the problem in your own words Step 2: Input and output types Step 3: Examples and Edge Cases Step 4: Data Structure(s) Step 5:…
Complete Coverage Path Planning(CCPP)算法总结
本文参考一下论文 On Complete Coverage Path Planning Algorithms for Non-holonomic Mobile Robots: Survey and Challenges.” Journal of Information Science & Engineering, 2017 CCPP can be achieved by using single-robot(单个机器人) or multi-robot(多个机器人) coverage according to the size of the environments. Single-robot coverage is suitable for the coverage task in small environments such as homes, workplaces, and restaurants because…
英语语法体系
本文内容和截图全部来自youtube博主英语兔的两期节目： 一个视频说清整个英语语法体系(重塑你的语法认知框架) 非谓语动词详解: 不定式, 动名词, 现在分词, 过去分词 英语的语法体系都是围绕动词来的。英语的五类基本句型其实都是在说动词，以及动词需要几个对象才能完整表达意思。五类谓语动词分别对应了五类基本句型，分别为 可以独立完成的动作(因而不需要宾语，0位动作的承受者) 不及物动词(intransitive verb) 对应该类谓语动词基本句型：主语+(不及物)动词 例句：Papa rabbit sleeps.(sleep这个动词不需要有动作的承受者) 只有一位动作的承受者 单及物动词(monotransitive verb) 对应该类谓语动词的句型：主语+(单及物)动词+宾语 例句：Papa rabbit likes you.(you是那位动作的承受者) 有两位动作的承受者 双及物动词(ditransitive verb) 对应该类谓语动词的句型：主语+(双及物)动词+间接宾语(indirect object)+直接动词(direct object) 例句：Papa rabbit teaches you English 只有一位动作的承受者，但与第二种动词不同 复杂及物动词(complex-transitive verb) 对应该类谓语动词的句型：主语+(复杂及物)动词+宾语+宾语补语(object complement) 例句：Papa rabbit considers you smart. (如果去掉宾语补语smart, 句子意思不完整) 用于把信息赋予主语的(连)系动词(不是一个动作) (连)系动词(linking verb) 对应该类谓语动词的句型：主语+(系)动词+主语补语(表语) 例句： Papa rabbit is tall. 所以在这里，我们总结说英语的结构都是“主语+谓语”，即主语以外的余下句子部分都是谓语，谓语动词只是谓语的一部分，所以谓语动词就是谓语中的动词。…
三大类CS算法的总结
根据我们之前的post–why数据结构与算法中写道 基于用途对算法分类(参考Princeton CS算法课程)： Sorting algorithmSearching algorithmGraph algorithm Recursive and iterative algorithm的区别 Both repeatedly execute the set of instructions. 通常我们尽量避免使用recursion, 而更倾向于使用iteration。 Recursion: when a statement in a function calls itself repeatedly. 格式: 总共有2 parts. A base case: The base case defines the termination condition. The general recursive case: The general case where it calls itself. Infinite…