剑指 Offer 03. 数组中重复的数字

class Solution {
public:
    std::set<int> s;
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            pair<set<int>::iterator,bool> p = s.insert(nums[i]);// 注意s.insert的返回值
            if(p.second==false) return nums[i];
        }
        return -1;
    }
};
// 时间复杂度: O(n), 空间复杂度: O(n)
// set方法，插入重复元素判断返回值是否为fasle，进而返回重复元素

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            while(nums[i]!=i){
                if(nums[nums[i]]==nums[i]) return nums[i];
                swap(nums[i],nums[nums[i]]);
            }
        }
        return -1;
    }
};
// 时间复杂度: O(n), 空间复杂度: O(1)
// 但是会改原数组

剑指 Offer 04. 二维数组中的查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) return false;
        //行、列 从0开始
        int rows =matrix.size()-1;
        int clos = matrix[0].size()-1;
        int i=0;
        while(clos>=0&&i<=rows){
            if(matrix[i][clos]==target) return true;
            else if(matrix[i][clos] < target) i++;
            else clos--;
        }
        return false;
    }
};
// 时间复杂度: O(n+m) 空间复杂度: O(1)
//右上角开始，比当前值小，移动到左边一列，比当前大，移动到下一行

剑指 Offer 05. 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for(auto c:s){
            if(c==' ') res+="%20";
            else res+=c;
        }
        return res;
    }
};
//时间复杂度: O(n) 空间复杂度: O(n)

剑指 Offer 06. 从尾到头打印链表

// 思路   依次入栈，出栈即反转
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        stack<int> s;
        while(head!=NULL){
            s.push(head->val);
            head=head->next;
        }
        //出栈
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};
//时间复杂度: O(n) 空间复杂度: O(n)

//思路 遍历链表将数据存入数组中，再反转数组
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        while(head!=NULL){
            res.push_back(head->val);
            head=head->next;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
//时间复杂度: O(n) 空间复杂度: O(n)

// 思路： 反转整个链表  背过反转模板
class Solution {
public:
    //反转链表模板  O(n)
    ListNode * reverseList(ListNode *head){
         if(head== NULL || head ->next == NULL) return head; //如果为空，则返回
        ListNode *p = head;
        ListNode* q = head->next;
        while(q){
            ListNode *tmp = q->next;
            q->next = p;
            p=q;
            q=tmp;
        }
        head->next =NULL;
        return p;
    }
    //打印
    vector<int> reversePrint(ListNode* head) {
       ListNode* p =  reverseList(head);
       while(p){
           res.push_back(p->val);
           p=p->next;
       }
       return res;
    }
private:
    vector<int> res;    
};

剑指 Offer 07. 重建二叉树

class Solution {
public:
    unordered_map<int,int> pos;//用以存储中序遍历中数字x的位置，这样可以使用O(1) 的时间查找
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<inorder.size();i++){
            pos[inorder[i]] = i;
        }
        return dfs(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* dfs(vector<int> &preorder,vector<int> & inorder,int pl,int pr,int il,int ir){
        if(pl>pr) return NULL;
        TreeNode *root = new TreeNode(preorder[pl]);
        int k = pos[preorder[pl]];
        root->left = dfs(preorder,inorder,pl+1,pl+k-il,il,k-1);
        root->right = dfs(preorder,inorder,pl+k-il+1,pr,k+1,ir);
        return root;
    }
};
//时间复杂度 O(n)

剑指 Offer 09. 用两个栈实现队列

class CQueue {
public:
stack<int> s1,s2;
    CQueue() {


    }

    void appendTail(int value) {
        if(s1.empty()) s1.push(value);
        else {
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
            s1.push(value);
            while(!s2.empty()){
                s1.push(s2.top());
                s2.pop();
            }
        }
    }

    int deleteHead() {
        if(s1.empty()) return -1;
        int x =s1.top();
        s1.pop();
        return x ;
    }
};

剑指 Offer 10- I. 斐波那契数列

class Solution {
public:
    int a=0,b=1;
    int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        for(int i=2;i<=n;i++){
            int tmp =b;
            b=b+a;
            a=tmp; 
            if(b>1e9+7) b=b%1000000007;
        }
        return b;
    }
};

剑指 Offer 10- II. 青蛙跳台阶问题

// 青蛙跳台阶问题： f(0)=1f(0)=1 , f(1)=1f(1)=1 , f(2)=2f(2)=2 ；
// 斐波那契数列问题： f(0)=0f(0)=0 , f(1)=1f(1)=1 , f(2)=1f(2)=1 。

class Solution {
public:
    int a=1,b=1; // 起始点不同
    int numWays(int n) {
        if(n==0) return 1;
        if(n==1) return 1;
        for(int i=2;i<=n;i++){
            int tmp =b;
            b+=a;
            a =tmp;
            if(b>1e9+7) b=b%1000000007;
        }
        return b;
    }
};

剑指 Offer 11. 旋转数组的最小数字

二分法

class Solution {
public:3
    int minArray(vector<int>& numbers) {
        if(!numbers.size()) return -1;
        int n= numbers.size()-1; //闭区间
        while(n>0&&numbers[n]==numbers[0]) n--;
        if(numbers[n]>numbers[0]) return numbers[0];
        int l=0,r=n;
        while(l<r){
            int mid = l+r>>1;
            if(numbers[mid] < numbers[0] ) r=mid;
            else l=mid+1;
        }
        return numbers[l];
    }
};

剑指 Offer 12. 矩阵中的路径

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                if(dfs(board,word,0,i,j)) return true;
            }
        }
         return false;
    }


    bool dfs(vector<vector<char>>& board,string &word,int u,int x, int y){
        if(board[x][y]!=word[u]) return false;
        if(u==word.size()-1) return true;

        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        char t = board[x][y];
        board[x][y] = '.';
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<board.size()&&b>=0&&b<board[a].size()){
                if(dfs(board,word,u+1,a,b)) return true;
            }
        }
        board[x][y]=t;
        return false;
    }
};

剑指 Offer 13. 机器人的运动范围

机器人路径 (宽搜问题)
宽搜模板

//BFS使用队列，把每个还没有搜索到的点一次放入队列，然后再弹出队列的头部元素当做当前遍历点。
//如果不需要确定当前遍历到了哪一层，BFS模板如下

压入初始状态
while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)


/*如果要确定当前遍历到了哪一层，BFS模板如下。这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解
为在一个图中，现在已经走了多少步了。size表示在开始遍历新的一层时，队列中有多少个元素，即有多少个点需要向
前走一步。*/

level = 0 
压入初始状态
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/bfsmo-ban-yi-ci-bei-hui-chu-chu-shi-yong-by-fuxuem/

class Solution {
public:
    //单个数字的数位和
    int singleSum(int num){
        int res =0;
        while(num){
            res+=num%10;
            num = num/10;
        }
        return res;    
    }
    //坐标是数位和
    int doubleSum(int a ,int b){
        return singleSum(a)+singleSum(b);
    }

    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visted(m,vector<bool>(n,false)); // 标记数组
        queue<pair<int,int>> q; //宽搜需要队列
        int count=0;//计数器
        int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
        q.push({0,0});///压入初始状态
        while(q.size()){ // 队列不为空
            pair<int,int > c=q.front();//点的坐标，取出头部元素
            q.pop();
            if(doubleSum(c.first,c.second)>k||visted[c.first][c.second]) continue;    
            visted[c.first][c.second] = true;
            count++;
            for(int i=0;i<4;i++){ // 该点的上下左右
                int a =c.first+dx[i],b=c.second+dy[i];
                if(a>=0&&a<m&&b>=0&&b<n){
                    q.push({a,b});
                }
            }
        }
        return count;
    }
};

剑指 Offer 14- I. 剪绳子

// 找规律 尽可能找到更多的3可以使得结果最大
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return 1*(n-1);
        int res =1;
        if(n%3==1) res*=4,n-=4;
        if(n%3==2) res*=2,n-=2;
        while(n){
            res*=3;
            n-=3;  
        }
        return res;
    }
};
// 时间复杂度：O(1)
// 空间复杂度：O(1)

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 15. 二进制中1的个数

class Solution {
public:
    int lowbit(uint32_t n){
        return n&-n; //返回x的最后一位1  例如 10100 --> 100   1010110 --> 10
    }
    int hammingWeight(uint32_t n) {
        int res=0;
        while(n){
            n-=lowbit(n);
            res++;
        }
        return res;
    }
};

剑指 Offer 16. 数值的整数次方

/*方法一
*超出了时间限制
*/
class Solution {
public:
    double myPow(double x, int n) {
        double res=1;
        for(int i=0;i<abs(n);i++){
            res*=x;
        }
        if(n<0) return 1/res;
        return res;
    }
};

/*方法二
* 
*/

class Solution {
public:
    double myPow(double x, int n) {
        if(x==1||n==0) return 1;
        double res=1;
        long  _n = abs(n);// leetcode中有超过int范围的数，用long定义

        while(_n){
            if(_n&1){
                res*=x;
            }
            x*=x;
            _n>>=1;//_n=_n>>1;
            //cout << _n;
        }
        if(n<0) return 1/res;
        return res;
    }
};

剑指 Offer 17. 打印从1到最大的n位数

/*
*简单解法
*/

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        if(n==0) return res;
        for(int i=1;i<pow(10,n);i++){
            res.push_back(i);
        }
        return res;
    }
};

// 大数

剑指 Offer 18. 删除链表的节点

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head==NULL|| head->next==NULL) return NULL;
        ListNode *pNode =head; // 对头节点单独判断
        if(pNode->val==val) {
            return pNode->next;
        }
        while(pNode!=NULL&&pNode->next->val!=val) pNode=pNode->next;
        pNode->next=pNode->next->next; 
        return head;
    }

};


//双指针
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *pCur =head->next;
        ListNode *pPre = head;
        if(head->val == val ) return head->next; // 对头节点单独判断
        while(pCur!=NULL&&pCur->val!=val){
            pPre=pCur;
            pCur=pCur->next;

        }
        pPre->next = pCur->next;
        return head;

    }
};

18.2在O(1)时间删除链表结点
假设链表一定存在，并且该节点一定不是尾节点。

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val =node->next->val;  // 有假设条件，不是尾节点，所以可以让下一个节点的值覆盖当前节点
        node ->next = node->next->next;//再删除下一个节点
    }
};

18.3.1 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。leetcode 83

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL) return NULL;
        ListNode *pCur = head;
        while(pCur->next){
            if(pCur->next->val==pCur->val) pCur->next = pCur->next->next;
            else pCur=pCur->next;
        }
        return head;
    }
};

//定义一个指针，判断当前节点的值是否与当前节点下一个节点的值相同，如果相同，删除下一个节点，如果不同，
//指针移向下一个节点
//遍历整个链表

//另外，由于头节点不会被删除，所以不需要定义

18.3.2 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留 leetcode 82

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* xhead = new ListNode(-1); // 有可能删除头节点，定义虚拟头节点将问题一般化
        xhead->next =head;
        ListNode *p = xhead;
        while(p->next){
            ListNode *q = p->next;
            while(q&&q->val==p->next->val) q=q->next;
            if(p->next->next==q) p =p->next; //如果区间长度为1
            else p->next=q; //区间长度不是1，则删除
        }
        return xhead->next;
    }
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        //双指针算法
        int i =0,j=nums.size()-1;
        while(i<j){
            while(i<j&&nums[i]%2==1) i++;
            while(i<j&&nums[j]%2==0) j--;
            if(i<j) swap(nums[i],nums[j]);
        }
        return nums;
    }
};

剑指 Offer 25. 合并两个排序的链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //头指针
        if(l1==NULL&&l2==NULL) return NULL;
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;

        ListNode *xhead =new ListNode(-1);
        ListNode * cur = xhead;

        ListNode *p1 =l1, *p2 =l2;
        while(p1!=NULL&&p2!=NULL){
            if(p1->val<=p2->val){
                cur->next = p1;
                p1 = p1->next;
                cur=cur->next;
            } 
            else{
                cur->next = p2;
                p2 =p2->next;
                cur=cur->next;
            }
        }
        if(p1==NULL) cur->next = p2;
        if(p2==NULL) cur->next =p1;
        return xhead->next;
    }
};

剑指 Offer 26. 树的子结构

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A||!B) return false; //递归出口
        if(A->val == B->val){  // 遍历A，找到与B的头节点相同的点
            if(isSub(A,B)) return true; // 头节点相同再递归判断AB左子树、右子树是否相同
        }
        return (isSubStructure(A->left,B)|| isSubStructure(A->right,B));
    }
    // 遍历到B的叶节点 真
    // 遍历到A的叶节点而B不为空，返回假
    // 如果AB根节点的值不相同的话，返回假
    bool isSub(TreeNode* a,TreeNode *b){
        if(!b) return true;// 如果b的节点遍历到叶节点，说明是子串
        if((!a&& b) || (a->val!=b->val)) return false;// 如果a为空，b不为空，返回false,相当于根节点
        return isSub(a->left,b->left)&&isSub(a->right,b->right);
    }
};

剑指 Offer 27. 二叉树的镜像

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return nullptr;
        mirrorTree(root->left);
        mirrorTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        stack<TreeNode*> stk;
        if(root) stk.push(root);
        while(stk.size()) {
            TreeNode* tr = stk.top();
            stk.pop();
            swap(tr->left, tr->right);
            if(tr->left) stk.push(tr->left);
            if(tr->right) stk.push(tr->right);
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size()) {
            TreeNode* tr = q.front();
            q.pop();
            swap(tr->left, tr->right);
            if(tr->left) q.push(tr->left);
            if(tr->right) q.push(tr->right);
        }
        return root;
    }
};

剑指 Offer 28. 对称的二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        return dfs(root->left,root->right);
    }

    bool dfs(TreeNode* mleft, TreeNode* mright){
        if(mleft==NULL&& mright==NULL) return true;
        if(mleft==NULL||mright==NULL||mright->val!=mleft->val) return false;
        return dfs(mleft->left,mright->right) && dfs(mleft->right,mright->left);       
    }
};

题解

剑指 Offer 29. 顺时针打印矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.size()==0||matrix[0].size()==0) return res;
        int rows = matrix.size(), cols = matrix[0].size();

        int l=0,r=cols-1,t=0,b=rows-1;
        while(l<=r&&t<=b){
            for(int i=l;i<=r;i++){
                res.push_back(matrix[t][i]);
            }
            for(int i=t+1;i<=b;i++){
                res.push_back(matrix[i][r]);
            }
            if(l<r&&t<b){
            for(int i=r-1;i>=l;i--){
                res.push_back(matrix[b][i]);
            }
            for(int i=b-1;i>t;i--){
                res.push_back(matrix[i][l]);
            }
            }
            l++;
            t++;
            r--;
            b--;
        }

        return res;
    }
};

题解

剑指 Offer 30. 包含min函数的栈

class MinStack {
public:
    /** initialize your data structure here. */

    MinStack() {

    }
    void push(int x) {
        s1.push(x);
        if(s2.empty()||x<=s2.top()){
            s2.push(x);
        }
        else{
            s2.push(s2.top());
        }
    }
    void pop() {
        if(!s1.empty()&& !s2.empty()){
            s1.pop();
            s2.pop();
        }
    } 
    int top() {
        return s1.top();
    }

    int min() {
        return s2.top();
    }
private:
    stack<int> s1,s2;
};

剑指 Offer 32 - I. 从上到下打印二叉树

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode*>  q;
        q.push(root);
        while(q.size()){
            TreeNode *tmp = q.front();
            q.pop();
            res.push_back(tmp->val);
            if(tmp->left) q.push(tmp->left);
            if(tmp->right) q.push(tmp->right);
        }
        return res;
    }
};

剑指 Offer 32 - II. 从上到下打印二叉树 II

class Solution {
    // 标准的 bfs 方法
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            vector<int> tmp; //定义在此处，每次会更新为空
            int t= q.size();
            for(int i=0;i<t;i++){
                TreeNode *p= q.front();
                q.pop();
                tmp.push_back(p->val);
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

剑指 Offer 32 - III. 从上到下打印二叉树 III

class Solution {

    //双端队列
    //bfs
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;

        deque<TreeNode*> d;//双端队列
        bool flag = true;
        d.push_back(root);
        while(d.size()){
            vector<int> v;
            int n = d.size();
            TreeNode *p;
            for(int i=0;i<n;i++){

                 if(flag){
                     p = d.front();
                     d.pop_front();
                     v.push_back(p->val);
                     if(p->left) d.push_back(p->left);
                     if(p->right) d.push_back(p->right);
                 }
                 else{
                     p=d.back();
                     d.pop_back();
                     v.push_back(p->val); 
                     if(p->right) d.push_front(p->right);
                     if(p->left) d.push_front(p->left);

                 }
            }
            flag=!flag;
            res.push_back(v);
        }
        return res;

    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

思路： 递归
二叉搜索树的左子树都小于根节点，右子树都大于根节点。因此需要找到分界点，分成左子树和右子树再分别遍历
步骤：

1. 如果大小小于等于1的话，可以直接返回，因为空树也是二叉搜索树
2. 递归函数，输入边界l和r

• 递归结束条件 ；l<=r
• 根节点一定位于数组最后一个元素
• 找到分界点，即找到第一个大于根节点的数，它的左边是左子树，右边是右子树
• 左边的数肯定成立了，因为这是循环结束的条件，所以判断右边是否成立，遍历比较，一旦有小于根节点的数，直接返回false

• 否则，本层成立，递归遍历左子树与右子树

  // 递归解法
  class Solution {
  public:
  vector<int> v; // 为了减少递归传递一个参数，定义成类的成员变量
    bool verifyPostorder(vector<int>& postorder) {
        v=postorder;
        if(postorder.size()<=1) return true;
        return dfs(0,v.size()-1);
    }
    bool dfs(int l,int r){
        if(l>=r) return true;// 递归结束条件，说明全部成立
        int k =l;
        int root = v[r];
        while(k<r&&v[k]<root) k++; // 到k,没有=
        for(int i=k;i<r;i++){
            if(v[i]<root) return false;
        }
  
        return dfs(l,k-1)&&dfs(k,r-1);
  
    }
  };
  // 时间复杂度 O(n^2)
  

  剑指 Offer 34. 二叉树中和为某一值的路径

思路：
dfs遍历每一条路径
结束条件：

• 遍历到根节点，即左右子树都为空

• _且_sum减为0

  class Solution {
  public:
    vector<vector<int>> res;
    vector<int> path; // 定义为类成员变量
  
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(!root) return res;
        dfs(root,sum);
        return res;
    }
    void dfs(TreeNode* root,int sum){
        if(!root) return ;
  
        sum-=root->val;
        path.push_back(root->val);
        // 如果到达了叶子节点即该节点的左右子树都为空且sum==0了，说明这条路径是满足的，保存到res中
        if(!root->left&&!root->right&&sum==0){
            res.push_back(path);
        }
        dfs(root->left,sum);
        dfs(root->right,sum);
        // 注意： 要回溯，恢复原状，因为sum是传递进去的参数，在递归中不满足返回上一层时不会影响sum，因此sum不用回溯，只需将path数组回溯
        path.pop_back();
    }
  };
  

  剑指 Offer 35. 复杂链表的复制

  

• 方法一 （最优解） 直接在原链表进行改造，时间复杂度O(n),空间复杂度O(1) ```cpp / // Definition for a Node. class Node { public: int val; Node next; Node* random;

  Node(int _val) {

    val = _val;
    next = NULL;
    random = NULL;
  

  } }; / class Solution { public: Node copyRandomList(Node* head) {

    if(!head) return head;
    Node* p =head;
    // 第一次遍历，复制每个节点并插入
    while(p){
        Node* q = new Node(p->val);
        Node *tmp = 
        q->next = p->next;
        p->next=q;
        p=p->next->next;
    }
    //第二次遍历，给random指针赋值，p->next->random=p->random->next;
    p = head;
    while(p){
        if(p->random){
            p->next->random=p->random->next;
        }
        p=p->next->next;
    }
    // 第三次遍历 ，将链表从中拆分处理
    Node *xhead = new Node(-1);
    p=head;
    Node *cur = xhead;
    while(p){
        cur->next= p->next;
        cur =cur->next;
        p->next=p->next->next;// 将原链表恢复原状
        p=p->next;
    }
    return xhead->next;
  

  } };

// 时间复杂度 三次遍历 所以为O(n) ，空间复杂度 O(1)

- 方法二 哈希表 需要额外的空间，时间复杂度O(n),空间复杂度O(n)
```cpp

//key 与 value 都为Node 节点
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        unordered_map<Node*,Node*> mhash;
        Node* p=head;
        while(p){
            mhash[p] = new Node(p->val);
            p=p->next;
        }
        p=head;
        while(p){
            if(p->next) mhash[p]->next= mhash[p->next];
            if(p->random) mhash[p]->random = mhash[p->random];
            p=p->next;
        }
        return mhash[head];
    }
};

剑指 Offer 36. 二叉搜索树与双向链表

整体思路：

1. 要求有序，二叉树又是搜索二叉树，因此采用中序遍历就可以排好序
2. 需要记录上次访问的节点pre，这样可以直接pre->right = cur; cur->left =pre; 完成双向链表的创建
3. 循环链表特殊处理 head->left = tail; tail ->right =head;

细节描述：

• 关于头节点head和尾节点的获取，当递归到左子树的叶节点时返回，此时root即位头节点，我们可以通过判断头节点是否为空，只赋值一次。尾节点即为最后的pre

  class Solution {
  public: 
    Node *pre =NULL;//定义一个node记录先前节点
    Node *head =NULL;
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        dfs(root);
        pre->right=head;
        head->left=pre;
        return head;
    }
    void dfs(Node *root){
        if(!root) return;
        dfs(root->left);
        if(!head){ // 初始化头节点和记录当前节点
            head=root;
            pre =root;
        }
        else{
            pre->right=root;
            root->left=pre; // 关键部分
            pre =root;
        }
        dfs(root->right);
    }
  };
  

  剑指 Offer 37. 序列化二叉树

  思路：
  序列化二叉树，可以用不同的遍历方法，只需要在恢复时按同样的顺序即可。
  先序递归遍历：

  class Codec {
  public:
    string res;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return res;
        dfs_s(root);
        return res;
    }
    void dfs_s(TreeNode* root){
        if(!root){
            res+="null ";//加空格,空格分割
            return ;
        }
        res+= to_string(root->val)+" ";
        dfs_s(root->left);
        dfs_s(root->right);
    }
  
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u =0;
        return dfs_d(data,u);
  
    }
    //u是引用，遍历过程中会依次后移
    TreeNode* dfs_d(string data,int &u){
        if(u==data.size()) return NULL;
        int k=u;
        bool flag=false;
        int sum;
        while(data[k]!=' ')k++;// 取得该字段末尾 比如说 "123"
        if(data[u]=='n'){
            u=k+1;
            return NULL;
        }
        for(int i=u;i<k;i++){
            //判断负数
            if(data[i]=='-'){
                flag=true;
                continue;
            }
            sum=sum*10+(data[i]-'0');
        }
        if(flag){
            flag=!flag;
            sum =-sum;
        }
        u=k+1;
        TreeNode* root = new TreeNode(sum);
        root->left=dfs_d(data,u);
        root->right=dfs_d(data,u);
        return root;
    }
  };
  

  剑指 Offer 38. 字符串的排列

  
  思路：

• dfs() 深搜

• 为了去除重复元素，我们可以先排序将相同的元素挨在一起，对于相同的元素，认为定义后一个元素只能排在上一个相同元素的后面，从而保证不重复。

  class Solution {
  public:
    vector<string> res;
    string path;
    vector<string> permutation(string s) {
        if(!s.size()) return res;
        path.resize(s.size());
        sort(s.begin(),s.end());
        dfs(s,0,0,0);
        return res;
    }
    // u :  s 中的第u个元素
    // start : 为了去重而设置，假如和前一个元素不相等，则从第一个位置开始枚举，如果相同，则只能从当前元素后面开始
    // flag : 也可以设置成bool数组，标志该位是否为空，但设置为数组时，记得回溯
    void dfs(string &s,int u,int start,int flag){
        if(u==s.size()){
            res.push_back(path);
            return;
        }
        if(!u||s[u]!=s[u-1]) start =0;
        for(int i=start;i<s.size();i++){
            if(!(flag>>i&1)){ // 第i为是否为空
                path[i]=s[u];
                dfs(s,u+1,i+1,flag+(1<<i));
        }
    }
    }
  };
  

  数字排列
  

  class Solution {
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        path.resize(nums.size());
        sort(nums.begin(),nums.end());
        dfs(nums,0,0,0);
        return res;
    }
    void dfs(vector<int>& nums,int u,int start,int flag){
        if(u==nums.size()){
            res.push_back(path);
            return;
        }
        if(!u||nums[u]!=nums[u-1]) start=0;
        for(int i=start;i<nums.size();i++){
            if(!(flag>>i & 1)){
                path[i]=nums[u];
                dfs(nums,u+1,i+1,flag+(1<<i));
  
            }
        }
  
    }
  };
  

  dfs问题
  
  写法1：
  采用和上述方法一致的写法，即标志采用标志位的写法
  注意：
  关于回溯的问题，因为我们将标志位传入了形参，因此不用再另行进行回溯。回溯见下一种写法，不过思想是一致的。 ```cpp

  include

  include

  using namespace std; vector path; vector> res; int n; void dfs(int u,int flag){ if(u==n) {

    res.push_back(path);
    return;
  

  } for(int i=0;i<n;i++){

    if(!(flag>>i &1)){
        path[u]=i+1; //因为i是从0开始的
        dfs(u+1,flag+(1<<i));
  

  } } } int main(){ cin >> n; path.resize(n); dfs(0,0); for(auto v:res){

    for(auto x:v)
        cout << x << ' ';
    cout << endl;
  

  } return 0; }

/ 3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 /

**写法二**<br />**
```cpp

#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
vector<vector<int>> res;
int n;
vector<bool> flag;
void dfs(int u){
    if(u==n){
        res.push_back(path);
        return;
    }
    for(int i=0;i<n;i++){
        if(!flag[i]){ // 未被访问
            path[u]=i+1;
            flag[i]=true; // 已访问
            dfs(u+1);
            flag[i]=false; //回溯
        }
    }
}
int main(){
    cin >> n;
    path.resize(n);
    flag=vector<bool>(n,false);
    dfs(0);
    for(auto v:res){
        for(auto x:v)
            cout << x << ' ';
        cout << endl;
    }
    return 0;
}
/*
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

剑指 Offer 39. 数组中出现次数超过一半的数字

//排序方法 时间复杂度O(nlgn),空间复杂度O(1)
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

// 哈希表 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> mhash;
        for(auto x:nums){
            mhash[x]++;
        }
        for(auto a:mhash){
            if(a.second>nums.size()/2)
            return a.first;
        }
        return 0;
    }
};

摩尔投票法
思路：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count =0;
        int val ;
        for(auto x:nums){
            if(!count) val=x,count=1;  // 如果count 为0 
            else{ // 如果count 不为0
                if(val==x) count++;
                else count--;
            }
        }
        return val;
    }
};
/*************************************************/
class Solution {
    public int majorityElement(int[] nums) {
        int vote = 0;   int target = nums[0];
        for(int i =0;i<nums.length;i++){
            if(nums[i]==target) vote++;
            if(nums[i]!=target) vote--;
            if(vote==0&&(i+1)<nums.length) target=nums[i+1];
        }
        return target;
    }
}

剑指 Offer 40. 最小的k个数

// 大根堆
// 大根堆在stl是以优先级队列的形式存在的
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> heap;
        for(auto x:arr){
            heap.push(x);
            if(heap.size()>k) heap.pop();
        }
        vector<int> res;
        while(heap.size()){
            res.push_back(heap.top());
            heap.pop();
        }
        reverse(res.begin(),res.end()); // 大根堆，顺序是反的，所以得反转
        return res;
    }
};

// 排序
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> res;
        if(arr.size()==0) return res;
        sort(arr.begin(),arr.end());
        for(int i=0;i<k;i++){
            res.push_back(arr[i]);
        }
        return res;
    }
};

剑指 Offer 41. 数据流中的中位数

思路：

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<int>> mheap;// 小顶堆
    priority_queue<int> lheap; // 大顶堆
    // mheap 当为奇数时，多存放一个元素比lheap，为偶数时，存放元素个数相等
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        if(mheap.size()!=lheap.size()){
            mheap.push(num);
            lheap.push(mheap.top());
            mheap.pop();
        }
        else{
            lheap.push(num);
            mheap.push(lheap.top());
            lheap.pop();
        }
    }

    double findMedian() {
        if(mheap.size()!=lheap.size()) return mheap.top();
        else return static_cast<double>((lheap.top()+mheap.top())/2.0);
    }
};

剑指 Offer 42. 连续子数组的最大和 ——-DP

DP

class Solution {
    //动态规划的思想
    // 假设当前项前一项的和为s， 如果s<0 , 则s=x;如果s>0,则s=s+x; 记录s出现的最大值
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int s=0;
        for(auto x:nums){
            if(s<0) s=0;
            s+=x;
            res= max(res,s);
        }
        return res;
    }
};

剑指 Offer 43. 1～n整数中1出现的次数

思路：
假设一个数 32 4 134
当前指向的数为 4 ， left =32 right = 134

• left： 00-31 后三位 000-999 即t=1000; res+= left t = 32 1000;
• 当前两位为32时， 当前位置分情况讨论，
  • cur=0时， 没有1的情况
  • cur=1时，000-134 即 res+ = right+1
  • cur>1时，000-999 即 res+= t;

步骤：

• 先分解
• 遍历每一位数，再求出 左侧和右侧两个参数
• 按规律分情况讨论

  class Solution {
  public:
    int countDigitOne(int n) {
        int res;
        vector<int> num;
        while(n){
            num.push_back(n%10);
            n/=10;
        }
        for(int i=num.size()-1;i>=0;i--){
            int left=0,right=0;
            int t=1;
            for(int j=i-1;j>=0;j--) right=right*10+num[j],t*=10;
            for(int j=num.size()-1;j>i;j--) left=left*10+num[j];
            res+= left*t;
            if(num[i]==1) res+=right+1;
            else if(num[i]>1) res+=t;
        }  
        return res;
    }
  };
  // 时间复杂度 O(logn) 空间复杂度 O(1)
  

  剑指 Offer 44. 数字序列中某一位的数字

格外注意 n与 i

class Solution {
public:
    int findNthDigit(int n) {
        int i =1;
        while(n>0.9*pow(10,i)*i) n-=0.9*pow(10,i)*i,i++; // 求出在几位数的区间 i表示，n表示在次区间的多少位
        int num = pow(10,i-1) + (n-1)/i; // base+ 
        string res = to_string(num);
        return res[(n-1)%i]-'0';
    }
};

剑指 Offer 45. 把数组排成最小的数

思路：

class Solution {
public:
// 注意添加static
static bool cmp(string &st1,string &st2){
        return st1+st2 < st2+st1;
    }
    string minNumber(vector<int>& nums) {
        vector<string> vst;
        for(int i=0;i<nums.size();i++){
            vst.push_back(to_string(nums[i]));
        }
        sort(vst.begin(),vst.end(),cmp);
        //拉姆达 表达式写法
        //sort(vst.begin(),vst.end(),[](string &st1,string &st2){return st1+st2<st2+st1;});
        string res;
        for(auto x:vst) res+=x;
        return res;
    }    
};

class Solution {
public:
    static bool cmp(int a, int b ){
        string sa =to_string(a),sb= to_string(b);
        return sa+sb < sb+sa;
    }
    string minNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string res;
        for(auto x:nums) res+=to_string(x);
        return res;
    }
};

剑指 Offer 46. 把数字翻译成字符串 ——DP

思路

class Solution {
public:
    int translateNum(int num) {
        //转换成字符串
        string s= to_string(num);
        int n =s.size();
        vector<int> dp(n+1,0);
        dp[0] =1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i] =dp[i-1];
            int t = (s[i-2] -'0')*10+(s[i-1]-'0');
            if(t>=10&&t<=25) dp[i]+=dp[i-2];
        }
        return dp[n];
    }
};

//时间复杂度 ：O(log(num))  这是转换成字符串的长度
//空间复杂度 ： O(n) 主要是dp数组， 当然还有字符串长度 O(lognum) 10 为底

class Solution {
public:
    int translateNum(int num) {
        //转换成字符串
        string s= to_string(num);
        int n =s.size();
        if(n<2) return 1;
        int a =0;
        int b=1;
        int c=1;
        for(int i=2;i<=n;i++){
            a=b; 
            int t = (s[i-2] -'0')*10+(s[i-1]-'0');
            if(t>=10&&t<=25) a+=c;
            c=b; b=a;//记录 i-1和i-2 的值
        }
        return a;
    }
};

剑指 Offer 47. 礼物的最大价值 ——DP

思路：

• 状态 ：
• 状态转移 ： 的值只能从 左边 或者 上边 中得到，选择二者中的最大值。

• 边界条件： 代码注释

  class Solution {
  public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(),m=grid[0].size();
        vector<vector<int>> dp(n+1,vector<int>(m+1)); // dp[i][j]  从1开始， dp[0][0~m]=0 dp[0~n][0] =0 边界条件
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[n][m];
    }
  };
  

  剑指 Offer 48. 最长不含重复字符的子字符串 ——双指针

  请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
  思路：
  双指针算法 O(2n)
  

  //双指针算法模板
  for(int i=0,j=0,i<n;i++){
    while(j<i&&check(i,j)) j++;
    res=max(res,i-j+1);
  }
  

  class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> mhash;
        int n=s.size();
        int res =0;
        for(int i=0,j=0;i<n;i++){
            mhash[s[i]]++;
            while(mhash[s[i]]>1){
                mhash[s[j]]--;
                j++;
            }
            res=max(res,i-j+1);
        }
        return res;
    }
  };
  

  相似的题目
  最长序列
  题目描述
  给定一个长度为的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。
  输入格式
  第一行包含整数。
  第二行包含个整数（均在0~100000范围内），表示整数序列。
  输出格式共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。
  数据范围
  样例

  输入样例：
  5
  1 2 2 3 5
  输出样例：
  3
  

  using namespace std;
  const int N =100010;
  int a[N],s[N];
  int main(){
    int n;
    int res=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0,j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1) {
            s[a[j]]--;
            j++;
        }
        res = max(res,i-j+1);
  
    }
    cout << res <<endl;
    return 0;
  }
  

剑指 Offer 49. 丑数 ——DP

思路：

简单来说，就是当前的状态由前面三个数分别承 2 3 5 中的最小值所确定。

class Solution {
public:
    int mmin(int a,int b,int c){
        if(a<b) return min(a,c);
        else return min(b,c);
    }
    int nthUglyNumber(int n) {
        int a=0,b=0,c=0;
        vector<int> dp(n+1,0);
        dp[0] =1;
        for(int i=1;i<=n;i++){
            dp[i] = mmin(dp[a]*2,dp[b]*3,dp[c]*5);
            if(dp[i]== dp[a]*2) a++;
            if(dp[i]== dp[b]*3) b++;
            if(dp[i]== dp[c]*5) c++;
        }
        return dp[n-1];
    }
};

剑指 Offer 50. 第一个只出现一次的字符 ——哈希表

思路：

• 先将所有元素压入哈希表中
• 在重新遍历，但是要按原字符顺序遍历（哈希表是无序的）找到第一个 value为1的数返回key 即可。

  class Solution {
  public:
    char firstUniqChar(string s) {
        char res;
        if(s.size()==0) return ' ';
        unordered_map<char,int> mhash;
        for(auto x:s) mhash[x]++;
        for(auto a:s) if(mhash[a]==1) return a;
         return ' ';
    }
  };
  

剑指 Offer 51. 数组中的逆序对 ——归并排序

-

• 数据范围分析， 假设最坏情况 n个数全部为逆序对，则 res= (n+ n-1 +n-2 + … +1) = (1+n)*n/2= n^2/2

数据是50000，n^2/2 = 25亿/2 =12亿，int 类型 的最大值大概为21亿，所以采用的Int 类型返回。

• 归并排序的顺序：
  • 找中点作为分界点，其他也可以
  • 递归分解
  • 归并 （开辟新的空间保存中间值，末尾需要重新赋给原数组，这样才会将原数组排序）

• 特点：

  • 在归并的过程，左右都是有序的，而这也是可以用作逆序对的原因

  • 时间复杂度 O(nlogn) 空间复杂度 O(n)

    class Solution {
    public:
    // 归并排序
    int res=0;
    int reversePairs(vector<int>& nums) {
       if(!nums.size()) return 0;
       int n = nums.size();
       vector<int> tmp(n,0);
       merge_sort(nums,tmp,0,n-1);
       return res;
    }
    void merge_sort(vector<int>& nums,vector<int> &tmp, int l,int r ){
       if(l>=r) return ;       
       int mid =(l+r) >>1;
       merge_sort(nums,tmp,l,mid);
       merge_sort(nums,tmp,mid+1,r);
       int i=l,j=mid+1;
       int k =0;
       while(i<=mid&&j<=r){
           if(nums[i]<=nums[j]) tmp[k++]=nums[i++];
           else {
               res+= mid-i+1;
               tmp[k++]= nums[j++];
           }           
       }
       while(i<=mid) tmp[k++]=nums[i++];
       while(j<=r) tmp[k++] =nums[j++];
    
       for(i=l,j=0;i<=r;i++,j++) nums[i] = tmp[j];
    }
    };
    

    归并排序模板

//归并排序
#include<iostream>
using namespace std;
const int N =100000;
int q[N],temp[N];
long long res=0; // 10^10/2 = 5*10^9  > 21亿
void merge_sort(int q[],int l,int r){
    if(l>=r) return;
    int mid = l+r>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else { 
            res += mid-i+1;
            temp[k++]=q[j++];
        }
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];

    for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j]; // 本段q的范围：l~r
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1); // 闭区间
    cout << res<<endl;
    for(int i=0;i<n;i++)printf("%d ",q[i]);
}

剑指 Offer 52. 两个链表的第一个公共节点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 =headA,*p2 =headB;
        while(p1!=p2){
            if(p1==NULL) p1=headB;
            else p1=p1->next;
            if(p2==NULL) p2=headA;
            else p2=p2->next;
        }
        return p1;
    }
};

1. 求长度再对齐 ```cpp class Solution { public: ListNode getIntersectionNode(ListNode headA, ListNode *headB) {

    int lengthA = ComputeLengthLN(headA);
    int lengthB = ComputeLengthLN(headB);
   

    if(lengthA>=lengthB) {
        int d = lengthA-lengthB;
          goahead(headA,d);//前进
    }
    else{
        int d=lengthB-lengthA;
         goahead(headB,d);
    }  

    ListNode *p1=headA,*p2 =headB;
    while(p1&&p2){
        if(p1==p2) return p1;

        p1=p1->next;
        p2=p2->next;
    }
    return NULL;

}

int ComputeLengthLN(ListNode* head){
    int res=0;
    ListNode* node=head;
    while(node){
        res++;
        node=node->next;
    }
    return res;
}
void goahead(ListNode* &head,int d){
    while(head&&d){
        d--;
        head=head->next;
    }
}

};

<a name="s0Kim"></a>
#### [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/) ----二分

![image.png](https://cdn.nlark.com/yuque/0/2020/png/474935/1594449239594-e8f3da11-10b5-4791-a24d-157f53582d1a.png#align=left&display=inline&height=609&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1218&originWidth=1241&size=147696&status=done&style=none&width=620.5)

![image.png](https://cdn.nlark.com/yuque/0/2020/png/474935/1594449273971-13c94d5c-092f-426e-ad59-97c83a344564.png#align=left&display=inline&height=255&margin=%5Bobject%20Object%5D&name=image.png&originHeight=511&originWidth=875&size=26385&status=done&style=none&width=437.5)

```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return 0;

        int l=0,r=nums.size()-1;
        while(l<r){
            int mid =l+r>>1;
            if(nums[mid] < target) l=mid+1;
            else r=mid;
        }
        if(nums[l]!=target) return 0;
        int a=l;
        l=0,r=nums.size()-1;
        while(l<r){
            int mid =(l+r+1)>>1;
            if(nums[mid ]<= target) l=mid;
            else r=mid-1;
        }
            return l-a+1;
    }
};

剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid =(l+r) >>1;
            if(nums[mid]!=mid) r=mid; // 如果不相等，说明错位的地方在当前位置的左边
            else l =mid+1;
        }
        if(nums[r]==r)  return r+1;;
        return l;
    }
};

取巧的方法

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size()+1;
        int sum= (0+n-1)*n/2;
        for(auto x:nums)  sum-=x;
        return sum;
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

做此题之前，先做一个 二叉搜索树的第k个结点

思路：

• 二叉搜索树，所以左子树< 根节点 < 右子树
• 中序遍历即位从小到大

class Solution {
public:
    TreeNode *res;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
    void dfs(TreeNode* root,int &k){
        if(!root) return;
        dfs(root->left,k);
        k--;
        if(!k) res =root;
        if(k>0) dfs(root->right,k); // 此处加上判断，可以提前结束，提高效率
    }
};

再来看本题思路：

• 调整顺序，右根左 即是从大到小的顺序
• 也是中序遍历的问题

  class Solution {
  public:
    int res;
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
    void dfs(TreeNode *root,int &k){
        if(!root) return ;
        dfs(root->right,k);
        k--;
        if(!k) res=root->val;
        if(k>0) dfs(root->left,k);
    }
  };
  

  剑指 Offer 55 - I. 二叉树的深度

  输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

  class Solution {
  public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int m =maxDepth(root->left); // 递归遍历左子树
        int n =maxDepth(root->right); // 递归遍历右子树
        return max(m,n)+1;  //返回左子树和右子树中最长路径 +1 根节点
    }
  };
  

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
思路：

• 同上题， 比较左右子树的最大深度，比较是否相差>1

  class Solution {
  public:
    bool res=true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode* root){
        if(!root) return 0;
        int mleft = dfs(root->left);
        int mright =dfs(root->right);
        if(abs(mleft-mright)>1) res=false;
        return max(mleft,mright)+1;
    }
  };
  

  剑指 Offer 56 - I. 数组中数字出现的次数 ——异或

  
  思路：
  

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum=0;
        for(auto x:nums) sum^=x;//x^=y
        int k=0;
        while(!((sum>>k)&1)) k++;
        int first=0;
        int second=0;
        for(auto x:nums) {
            if((x>>k)&1) first^=x;
            else second^=x;
        }
        return vector<int>{first,second};
    }
};

// 优化一部分
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum=0;
        for(auto x:nums) sum^=x;//x^=y
        int k=0;
        while(!((sum>>k)&1)) k++;
        int first=0;
        for(auto x:nums) if((x>>k)&1) first^=x;  
        return vector<int>{first,sum^=first}; // sexond = sum^=first;
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
思路：

• 进行位运算，逐位数出数组中该位为1的个数，为1的位为3的倍数

如果个数刚好是3的倍数，说明，唯一的那个数在该位上为0。
如果个数不是3的倍数，说明，唯一的那个数在该位上为1。
遍历每一位之后我们可以得出唯一的那个数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;  
        for(int i=0;i<32;i++){
            int count =0;
            for(auto x:nums){
                if((x>>i)&1) count++;
            }
            if(count%3!=0) res|= (1<<i);
        }
        return res;
    }
};

有限状态机 ： 推导[https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/]
没看懂 ：（

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones=0,twos=0;
        for(auto x:nums){
            ones=(ones^x)& ~twos;
            twos= (twos^x)& ~ones;
        }
        return ones;
    }
};

剑指 Offer 57. 和为s的两个数字

方法一： 哈希表 unordered_set;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int> hashset;
        for(int i=0;i<nums.size();i++){
            if(hashset.count(target-nums[i])) return vector<int>{target-nums[i],nums[i]};
            hashset.insert(nums[i]);
        }
        return vector<int>();
    }
};

方法二
思路：

• 可以先用二分法找到第一个大于target的数，因次右指针可以指向它 // logn
• 双指针算法，>target j— < target i++ 因为是有序数组。

  class Solution {
  public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //二分法把大于target的第一个数找到
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] <=target ) l=mid+1;
            else r=mid;
        }
        cout << nums[l]<<endl;
        //双指针算法
        int i=0,j=r;
        while(i<j){
            int sum = nums[i]+nums[j];
            if(sum >target) j--;
            else if(sum<target) i++;
            else if(sum==target) return vector<int>{nums[i],nums[j]};
        }       
        return vector<int> ();
    }
  };
  

  剑指 Offer 57 - II. 和为s的连续正数序列 ——双指针

  
  链接
  

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        //双指针算法
        int i=1,j=1;
        int sum =1; // 小区间中的和
        vector<vector<int>> res;
        // 左指针小于中值  (上取整)
        while(i<((target+1)/2)){
            if(sum<target) {
                j++;
                sum+=j;
            }
            else if(sum>target){             
                sum-=i; 
                i++;
            }
            else if(sum==target){
                vector<int> path;
                for(int m=i;m<=j;m++){
                    path.push_back(m);
                }
                res.push_back(path);
                sum-=i;
                i++;
            }
        }
        return res;
    }
};

剑指 Offer 58 - I. 翻转单词顺序

思路1： 双指针算法
时间复杂度 O(n) ,空间复杂度O(n);

class Solution {
public:
    string reverseWords(string s) {
        string res;
        if(s.empty()) return res;
        // 去除首位空格
        int n=s.size()-1;
        int end=n;
        while(end>=0&&s[end]==' ')end--;
        if(end<0) return ""; // 做一个特判，防止全都为空格
        int start=0;
        while(s[start]==' ') start++;

        for(int i=end,j=end;i>=start;i--){
            while(i>=start&&s[i]==' ') i--;
            j=i;
            while(i>=start&&s[i]!=' ') i--;
            for(int m=i+1;m<=j;m++){
                res+=s[m];
            }
            res+=' ';
        }
        res.pop_back();
        return res;
    }
};

假设中间不存在空格问题的话
（存在空格的话还没写）
思路：整体翻转+ 局部反转
时间复杂度O(n)， 空间复杂度 O(1)

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(),s.end());
        for(int i=0,j=0;i<s.size();i++){
            j=i;
            while(i<s.size()&&s[i]!=' ')i++;
            reverse(s.begin()+j,s.begin()+i);
        }
        return s;
    }
};

剑指 Offer 58 - II. 左旋转字符串

思路：
“abcdefg” 翻转 “gfedcba” 从n处分割开 gfedc ba
我们的期望 是 “cdefgab” 从n处分割开 cdefg ab
我么可以发现，刚好是各自翻转

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(),s.end());
        reverse(s.begin(),s.end()-n);
        reverse(s.end()-n,s.end());
        return s;
    }
};

剑指 Offer 59 - I. 滑动窗口的最大值 —-单调队列

1. 暴力解法

   class Solution {
   public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 暴力做法
        vector<int> res;
        if(nums.empty()) return res;    cout << nums.size()<<" "<< nums.size()-k;    
        for(int i=0;i<=nums.size()-k;i++){
            int xmax=INT_MIN; // 值要刷新
            for(int j=i;j<i+k;j++){
                xmax=max(xmax,nums[j]);
            }
            res.push_back(xmax);
        }
        return res;
    }
   };
   

2. 单调队列

思路

步骤：

• 先删除不属于当前区间的元素
• 关键，队列的末尾如果小于当前元素，弹出
• 为了判断区间内首元素是否还在，存入的是索引值

  class Solution {
  public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for(int i=0;i<nums.size();i++){
            // 先删除不属于当前区间的元素
            while(q.size()&&q.front()<=i-k) q.pop_front();
            //关键，队列的末尾如果小于当前元素，弹出
            while(q.size()&&nums[q.back()]<=nums[i]) q.pop_back();
            // 为了判断区间内首元素是否还在，存入的是索引值
            q.push_back(i);
            if(i>=k-1) res.push_back(nums[q.front()]);
        }
        return res;
    }
  };
  

  剑指 Offer 59 - II. 队列的最大值

  

思路:
维护有一个辅助双端队列，队首一直存放着最大值

class MaxQueue {
public:
    queue<int> q;
    deque<int> maxq; // 双端队列， 维护一个队首一直是最大值的双端队列
    MaxQueue() {
    }   
    int max_value() {
        if(q.empty()) return -1;
        return maxq.front();
    }

    void push_back(int value) {
        q.push(value);
        while(maxq.size()&&value>maxq.back()) maxq.pop_back();
        maxq.push_back(value);
    }

    int pop_front() {
        if(q.empty()) return -1;
        if(maxq.front()==q.front()) maxq.pop_front();
        int res = q.front();
        q.pop();
        return res;
    }
};

剑指 Offer 60. n个骰子的点数 —-DP（分组背包问题）

题解

class Solution {
public:
    vector<double> twoSum(int n) {
        vector<double> res;
        vector<vector<int>> dp(n+1,vector<int>(6*n+1,0));// 1开始
        //初始化
        for(int i=1;i<=6;i++) dp[1][i] = 1;
        for(int i=2;i<=n;i++){
            for(int j=i;j<=i*6;j++){
                for(int tmp=1;tmp<=6;tmp++){
                    if(j-tmp<0) break;
                    dp[i][j]+=dp[i-1][j-tmp];
                }
            }
        }
        int sum =pow(6,n);
        for(int i=n;i<=6*n;i++){
            res.push_back(dp[n][i]*1.0/sum);
        }
        return res;
    }
};
// 状态表示 dp(n,j)  n个骰子出现的点数
// 状态转移： dp(n,j) = d(n-1,j-1)+ d(n-1,j-2)+d(n-1,j-3)+d(n-1,j-4)+d(n-1,j-5)+d(n-1,j-6) = d(n-1,j-i) i=1~6
// 初始条件 dp(1,j)=1;

初始条件不同

class Solution {
public:
    vector<double> twoSum(int n) {
        vector<double> res;
        vector<vector<int>> dp(n+1,vector<int>(6*n+1));
        dp[0][0] =1;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=6*i;j++){
                for(int tmp =1;tmp<=min(j,6);tmp++){
                    dp[i][j] += dp[i-1][j-tmp];
                }
            }
        }
        int sum =pow(6,n);
        for(int i=n;i<=6*n;i++) res.push_back(dp[n][i]*1.0/sum);
        return res;
    }
};
// 初始条件  当投0次时，s=0 的方案数为1个

剑指 Offer 61. 扑克牌中的顺子

思路：

• 数组中除0外，不能有相同元素，有相同元素不能构成顺子
• 数组中除去0后，最大值-最小值<5 ,则能构成顺子

步骤：

• 排序 方便去0 和判断重复元素和差值
• 去除0
• 查看是否有相同元素
• 判断差值是否 <5

  class Solution {
  public:
    bool isStraight(vector<int>& nums) {
        if(nums.empty()) return false;
        sort(nums.begin(),nums.end());
        int k=0;
        while(nums[k]==0) k++;// 指向第一个不为0的元素
        for(int i=k+1;i<nums.size();i++){
            if(nums[i]==nums[i-1]) return false;
        }
        return nums.back()-nums[k]<5;
    }
  };
  

  剑指 Offer 62. 圆圈中最后剩下的数字 —-约瑟夫问题

  
  题解：

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n==1) return  0;
        return (lastRemaining(n-1,m)+m)%n;
    }
};

// 递归做法

class Solution {
public:
    int lastRemaining(int n, int m) {
        int res=0;
        for(int i=2;i<=n;i++){
            res=(res+m)%i;
        }
        return res;
    }
};
// 迭代做法，还没想明白

剑指 Offer 63. 股票的最大利润

思路：

• 维护一个最小值的变量
• 遍历数组，将与最小值的差记录，更新当前的最大值

  class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int res=0,mmin=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]-mmin>0)
            res=max(res,prices[i]-mmin);
            mmin=min(mmin,prices[i]);
        }
        return  res;
    } 
  };
  

  剑指 Offer 64. 求1+2+…+n

  求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
  思路：
  A&& B 当A不满足条件时，将不会执行B，因此可以替换 if 判断语句

  class Solution {
  public:
    int sumNums(int n) {
        int res=n;
        //if(n>0) res+= sumNums(n-1);
        (n>0)&& (res+=sumNums(n-1));
        return res;
    }
  };
  

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

class Solution {
public:
    int add(int a, int b) {
        while(b){
             int sum = a^b;//不带进位的数
             int carry=(unsigned int)(a&b)<<1; // 进位
             a=sum;
             b=carry;
        }
       return a;
    }
};

剑指 Offer 66. 构建乘积数组

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n =a.size();
        vector<int> res(n);
        if(!n) return res;

        for(int i=0,p=1;i<n;i++){
            res[i]=p;
            p*=a[i];
        }
        for(int i=n-1,p=1;i>=0;i--){
            res[i]*=p;
            p*=a[i];
        }
        return res;
    }
};

剑指 Offer 67. 把字符串转换成整数

class Solution {
public:
    int strToInt(string str) {
        int k=0;
        while(k<str.size()&&str[k]==' ')k++;
        bool flag=false;// 负数标志
        if(k<str.size()&&str[k]=='+') k++;
        else if(k<str.size()&&str[k]=='-') k++,flag=true;
        long long num =0;
        while(k<str.size()&& str[k]>='0'&&str[k]<='9') {
            num=num*10+(str[k]-'0'); 
            if(num>INT_MAX&&(!flag)) return INT_MAX;
            if(num>INT_MAX&&flag) return INT_MIN;
            k++;
        }
        if(flag) num=num*(-1);  
        return (int)num;
    }
};