一篇平平无奇的课堂笔记 内容长且无规则
普适思想
- coding style
- 考虑全面各种情况(第一步永远是边界检测)
- bug free
- 交流-思考-渐进的过程
例题:strstr
重点:不要总想着kmp算法,因为它仅仅只是一个算法
第一步库函数(int pos = haystack.find(needle);)
第二步暴力解法 (for循环嵌套)
第三步优化
递归recursion的思想
重点:使用深度优先搜索DFS实现递归==使用回溯的思想。
递归的三个要素:
第一步:定义要用递归完成的事情
第二步: 如何将问题变为子问题
第三步: 什么时候退出递归(什么时候给返回值)
使用深度优先搜索的情境or排列组合模板总结:
- 适用范围:几乎所有的搜索问题
- 需要做出的改动:1. 什么时候输出;2. 哪些情况需要跳过
- 试着举例:
- permutations/unique permutations
- combination sum/letter combination of a phone number
- palindrome partitioning
- restore ip address
例题:subsets
两种解法需要掌握:
递归实现DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void helper(vector<vector<int> >& res,
vector<int> tmp,
vector<int>& nums,
int level) {
if (level >= nums.size()) {
res.push_back(tmp);
return;
}
tmp.push_back(nums[level]);
helper(res, tmp, nums, level + 1);
tmp.pop_back();
helper(res, tmp, nums, level + 1);
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > res;
vector<int> tmp;
helper(res, tmp, nums, 0);
return res;
}考虑层序遍历求解,每次加入一个元素就扩充res的长度,直到所有元素添加完毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > res(1);
for(int i=0;i<nums.size();i++){
int cnt=res.size();
for(int j=0;j<cnt;j++){
vector<int> tmp=res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}
};二进制位运算解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int S = nums.size();
int N = 1 << S;
vector<vector<int> > res;
for (int i = 0; i < N; ++i) {
vector<int> v;
for (int j = 0; j < S; ++j)
if (i & (1 << j))
v.push_back(nums[j]);
res.push_back(v);
}
return res;
}
};
基础算法问题的 Time Complexity
O(1) 极少
O(logn) 几乎都是二分法
O(n) 遍历
O(nlogn) 一般都需要排序
O(n²) 数组、枚举、动态规划
O(n^3)数组、枚举、动态规划
O(2^n) 与组合有关的搜索
O(n!) 与排列有关的搜索
二分法binary search的思想
二分法中的循环仅仅是为了缩小范围,而不是获得结果,二分法的核心就是将答案的范围缩小。
** 比O(n)更优的时间复杂度几乎只能是O(logn)的二分法**。
T(n) = T(n/2) + O(1) = O(logn)
通过O(1)的时间把规模为n的问题变为n/2=O(logn)
通过O(n)的时间把规模为n的问题变为n/2=O(n)
recursion or Loop?
一般使用loop,因为recursion涉及到了调用栈,占用内存较大,所以recursion不是常用解决办法。但如果recursion会更简单,可以先用recursion解决。
通用的二分法模板:
- while (start + 1 < end)
- 不用start < end 或 start <= end 或start + 1 <= end 是为了防止死循环,确保在只剩最后两个数时就开始做判断
- int mid = start + (end - start)/2
- 不用(start + end)/2是为了防止溢出,因为int型最大只有2^32-1
- A[mid] == , < , >
- 不管是否可以<=或>=,都先判断三种情况,以确保条件判断正确。
- A[start] , A[end] ? target
- first-pos-of-target时先判断start;last-pos时先判断end
- start = mid
- 不使用mid + 1是为了防止死循环(极端情况只有两个数时)
- end = mid
例题:binary-search
/first-or-last-pos-of-target
/search-a-2d-matrix
/search-insert-pos
/search-in-a-infinite-sorted-array
/search-a-rotated-sorted-array
/Find-peak-element
二叉树
T(n) = 2T(n/2) + O(1) = O(n)
T(n) = 2T(n/2) + O(n) = O(nlogn)
前中后序遍历
递归方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36typedef struct BiTNode{
TElemType data;//数据
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c", T->data); /*显示结点数据,可以更改为其他对结点操作*/
PreOrderTraverse(T->lchild); /*再先序遍历左子树*/
PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/
}
/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /*中序遍历左子树*/
printf("%c", T->data); /*显示结点数据,可以更改为其他对结点操作*/
InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}
/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /*先后序遍历左子树*/
PostOrderTraverse(T->rchild); /*再后续遍历右子树*/
printf("%c", T->data); /*显示结点数据,可以更改为其他对结点操作*/
}非递归方法-利用栈进行遍历
前序
1
2
3
4
5
6
7
8
9
10栈S;
p= root;
while(p || S不空){
while(p){
访问p节点;
p的右子树入S;
p = p的左子树;
}
p = S栈顶弹出;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> S;
vector<int> v;
TreeNode* rt = root;
while(rt || S.size()){
while(rt){
S.push(rt->right);
v.push_back(rt->val);
rt=rt->left;
}
rt=S.top();S.pop();
}
return v;
}后序
1
2
3
4
5
6
7
8
9
10
11栈S;
p= root;
while(p || S不空){
while(p){
访问p节点;
p的左子树入S;
p = p的右子树;
}
p = S栈顶弹出;
}
结果序列逆序;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> S;
vector<int> v;
TreeNode* rt = root;
while(rt || S.size()){
while(rt){
S.push(rt->left);
v.push_back(rt->val);
rt=rt->right;
}
rt=S.top();S.pop();
}
reverse(v.begin(),v.end());
return v;
}中序
1
2
3
4
5
6
7
8
9
10
11栈S;
p= root;
while(p || S不空){
while(p){
p入S;
p = p的左子树;
}
p = S.top 出栈;
访问p;
p = p的右子树;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> S;
vector<int> v;
TreeNode* rt = root;
while(rt || S.size()){
while(rt){
S.push(rt);
rt=rt->left;
}
rt=S.top();S.pop();
v.push_back(rt->val);
rt=rt->right;
}
return v;
}
层次遍历(BFS-Queue)
1 | typedef struct Node{ //定义二叉链 |
maxlength/minlength of B-tree : Traverse or Divide-Conquer
分治的方法优于遍历的方法
这是因为分治不会一直传结果,而遍历会把结果当成参数传下去,造成冗余。
动态规划
链表 linked-list
声明:
1 | // |
Dummy Node
1 | ListNode* result = new ListNode(0); |
两两翻转链表
主体:
1 | while (p != NULL && p->next != NULL){ |
k个一组翻转链表
主体:
1 | for (i = 0; i < loopNum; i++){ |
全部:
1 | class Solution { |
快慢指针
删除倒数第k个节点
数组 array
声明:
1 | //type arrayname[arraysize]; |
双指针问题(Two Sum)
two sum可以用hash做,也可以用相向双指针做
three-sum/two-sum-closest 用相向双指针
partition-array 思想和快排类似,典型题可以分为两部分和三部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14while (i <= j) {
while (i <= j && a[i] < target) {
i++;
}
while (i <= j && a[j] >= target) {
j--;
}
if (i <=j) {
swap(a[i], a[j]);
i++;
j--;
}
}
return j+1;
SubArray
- best time to buy and sell stock/数飞机/Maximum Array
- prefix sum问题
Sorted Array
merge-two-sorted-array
- 一是可以开辟新空间的
- 二是存在同一个数组中的,反向比较
两个有序数组中的中位数/第k个数
一是O(m+n)的双指针寻找
二是O(logn)的二分法,两个数组的前k/2
1
2
3
4比较nums1[k/2]和nums2[k/2]的大小
小的那个数组count+k/2;
k = k - k/2;
直到取到第k个
- 数组内积(点乘)
- intersection-可以用哈希
数据结构
Queue == BFS
支持操作:O(1) push; O(1) pop; O(1) top
Stack == DFS
支持操作:O(1) push; O(1) pop; O(1) top
数据结构实现题/非递归问题(DFS问题)/单调栈问题
例题:min stack
构造一个存放最小值的栈,同步更新
例题:largest rectangle in histogram
例题:两个栈做一个队列两个队列做一个栈
HASH
实现原理,减小冲突: array+list形式;多个hash function;
rehashing很复杂所以要避免!
支持操作:O(1) insert; O(1) find; O(1) delete
构造:
1 | // 定义一个map对象 |
查找:
1 | map<int,CacheNode*>::iterator it = mp.find(key); |
删除:
1 | //迭代器刪除 |
其他基本函数:
1 | C++ maps是一种关联式容器,包含“关键字/值”对 |
Hash Table/Hash Map/Hash Set的区别是什么?
hash table支持多线程
多线程的producer/ consumer模式
LRU-cache算法
hashmap<key, DoublyListNode>;
Heap == Priority Queue
支持操作:O(logn) add; O(logn) remove; O(1) min or max
例题:ugly-number
1 | O(n) |