Category Archives: Data Structure and Algorithms
如何写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:…
三大类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…
why数据结构与算法
一个数据结构的组成(From Wikipedia) A collection of data items The relationships among them The operations that can be applied to the data structure 数据结构的Common operations(From Geeks4Geeks) Access: Get a data item in the given data structure. Search: Find a particular data item in the given data structure. Insert: Add a data item in the given data structure. Delete:…