刷题笔记

易忘点

c++基本数据类型及其宏定义

创建对象的几种方式

//显式创建
//会创建一个临时对象，然后将临时对象复制到person中，并丢弃临时对象。此时，将为临时对象调用析构函数
Person person = Person("ker",23);
//隐式调用
//与上面一样，只是换一种格式
Person person("ker",23);
//使用默认构造函数显式调用
Person person = Person();
//使用默认构造函数隐式调用
Person person;

//上面的方式都是得到的对象，创建时会生成临时对象，空间分配在栈中
//使用new关键字是会调用malloc在堆中分配空间，需要我们自己释放
Person* person = new Person("ker",123);
//用了new一定记得delete
delete person;

vector的操作

1. size()
2. front(), back()
3. push_back(), emplace_back()
4. erase(iterator), 例如：myvector.erase (myvector.begin()+5);
5. pop_back()

string的常用操作

1. []
2. append() //添加string
3. push_back()//添加char
4. std::stoi()//转化成int
5. std::to_string(。。。)//其他转化成string
6. erase()//删除
7. +=
9. sutstr(a,b)。取子串，a为子串起始位置，b为子串长度，b可以为空，则默认取到字符串末尾。

priority_queue的操作

1. 构造

   priority_queue<typename,container<typename>,compare<typename> queue(it.begin(),it.end())
   priority_queue<Type, Container, Functional>
   //例如
   priority_queue<MyStruct,vector<MyStruct>,less<MyStruct>> queue(it.begin(),it.end())
   
   //对于compare，可以用自己的比较方式，有两种方法
   //对于自己构建的类，比如MyStruct，可以在MyStruct中overload操作符<，相当于less<MyStruct>中less会调用MyStruct操作符<来进行比较
   //注意这两个const一定不能少，少了就不对了
   bool operator< (const MyStruct& s) const{
   	
   }
   priority_queue<MyStruct> queue;
   //也可以自己构建一个compare类（function-like class），这个类需要覆写operator（）来实现比较
   class cmp{
       bool operator()(MyStruct s1,MyStruct s2){
           return s1.time<s2.time;
       }
   }
   priority_queue<MyStruct,vector<MyStruct>,cmp> queue;

2. 基本操作

   queue.emplace(...);
   queue.top();
   queue.pop();
   queue.push();
   queue.size();

杂项

1. pop()并不会返回top值。
2. multiset和multimap的erase(obj)函数会擦除所有找到的，只有使用erase(iterator it)才会擦除指定的一个
3. sort默认是从小到大排序，priority_queue默认是从大到小排序。
4. 对于一个类，如果自己实现了构造函数，则编译器不会再自动添加无参构造函数了，必须自己显式声明
5. static函数（成员）不能加const
6. vector初始化时指定了大小后，再用push_back()会加到长度之外，记得用[]访问修改

一些常用函数

1. std::stoi(string str)：字符串转int

2. std::reverse(iterator begin,iterator end)：反转，可以用来反转字符串

3. #include isalnum(int c); 判断输入是否字符是数字或者大小写字母

4. 初始化二维vector(r*c,初始值为0）：

   vector<vector<int> > newOne(r, vector<int>(c, 0));

5. sort使用自定义逻辑

   //自定义函数，下面是比较int的，返回bool值，true为前者小于后者，false为前者大于等于后者
   bool myfun(int a,int b) {return a<b;}
   
   sort(arr.begin(),arr.end(),myfun)

6. 整数除法向上取整

   int a = 11;
   int b = 2;
   int c = (a+b-1)/b;		//6
   c = ceil(a/b);			//5
   c = ceil((double)a/b);	//6

循环用快慢指针

1. 看到判断是否有循环，就可以考虑快慢指针

2. 判断循环的入口，考虑用数学思维。（142. 环形链表）

   面试题 02.07. 链表相交 也考虑用数学规律

3. 不只有链表，(202. 快乐数)也可以用快慢指针，需要判断循环点是什么。

几数之和

1. 如果要求是几个数的下标，则不能排序，这需要用map或set记录。（1. 两数之和）
2. 如果只是需要数的值，，则可以用排序，这时候考虑双指针。其他指针固定，两个指针动。（ 第15题. 三数之和，第18题. 四数之和）

单调队列

1. 239.滑动窗口最大值题，维护一个单调队列，队头的值一直为最大值，并单调递减，队列中不存在位置在队头前的数，

二叉树

遍历

1. 迭代式遍历，一个节点一开始放进去并不会读取，只是用来加入其它的节点，并在该节点上方加一个标记(nullptr)，第二次读到的时候从栈中弹出。如下是中序遍历，其它遍历只需要变更顺序就好了

class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr){
            return res;
        }
        stack<TreeNode*> stack;
        stack.push(root);
        while (!stack.empty()){
            TreeNode* cur = stack.top();
            stack.pop();
            if (cur == nullptr){
                TreeNode* n = stack.top();
                stack.pop();
                res.push_back(n->val);
            }else{
                if (cur->right != nullptr){
                    stack.push(cur->right);
                }
                stack.push(cur);
                stack.push(nullptr);
                if (cur->left != nullptr){
                    stack.push(cur->left);
                }
            }
        }
        return res;
    } 
};

2. 层序遍历模板，用一个队列

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root==nullptr){
            return res;
        }
        queue<TreeNode*> queue;
        queue.push(root);
        vector<int> temp;
        while (!queue.empty()){
            temp = vector<int>();
            //相当于遍历当前层
            int size = queue.size();
            for (int i=0;i<size;++i){
                TreeNode* cur = queue.front();
                queue.pop();
                //在这里进行操作，根据题目意思来
                temp.push_back(cur->val);
                //把下一层节点添加进去
                if (cur->left!=nullptr){
                    queue.push(cur->left);
                }
                if (cur->right!=nullptr){
                    queue.push(cur->right);
                }
            }
            res.push_back(temp);
        }
        return res;
    }

二叉搜索树

1. 特征：左子树小，右子树大，相当于二分法，log时间复杂度，中序遍历为递增序列。
2. 98.验证二叉搜索树，中，注意陷阱，不能只用root比较left和right，否则left的right可能比left的root大，就不合理。可以用中序遍历的思想，用一个全局变量记录pre，永远比pre大就行。
3. 利用中序遍历有序的性质的题：98，530,501

最近公共祖先

1. LeetCode236. 二叉树的最近公共祖先。使用后序遍历，如果左子树和右子树都有目标节点，说明当前节点就是最近公共祖先，就返回，如果只有一边有，就返回一边的，如果都没有，就返回null。
2. LeetCode235. 二叉搜索树的最近公共祖先。二叉搜索树有一个特性，最近公共祖先的祖先肯定数值范围在目标范围之外（因为公共祖先所在的树肯定只是一边，就都比它小或者大，就不会在范围之间），所以从上往下找，只要在范围之间就是最近公共祖先。

修改

1. 701.二叉搜索树中的插入操作。插入只需要用前序遍历，一直找到一个合适的叶子节点的位置插入就行。
2. 450.删除二叉搜索树中的节点考虑用递归的方式，前序遍历，每次递归返回当前树的头结点，把左子树加到右子树的最左节点上。
3. 669. 修剪二叉搜索树同上一题类似，并且可以利用有序性，一次性直接舍去左子树/右子树。

回溯

1. 回溯模板

2. 对于组合问题，为了避免重复，可以考虑使用startindex，即之后的遍历都从当前index（或者index+1，区别在能不能重复使用）开始，前面的就不用了，就能避免重复。典型问题有77.组合 、216.组合总和III和39.组合总和

3. 当候选列表中有重复元素时，为了避免选出的组合重复，需要在树的同一层选择的时候进行去重（比如先对数组排序，然后同一层与前一个元素相同就跳过），也即在一次选择中不选相同的，每次选择都这样就能避免选出相同的组合。比如40.数组总和II

   //同一层的选择遍历
   for (int i=index;i<candidates.size();++i){
   	//跳过相同的元素，candidates是有序的。
   	//注意：是大于index而不是大于0，这样才是在比较同一层元素
   	if (i > index&&candidates[i]==candidates[i-1]){
   		continue;
   	}
   	//常规回溯流程
   	temp.push_back(candidates[i]);
   	backTrack(candidates,sum+candidates[i],i+1,temp);
   	temp.pop_back();
   }

4. 与组合问题不同，131.分割回文串和93.复原IP地址等题目，每一次的（一层中）的选择不是选择哪一个，而是选择多少个（连续的），所以需要转化思路，每一层的选择是选择连续多少个。

   //131题部分节选
   for (int i=index;i<s.size();++i){
       //并不pop，因为是要选择连续多少个
   	temp.push_back(s[i]);
       //符合条件就加入
   	if (isTarget(temp)){
   		ve.emplace_back(temp);
   		backTrack(s,i+1,ve,len+temp.size());
   		ve.pop_back();
   	}
   }

贪心算法

1. 在135.分发糖果中，对于局部既需要考虑左侧又需要考虑右侧时，可以考虑先只考虑与左侧比（从前往后遍历），再考虑与右侧比（从后往前遍历），分开考虑。821.字符串的最短距离也是这种思路。
2. 在134.加油站中，先考虑整体是否能够走完（用一个变量累加全局，要是是负数说明走不完），然后再全局能走完的情况下，思考起点。对于起点，如果(i,j)区间内的累加值为负数，则起点可能不在其中，就可以从j+1开始考虑。
3. 在942. 增减字符串匹配中，不用使用回溯算法，直接每次选可选的最大的或者最小的就行。

不会做的题

1. 190.颠倒二进制位

2. 96.不同的二叉搜索树用动态规划，只用考虑形状

3. 812. 最大三角形面积根据数学知识，三角形面积等于两条边向量叉乘/2.