快速排序三种实现方式

大家都知道快速排序一次后左边比标兵小，右边比标兵大。但是要注意市面上现在主要有两种快速排序：一种是标兵不动版（只在每趟最后做一次交换），一种是标兵移动版。两种效率都一样，原因在于最初的论文和《算法》书中的不一样。

力扣43 字符串相乘

https://leetcode-cn.com/problems/multiply-strings/

力扣784

https://leetcode-cn.com/problems/letter-case-permutation/

本题和1219 黄金矿工类似，属于枚举型回溯

这是2019/09/06的一篇笔记，现在补上。这是《算法》第四版中提到的，如何实现sqrt(x)，当时和文德在实验室里面一起研究了一下。今天深信服笔试又遇到了简单版的题目。

力扣456

https://leetcode-cn.com/problems/132-pattern/

力扣1219

https://leetcode-cn.com/problems/path-with-maximum-gold/

另一种回溯类型：枚举型

以前都是for循环里面递归的，但是有时候因为情况少（比如四个方向），for循环写起来反而麻烦

力扣60

https://leetcode-cn.com/problems/permutation-sequence/

这题虽然是一道回溯题，但如果只是仅仅简单的回溯一下，会超时，经过剪枝和优化可以到13%。此题可以数学优化，还是有点挑战性的。再说了，我相信很多人和我一样看到题目第一个想到的肯定是先计算出开头数字，但是写起来还是回溯…

从大佬那里学的https://zhuanlan.zhihu.com/p/93530380，再加上自己做题过程中的一些心得

模板伪代码（python看起来简洁一些）

力扣40

https://leetcode-cn.com/problems/combination-sum-ii/

无脑套回溯模板就vans了

这题能评中等，大概率是因为去重的方式吧

力扣131

https://leetcode-cn.com/problems/palindrome-partitioning/

回溯问题，一开始看到样例的结果是单个的在最后面，导致想复杂了