LeetCode
LeetCode copied to clipboard
ylqi007
## Quick Select * https://leetcode.com/problems/top-k-frequent-elements/editorial/ ## Quickselect (Hoare's selection algorithm) 1. [215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) [讲解不错，算法实现简单易明白] 2. [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)
Top Frequency: Top 10 1. [314. Binary Tree Vertical Order Traversal](https://leetcode.com/problems/binary-tree-vertical-order-traversal/) [BFS] 2. [1249. Minimum Remove to Make Valid Parentheses](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/) [Stack] 1. [1963. Minimum Number of Swaps to Make the...
# Queue (队列) Queue是**线性表**的一种，在操作数据元素时，按照先进先出(First In First Out, FIFO)的规则。 **Queue的实现方式:** 队列的实现同样有两种方式：顺序存储和链式存储。两者的区别在于数据元素在物理存储结构上的不同。 1. 顺序存储 2. 链式存储 #### 1. 顺序存储 **顺序存储存在的问题:** 由于数组申请的空间有限，到某一时间点，就会出现`rear`队尾指针到了数组的最后一个存储位置，如果继续存储，由于`rear`指针无法后移，则会出错。 > 在数组中做删除数据元素的操作，只是移动了队头指针而没有释放所占空间。 顺序存储的升级版：使用数组存取数据元素时，可以将数组申请的空间想象成首尾连接的环状空间使用。 如何区分空队列和满队列的情况？办法是：牺牲掉一个存储空间 * 当队列为空时，尾指针`rear`等于头指针`front` * 当队列为满时，为指针`rear`的下一个位置等于头指针`front` #### 2. 链式存储...
杂记
如何取数组的中间值？ **Method 1** ``` middle = (left + right) / 2; ``` * 局限：(left + right) 可能会出现溢出，从而造成错误 **Method 2** ``` middle = left + (right - left)/2; ``` * 避免了溢出的情况...
排序算法
1. 冒泡排序 2. 插入排序 3. 选择排序 4. 希尔 Shell 排序 5. 快速排序 (Quick Sort) 6. 归并排序 (Merge Sort) 7. 堆排序 8. 线性排序算法 9. 自省排序 10. 间接排序 11. 计数排序 12. 基数排序...
回溯算法(backtracking)也叫试探法，它是一种系统地搜索问题解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退，换一条路再试。回溯算法其实就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达的最终状态的节点，从而减少状态空间树节点的生成。 Backtracking属于DFS。 * 普通的DFS主要用于**可达性问题**，这种问题只需要执行到特定点的位置然后返回即可。 * 而Backtracking主要用于**排列组合**问题，这种问题在执行到特定的位置之后还会继续执行求解过程。 因为Backtracking不是立即就返回，而要继续求解，因此在实现算法时，需要注意对元素的标记问题： * 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不再重复访问该元素。 * 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。 **Reference:** * [算法思想 - 回溯算法](https://pdai.tech/md/algorithm/alg-core-backtracking.html) * [五大基本算法之回溯算法 backtracking](https://juejin.cn/post/7113160186977583134) * [回溯算法几种问题的复杂度分析](https://zhuanlan.zhihu.com/p/448969860) **Template:** ``` result = [] func backtrack(选择列表,路径): if 满足结束条件:...
* [五大基本算法之貪心算法](https://juejin.cn/post/7122623403269292046)