剑指offer题解和笔记(一刷)

引言

3.21一刷结束

数据结构-数组

数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

这个绝对不是简单题，是与面试官交流的问题

• 时间优先：字典，哈希表
• 空间优先：利用题中性质：

范围在\(0...n-1\)所以如果没出现重复的数，重排之后是按照0~n-1这样排序的。

这题简单的方法是直接排序，这样时间复杂度\(O(nlogn)\)

但是可以更优化一下，如果当前位置\(i\)不等于\(a[i]\)，就让位置\(i\)与位置\(a[i]\)的值交换

这样每个数最多交换两次，第一次交换到\(i\)位置，第二次交换回到正确位置

如果\(a[i]==a[a[i]]\)，那么说明找到重复的了

时间复杂度 \(O(n)\) 空间复杂度\(O(n)\)

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int ans = -1;
        for(int i = 0;i < nums.size();++i){
            while(i!=nums[i]){
                if(nums[nums[i]] == nums[i]) {
                    ans = nums[i];
                    break;
                }
                else swap(nums[i],nums[nums[i]]); 
            }
            if(ans != -1) break;
        }
        return ans;
    }
};

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

第一次我直接用二分

但是有更简单的做法，如果站在右上角看的话就是一个查找二叉树

时间复杂度\(O(logn)\)

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        bool isFound = 0;
        if(matrix.empty()) return 0;
        int m = matrix[0].size(),n = matrix.size();
        int i = 0,j = m - 1;
        while(i < n && j != -1){
            if(matrix[i][j] == target){
                isFound = 1;
                break;
            }
            if(matrix[i][j] > target){
                --j;
            }
            else if(matrix[i][j] < target){
                ++i;
            }
        }
        return isFound;
    }
};

这题更重要的是测试样例

• 二维数组里存在的数
• 不存在的数
• 空指针

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"

如果是要求时间最快写得最简单，完全可以新建字符串

时间复杂度\(O(n)\),空间复杂度$O(n) $

class Solution {
public:
    string replaceSpace(string s) {
        int len = s.length();
        if(len == 0) return s;
        string ans;
        for(int i = 0;i < len;++i){
            if(s[i]==' '){
                ans += "%20";
            }
            else ans += s[i];
        }
        return ans;
    }
};

如果要求空间最小，那么需要在原字符串上进行替换操作。

• \(O(n^2)\):这个很容易想到，每出现一个空格，后面就移位
• \(O(n)\)：采用从后往前的做法，这样每个字符只用移动一次

先求出空格个数，设定两个指针，一个指向要移动到的位置，一个指向原来的位置

ps:这题leetcode上差点意思，我就在牛客上提交的

时间复杂度\(O(n)\),没有新开空间

class Solution {
public:
	void replaceSpace(char *str,int length) {
        if(length == 0) return;
        int numberOfBlank = 0;
        for(int i = 0;i < length;++i){
            if(str[i] == ' ') numberOfBlank++;
        }
        int newStingLength = length + (numberOfBlank << 1);
        int p1 = newStingLength - 1,p2 = length - 1;
        
        while(p2 >= 0){
            if(str[p2] == ' '){
                str[p1--] = '0';
                str[p1--] = '2';
                str[p1--] = '%';
            }else{
                str[p1--] = str[p2];
            }
            p2--;
        }
	}
};

数据结构-链表

从头到尾打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

一开始我写成了不能开辟额外空间的链表反转

这种情况一定要问清楚，可不可以改变原链表的形状

时间复杂度\(O(n)\)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
         vector<int> ans;
        if(head == NULL) return ans;
        ListNode *preNode = NULL,*nowNode = head,*tmpNode = NULL;
        while(nowNode->next){
            tmpNode = nowNode->next;
            nowNode -> next = preNode;
            preNode = nowNode;
            nowNode = tmpNode;
        }
        nowNode -> next = preNode;
        while(nowNode){
            ans.push_back(nowNode->val);
            nowNode = nowNode -> next;
        }
        return ans;
    }
};

但是这种题已经要求了用数组存，那就可以用更简单更快的方法

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
         vector<int> ans;
        if(head == NULL) return ans;
        ListNode *nowNode = head;
        int listLength = 0;
        while(nowNode){
            ans.push_back(nowNode->val);
            nowNode = nowNode ->next;
            listLength++;
        }
        for(int i = 0;i < listLength/2;++i){
            swap(ans[i],ans[listLength-i-1]);
        }
        return ans;
    }
};

翻转可以当作以中间的数作为根节点，然后左右子树交换。

除此之外还可采用栈的方法。

数据结构-树

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

前序遍历找根，然后中序遍历根的两侧就是子树

先确定子树的范围，然后先左子树再右子树地确定根

class Solution {
private:
     map<int,int>posTable;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return NULL;
        int n = preorder.size(),k=0;
        for(int i = 0;i < n;++i){
            posTable[inorder[i]] = i;
        }
        return build(preorder,inorder,0,n-1,k);
    }
    TreeNode* build(const vector<int>& preorder,const vector<int>& inorder,int l,int r,int& pos){
        if(l>r) return NULL;
        int p = posTable[preorder[pos++]];
        TreeNode *node = new TreeNode(inorder[p]);
        node ->left = build(preorder,inorder,l,p-1,pos);
        node -> right = build(preorder,inorder,p+1,r,pos);
        return node;
    }
};

如果要求不能用map，那就只能遍历l到r找根点了

二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

这道题就是模拟，这个点的下一个结点不能简单认为就是右结点，应该是右结点的左链的最深结点。如果没有右结点，也不能随意认为是父节点。如果该点是左儿子答案就是父节点，如果是右儿子答案得看父亲的父亲。

画个图就明白了

class Solution {
private:
    bool getNext(TreeLinkNode* pNode){
        return pNode == pNode -> next -> left;
    }
    TreeLinkNode* findLeft(TreeLinkNode* pNode){
        while(pNode -> left != NULL){
            pNode = pNode -> left;
        }
        return pNode;
    }
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode){
        if(pNode == NULL) return pNode;
        if(pNode -> right != NULL) return findLeft(pNode -> right);
        if(pNode -> next != NULL){
            if(getNext(pNode)){
                return pNode -> next;
            }else{
                if(getNext(pNode->next)) return pNode ->next ->next;
                else return NULL;
            }
        } 
        return NULL;
    }
};

数据结构-栈和队列

用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

用栈可以实现数组翻转

可以翻转输出到另外一个栈

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(!stack2.empty()) {
            int val = stack2.top();
            stack2.pop();
            return val;
        }
        else {
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            int val = stack2.top();
            stack2.pop();
            return val;
        }
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

算法和数据操作-递归和循环

斐波那契数列

如果希望代码简介，直接递归即可

但是那效率太低了

所以采用循环

class Solution {
    private:
    const int mod = 1e9+7;
public:
    int fib(int n) {
        int fibNMinusOne = 1;
        int fibNMinusTwo = 0;
        if(n == 0) return fibNMinusTwo;
        if(n == 1) return fibNMinusOne;
        for(int i = 2;i <= n;++i){
            fibNMinusTwo = (fibNMinusOne + fibNMinusTwo)%mod;
            swap(fibNMinusTwo,fibNMinusOne);
        }
        return fibNMinusOne;
    }
};

本题还有矩阵快速幂的做法

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

这题是斐波那契的简单运用。

无非是这个递推式：dp[n]=dp[n-1]+dp[n-2]可以由上一个台阶或上两个台阶的方案数转移过来

算法和数据操作-排序和查找

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

一个比较特别的二分，就是跟以前在单调递增的二分不一样

二分边界条件怎么确定？要明白一点：(l+r)>>1取到的是l

如果答案是3，此时l为2，r为3，那么答案就是mid+1

如果l为3，r为4，那么答案就是mid

其中有重复的，那就要去重

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

算法和数据操作-回溯法

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

要注意这题不能用广搜，因为是求一整条路径

class Solution {
    private:
    vector<vector<bool> >isVisit;
    int rows,cols;
public:
    bool exist(vector<vector<char>>& board, string word){
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        rows = board.size();
        cols = board[0].size();
        for(int i=0;i<rows;++i){
            isVisit.push_back(vector<bool>());
            for(int j=0;j<cols;++j){
                isVisit[i].push_back(0);
            }
        }
        bool isFound = 0;
        for(int i = 0;i < rows;++i){
            for(int j = 0;j < cols;++j){
                if(board[i][j] == word[0]){
                    isVisit[i][j] = 1;
                    isFound |= dfs(i,j,1,word,board,dx,dy);
                    isVisit[i][j] = 0;
                }
            }
        }
        return isFound;
    }
    inline bool check(int row,int col){
        if(row >= 0 && row < rows && col >= 0 && col < cols){
             if(isVisit[row][col] == 0){
                 return true;
             }
             return false;
        }
        return 0;
    }
    bool dfs(int row,int col,int pos,const string &word,const vector<vector<char>>& board,int dx[],int dy[]){
        bool isFound = 0;
        if(pos == word.size()) return true;
        for(int i=0;i<4;++i){
            if(check(row+dx[i],col+dy[i])){
                    if(board[row + dx[i]][col + dy[i]] == word[pos]){
                    isVisit[row + dx[i]][col + dy[i]] = 1;
                    isFound = dfs(row + dx[i],col + dy[i],pos + 1,word,board,dx,dy);
                    isVisit[row + dx[i]][col + dy[i]] = 0;
                    if(isFound) break;
                }
            }
        }
        if(isFound) return true;
        return false;
    }
};

可以加一个优化，其实vis是没有必要的，可以直接修改board

机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

dfs搜一遍就行,就是搜索求连通块

class Solution {
private:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool> >isVisit(m,vector<bool>(n,0));
        return dfs(0,0,m,n,k,isVisit);
    }
    inline bool check(int row,int col,int &m,int &n,int &k, vector<vector<bool> >&isVisit){
        if(row >= 0 && row < m && col >= 0 && col < n){
            if(isVisit[row][col] == 0){
                if(getNSum(row)+getNSum(col) <= k) return true;
            }
            return false;
        }
        return false;
    }
    inline int getNSum(int num){
        int res = 0;
        while(num){
            res += num%10;
            num/=10;
        }
        return res;
    }
    int dfs(int row,int col,int &m,int &n,int &k, vector<vector<bool> >&isVisit){
        int sum = 1;
        isVisit[row][col] = 1;
        for(int i = 0;i < 4;++i){
            if(check(row + dx[i],col + dy[i],m,n,k,isVisit)){
                sum += dfs(row + dx[i],col + dy[i],m,n,k,isVisit);
            }
        }
        return sum;
    }
};

算法和数据操作-动态规划和贪心策略

剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0] * k[1] * ... * k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

• 动态规划做法

f[n] = max(f[n-i]*f[i])

但是要特判一下前几个，如果说\(m\)可以为1，那么1，2，3都可以不减。然而\(m>1\)

class Solution {

public:
    int cuttingRope(int n) {
        if(n < 2) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int *dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4;i<=n;++i){
            dp[i] = 0;
            for(int j = 1;j <= i/2;++j){
                dp[i] = max(dp[i],dp[j]*dp[i-j]);
            }
        }
        int maxx = dp[n];
        delete []dp;
        return maxx;
    }
};

• 贪心做法

优先取3，否则取2

证明：3(n-3)>n 2(n-2)>n 3(n-3)>2(n-2)在\(n\geq 5\) 成立

同时：\(3(n-3)<4(n-4)\)在\(n>7\)的时候成立，但其实是f(4)*f(3)

如果绳长为4,那应该采用取2的做法；

class Solution {

public:
    int cuttingRope(int n) {
        if(n < 2) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        
        int timesOf3 = n/3;
        if(n - timesOf3*3 == 1){
            timesOf3--;
        }
        int timesOf2 = (n - timesOf3*3) >> 1;
        return (int)pow(3,timesOf3)*(1 << timesOf2);
    }
};

算法和数据操作-位运算

二进制中1的个数

n&(-n)代表的是最后一个1的位置

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
        while(n){
            ans++;
            n -= n&(-n);
        }
        return ans;
    }
};

高质量的代码-代码的完整性

数值的整数平方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

要注意数据范围，n可能为负数，然后这题要用快速幂

我一开始当n为负数的时候取反然后再乘，这个想法没问题

但是，如果\(n=-2^{31}\)会怎么样？

取反会溢出，炸Int

不管n是正数还是负数，都可以用快速幂，因为奇偶不分正负。

就是不能再用n>>=1

class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1.0;
        if(n == 0) ans = 1.0;
        else if(n > 0){
           ans = qpow(x,n);
        }else{
          // n = n+1;
           ans = qpow(x,n);
           ans = 1.0/ans;
        }
        return ans;
    }
    inline double qpow(double x,int n){
        double res = 1.0;
        while(n){
            if(n&1) res = res * x;
            x = x * x;
            n/=2;
        }
        return res;
    }
};

打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

\(n\)可能很大的话，就采用大数加法的写法。

有一个注意的地方，就是判断是否到最大值那里，如果一直用strcmp来与最大值进行比较，每次比较的复杂度都是\(O(n)\)的，这样不可取。

有两种方法优化：

• 如果\(i=0\)的时候还有进位，那就到达最大值了
• 可以算出总共有多少个数，然后for就行

class Solution {
public:
    vector<int> printNumbers(int n) {
        char *number = new char[n+1];
        vector<int> ans;
        memset(number,'0',n);
        number[n] = '\0';
        while(!checkNumber(number,n)){
            ans.push_back(changeNumber(number,n));
        }
        return ans;
    }
    int changeNumber(char *number,int n){
        int res = 0;
        for(int i = 0;i < n;++i){
            res = res*10 + number[i]-'0';
        }
        return res;
    }
    bool checkNumber(char *number,int n){
        int nLength = n;
        bool isOverFlow = 0;
        int isTakeOver=1;
        for(int i = nLength - 1;i >= 0;--i){
            number[i] = number[i] + isTakeOver;
            if(number[i] > '9'){
                if(i == 0) {
                    isOverFlow = 1;
                    break;
                }
                number[i] = '0';
                isTakeOver = 1;
            }else{
                isTakeOver = 0;
            }
        }
        return isOverFlow;
    }
};

还有一种全排列的写法：

class Solution {

public:
    vector<int> printNumbers(int n) {
        char *str = new char[n+1];
        vector<int>ans;
        dfsChooseNum(0,n,str,ans);
        return ans;
    }
    void dfsChooseNum(int pos,const int& n,char* now,vector<int>& ans){
        if(pos == n){
            int res = 0;
            for(int i = 0;i < n;++i){
                res = res*10 + now[i] - '0';
            }
            if(res) ans.push_back(res);
            return;
        }
        for(int i=0;i<=9;++i){
            now[pos] = '0' + i;
            dfsChooseNum(pos+1,n,now,ans);
        }
    }
};

删除链表的结点

链表模拟题

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* toDeleteNode = NULL,*preNode = NULL;
        for(ListNode* now = head;now != NULL;now = now -> next){
            if(now->val == val){
                toDeleteNode = now;
                break;
            }
            preNode = now;
        }
        if(preNode != NULL){
            preNode -> next = toDeleteNode -> next;
             delete toDeleteNode;
        }
        else {
            head = toDeleteNode -> next;
        }
        return head;
    }
};

正则表达式匹配

请实现一个函数用来匹配包含'. '和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

这是一个有限自动机

• 当前状态匹配：
  • 判断下一个是不是'*'，如果是
    • 可能含义是出现0次，那这次匹配就不算，str不移动，匹配串右移2（*不参与匹配）
    • 可能含义是出现1次，那这次匹配算，str右移1，匹配串右移2
    • 可能含义是出现n次，那这次匹配算，str右移1，匹配串不移动
  • 不是'*'，str右移1，匹配串右移1
• 当前状态不匹配：
  • 判断下一个是不是'*'：如果是，就把'*'当做出现0次，这次匹配不算
  • 不是'*'，返回false
• 终止状态：两个串同时为'\0'返回true，如果匹配串为空而str不为空，返回false
• 注意，并不是str为空就终止，可能匹配串是'a*'这类

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.size() == 0&&p.size() == 0){
            return true;
        }
        char *str = s.data(),*pattern = p.data();
        return matchState(str,pattern);
    }
    bool matchState(char *str,char *pattern){
        if(*str == '\0' && *pattern == '\0') return true;
        if(*str != '\0' && *pattern == '\0') return false;

        if(*pattern == *str ||(*pattern == '.' && *str != '\0')){
            if(*(pattern + 1) != '*'){
                return matchState(str + 1,pattern + 1);
            }else{
                return matchState(str,pattern + 2)||//0
                       matchState(str + 1,pattern + 2)||//next state
                       matchState(str + 1,pattern);//ignore
            }
        }
        
        if(*(pattern + 1) == '*'){
            return matchState(str,pattern + 2);
        }

        return false;
    }
};

动态规划做法

回溯的做法是向前推导，看当前状态能转移到哪些状态，再回溯

动态规划的做法就是当前的状态是考虑当前状态是怎么得出的

样例测试：

1. aaa a**

2. aaa a.*

3. b a*

class Solution {
public:
    bool isMatch(string s, string p) {
        int sLength = s.size() , pLength = p.size();
        bool dp[sLength + 1][pLength + 1];

        memset(dp,0,sizeof(dp));
        dp[0][0] = true;
        for(int i = 2;i <= pLength;++i){
            if(p[i-1] == '*' && dp[0][i-2] == true){
                dp[0][i] = true;
            }
        }

        for(int i = 1;i <= sLength;++i){
            for(int j = 1;j <= pLength;++j){
                if(s[i-1] == p[j-1] || p[j - 1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p[j - 1] == '*'){
                    dp[i][j] = dp[i][j-1]||dp[i][j-2]||(dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2]=='.'));
                }else dp[i][j] = false;
            }
        }

        return dp[sLength][pLength] == 1;
    }
};

表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

一个很恶心的模拟

根据数据来敲代码还是不难的

按照状态的顺序来执行

class Solution {
public:
    bool isNumber(string s) {
        char *str = s.data();
        checkSpace(str);
        bool flag = checkNumber(str);
        if(!flag) return false;
        if(*str == 'e'){
            ++str;
            if(*str == '\0') return false;
            flag = checkInteger(str);
            if(!flag) return false;
        }
       return checkTail(str);
    }
    bool checkNumber(char* &str){
        if(*str == '+' || *str == '-') ++str;
        return checkNum1(str);
    }
    bool checkInteger(char* &str){
        if(*str == '+'||*str == '-') ++str;
        return checkNum2(str);
    }
    bool checkNum1(char* &str){
        bool flag = 0;
        while(isdigit(*str)) ++str,flag = 1;
        if(*str == '.') ++str;
        while(isdigit(*str)) ++str,flag = 1;
        return flag;
    }
     bool checkNum2(char* &str){
        bool flag = 0;
        while(isdigit(*str)) ++str,flag = 1;
        return flag;
    }
    void checkSpace(char* &str){
        while(*str == ' ') ++str;
    }
    bool checkTail(char* &str){
         checkSpace(str);
        if(*str == '\0') return true;
        return false;
    }
};

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

reverse就一定要想到交换

双指针，两个指针外的都是满足题意的

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int lastNums = nums.size() - 1;
        int firstNums = 0;
        while(firstNums < lastNums){
            if(!(nums[lastNums]&1)) lastNums--;
            else if(nums[firstNums]&1) firstNums++;
            else{
                swap(nums[firstNums],nums[lastNums]);
                firstNums++;
                lastNums--;
            }
        }
        return nums;
    }
};

高质量的代码-代码的鲁棒性

链表中倒数第k个节点

快慢指针

这样就只用遍历一次

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *pFirst = head ,*pSecond = head;
        if(pFirst == NULL) return pFirst;
        short pCount = 1;
        while(pSecond ->next != NULL){
            if(pCount >= k){
                pFirst = pFirst ->next;
            }
            pSecond = pSecond -> next;
            pCount++;
        }
        if(pCount < k) return NULL;
        return pFirst;
    }
};

反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL,*now = head,*tmp = NULL;
        if(now == NULL) return now;
        while(now -> next != NULL){
            tmp = now -> next;
            now -> next = pre;
            pre = now;
            now = tmp;
        }
        now -> next = pre;
        return now;
    }
};

合并两个排序的链表

类似于归并排序中的合并，加了个头结点让编程更舒服

如果不能用的话，那就要记录一下第一个节点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* lastNode = head;
        while(l1 != NULL && l2 != NULL){
            if(l1 -> val <= l2 -> val){
                lastNode -> next = l1;
                l1 = l1 -> next;
            }else{
                lastNode -> next = l2;
                l2 = l2 -> next;
            }
            lastNode = lastNode -> next;
        }
        if(l1 != NULL){
            lastNode -> next = l1;
        }
        if(l2 !=NULL){
            lastNode -> next = l2;
        }
        return head -> next;
    }
};

树的子结构

前序遍历暴力判断

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL) return false;
        bool flag = 0;
        preOrder(A,B,flag);
        return flag;
    }
    void preOrder(TreeNode *a,TreeNode *b,bool& flag){
        if(a -> val == b -> val){
            flag |= check(a,b);
        }
        if(a -> left)  preOrder(a -> left,b,flag);
        if(a -> right) preOrder(a -> right,b,flag);
    }
    bool check(TreeNode *a,TreeNode *b){
        if(a -> val != b -> val) return false;
        if(b->right != NULL){
            if(a -> right == NULL) return false;
            return check(a -> right,b -> right);
        }
        if(b->left != NULL){
            if(a -> left == NULL) return false;
            return check(a -> left,b -> left);
        }
        return true;
    }
};

后来我想了一下，我觉得后序遍历应该更快一定

继承了子树的答案，如果正确那就直接更新

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL || B == NULL) return false;
        return behindOrder(A,B);
    }
    bool behindOrder(TreeNode *a,TreeNode *b){
        if(a -> left)   if(behindOrder(a -> left,b)) return true;
        if(a -> right)  if(behindOrder(a -> right,b)) return true;
        if(a -> val == b -> val){
            if(check(a,b)) return true;
        }
        return false;
    }
    bool check(TreeNode *a,TreeNode *b){
        if(a -> val != b -> val) return false;
        if(b->right != NULL){
            if(a -> right == NULL) return false;
            return check(a -> right,b -> right);
        }
        if(b->left != NULL){
            if(a -> left == NULL) return false;
            return check(a -> left,b -> left);
        }
        return true;
    }
};

解决面试题的思路-画图让抽象问题形象化

二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

4

/
2 7
/ \ /
1 3 6 9
镜像输出：

4

/
7 2
/ \ /
9 6 3 1

左右子树交换

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL) return root;
        preOrder(root);
        return root;
    }
    void preOrder(TreeNode* root){
        if(root -> left) preOrder(root -> left);
        if(root -> right) preOrder(root -> right);
        if(root -> left ==NULL && root -> right == NULL) return;
        swap(root -> left,root -> right);
    }
};

对称的二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return preOrder(root,root);
    }
    bool preOrder(TreeNode *a,TreeNode *b){
        if(a == NULL && b == NULL) return true;
        if(a == NULL || b == NULL) return false;
        if(a -> val != b -> val) return false;
        return preOrder(a -> left,b -> right) && preOrder(a -> right,b -> left);
    }
};

顺时针打印矩阵

设定上下左右限制，每次都是遍历边上的

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty()) return ans;
        if(matrix[0].empty()) return ans;
        int rows = matrix.size(),cols = matrix[0].size(); 
        int left = 0 ,right = cols - 1,up = 0,down = rows -1;
        int num = rows*cols;
        while(true){
            int i;
            for(i=left;i<=right;++i) ans.push_back(matrix[up][i]);
            up++;
            if(up>down) break;
            for(i=up;i<=down;++i) ans.push_back(matrix[i][right]);
            right--;
            if(right<left) break;
            for(i=right;i>=left;--i) ans.push_back(matrix[down][i]);
            down--;
            if(down<up) break;
            for(i=down;i>=up;--i) ans.push_back(matrix[i][left]);
            left++;
            if(left>right) break;
        }
        return ans;
    }
};

解决面试题的思路-举例让抽象问题具体化

包含min函数的栈

我写了个动态数组2333

如果要求min必须是\(O(1)\)需要用一个辅助数组

class MinStack {
private:
int Size;
int *numStack,*minStack,*tmpStack1,*tmpStack2;
int tail;
public:
    /** initialize your data structure here. */
    MinStack() {
        Size = 1;
        numStack = new int[Si***Stack = new int[Size];
        tail = -1;
    }
    
    void push(int x) {
        tail++;
        if(tail == Size){
            Size <<= 1;
            tmpStack1 = new int[Size];
            tmpStack2 = new int[Size];
            for(int i = 0;i < tail;++i){
                tmpStack1[i] = numStack[i];
                tmpStack2[i] = minStack[i];
            }
            std::swap(tmpStack1,numStack);
            std::swap(tmpStack2,minStack);
            delete []tmpStack1;
            delete []tmpStack2;
        }
        numStack[tail] = x;
        if(tail == 0) minStack[tail] = x;
        else minStack[tail] = std::min(x,minStack[tail-1]);
    }
    
    void pop() {
        tail--;
    }
    
    int top() {
        return numStack[tail];
    }
    
    int min() {
        return minStack[tail];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

想好再写，思路清晰

要举出几个例子

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty()) return true;
        int stackLen = pushed.size();
        int *tmpStack = new int[stackLen],tmpLen = 0,popPos = 0;
        for(int i = 0;i < stackLen; ++i){
            tmpStack[tmpLen++] = pushed[i];
            while(tmpLen&&tmpStack[tmpLen - 1] == popped[popPos]){
                tmpLen--;
                popPos++;
            }
        }
        delete []tmpStack;
        return tmpLen == 0;
    }
};

从上到下打印出二叉树

• 考察广搜

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

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

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        std::queue<TreeNode*> printQue;
        vector<vector<int> >ans;
        if(root == NULL) return ans;
        printQue.push(root);
        while(!printQue.empty()){
            vector<int>cnt;
            int Size = printQue.size();
            while(Size--) {
                TreeNode* tmp = printQue.front();
                printQue.pop();
                cnt.push_back(tmp -> val);
                if(tmp -> left) printQue.push(tmp -> left);
                if(tmp -> right) printQue.push(tmp -> right);
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

可以按照上面的做法，然后reverse

更高效率的是用栈和队列，或者双端队列模拟

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        std::stack<TreeNode*> printStk;
        queue<TreeNode*>printQue;
        vector<vector<int> >ans;
        if(root == NULL) return ans;
        printStk.push(root);
        bool flag = 0;
        while(!printStk.empty()){
            vector<int>cnt;
            while(!printStk.empty()) {
                TreeNode* tmp = printStk.top();
                printStk.pop();
                printQue.push(tmp);
                cnt.push_back(tmp -> val);
            }
            while(!printQue.empty()) {
                TreeNode* tmp = printQue.front();
                 printQue.pop();
                 if(!flag){
                    if(tmp -> left) printStk.push(tmp -> left);
                    if(tmp -> right) printStk.push(tmp -> right);
                 }else{
                     if(tmp -> right) printStk.push(tmp -> right); 
                     if(tmp -> left) printStk.push(tmp -> left);
                 }
            }
            flag ^= 1;
            ans.push_back(cnt);
        }
        return ans;
    }
};

解决面试题的思路-分解让复杂问题简单化

复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

可以用哈希的方法

但这种方法浪费空间，更好的方法是在原来的基础上修改

需要复制某个结点，val和next好复制，random不好复制

必须要新旧结点建立某种联系就好办了,因为我想马上知道一个结点的另一个copy结点，那就先将copy结点插入到原链表中。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return head;
        Node* nowNode = head;
        while(head != NULL){
            Node* newNode = new Node(head -> val);
            newNode -> next = head -> next;
            head -> next = newNode;
            head = newNode -> next;
        }
        head = nowNode;
        while(head != NULL){
            if(head -> random != NULL) head -> next -> random = head -> random -> next;
            head = head ->next -> next;
        }
        head = nowNode;
        Node *newHead = NULL;
        while(head != NULL){
            nowNode = head -> next;
            head -> next = nowNode ->next;
            if(newHead == NULL){
                newHead = nowNode;
            }
            if(head -> next != NULL) nowNode -> next = head -> next ->next;
            head = head -> next;
        }
        return newHead;
    }
};

二叉搜索树与双向链表

把二叉搜索树转为双向链表

做法其实就是中序遍历

记录一下中序遍历上一个访问的结点

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        Node* head = NULL,*tail = NULL;
        if(root == NULL) return head;
        change(root,tail,head);
        head -> left = tail;
        tail -> right = head;
        Node *nowhead = head;
        return head;
    }
    void change(Node* now,Node* &last,Node* &head){
        if(now -> left) change(now ->left,last,head);

        if(last != NULL){
            last -> right = now;
            now -> left = last;
        }
        else head = now;
        last = now;

        if(now->right) change(now -> right,last,head);
    } 
};

序列化二叉树

按照层序遍历来序列化。

stringstream可以关注一下

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* tmp = q.front();
            q.pop();
            if (tmp) {
                out<<tmp->val<<" ";
                q.push(tmp->left);
                q.push(tmp->right);
            } else {
                out<<"null ";
            }
        }
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string val;
        vector<TreeNode*> vec;
        while (input >> val) {
            if (val == "null") {
                vec.push_back(NULL);
            } else {
                vec.push_back(new TreeNode(stoi(val)));
            }
        }
        int j = 1;                                          // i每往后移动一位，j移动两位，j始终是当前i的左子下标
        for (int i = 0; j < vec.size(); ++i) {              // 肯定是j先到达边界，所以这里判断j < vec.size()
            if (vec[i] == NULL) continue;                   // vec[i]为null时跳过。
            if (j < vec.size()) vec[i]->left = vec[j++];    // 当前j位置为i的左子树
            if (j < vec.size()) vec[i]->right = vec[j++];   // 当前j位置为i的右子树
        }
        return vec[0];
    }

};

字符串的排列

将问题分解为当前字符与后面的字符，接下来就是求后面字符的排列。

 *  [a, [b, c]]
 * [b, [a, c]] [c, [b, a]]
 *
 * 如上，对字符串"abc"分割，每次固定一个字符为一部分，
 * 其他字符为另一部分，再将固定字符与其他字符进行交换，
 * 依次遍历每个字符，再进行回溯递归。

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        if(s.size() == NULL) return ans;
         map<string,bool>mp;
        dfs(mp,ans,s,0);
        return ans;
    }
    void dfs(map<string,bool>& mp,vector<string>&ans,string& a,int pos){
        if(pos == a.size()){
            if(mp.count(a) == 0) {
                ans.push_back(a);
                mp[a] = 1;
            }
            return;
        }
        for(int i = pos;i < a.size();++i){
            swap(a[pos],a[i]);
            dfs(mp,ans,a,pos+1);
            swap(a[i],a[pos]);
        }
    }
};

优化时间和空间效率-时间效率

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

可以用哈希表

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int>table;
        int maxx = 0,t =1,tmp;
        for(int x:nums){
            table[x]++;
            tmp = table[x];
            if(tmp>maxx){
                maxx = tmp;
                t = x;
            }
        }
        return t;
    }
};

但其实有更加高效的做法，因为次数超过一半，这个数列可以分解为等于众数的和不等于众数的

两两抵消，多出来的一定是众数

关注一下摩尔投票

最小的k个数

大根堆

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int>que; vector<int>vt;
        if(!k) return vt;
        for(int x:arr){
           if(que.size() < k) que.push(x);
           else if(x < que.top()){
               que.pop();
               que.push(x);
           }
        }
       
        while(!que.empty()){
            vt.push_back(que.top());
            que.pop();
        }
        return vt;
    }
};

数据流中的中位数

一种方法是维护两个堆，一个是大根堆，一个是小根堆

关键是大根堆的大小与小根堆的差距不超过1

并且小根堆的值一定比大根堆大

class MedianFinder {
private:
    priority_queue<int>queL;
    priority_queue<int,vector<int>,greater<int> >queR;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(queL.size() <= queR.size()){
            queL.push(num);
        }else{
            queR.push(num);
        }

        if(queL.empty() || queR.empty()) return;

        if(queL.top()>queR.top()){
            int x = queL.top();
            queL.pop(); 
            queR.push(x);

            x = queR.top(); 
            queR.pop();
            queL.push(x);
        }
    }
    
    double findMedian() {
        if((queL.size()+queR.size())&1){
            return queL.top()*1.0;
        }else{
            return (queL.top() + queR.top())/2.0;
        }
    }
};

连续子数组的最大和

动态规划

当前的最优解：如果加上前面的和比本身要小，那就不要加，从这个位置重新开始

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0],len = nums.size();
        for(int i=1;i<len;++i){
            nums[i] += max(0,nums[i-1]);
            ans = max(nums[i],ans);
        }
        return ans;
    }
};

1-n整数中1出现的次数

从最高位考虑，分为最高位中的1和其他位上1

举例的方法： 23456

最高位是1的为[10000,19999]一共是20000个

然后再考虑大于3456的1出现个数

可分为[3457,9999]∪[20000,23456] 和[10000,19999]两个区间

然后在4位中选择1位是1，其余位随便。排列组合：\(2*4*10^3\)

class Solution {
public:
    int countDigitOne(int n) {
        return solve(n);
        
    }
    int solve(int n){
        string str = to_string(n);

        int highNum = str[0] - '0'; 
         int strLen = str.size();
        if(strLen == 1 && highNum == 0) return 0;
        if(strLen == 1 && highNum > 1) return 1;

       
        int withoutHigh = n - highNum * pow(10,strLen-1);
       
        int ans = 0;
        if(highNum > 1){
            ans += pow(10,strLen - 1);
        }else if(highNum == 1){
            ans += withoutHigh + 1;
        }

        ans += highNum * (strLen -1) *pow(10,strLen -2);
        return ans += solve(withoutHigh);

    } 
};

还有找规律的方法：

https://blog.csdn.net/qq_22873427/article/details/78159057

数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

找规律的题目，要找到属于哪个区间

按照位数来划分区间

class Solution {
public:
    int findNthDigit(int n) {
        if(n == 0) return 0;
        n--;
        long long k = 9,x = 1,cnt = 1;
        while(n > x*k){
            n -= k*x;
            x++;
            k*=10;
            cnt *= 10;
        }
        int p = cnt + n/x;
        string str = to_string(p);
        return str[n%x] - '0'; 
    }
};

把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

直接排序就可。但是有个问题就是并不是字典序最小的放在前面最优：3，30

所以在cmp函数里可以这么用：return a+b<b+a

记得cmp前面要加static

理由：https://blog.csdn.net/qq_43827595/article/details/104242037

class Solution {
public:
    static bool cmp(const string &x,const string &y){
        return x + y < y + x;
    }
    string minNumber(vector<int>& nums) {
        vector<string>vt;
        for(int x:nums){
            vt.push_back(to_string(x));            
        }
        sort(vt.begin(),vt.end(),cmp);
        string ans;
        for(string x:vt){
            ans += x;
        }
        return ans;
    }
};

礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

最基本的那种dp

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int rows = grid.size(),cols = grid[0].size();
        for(int i = 0;i < rows;++i){
            for(int j = 0;j < cols;++j){
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] += grid[i][j-1];
                else if(j == 0) grid[i][j] += grid[i-1][j];  
                else grid[i][j] = max(grid[i-1][j],grid[i][j-1]) + grid[i][j];
            }
        }
        return grid[rows-1][cols-1];
    }
};

把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

一个简单dp

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int strLen = s.size();
        int *dp = new int[strLen]{0};
        dp[0] = 1;
        for(int i=1;i<strLen;++i){
            if(s[i-1]!='0'&&(s[i-1]-'0')*10+s[i]-'0' < 26){
                if(i == 1) dp[i] = 2;
                else dp[i] = dp[i-1] + dp[i-2];
            }else{
                dp[i] = dp[i-1];
            }
        }
        return dp[strLen - 1];
    }
};

最长不含重复字符的子字符串

用一个滑动窗口来模拟一个双端队列

队列里面维护的是一个没有重复字符的字符串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int sLength = s.size(),ans=0;
        if(sLength == 0) return 0;
        int *que = new int [sLength]{0},head =0,tail=0;
        bool *vis = new bool[256]{0};
        for(int i = 0;i<sLength;++i){
            if(vis[s[i]] == 0){
                que[tail++] = s[i];
                vis[s[i]] = 1;
            }else{
                while(head < tail && que[head] != s[i]){
                    vis[que[head]] = 0;
                    head++;
                }
                head++;
                que[tail++] = s[i];
            }
            ans = max(ans,tail-head);
        }
        return ans;
    }
};

优化时间和空间效率-时间效率与空间效率的平衡

丑数

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

可以发现每个丑数都是比它前面每个丑数x2x3x5得来的

class Solution {
public:
    int nthUglyNumber(int n) {
        int *dp = new int[n]{0},p2 = 0,p3 = 0,p5 = 0;
        dp[0] = 1;
        for(int i = 1;i < n;++i){
            dp[i] = min(min(dp[p2]*2,dp[p3]*3),dp[p5]*5);
            if(dp[i] == dp[p2]*2) p2++;
            if(dp[i] == dp[p3]*3) p3++;
            if(dp[i] == dp[p5]*5) p5++;
        }
        return dp[n - 1];
    }
};

其实这个方法有些难想到，可以采用队列的方法，用三个队列，这样就可以避免重复

第一个只出现一次的字符

哈希map水题

class Solution {
public:
    char firstUniqChar(string s) {
        int *hashTable = new int[256]{0};
        if(s =="") return ' ';
        int strLen = s.size();
        for(int i=0;i<strLen;++i){
            hashTable[s[i]]++;
        }
        for(int i = 0;i<strLen;++i){
            if(hashTable[s[i]] == 1){
                return s[i];
            }
        }
        return ' ';
    }
};

数组中的逆序对

直接归并排序

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int numsLength = nums.size();
        int ans = 0;
        vector<int>tmp(numsLength);
        Msort(0,numsLength - 1,nums,ans,tmp);
        return ans;
    }
    void Msort(int l,int r,vector<int>& nums,int &ans,vector<int>& tmp){
        if(l == r) return;
        int mid = (l+r) >> 1;
        Msort(l,mid,nums,ans,tmp);
        Msort(mid + 1,r,nums,ans,tmp);
        Megre(l,r,nums,ans,tmp);
    }
    void Megre(int l,int r,vector<int>& nums,int &ans,vector<int>& tmp){
        int mid = (l+r) >> 1,i = l,j = mid + 1,p = l;
        while(i <= mid && j <= r ){
            if(nums[i] <= nums[j]) {
                tmp[p++] = nums[i++];
            }else{
                ans += mid - i + 1;
                tmp[p++] = nums[j++];
            }
        }
       while(i <= mid){
           tmp[p++] = nums[i++];
       } 
       while(j <= r){
           tmp[p++] = nums[j++];
       }
       for(int k=l;k<=r;++k) nums[k] = tmp[k];
    }
};

两个链表的第一个公共结点

求出两个长度就好做了

其实还可以用双指针O(n+m)的方法

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr) return nullptr;
        int lenA = getLen(headA),lenB = getLen(headB);
        while(headA != nullptr && headB != nullptr){
            if(lenA > lenB) headA = headA -> next,lenA--;
            else if(lenA <lenB) headB = headB -> next,lenB--;
            else{
                if(headA == headB) return headA;
                headA = headA -> next;
                headB = headB -> next;
            }
        }
        return nullptr;
    }
    inline int getLen(ListNode* head){
        int ans = 0;
        while(head != nullptr){
            ans++;
            head = head -> next;
        }
        return ans;
    }
};

面试中的各项能力-知识迁移能力

在排序数组中查找数字

直接二分

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int l = 0,r = len - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] >= target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        int ans = 0;
        while(l < len && nums[l] == target){
            ans++;
            l++;
        }
        return ans;
    }
};

0 - n-1中缺失的数字

二分的条件为是否前面包括自己已经出现了缺失

前0后1查找最小的1

class Solution {
public:
    int missingNumber(vector<int>& nums) {
       int len = nums.size();
        int l = 0,r = len - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] != mid){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        if(nums[l] == l) l++;
        return l;
    }
};

二叉搜索树的第k大节点

反过来的中序遍历

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

二叉树的深度

水题

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return dfs(root);
    }
    int dfs(TreeNode* root){
        int dep = 0;
        if(root -> left) dep = max(dep,dfs(root -> left));
        if(root -> right) dep = max(dep,dfs(root -> right));
        return dep + 1; 
    }
};

平衡二叉树

然鹅这题只是判断一下是不是平衡二叉树

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return 1;
        bool flag = 1;
        dfs(root,flag);
        return flag;
    }
     int dfs(TreeNode* root,bool &flag){
        int l = 0,r = 0;
        if(root -> left) l = dfs(root -> left,flag);
        if(root -> right) r = dfs(root -> right,flag);
        if(abs(l-r) > 1) flag = 0;
        return max(l,r) + 1; 
    }
};

数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

如果只出现一次，那么其实可以采用异或和的方法

现在出现两次，异或和之后得到的值是两个数的异或和

然后找到第一个异或和二进制位上的某个1，1代表的是这两个数不同的地方

然后再将这个数组分类

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xorSum = 0,lorSum = 0,rorSum = 0,k = 0,numsLen = nums.size();
        for(int i = 0;i<numsLen;++i){
            xorSum ^= nums[i];
        }
        while(xorSum % 2 == 0) k++,xorSum >>= 1;
        for(int i = 0;i<numsLen;++i){
            if((nums[i]>>k)&1){
                lorSum ^= nums[i];
            }else{
                rorSum ^= nums[i];
            }
        }
        vector<int>ans;
        ans.push_back(lorSum);
        ans.push_back(rorSum);
        return ans;
    }
};

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

按照二进制位，对每个位出现的个数%3

如果是0说明不是这数，否则是

这样的复杂度是O(n)的，空间复杂度O(1);

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int *bit = new int [31]{0},numsLength = nums.size();
        for(int i=0;i<numsLength;++i){
            for(int j = 30;j>=0;--j){
                if((nums[i]>>j)&1) bit[j]++;
            }
        }
        int ans = 0;
        for(int i = 30;i >= 0;--i){
            if(bit[i]%3 != 0){
                ans += 1<<i;
            } 
        }
        delete []bit;
        return ans;
    }
};

和为s的两个数

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

单调性，双指针。

如果此时决策空间里最大的和最小的加在一起比目标大，说明最大的那个会被排除

反之同理

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int firstP = 0,lastP = nums.size() - 1;
        vector<int>ans;
        while(firstP<lastP){
            if(nums[firstP] + nums[lastP] > target){
                lastP--;
            }else if(nums[firstP] + nums[lastP] < target){
                firstP ++;
            }else{
                ans.push_back(nums[firstP]);
                ans.push_back(nums[lastP]);
                break;
            }
        }
        return ans; 
    }
};

和为s的连续正数序列

跟上题一样采用双指针

首先第一个数肯定不可以超过target/2

如果等比数列求和得到的数超过target，那么首项肯定没用了，firstP++

不到的话自然是lastP++

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        long long firstP = 1,lastP = 1;
        long long  len = target/2,sum = 0;
        vector<vector<int> >ans;
        while(firstP <= len){
            sum = (lastP-firstP+1)*firstP + (lastP-firstP+1)*(lastP-firstP)/2;
            if(sum == target) {
                vector<int>tmp;
                for(int i=firstP;i<=lastP;++i){
                    tmp.push_back(i);
                }
                ans.push_back(tmp);
            }
            if(sum <= target){
                lastP++;
            }else {
                firstP++;
            }
        }
        return ans;
    }
};

翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

每个单词翻转一次，然后整体翻转一次

注意它的输入有多余的空格

class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        for (int i = 0; i < s.size(); ++ i){
            while (i < s.size() && s[i] == ' ') ++i;  //找到第一个非空格字符
            if (i == s.size()) break;
            int j = i;
            while (j < s.size() && s[j] != ' ') ++j;    //遍历1个非空单词
            reverse(s.begin() + i, s.begin() + j);      //反转1个单词
            if (k) s[k++] = ' ';
            while (i < j) s[k++] = s[i++];      //反转后的1个单词赋给s[k]
        }
        s.erase(s.begin() + k, s.end());   //删除 k后面的东西
        reverse(s.begin(), s.end());
        return s;
    }
};

左旋转字符串

可以采用取模的方法

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string S = "";
        int len = s.length();
        for(int i = 0; i < len; i++){
            int x = (i + n) % len;
            S += s[x];
        }
        return S;
    }
};

用string模拟

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        for(int i = 0;i<n;++i){
            s += s[i];
        }
        s.erase(s.begin(),s.begin()+n);
        return s;
    }
};

滑动窗口的最大值

维护一个递减队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int numsLen = nums.size();
        int *que = new int[numsLen];
        int head = 0,tail = 0;
        vector<int>ans;
        for(int i=0;i<numsLen;++i){ 
            while(head < tail && nums[que[tail-1]] <= nums[i]) tail--;
            que[tail++] = i;
            while(head < tail && que[head] < i - k + 1) head++;
            if(i >= k - 1) ans.push_back(nums[que[head]]); 
        }
        delete []que;
        return ans;
    }
};

队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

维护一个递减的队列

准确的说是不降的队列

这样就不会删除多了

class MaxQueue {
private:
    queue<int>q;
    deque<int>d;
public:
    MaxQueue() {

    }
    
    int max_value() {
        if(d.empty()) return -1;
        return d.front();
    }
    
    void push_back(int value) {
        while(!d.empty() && d.back() < value){
            d.pop_back();
        }
        d.push_back(value); 
        q.push(value);
    }
    
    int pop_front() {
        if(q.empty()) return -1;
        int val = q.front();
        if(val == d.front()) d.pop_front();
        q.pop();
        return val;
    }
};

面试中的各项能力-建模抽象能力

n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

动态规划，因为只与上一个状态有关，所以可以化为一维的dp

转移也比较简单，枚举当前可能的值

class Solution {
public:
    vector<double> twoSum(int n) {
       int dp[70];
       memset(dp,0,sizeof(dp));
        for(int i = 1;i<=6;++i) dp[i] = 1;
        for(int i = 2;i <= n;++i){
            for(int j = 6*i;j >= i; --j){
                dp[j] = 0;
                for(int z = 1;z<=6;++z){
                    if(j - z < i-1) break;//注意边界
                    dp[j] += dp[j - z]; 
                }
            }
        }
        vector<double>ans;
        double all = pow(6,n);
        for(int i = n;i<=6*n;++i){
            ans.push_back(dp[i]*1.0/all);
        }
        return ans;
    }
};

扑克牌中的顺子

水题

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int k=0;
        for(int i=0;i<5;++i){
            if(nums[i]==0) k++;
        }
        for(int i=0;i<4;++i){
            if(nums[i]!=0){
                if(nums[i+1] == nums[i]) return false;
                if(nums[i+1] != nums[i]+1){
                    k -= nums[i+1]-nums[i]-1;
                }
            }
            if(k<0) return false;
        }
        return true;
    }
};

圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

这是约瑟夫环的模板题

具体证明待更

class Solution {
public:
    int lastRemaining(int n, int m) {
        int flag = 0;   
    for (int i = 2; i <= n; i++) {
        flag = (flag + m) % i;
    }
    return flag;
    }
};

股票的最大利润

贪心水题

得知比当前的价格小就行了

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

面试中的各项能力-发散思维能力

求1+2+...n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

用递归和&&

class Solution {
public:
    int sumNums(int n) {
        n&&(n+=sumNums(n-1));
        return n;
    }
};

不用加减乘除做加法

很明显是二进制瞎搞

两个数取并运算就是进位的数，异或运算就是加之后没有进位的数

循环一下就好了

class Solution {
public:
    int add(int a, int b) {
        while (b) {
            int carry = (unsigned int)(a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};

构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

构造前缀积和后缀积

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        vector<int> ret(n, 1);
        int left = 1;
        for (int i = 0; i < n; i ++) {
            ret[i] = left;
            left = left * a[i];
        } 
        int right = 1;
        for (int i = n-1; i >= 0; i --) {
            ret[i] *= right;
            right *= a[i];
        }
        return ret;
    }
};

把字符串转换成整数

模拟题

class Solution {
public:
    int strToInt(string str) {
        int i=0,len = str.size();
        long long flag = 1;
        while(str[i] == ' ') ++i;
        if(str[i] == '-') flag = -1,++i;
        else if(str[i] == '+') ++i;
        if(!isdigit(str[i])) return 0;
        long long ans = 0;
        while(i < len){
            if(!isdigit(str[i])) break;
            ans = ans * 10 + str[i]-'0';
            if(ans*flag >= INT_MAX) return INT_MAX;
            if(ans*flag <= INT_MIN) return INT_MIN;
            ++i;
        }
        return ans*flag;
    }
};

二叉搜索树的最近公共祖先

因为是二叉搜索树，所以可以充分利用性质

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p == q) return p;
        if(p -> val > q -> val) swap(p,q);
        while(true){
            if(root -> left && root -> val > q -> val){
                root = root ->left;
            }else if(root -> right && root -> val < p -> val ){
                root = root -> right;
            }else{
                return root;
            }
        }
        return nullptr;
    }
};

二叉树的最近公共祖先

在没有指向父亲的指针的情况下，可以采用辅助数组记录路径，因为数都是不同的

也可以采用后序遍历，判断子树是否遍历到相关节点

对于比这两个节点深度浅节点，无非有两种情况。一是这两个节点在同一侧，二是在两侧。

只需后序遍历判断一下左右子树中有无相关节点即可。如果两边都有，那就返回该节点，如果只有一边有，那就返回子树的答案。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return behindOrder(root,p,q);
    }
    TreeNode* behindOrder(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root == p) return root;
        if(root == q) return root;

        TreeNode* l1 = nullptr,*l2 = nullptr;
        if(root -> left) l1 = behindOrder(root -> left,p,q);
        if(root -> right) l2 = behindOrder(root -> right,p,q);

        if(l1 && l2) return root;
        if(l1 != nullptr) return l1;
        if(l2 != nullptr) return l2; 
        return nullptr;
    }
};