算法
快速排序
void quickSort(int arr[], int low, int high)
{
if (low < high){ //low == high就直接结束了
int pi = partition(arr, low, high); //先用partition得到pivot的index
quickSort(arr, low, pi - 1); //分治法, 两边各自快排
quickSort(arr, pi + 1, high);
}
}
int partition(int arr[], int low, int high) //闭区间
{
int pivot = arr[high]; //选最后一个元素作为中枢元素pivot
int ptr = low;
//从low到high-1扫一遍, 把<=pivot的放前面
for (int i = low; i <= high - 1; ++i)
if (arr[i] < pivot){
swap(&arr[i], &arr[ptr]);
++ptr;
//刚开始可能存在i = ptr的情况, 即自己和自己交换
}
swap(&arr[ptr], &arr[high]); //最后把pivot放到中间位置
return ptr; //返回的是pivot的index
}
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
修改于GeeksforGeeks (源程序有很多不足之处)。注意再有些书上(如剑指offer)，会判断是否i == ptr，这是为了减少自我swap来提高性能；然而这样却在大规模数据上不合适，因为每扫一个元素都要进行一次判定。
以下是另一个版本：
public void quicksort(int[] v, int left, int right){
//如果left >= right, 整个if语句都不会执行
if(left < right){
int key = v[left]; //好像叫中枢元素
int low = left;
int high = right;
while(low < high){
while(low < high && v[high] > key)
--high;// 效率高
//找到了第一个比key小的元素index
if(low < high)
//注意到可能是因为low == high 导致的while终止
v[low++] = v[high];
while(low < high && v[low] < key)
++low;
if(low < high)
v[high--] = v[low];
}//每次循环后都是a[low]占坑
v[low] = key;
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}
快速排序是不稳定的：如序列5 3 3 4 3 8 9 10 11，第一轮while循环中，中枢元素5和3(第5个元素)交换就会把元素3的稳定性打乱，不稳定发生在中枢元素和a[j]交换的时刻。
堆/堆排序
堆的逻辑结构是完全二叉树，但是是存在数组中。堆的建立(从一堆数据中进行建立)、插入、删除，利用堆进行堆排序见这里。
堆获取最大元素复杂度为O(1)，插入和删除复杂度为O(log n)(其实就是堆调整)。
堆的应用
- Top K问题：即从海量数据中查找最大的K个元素，堆的插入是
log(n)复杂度，所以比直接插入要好，更多见这里； - 第K大的元素/中位数：中位数就是第
size() + 1 /2大的元素(size()为奇数情况下)，具体参见这里。
C++ STL中set和multiset都是基于红黑树实现的，优先级队列？
快速幂
计算$x^n$，这里只考虑$n>0, x\neq 0$。快速幂算法是考虑了拆解指数，$n=a_0+a_12^1+a_22^2\cdots, a_i\in\{0,1\}$，这里的$a_i$就是$n$的二进制的每一位。令$base(i)=x^{2^i}$，有$base(i+1) = base(i)\cdot base(i)$。
double poww(double x,int n){
int res = 1, base = x;
while(n != 0){
if(n & 1 != 0)
res *= base;
base *= base;
n >>= 1; //右移赋值
}
return res;
}
二分查找
参考知乎
Key Observation
假设输入样例是2, 3, 3, 3, 6，目标为3。
2个关键点：上取整还是下取；不断夹逼，永远保证闭区间[l, r]里包含目标值target。
查不到返回什么？对于无重复元素情况，一般就会让返回恰好比它大的index；对于有重复元素的情况，可能就最多让返回-1了，所以不用太纠结。
判定条件lo < hi和lo <= hi的区别：对于无重复元素情况，只是出口不同，如果使用lo < hi，最后需要多一行if (a[lo] == target)，所以建议一律用lo <= hi，目的是少些一点代码；对于有重复元素情况，因为注意到更新方式里有hi = mid，必须用lo < hi，否则会死循环。同理，最后需要多判断一个if (a[lo] == target)。
所有的情况都是return lo;
无重复元素 返回目标的index, 否则返回恰好比目标大的index。
int binarySearchInsert(const vector<int>& a, int target) {
int low = 0, high = a.size() - 1;
while(low <= high){ //这时候出口判定就是lo > hi
int mid = low + ((high - low) >> 1); //用加法可能会溢出哦
if (a[mid] == target) return mid;
else if (a[mid] > target) high = mid - 1;
else low = mid + 1;
}
return low; //也可以return -1;
}//注意, 如果target大于所有元素, 那么最后low = a.length, 小心越界
假设最后只剩两个元素[2, 4]，则mid = low = 0, high = 1
- 如果查找
1，跳出循环时high = mid - 1 = -1； - 如果查找
2，跳出循环时low = mid = 0； - 如果查找
3，跳出循环时low = high = 1； - 如果查找
4，跳出循环时low = high = 1； - 如果查找
5，跳出循环时low = high = 1； - TBD
int binarySearchInsert(const vector<int>& a, int target) {
int low = 0, high = a.size() - 1;
while(low < high){ //这时候出口判定就是low == high
int mid = low + ((high - low) >> 1); //用加法可能会溢出哦
if (a[mid] == target) return mid;
else if (a[mid] > target) high = mid - 1;
else low = mid + 1;
}
return low;
}
有重复元素
- 求最小的i，使得
a[i] = key；若不存在，则返回-1
int binarySearchLow(vector<int> a, int target)
{
int mid, lo = 0, hi = a.size() - 1;//闭区间 [0, n - 1]
while (lo < hi){ //注意思考, 这种做法不会死循环; 出口条件是l==r
mid = lo + ((hi - low) >> 1); //注意, 移位必须加括号
//如, 0, 1取0; 0, 1, 2取1
if (a[mid] < target) lo = mid + 1;
//因为a[mid]肯定不等于key了, 所以lo = mid + 1; 并且防止死循环
else hi = mid; //可能会丢掉右边一部分3, 无所谓
}
if (a[lo] == target) return lo;
return -1;
}
- 求最大的i，使得
a[i] = key；若不存在，则返回-1
int binarySearchHigh(vector<int> a, int target)
{
int mid, lo = 0, hi = a.size() - 1;//闭区间[0, n - 1]
while (lo < hi){
mid = lo + ((hi - lo + 1) >> 1); //上取整
if (a[mid] <= target) lo = mid;
//可能会丢掉左边一部分3, 无所谓
else hi = mid - 1;
}
if (a[lo] == target) return lo;
return -1;
}
- 求最小的i，使得
a[i] > key，若不存在，则返回-1 (待定修改)
int binary_search_3(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//闭区间[0, n - 1]
while (l < r){
m = l + ((r - l) >> 1);//向下取整
if (a[m] <= key) l = m + 1;
//和1的区别就是a[m] <= key, 把a[m]也从区间去除
else r = m;
}
if (a[r] > key) return r;
return -1;
}
- 求最大的i，使得
a[i] < key，若不存在，则返回-1
int binary_search_4(int a[], int n, int key)
{
int m, l = 0, r = n - 1;//闭区间[0, n - 1]
while (l < r){
m = l + ((r + 1 - l) >> 1);//向上取整
if (a[m] < key) l = m;
else r = m - 1;
}
if (a[l] < key) return l;
return -1;
}
位运算
计算机一般用补码来存储数字，正数a的补码和原码相同，负数b的补码是|b|(|b|>0)的原码所有位取反，再加一。
1的原码 0000...0001
-1的原码 1000...0001
1的补码 0000...0001
-1的补码 1111...1111
二叉树遍历
参考这里。
中序遍历
void inOrder1(Node* root){ //递归版
if (root){
inOrder(root->left);
cout << root-> val << " ";
inOrder(root->right);
}
}
void inOrder2(Node* root){ //递归版
stack<Node*> s;
Node* p = root;
while (p or !s.empty()){
while (p){
s.push(p);
p = p->left;
}
if (!s.empty()){
p = s.top();
cout << p->val; << " ";
p = p->right;
}
}
}
Topics
Array 98, Dynamic Programming 80, String 78, Math 74, Hash Table 65,Tree 64, Depth-first Search 55, Binary Search 39, Two Pointers 37, Backtracking 35, Design 32, Stack 29, Breadth-first Search 28, Linked List 27, Bit Manipulation 26
先把题目解出来，再想有没有更优化的方法
不要图简洁把if判断的条件加在for循环里，因为这样会中止循环。
Sum问题
1. Two Sum(simple two sum) 使用HashMap，此外还有Sorted Two Sum，其思想在3 Sum和4 Sum里面会用到, 参考Sum系列)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//sort(nums.begin(), nums.end());
map<int, int> a;
for (int i = 0; i < nums.size(); i++){
if (a.find(target - nums[i]) != a.end())
return vector<int> {i, a[target - nums[i]]};
else
a.insert(make_pair(nums[i], i));
}
}
};
15. 3 Sum 注意本题要输出不重复的三元组，主要思路是固定i，然后剩下的用Sorted Two Sum思路做(lo和hi在[i+1, length-1]区间上往中间靠)'；此外去重可以考虑用set。
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> res;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); ++k) {
if (nums[k] > 0) break;
int target = 0 - nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res.insert({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else --j;
}
}
return vector<vector<int>>(res.begin(), res.end());
}
Remove Duplicates
26. Remove Duplicates from Sorted Array 此题和27. Remove Element类似；易错点，当平移下标identifer时，注意使用短路机制防止其越界。
//找到第一个不等于val的下标
int id = a.length - 1;
while (id >= 0 && a[id] == val) id--;
//如果不加id>=0, 可能会出现a[-1]的情况
80. Remove Duplicates from Sorted Array II: 设置两个index，一个用来遍历数组，一个用来记录当前需要移除的元素的位置。
二分查找问题
二分查找问题都是通过每一轮循环，把闭区间减少一半的做法来减少范围。
33. Search in Rotated Sorted Array 注意， 最终的循环一定会落在一个递增序闭区间上面来查找，所以只要把case2和case3转化为case1即可，参考这里
public int search(int[] a, int target) {
if (a.length == 0) return -1;
int lo = 0, mid = 0, hi = a.length - 1;
while (lo <= hi){
mid = (hi - lo) / 2 + lo;
if (a[lo] <= a[mid] && a[hi] < a[lo]){ //Case 2
if (a[lo] <= target && target <= a[mid]) hi = mid;
else lo = mid + 1;
}
else if (a[mid] < a[hi] && a[hi] < a[lo]){ //Case 3
if (a[mid] <= target && target <= a[hi]) lo = mid;
else hi = mid - 1;
}
else break; //Case 1
}
//Binary Search
while (lo <= hi){
mid = (hi - lo) / 2 + lo;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
74. Search a 2D Matrix 这题非常考验二分查找的基本功，首先对第一列的元素二分插入查找，找到元素所在的行；在对那一行进行二分查找(找不到return false即可)。
回溯问题
79. Word Search 经典题 (剑指offer 12)，给一个字符矩阵，判断其内部是否存在一条包含某字符串的路径。这里的关键在于设计一个从矩阵某个点开始寻找剩余子串的递归函数。
bool exist(vector<vector<char>>& board, string word) {
if (board.size() < 1 || board[0].size() < 1)
return false;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if(search_here(board, word, i, j, 0))
return true;
return false;
}
bool search_here(vector<vector<char>>& board, string& word, int i, int j, int ptr){
if (i >= board.size() || i < 0 || j >= board[0].size() || j < 0 //角标越界时
|| word[ptr] != board[i][j] || ptr >= word.size()) //当前位置char不匹配时
return false;
if (ptr == word.size() - 1) //此时, char肯定匹配, 而又恰好是最后一个字符
return true;
//不是最后一个字符? 接着往下递归查找
char tmp = board[i][j];
board[i][j] = '$'; //设置一个奇怪的字符, 当bool矩阵用了
if (search_here(board, word, i + 1, j, ptr + 1) ||
search_here(board, word, i, j + 1, ptr + 1) ||
search_here(board, word, i - 1, j, ptr + 1) ||
search_here(board, word, i, j - 1, ptr + 1))
return true;//只要有一个路径匹配即可
board[i][j] = tmp;
return false; //确实找不到可行路径
}
46. Permutations 经典题，求不带重复元素的全排列
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, 0, result);
return result;
}
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result) {
if (begin == num.size()) {
result.push_back(num);
return;
}
for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
swap(num[begin], num[i]);
//需要reset, 这样permuteRecursive就不会把nums弄乱, 在每一层递归时都是顺序完好的
}
}
47. Permutations 经典题，求带重复元素的全排列
void permuteRecursiveUnique(vector<int>& num, int begin, vector<vector<int> > &res) {
if (begin == num.size()) {
res.push_back(num);
return;
}
for (int i = begin; i < num.size(); i++) {
if (i != begin && num[i] == num[begin]) continue;
swap(num[i], num[begin]);
recursion(num, i + 1, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
permuteRecursiveUnique(num, 0, res);
return res;
}
40. combination sum II 给定有重复元素的数组C，找到C所有子序列T，使得T里的元素之和为target，每个元素只能用一次(元素本身可以重复)；I和II的区别是，I数组里没有重复的数，但一个数可以用多次；II数组里有重复，一个数只能用一次；I和II都要求返回结果中没有重复的解，且每个解中的数都按非递减排好序。
思路：对注意到结果可以按照头元素不同分成几，所以可以利用回溯法。
public static List<List<Integer>> combinationSum2(int[] a, int target) {
Arrays.sort(a); //注意, 先对原数组进行排序; 无重复的版本可以不用排序
List<List<Integer>> res = new LinkedList<>();
List<Integer> tmp = new LinkedList<>();
back(res, a, tmp, target, 0);
return res;
}
public static void back(List<List<Integer>> res, int[] a, List<Integer> tmp, int target, int start){
// 第i次递归调用back函数, 是在决定T的第i个元素
if (target < 0)
return;
else if (target == 0)
res.add(new LinkedList<>(tmp));
else{
for (int i = start; i < a.length; i++){
if (i > start && a[i] == a[i-1])
continue;
//每一轮循环, 进入tmp的第一个元素都不同, 保证了本次递归的结果的不重复性
tmp.add(a[i]);
back(res, a, tmp, target - a[i], i + 1); //只能用一次
tmp.remove(tmp.size() - 1); //每轮次循环都要清空当前递归给tmp添加的元素
}
}
}
78. Subsets 给定无重复元素的列表，输出所有子集；和前一题相似，本题也是采用回溯法。
public List<List<Integer>> subsets(int[] a) {
List<List<Integer>> res = new LinkedList<>();
back(res, new LinkedList<>(), a, 0);
return res;
}
public static void back(List<List<Integer>> res, List<Integer> tmp, int[] a, int start){
for (int i = start; i <= a.length; i++){
if (i == a.length){
res.add(new LinkedList<>(tmp));
return;
}
tmp.add(a[i]);
back(res, tmp, a, i + 1);
tmp.remove(tmp.size() - 1);
}
}
子串问题
3. Longest Substring Without Repeating Characters
int lengthOfLongestSubstring(string s) {
if (s.size() <= 1)
return s.size();
unordered_map<char, int> m;
int curr_len = 0, max_len = 0;
for (int i = 0; i < s.size(); i++){
if (m.find(s[i]) == m.end() or (i - m[s[i]]) > curr_len)
curr_len++;
else{
curr_len = i - m[s[i]];
}
max_len = (max_len < curr_len) ? curr_len : max_len;
m[s[i]] = i;
}
return max_len;
}
lintcode 32 最小窗口字符串 参考这里
正则表达式
问题说明参考这里，注意这里应str和pattern全部匹配。基本思路如下：
在*s != '\0'并*p != '\0'的情况下
- 如果
*(p + 1) == '*'(case 1) - 如果
*s == *p：s不移动，p移动两位(不匹配s，用掉此匹配) ||s移动一位，p移动两位(匹配s，用掉此匹配) ||s移动一位，p不移动(匹配s，不用掉此匹配) - 如果
*p == '.'：同上 (case 2) - 如果
*s != *p：只能p移动两位 *s == *p或者*p = '.'：s和p都移动一位
下面考虑s和p里有一个为'\0'的情况
*s == '\0' and *p == '\0'happy*s != '\0' and *p == '\0'gg*s == '\0' and *p != '\0'如果*p == '*'，那么就看*(s - 1)和*(p - 1)的关系了，此情况可以合并在(case 1)中。(可以考虑样例s = "",t = ".")
后序表达式
将中序表达式A+B转化为后序/逆波兰表达式/Reverse Polish Notation，有利于计算机处理表达式的求值，因为其去除了优先级高低的考虑。其主要包含两个部分：1) 中序转化为后续；2) 后序如何求值，具体参考CSDN和Wiki。
Last updated on Jun 19, 2019.