/Coding

coding能力需要每天加强练习~剑指offer~leetcode~

Primary LanguageC++

Coding

coding能力需要每天加强练习~ 剑指offer~ leetcode~

数据结构与算法

数据结构研究的是数据如何在计算机中组织和存储，使得我们可以高效地获取数据和修改数据。

我们需要根据应用场景的不同，灵活选择最合适的数据结构。

  • 线性结构

  1. 数组

  2. 链表

  3. 栈

  4. 队列

  5. 哈希表

  • 树结构

  1. 二叉树

  2. 二分搜索树

  3. 平衡二叉树 AVL

  4. 红黑树

  5. 平衡树 Treap二叉搜索树和堆合并构成的新数据结构，所以它的名字取了Tree和Heap各一半，叫做Treap。

  6. 伸展树 Splay也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。

  7. 堆

  8. 字典树 Trie：前缀树，解决毫秒级通讯录查询。

  9. 线段树 LeetCode相关线段树的问题208、611、277

  10. k-D树 K-D树是把K维空间中的点组织起来的空间划分数据结构，与四叉树不同的是，K-D树对空间的划分不是按照某种固定模式进行的，对空间的划分更有效。

  11. 并查集

  12. 哈夫曼树

  • 图结构

  1. 存储方式：邻接矩阵、邻接表

  2. 最小生成树 Minimun Span Tree：Prim算法、kruskal算法

  3. 最短路径 Shortest Path：Dijkstra算法、Bellman-Ford算法

算法面试需要熟练掌握的数据结构

数组、链表、栈、队列、堆、二分搜索树

算法竞赛需要熟练掌握的数据结构

线段树、Trie、并查集

代码量大，比较复杂的数据结构，需要掌握时间、空间与均摊复杂度分析amortized

平衡二叉树AVL、红黑树、哈希表

算法与应用

  • 排序算法

  • 寻路算法：图论算法，DFS使用栈、BFS使用队列

  • 压缩算法：哈夫曼树

  • 位运算：只有5种运算，与、或、异或、左移和右移

算法竞赛需要熟练掌握的算法

图论、计算几何、组合数学、概率以及更复杂的数据结构等。

总结

1.有成熟的时间复杂度为O(n)的算法得到数组中任意第K大数字，Partition

2.把整数右移一位和将整数除以2，在数学上是等价的，但除法的效率比位运算低的多，在实际编程中应尽可能地使用位运算代替乘除法.

3.去符号的方法：a & 0x7fffffff

TODO

  • 更多数据结构

笛卡尔树Cartesian Tree

  • 更多算法

点分治与动态点分治 点分树 Tarjan算法是由Robert Tarjan(罗伯特·塔扬,不知有几位大神读对过这个名字) 发明的求有向图中强连通分量的算法。 预备知识:有向图,强连通。

参考资料

  1. 《剑指offer》
  2. 慕课网-刘宇波老师相关课程
  3. leetcode官网
  4. 牛客网