主要使用c++。

写代码时易错点

-要考虑到特殊输入并做相应处理，如空指针，空数组等。

题11 旋转排序数组的最小数字

二分查找 。大体思路是 维护两个指针，分别指向第一个和最后一个元素。然后找到数组中间的元素，如果这个值大于等于第一个指针指向的元素，那么该中间元素就位于数组中前面递增的部分，这样就把前面的指针指向该中间元素。如果这个中间值小于等于后面指针指向的元素，那么该中间值就位于数组中后面递增的部分，这样就把后面的指针指向中间元素。这样不管时移动哪一个指针，查找范围都会缩小为原来的一半，然后再对更新后的两个指针做新一轮的查找。最终两个指针会指向两个相邻的元素，而第二个指针正好是指向最小的元素，这就是循环结束的条件。

相关题目　旋转数组中查找一个数　logN时间

题12 矩阵中的路径

判断矩阵中是否存在一条包含某字符串所有字符的路径。
递归实现，回溯法。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项，当我们在某一步选择了其中的一个选项时，下一步又面临新的多个选项。这样重复选择直到到达最终的状态。用回溯法解决的问题的所有选项可以形象的用数状结构来表示。
程序中都要用一个和原矩阵一样大的bool矩阵visited来标记每个位置是否被访问过。

题13 机器人的运动范围

同题12。

相关题目　在0/1矩阵矩阵中的最大活动范围。

遍历每一个元素，每一个元素都可能作为起点。当然，这个时可以再优化的。

程序中都要用一个和原矩阵一样大的bool矩阵visited来标记每个位置是否被访问过。

题15 二进制中1的个数

题21 调整数组顺序使奇数位于偶数前面

不要求稳定

维护两个指针，初始化时分别指向第一个和最后一个数字，前面的指针只向后移动，后面的指针只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字为偶数，第二个指针指向的数字为奇数，则交换这两个数字。

要求稳定

用冒泡排序的思想，复杂度为O(n^2)。

void reOrderArray(vector<int> &array)
{
    for(int i = 0;i < array.size();i++)
    {
        for(int j = array.size()-1; j>i;j--)
        {
            if(array[j]%2==1&&array[j-1]%2==0)
                swap(array[j],array[j-1]);
        }
    }
}

题22 链表中倒数第k个节点

维护两个指针，让第一个指向第一节点，另一个指向第k个节点。然后两个指针同步往后走，当后面的指针走到最后一个节点时，前面的指针正好就走到了倒数第k个节点。

相关问题 求链表的中间节点

维护两个指针，同时从链表的头节点出发，一个指针每次走一步，另一个指针一次走两步，当走的快的指针走到链表的末尾时，走的慢的指针正好走到链表的中间。

题23 链表中环的入口节点

先确定链表中是否存在环，让两个指针都从头节点出发，一个一次走一步，另一个走快些，比如一次走两步，如果走的快的指针能追上走的慢的指针，那么链表中就有环，并且追上时的节点就是环中的节点。然后从这个节点出发一边往后走一遍计数，再次回到这个节点时，就计数得到环中的节点个数了。环中节点个数设为k，这时链表中环的入口节点就相当于链表尾节点，同事也是倒数第k个节点。两指针从头节点出发，快指针先走k步，然后两个同步走，当两个指针相遇时，他们便是到了环的入口节点。

题24 反转链表

思路一 用栈先进后出记住链表的顺序，比较费内存

把所有节点依次放入一个栈里。最后的节点为要返回的节点，先保存着。然后从栈里每次取出节点，使其指向栈里的下一个节点。

思路二 连续的三个为一组，从前往后走

维护三个指针，分别指向当前要处理的节点、其前一个节点、其后面一个节点，逐步往后走。记住后面一个节点，以防当前节点反转完后后面的节点找不到了。

题25 合并两个排序的链表

比较合并两个链表的头节点，使用递归

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == nullptr)   return pHead2;
        else if(pHead2==nullptr) return pHead1;
        ListNode* pMergedHead = nullptr;
        if(pHead1->val<pHead2->val)
        {
            pMergedHead=pHead1;
            pMergedHead->next=Merge(pHead1->next,pHead2);
        }
        else
        {
            pMergedHead=pHead2;
            pMergedHead->next=Merge(pHead1,pHead2->next);
        }
        return pMergedHead;
    }
};

相关题目 合并两个有序数组 参见这里的解法二和解法三

再熟悉下这个，再引申，合并n个有序数组呢

题32 从上倒下打印二叉树

题33 二叉搜索树的后序遍历序列

题34 二叉树中和为某一值的路径

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> result;
        if(root == nullptr)
            return result;
        vector<int> path;
        int currentSum = 0;
        return FindPath( root,  expectNumber, path, currentSum,result);
    }
    vector<vector<int>> FindPath(TreeNode* root, int expectedNumber,vector<int>&path,int currentSum,vector<vector<int>>& result)
    {
        currentSum += root->val;
        path.push_back(root->val);
        
        bool isLeaf = root->left == nullptr && root->right==nullptr;
        if(isLeaf && currentSum==expectedNumber)
            result.push_back(path);
        if(root->left != nullptr)
            result = FindPath(root->left,expectedNumber,path,currentSum, result);
        if(root->right != nullptr)
            result = FindPath(root->right,expectedNumber,path,currentSum, result);
        path.pop_back();
        currentSum -=root->val;
        return result;
    }
};

题38 字符串的排列

题39 数组中出现次数超过一半的数字

题40 最小的k个数

题41 数据流中的中位数，这题太难了！

书上的解法中用到了平衡二叉搜索树，太麻烦艰涩。牛客网上有用优先队列来做的，优先队列priority_queue本质也是一个堆。

class Solution {
    priority_queue<int, vector<int>, less<int> > p;
    priority_queue<int, vector<int>, greater<int> > q;
     
public:
    void Insert(int num){
        if(p.empty() || num <= p.top()) p.push(num);
        else q.push(num);
        if(p.size() == q.size() + 2) q.push(p.top()), p.pop();
        if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();
    }
    double GetMedian(){ 
      return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
    }
};

题42 连续子数组的最大和

#include<bits/stdc++.h>
using namespace std;
int FindGreatestSumOfSubArray(vector<int> array) 
{
    int curSum = 0;
    int maxSum = array[0];
    for(int i = 0;i<array.size();i++)
    {
        if(curSum<=0)
            curSum = array[i];
        else
            curSum+=array[i];
        if(curSum>maxSum)
            maxSum = curSum;
    }
    return maxSum;
}

题47 礼物的最大价值

题51 数组中的逆序对

题52 两个单向链表的第一个公共节点

首先注意，两个链表从第一个公共节点开始，之后的所有节点都是重合的，不可能再出现分叉，其拓扑形状就像一个Y，而不可能像x。

方法一 使用两个辅助栈，空间复杂度和时间复杂度都是O(m+n)

分别把连个链表的节点放入两个栈里，这样两个链表的尾节点就位于两个栈的栈顶，接下来从两个栈顶的节点开始依次比较，直到找到最后一个相同的节点。

方法二 不再使用辅助栈，时间复杂度为O(m+n)

先遍历得到两个链表的长度，得到长的链表比短的链表多几个节点。然后在较长的链表上先多走这几个节点。再接下来在两个链表上一起往后走，一直找到第一个相同的节点就是他们的第一个公共节点。

题63 股票的最大利润

题68 树中两个节点的最低公共祖先

关于递归的思路，要先想清楚第n级和第n-1级的di

c++常用语法

vector

• 两个vector相连接，比如在a后面插入b，则为a.insert(a.end(),b.begin(),b.end())
• vector赋值: vec2.assign(vec1.begin()+k,vec1.end())
• 截取vec1中的一部分：vector<int>(vec1.begin()+m,vec.begin()+n)
• vector去重

set<string> st(all_posible.begin(), all_posible.end());
all_posible.assign(st.begin(), st.end());

string

• 截取str的第pos开始的连续len个字母组成的字符串 str.sub(int pos,int len),如果第二个参数缺省，则取到最后一个字母。
• str.find(string sub, int i)返回str中第i个位置开始，第一次出现字符串sub的位置。经典例子，求字符串str中出现字符串sub的次数

int fun1(const std::string& str, const std::string& sub)
{
    int num = 0;
    for (int  i = 0; (i = str.find(sub, i)) != std::string::npos; num++, i++);
    return num;
}

• 两字符串相连想，直接str1+=str2.

set

• 用别的容器对set进行赋值：```set<string> st(all_posible.begin(), all_posible.end());

#### stack 
#### 万能头文件

include<bits/stdc++.h>

using namespace std;

## 常用的小知识点
- 错排公式：D(n)=(n-1)*[D(n-1)+D(n-2)]。[详解](https://blog.csdn.net/bengshakalakaka/article/details/83420150)