剑指Offer的刷题总结。最近LeetCode上下架了该合集，牛客上的合集也开始了收费。所幸各个题目还不收费，在此收集一下，并写一些题解以供复习。

1.二维数组的查找

法一：

从右上往左下找，由于每一行每一列都是递增的，

当前位置小于target， target在下一行，h++。
当前位置大于target， target在这一行，w—。
相等，表示找到了返回true。

class Solution {
public:
    bool Find(int target, vector<vector<int> >& array) {
        if(array.size() == 0 && array[0].size()) return false;
        int row = array.size(), col = array[0].size();
        int h = 0, w = col - 1;
        while(w >= 0 && h < row){
            if(array[h][w] > target) w--;
            else if(array[h][w] < target) h++;
            else return true;
        }
        return false;
    }
};

法二：

不考虑每一列的顺序，只利用每一行的有序性，在每一行中都使用二分法。

class Solution {
public:
    bool hasFound(vector<int> & array,int target){
        int start = 0,end = array.size() - 1;
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(array[mid] < target) start = mid + 1;
            else if(array[mid] > target) end = mid - 1;
            else return true;
        }
        return false;
    }
    bool Find(int target, vector<vector<int> >& array) {
        if(array.size() == 0 || array[0].size() == 0) return false;
        for(int i = 0;i<array.size();i++){
            if(hasFound(array[i],target)) return true;
        }
        return false;
    }
};

2.替换空格

替换空格_牛客题霸_牛客网 (nowcoder.com)

记得当时在Leetcode上做的时候参数是string，牛客是str，不过都一样。

法一：

若参数是string的话还得resize一下，str的话可以直接写，但这样其实本身并不优雅。

class Solution {
public:
	void replaceSpace(char *str,int length) {
		int cnt = 0;
		for(int i = 0;i<length;i++){
			if(str[i] == ' ') cnt++;
		}
		int	totalLength = length + 2* cnt;
		str[totalLength] = '\0';
		for(int i = length,j = totalLength;i>=0 && i != j;i--){
			if(str[i] != ' ') str[j--] = str[i];
			else{
				str[j--] = '0';
				str[j--] = '2';
				str[j--] = '%';
			}
		}
	}
};

其他

如果参数是string的话就方法就更多了。

正则
replace等

3.从尾到头打印链表

从尾到头打印链表_牛客题霸_牛客网 (nowcoder.com)

法1：

从前往后保存，然后reverse一下就行了。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* cur = head;
        vector<int> ans;
        while(cur){
            ans.push_back(cur->val);
            cur = cur->next;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

法2：

递归

class Solution {
public:
    void recursion(ListNode* head,vector<int>& ans){
        if(head != nullptr){
            recursion(head->next, ans);
            ans.push_back(head->val);
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        recursion(head,ans);
        return ans;
    }
};

法3：

还可以先弄到栈里，然后一个个出栈。但感觉跟法1的reverse区分度不大。代码略。

4.重建二叉树

重建二叉树_牛客题霸_牛客网 (nowcoder.com)

法一：

根据二叉树先序遍历和中序遍历的规则，找到根节点，递归建立二叉树。

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        if(preOrder.size() == 0 || vinOrder.size() == 0) return nullptr;
        int mid = distance(begin(vinOrder),find(vinOrder.begin(),vinOrder.end(),preOrder[0]) );
        TreeNode* root = new TreeNode(preOrder[0]);
        vector<int> leftPre(preOrder.begin() + 1,preOrder.begin() + mid + 1);
        vector<int> rightPre(preOrder.begin() + mid + 1,preOrder.end());
        vector<int> leftVin(vinOrder.begin(),vinOrder.begin() + mid);
        vector<int> rightVin(vinOrder.begin() + mid + 1,vinOrder.end());
        root->left = reConstructBinaryTree(leftPre, leftVin);
        root->right = reConstructBinaryTree(rightPre, rightVin);
        return root;
    }
};

法二：

空间换时间。每次都用distance去中序序列中找根节点太麻烦了，直接一开始用哈希表记录每个节点和它的索引。之后就不需要每次计算距离了，只要去查哈希表即可。

class Solution {
public:
    TreeNode* reConCore(vector<int>& preOrder,unordered_map<int,int>& mp,int root,int start,int end){
        if(start > end) return nullptr;
        TreeNode* tree = new TreeNode(preOrder[root]);
        int vinIndex = mp[preOrder[root]];
        tree->left = reConCore(preOrder, mp, root + 1, start, vinIndex - 1);
        tree->right = reConCore(preOrder, mp, (root + 1) + (vinIndex - start ), vinIndex + 1 , end );
        return tree;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        unordered_map<int,int> mp;
        for(int i = 0;i<vinOrder.size();i++) mp.insert({vinOrder[i],i});
        return reConCore(preOrder,mp,0,0,preOrder.size() - 1);
    }
};

5.用两个栈来实现队列

用两个栈实现队列_牛客题霸_牛客网 (nowcoder.com)

很简单，一个栈进，一个栈出。pop时如果出栈为空就把入栈的队列里的数据放放进出栈。

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

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

        temp = stack2.top();
        stack2.pop();
        return temp;
    }

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

6.旋转数组的最小数字

旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)

法一：

常规做法，直接遍历找第一个减小的数字。（也可以sort后，直接return nums[0]）

class Solution {
public:
    int minNumberInRotateArray(vector<int>& nums) {
        for(int i = 1;i<nums.size();i++){
            if(nums[i] < nums[i-1]) return nums[i];
        }
        return nums[0];
    }
};

法二：

使用二分法。虽然数组不是完全有序，但

每次nums[mid] < nums[right]时，表示右边有序。
两者相等时，可能有两种情况或者是右边全是一个数，或者是最小值在右边（数值先小后大，故两者相等）。
每次nums[mid] > nums[right]时，表示最小值在右边。
边界控制，由于最后left和right会控制相邻的两个数值中。故边界为left + 1 < right。否则会陷入死循环。

class Solution {
public:
    int minNumberInRotateArray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]) right = mid;
            else if(nums[mid] == nums[right]) right--;
            else left = mid;
        }
        return min(nums[left],nums[right]);
    }
};

7.斐波那契数列

斐波那契数列_牛客题霸_牛客网 (nowcoder.com)

经典题目

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 2) return 1;
        else return Fibonacci(n-1) + Fibonacci(n-2);
    }
};

8.跳台阶

跳台阶_牛客题霸_牛客网 (nowcoder.com)

经典题目。

class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 2) return number;
        else return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};

9.跳台阶扩展问题

跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)

法一：

经典dp

class Solution {
public:
    int jumpFloorII(int number) {
        vector<int> dp(number + 1);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i< dp.size();i++){
            dp[i] = 2* dp[i-1];
        }
        return dp[number];
    }
};

法二：

发现规律，2^(n-1)；

class Solution {
public:
    int jumpFloorII(int number) {
        if(number <= 1) return 1;
        else return pow(2,number - 1);
    }
};

10.矩阵覆盖

矩形覆盖_牛客题霸_牛客网 (nowcoder.com)

本质还是斐波那契。

class Solution {
public:
    int rectCover(int number) {
        if(number <=2 ) return number;
        else return rectCover(number - 1) + rectCover(number - 2);
    }
};

11.二进制中1的个数

二进制中1的个数_牛客题霸_牛客网 (nowcoder.com)

法一：

使用库函数bitset。

class Solution {
public:
    int NumberOf1(int n) {
        return bitset<32>(n).count();
    }
};

法二：

手动位运算。对于n=1100，n-1=1011。n &= n-1后，n=1000。这个过程相当于从二进制数中消去了一个1。

class Solution {
public:
    int NumberOf1(int n) {
        int count = 0;
        while(n){
            count++;
            n &= (n-1);
        }
        return count;
    }
};

12.数值的整数次方

数值的整数次方_牛客题霸_牛客网 (nowcoder.com)

LCR 134. Pow(x, n) - 力扣（LeetCode）

法一：

常规解法，区分正负即可。

class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1.0;
        if(base == 0) return 0.0;
        bool flag = false;
        if(exponent < 0){
            flag = true;
            exponent *= -1;
        }
        double ans = 1.0;
        for(int i = 0;i<exponent;i++){
            ans*= base;
        }
        if(flag) ans = 1/ans;
        return ans;
    }
};

法二：

快速幂：把幂次按照二进制拆开，分别计算。例如，计算一个数的10次方相当于计算一个数的1010（二进制）次方，可以看作按照x的2次方一次递增。

class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0) return 1;
        if(base == 0) return 0;
				// exp一定要用long。假设exponent=INT_MIN，其对应的正数大于INT_MAX，故不能用int
        long exp = exponent;
        if(exponent < 0){
            exp = exponent *(-1.0);
        }
        double ans = 1.0;
        while(exp != 0){
            if((exp & 1) == 1){
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return exponent < 0 ? 1 /ans : ans;

    }
};

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

调整数组顺序使奇数位于偶数前面_牛客题霸_牛客网 (nowcoder.com)

法一：

使用辅助数组

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> vec;
        for(auto& i : array)
            if(i & 1) array.push_back(i);
        for(auto& i : array)
            if(!(i & 1)) array.push_back(i);
        
        copy(vec.begin(),vec.end(),array.begin());
    }
};

法二：

in-place算法。

用i记录当前需要插入的奇数的位置，用j遍历数组。如果遇到奇数，就将其插入到i所在的位置（i到j-1之间所有的数据往后挪一位）。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int i = 0;
        for(int j = 0;j<array.size();j++){
            if(array[j] & 1){
                int temp = array[j];
                for(int k = j-1;k>=i;--k){
                    array[k+1] = array[k];
                }
                array[i++] = temp;
            }
        }
    }
};

法三：

使用STL函数****stable_partition()****对指定区域内的数据进行分组，重新排列指定区域内存储的数据，使其分为两组，第一组位符合筛选条件的数据，另一组为不符合筛选条件的数据。

函数原型：

1
2
3

template< class BidirIt, class UnaryPredicate >

BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

第三个参数可以传入一个仿函数，函数指针，lambda表达式。

#include <algorithm>
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(),array.end(),[](int x){return x & 1;});
    }
};

14.链表中倒数第k个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

双指针

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
		if(!pListHead || k <= 0) return nullptr;
		auto slow = pListHead,fast = pListHead;
		int n = 0;
		while(k--){
			if(fast)
				fast = fast->next;
			else
			 	return nullptr;
		}
		while(fast){
			fast = fast->next;
			slow = slow->next;
		}
		return slow;
    }
};

15.反转链表

反转链表_牛客题霸_牛客网 (nowcoder.com)

法一：

双指针。以1，2，3链表为例，用三个指针，

cur指针用来遍历，指向head。
pre指向cur的前一个节点，故一开始其必须初始化为nullptr。
由于在遍历过程中需要将cur->next指向pre。故还需要一个temp指针用来保存cur->next实现遍历。

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* dummyNode = new ListNode(0);
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* temp = nullptr;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

法二：

递归。一次反转整个链表很困难，但反转第一个元素和第二个元素比较容易。

故将原问题可以减小为反转前两个元素。依次往后递归。
在思考时，假定ReverseList(head->next)代表已经反转好的后续元素。只需要改变链表前两个元素的指针指向并考虑边界条件即可。
边界条件:head == nullptr代表链表本身为空，head->next == nullptr代表递归出口

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return head;
        ListNode* ans = ReverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
};

16.合并两个有序链表

合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)

经典题目。起一个虚拟头节点，然后一边遍历，一边将小的插在都节点后面，直到两个链表有一个为空。最后将不为空的链表插入到结果的后面即可。

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        ListNode* dummyNode = new ListNode(0);
        ListNode* cur = dummyNode;
        while(pHead1  && pHead2){
            if(pHead1->val < pHead2->val){
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        if(pHead1) cur->next = pHead1;
        if(pHead2) cur->next = pHead2;
        return dummyNode->next;
    }
};

17.树的子结构

树的子结构_牛客题霸_牛客网 (nowcoder.com)

树的问题归根结底的递归问题。

根据题意，判断B是不是A的子结构。由于题意表明空树不是任意一个树的子结构，故一开始就将空树进行处理（直接return false）。

之后判断B是否是A的子结构。若B是，则A的任意一个节点都有可能是B的根节点。故需要先序遍历A的每个节点判断以A中的节点node为根节点的子树是否包含树B。（isSameTree）在该函数中，

终止条件：
- B为空，表示，B已匹配完成，返回true
- A为空，表示已经越过A的叶节点，即匹配失败，返回false
- A和B的值不同：表明匹配失败，返回false
返回值：到了最后返回的时候表明A和B的根节点相同，故需要判断其左右子树是否相等。故返回值为isSameTree(pRoot1->left,pRoot2->left) && isSameTree(pRoot1->right,pRoot2->right);

class Solution {
public:
	bool isSameTree(TreeNode* pRoot1,TreeNode* pRoot2){
		if(pRoot2 == nullptr) return true;
		if(pRoot1 == nullptr || pRoot1->val != pRoot2->val) return false;
		return isSameTree(pRoot1->left,pRoot2->left) && isSameTree(pRoot1->right,pRoot2->right);
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(pRoot1 == nullptr || pRoot2 == nullptr) return false;
		return isSameTree(pRoot1,pRoot2) || HasSubtree( pRoot1->left, pRoot2) || HasSubtree(pRoot1->right,pRoot2);
    }
};

18.二叉树的镜像

二叉树的镜像_牛客题霸_牛客网 (nowcoder.com)

只要能遍历一遍所有节点，然后交换每个节点的左右孩子即可。故三种遍历及其迭代法改造以及层序遍历都可以。

法一：

理解了递归，就理解了树。这里用先序遍历，先交换节点的左右子节点，之后分别递归处理左右子树。

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == nullptr) return nullptr;
        TreeNode* temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};

法二:

先序迭代法

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == nullptr) return nullptr;
        stack<TreeNode*> st;
        st.push(pRoot);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            swap(cur->left,cur->right);
            if(cur->left) st.push(cur->left);
            if(cur->right) st.push(cur->right);
        }
        return pRoot;
    }
};

法三：

中序遍历。采用递归实现的中序遍历，部分节点的左右孩子会反转两次。故与传统中序写法不太一致。

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == nullptr) return nullptr;
        Mirror(pRoot->left);   // 左
        swap(pRoot->left,pRoot->right);  //中
        Mirror(pRoot->left);  //“右”，因为左右节点已经交换了，所赐此时的left为原来的right
        return pRoot;
    }
};

19.顺时针打印矩阵

顺时针打印矩阵_牛客题霸_牛客网 (nowcoder.com)

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        if(matrix.empty()) return ans;
        int rl = 0, rh = matrix.size()-1;
        int cl = 0, ch = matrix[0].size()-1;
        while(1){
            for(int i = cl;i<=ch;i++) ans.push_back(matrix[rl][i]);
            if(++rl > rh) break;
            for(int i = rl;i<=rh;i++) ans.push_back(matrix[i][ch]);
            if(--ch < cl) break;
            for(int i = ch;i >= cl ;i--) ans.push_back(matrix[rh][i]);
            if(--rh < rl) break;
            for(int i = rh;i >= rl;i--) ans.push_back(matrix[i][cl]);
            if(++cl > ch) break;
        }
        return ans;
    }
};

20.包含min函数的栈

包含min函数的栈_牛客题霸_牛客网 (nowcoder.com)

法一：

用一个栈，每次存完以后额外存一下最小值。

class Solution {
public:
    void push(int value) {
        if(st.empty()){
            st.push(value);
            st.push(value);
        }else{
            int mi = st.top();
            mi = value < mi ? value : mi;
            st.push(value);
            st.push(mi);
        }
    }
    void pop() {
        if(st.empty()) return ;
        st.pop();
        st.pop();
    }
    int top() {
        if(st.empty()) return -1;
        int temp = st.top();
        st.pop();
        int ans = st.top();
        st.push(temp);
        return ans;
    }
    int min() {
        if(st.empty()) return -1;
        return st.top();
    }
private:
    stack<int> st;
};

法二

也可以用两个栈，一个存数据，另一个存最小值。跟上面原理一样。

class Solution {
public:
    void push(int value) {
        if(st.empty()){
            st.push(value);
            minSt.push(value);
        }else{
            int mi = minSt.top();
            mi = value < mi ? value : mi;
            minSt.push(mi);
            st.push(value);
        }
    }
    void pop() {
        if(st.empty()) return ;
        st.pop();
        minSt.pop();
    }
    int top() {
        if(st.empty()) return -1;
        return st.top();
    }
    int min() {
        if(st.empty()) return -1;
        return minSt.top();
    }
private:
    stack<int> st;
    stack<int> minSt;
};

21.栈的压入、弹出序列

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

既然是栈的序列，那就用栈模拟。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if(pushV.empty() || popV.empty()) return false;
        stack<int> st;
        int j = 0;
        for(int i = 0;i<pushV.size();i++){
            st.push(pushV[i]);
            while(!st.empty() && st.top() == popV[j]){
                j++;
                st.pop();
            }
        }
        return st.empty();
    }
};

22.从上往下打印二叉树

从上往下打印二叉树_牛客题霸_牛客网 (nowcoder.com)

我一个层序遍历就出来了。

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
		queue<TreeNode*> que;
		vector<int> ans;
		if(root != nullptr) que.push(root);
		while(!que.empty()){
			int size = que.size();
			for(int i = 0;i<size;i++){
				TreeNode* node = que.front();
				que.pop();
				ans.push_back(node->val);
				if(node->left) que.push(node->left);
				if(node->right) que.push(node->right);
			}
		}
		return  ans;
    }
};

23.二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列_牛客题霸_牛客网 (nowcoder.com)

法一：递归

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        return check(sequence,0,sequence.size() - 1);
    }
    bool check(vector<int>& sequence,int l, int r){
        if(l >= r) return true;
        int root = sequence[r];
        int j = r - 1;
        while(j >= 0 && sequence[j] > root) j--;
        for(int i = 0;i<j;i++){
            if(sequence[i] > root) return false;
        }
        return check(sequence,l,j) && check(sequence, j + 1, r - 1);
    }
};

法二：

二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列。
若是二叉搜索树，对后序遍历序列排序就得到了中序遍历序列。
将中序遍历序列作为入栈序列，检查后续遍历序列是否是一个合法的出栈序列即可（栈的压入、弹出）

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        vector<int> inorder(sequence);
        sort(inorder.begin(),inorder.end());
        return isPopOrder(inorder,sequence);
    }
    bool isPopOrder(vector<int> pushV,vector<int>& popV){
        if(pushV.empty() || popV.empty()) return false;
        stack<int> st;
        int j = 0;
        for(int i = 0;i<pushV.size();i++){
            st.push(pushV[i]);
            while(!st.empty()&& st.top() == popV[j]){
                j++;
                st.pop();
            }
        }
        return st.empty();
        
    }
};

24.二叉树中和为某一值的路径

二叉树中和为某一值的路径(二)_牛客题霸_牛客网 (nowcoder.com)

回溯法，也是DFS。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void bt(TreeNode* root,int sum){
        if(root == nullptr) return ;
        path.push_back(root->val);
        sum -= root->val;
        if(root->left == nullptr && root->right == nullptr && sum == 0)
            ans.push_back(path);
        bt(root->left,sum);
        bt(root->right,sum);
        path.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode* root, int target) {
        // write code here
        bt(root,target);
        return ans;
    }
};

25.复杂链表的复制

复杂链表的复制_牛客题霸_牛客网 (nowcoder.com)

法一：

将整个复杂过程分为三部。

在每个节点后面插入对应的拷贝节点。
遍历一次连表，逐个复制每个原有节点的random指针内容到拷贝节点中。（使用双指针，一个指向原链表的节点，一个指向拷贝链表的节点）
用双指针将链表拆分。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        RandomListNode* cur = pHead;
        // 每个节点后面新增对应拷贝节点
        while(cur){
            RandomListNode* temp = new RandomListNode(cur->label);
            temp->next = cur->next;
            cur->next = temp;
            cur = temp->next;
        }

        RandomListNode *old = pHead,*clone = pHead->next,*ret = pHead->next;
        // 拷贝random指针内容
        while(old){
            clone->random = old->random == nullptr ? nullptr : old->random->next;
            if(old->next) old = old->next->next;
            if(clone->next) clone = clone->next->next; 
        }
        // 将链表拆分
        old = pHead,clone = pHead->next;
        while(old){
            if(old->next) old->next = old->next->next;
            if(clone->next) clone->next = clone->next->next;
            old = old->next;
            clone = clone->next;
        }
        return ret;
    }
};

法二

本题的复杂之处在于多了一个random指针的复制。next指针的复制十分轻松，但复制之后如何完成random指针的复制是个问题。可以考虑在复制next指针时，用哈希表存储原节点与复制节点的映射。这样只要两次遍历，第一次复制next指针，第二次根据映射关系将原来random的指向映射到新链表上即可完成random指针的复制。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;
        RandomListNode* dummy = new RandomListNode(0);
        RandomListNode* cur = pHead;
        RandomListNode* pre = dummy;
        unordered_map<RandomListNode*, RandomListNode*> mp;
        while(cur){
            RandomListNode* temp = new RandomListNode(cur->label);
            pre->next = temp;
            mp[cur] = temp;
            cur = cur->next;
            pre = pre->next;
        }
        for(auto& [key,value] : mp){
            value->random = key->random == nullptr ?  nullptr : mp[key->random];
        }
        return dummy->next;
    }
};

26.二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

法一：

先中序遍历二叉树，将其放入一个vector中，然后遍历vector改变指针朝向即可。但这样做在push_back时也属于创建了新的节点，而不是直接改变指针朝向。

class Solution {
public:
	vector<TreeNode*> vec;
	void  inorder(TreeNode* root){
		if(!root) return ;
		inorder(root->left);
		vec.push_back(root);
		inorder(root->right);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
		inorder(pRootOfTree);
		for(int i = 0;i<vec.size() - 1;i++){
			vec[i]->right = vec[i + 1];
			vec[i+1]->left = vec[i];
		}
		return vec[0];
    }
};

法二：

用一个全局的pre指针记录当前遍历节点的前继节点。

每次递归处理过程中，root->left = pre。并且pre->right = root。最后pre = root，更新pre的值。

class Solution {
public:
	TreeNode* pre = nullptr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
		TreeNode* ans = pRootOfTree;
		while(ans->left) ans = ans->left;
		inorder(pRootOfTree);
		return ans;
    }
	void inorder(TreeNode* root){
		if(!root) return ;
		inorder(root->left);
		root->left = pre;
		if(pre){
			pre->right = root;
		}
		pre = root;
		inorder(root->right);
	}
};

27.字符串的排列

字符串的排列_牛客题霸_牛客网 (nowcoder.com)

法一：

用回溯法，相当于求有重复元素数组的全排列。

由于有重复元素，故需要去重
由于求全排列需要用回溯。
递归三部曲：
1. 递归参数：由于求全排列，故需要用一个数组记录已经访问过的元素，下次递归过来就不访问了。
2. 递归终止条件：当path.size() == str.size()表示str已经遍历完了，就终止。
3. 单层搜索的逻辑：每次都需要从0开始遍历整个str。中间遇到已经访问过的元素，则continue。
去重：由于str中存在重复元素，需要去重。例如”aa”,若不去重，会有[a,a]、[a,a]两种结果。
- 去重首先需要将str中各个元素排序。
- 之后在递归的树形结构中，used记录了是否访问过，str记录了所有数据。如果str[i] == str[i-1]表明需要考虑去重。
- 若此时，used[i-1] = false表明该在本次全排列计算过程中used[i-1]没有访问过，此时如果继续递归会重复。举例如下：对于[1,1,2]，在以第二个1为首元素时，used[i-1]= false。此时如果继续递归下去，和以第一个1为首元素进行递归的结果会重复。
- 若此时，used[i-1] = true表明在本次全排列计算时，used[i-1]已经访问过，此时不应去重。举例如下：对于[1,1,2]，表明第一个元素为1，第二个元素为1的情况，此时应该继续递归去寻找第三个元素。如果此时直接跳过，得到的全排列中的各个元素之间都是不重复的，这就与题意不符了。

class Solution {
public:
    vector<string> ans;
    string path;
    void bt(string& str,vector<bool>& used){
        if(path.size() == str.size()){
            ans.push_back(path);
            return ;
        }
        for(int i = 0;i<str.size();i++){
            if(i >0 && str[i] == str[i - 1] && used[i - 1] == false) continue;
            if(used[i] == true) continue;
            used[i] = true;
            path.push_back(str[i]);
            bt(str,used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<string> Permutation(string str) {
        sort(str.begin(),str.end());
        vector<bool> used(str.size(),false);
        bt(str,used);
        return ans;
    }
};

法二：

使用STL 中的**next_permutation**返回全排列。该函数必须先排序才能使用。

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ans;
        sort(str.begin(),str.end());
        do{
            ans.push_back(str);
        }while(next_permutation(str.begin(), str.end()));
        return ans;
    }
};

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

数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)

法一：

排序后直接返回中间位置的数即可。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        sort(numbers.begin(),numbers.end());
        return numbers[numbers.size() / 2];
    }
};

法二：

用哈希表记录一下每个元素有几个。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        unordered_map<int,int> mp;
        for(auto& i : numbers){
            mp[i]++;
            if(mp[i] > numbers.size() / 2) return i;
        }
        return -1;
    }
};

法三：

摩尔投票法：寻找一组元素中占多数的元素的算法。时间复杂度O(n)。

基本思想：每次从序列中选两个不相同的数字删除掉（“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一般的那个。
实现：
1. 设置一个计数器遍历时遇到不同数字就-1，遇到相同数字就+1。
2. 只要在计数器归0时，就重新假定当前数字为众数继续遍历。
3. 最后，计数器记录的数字就可能是众数。
4. 最后再遍历一次数组，看看该数出现了几次，或者直接用STL中的count()数一下就好。
5. 由于本题确定众数存在，故找到可能的众数后返回即可。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int cnt = 0,num = 0;
        for(int i = 0;i<numbers.size();i++){
            if(cnt == 0){
                num = numbers[i];
                cnt = 1;
            }else{
                numbers[i] == num ? cnt++ : cnt--;
            }
        }
        return num;
    }
};

29.最小的K个数

最小的K个数_牛客题霸_牛客网 (nowcoder.com)

法一

排序之后慢慢数。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        sort(input.begin(),input.end());
        vector<int> ans;
        for(int i = 0;i<k;i++){
            ans.push_back(input[i]);
        }
        return ans;
    }
};

法二

用优先队列（小根堆）。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // priority_queue默认为大根堆，故需要用第三个参数指明是小根堆
        priority_queue<int,vector<int>,greater<int>> pq;
        for(auto& i : input) pq.push(i);
        vector<int> ans;
        while(k--){
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
    }
};

补充：C++中优先队列的用法。

定义：priority_queue<Type, Container, Functional>
- Type：数据类型
- Container：容器类型，必须是连续存储空间容器，比如vector,deque等，STL默认用vector。
- Functional：比较的方式。使用自定义数据类型时需要用该参数表示如何比较类型的大小。使用基本数据类型时，只需要传入数据类型，默认大顶堆。

//升序队列（小顶堆）
priority_queue <int,vector<int>,greater<int> > pq;
//降序队列（大顶堆）
priority_queue <int,vector<int>,less<int> > pq;

greater和less是两个仿函数（使一个类的使用看起来像个函数，就是类中实现了一个operator()）。

30.连续子数组的最大和

连续子数组的最大和_牛客题霸_牛客网 (nowcoder.com)

法一

常规dp。dp[i]表示以array[i]结尾的连续子数组的最大和。

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

法二

利用array的空间作为dp数组，减少空间复杂度。

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

法三

贪心算法。

连续子数组的最大值的贪心原则是在累加过程中只要中间结果≥0就不中断计数。
例如，4,-1,2中虽然4与-1的和比4小，但其还是正数与之后的2相加时还会贡献一部分数值。
这样做的一个问题是，连续子数组的最大值可能在中间结果产生，例如4，-2，1中最大结果为4，而如果用一个变量来进行累加，该变量的值最后是3。
该问题的解决方案是用一个变量专门记录最大值，在每次累加过程后都更新以下该变量。

具体实现而言，可以用一个计数器cnt记录寻找过程中的子数组和。

在累加的过程中，遵循以下规则。

当遇到正数或零时，我们直接将其加到计数器 cnt 上，并同时更新记录的最大值。
若遇到负数，需要考虑两种状态
1. 如果将负数加到当前的累加结果后仍然得到正数，比如 3 + (-2)。此时则将负数加到累加结果上，并继续累加。这是因为这样做有可能对后续的连续子数组结果产生增益。
2. 如果将负数加到当前的累加结果后变成了负数，比如 1 + (-2)。此时，将负数加到当前结果会对之后的连续子数组结果产生负面影响。故将 cnt 清零，重新开始累加。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        int ans = INT_MIN;
        int cnt = 0;
        for(int i = 0;i<array.size();i++){
            cnt += array[i];
            ans = max(ans,cnt);
            if(cnt < 0) cnt = 0; 
        }
        return ans;
    }
};

31.整数中1出现的次数

整数中1出现的次数（从1到n整数中1出现的次数）_牛客题霸_牛客网 (nowcoder.com)

法一

题目怎么说，我就怎么做。主打的就是一个暴力。但数据量一上来就超时了。

class Solution {
public:
    int countOne(int n){
        int cnt = 0;
        while(n){
            if(n % 10 == 1) cnt++;
            n /= 10;
        }
        return cnt;
    }
    int NumberOf1Between1AndN_Solution(int n) {
        int ans = 0;
        for(int i = 1;i<=n;i++){
            int cnt = countOne(i);
            ans += cnt; 
        }
        return ans;
    }
};

法二

分情况讨论求解吧。1出现的位数为1在n的各个数位上出现的次数之和。

剑指offer-整数中1出现的次数（从1到n整数中1出现的次数）-CSDN博客

举例如下，

对于n = 1140143，

假设base为10，将其分组为high = n / base / 10 = 11401 ，cur = n / base % 10 = 4，low = n % base = 3。此时，cur > 1，故1在“十位”上出现的次数有(0~11401)x(0~9)即(high + 1)*base。
假设base为100，将其分组为high = n / base / 10 = 1140 ，cur = n / base % 10 = 1，low = n % base = 43。此时，cur == 1，故1出现的次数需要分情况讨论
- 当high为（0~1139）时，low依旧可以在（0~99）中间任意选择。故1出现的次数为high * base
- 当high为1140时，low必须在(0~low)中间选择。否则结果会大于n。故1出现的次数为low + 1。
- 综合两种情况，此时1在“百位”上出现的次数为high * base + (low + 1)
假设base为1000，将其分组为high = n / base / 10 = 114 ，cur = n / base % 10 = 0，low = n % base = 143。此时，high只能在(0~113)中选择，base可以在(0~999)中选择。故1在“千位”上出现的次数为high * base。

最后只要将base从1到n走一遍，就将所有情况统计全了。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int base = 1;
        int ans = 0;
        while(base <= n){
            int low = n % base;
            int high = n / base;
            int cur = high % 10;
            high /= 10;
            if(cur > 1){
                ans += (high + 1) * base;
            }else if(cur == 1){
                ans += high * base + (low + 1);
            }else{  
                ans += high * base;
            }
            base *= 10;
        }
        return ans;
    }
};

法三

与法二相似，还是逐位统计1的个数，但是从最高位开始分段处理。

例如对于1145。最高位为high = 1，最高位权重为base = 1000。

最高位是1
- 最高位1的次数为last + 1（1000-1145），这里对于（1000-1145）只计算其千位上的1，（000~145）这三位上的留在之后计算。
- 去除最高位的次数，0-999的1的个数为high*NumberOf1Between1AndN_Solution(base - 1)
- 剩余部分1的个数为NumberOf1Between1AndN_Solution(last)（这部分为145中1的个数，但与0-999中的不冲突，因为此时的代表最高位为1时，剩余部分1的个数）
最高位不是1，例如是2
- 最高位1的次数为base(1000-1999)
- 去除最高位的次数，即0-999，1000-1999high*NumberOf1Between1AndN_Solution(pow - 1)
- 剩余部分1的个数为NumberOf1Between1AndN_Solution(last)

以上两种情况的差别仅在于最高位1的次数。故可以合并处理。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0) return 0;
        if(n < 10) return 1;
        int high = n,base = 1;
        while(high >= 10){
            high /= 10;
            base *= 10;
        }
        int last = n - high * base;
        int cnt = high == 1 ? last + 1 : base;
        return cnt + high*NumberOf1Between1AndN_Solution(base - 1) + NumberOf1Between1AndN_Solution(last);
    }
};

32.把数组排成最小的数

把数组排成最小的数_牛客题霸_牛客网 (nowcoder.com)

该问题所求其实就是数组中各个数字如何排列拼接而成的字符串表示的值最小。对于a和b两个数，如果ab大于ba那么a一定在b前面。

例如，a=12,b = 34。则ab=1234,ba=3412，最终排列时b一定在a前面。

故，可以数自定义一种比较方式利用sort实现排序。

class Solution {
public:
    string PrintMinNumber(vector<int>& numbers) {
        string ans = "";
        if(numbers.size() == 0) return ans;
        vector<string> nums;
        for(auto& num : numbers){
            nums.push_back(to_string(num));
        }
        sort(nums.begin(),nums.end(),[](string& a,string& b){
            return a + b < b + a;
        });
        for(auto& num : nums){
            ans += num;
        }
        return ans;
    }
};

注：若sort函数的第三个参数不使用lambda表达式而使用比较函数，该函数需要定义为静态函数。

这是因为在类内定义的非static成员函数在经过编译后会隐式添加一个this指针参数，而标准库的sort()函数的第三个cmp函数指针参数中并没有这样this指针参数，因此会出现输入的cmp参数和sort()要求的参数不匹配，从而导致了：error: reference to non-static member function must be called。

正确写法如下，

class Solution {
public:
    static bool cmp(string& a,string & b){
        return a + b < b + a;
    }
    string PrintMinNumber(vector<int>& numbers) {
        string ans = "";
        if(numbers.size() == 0) return ans;
        vector<string> nums;
        for(auto& num : numbers){
            nums.push_back(to_string(num));
        }
        sort(nums.begin(),nums.end(),cmp);
        for(auto& num : nums){
            ans += num;
        }
        return ans;
    }
};

33.第N个丑数

丑数_牛客题霸_牛客网 (nowcoder.com)

法一

三指针法。

丑数就是只包含质因子2、3、5的数。

从1开始逐个判断是否为丑数是一个直观的解决方案。具体而言，可以依次检查能否被2、3、5整除。如果能被2整除，则除以2；如果能被3整除，则除以3；最后，如果剩下的是1，那么就是丑数，否则不是。
上面的重复计算很多。比如，假设我们知道4是丑数，8首先除以2得到4之后完全没必要继续除下去了，可以得到8也是丑数的结果。故，可以用空间换时间。
- 只计算丑数，根据定义。丑数应该是一个丑数乘以2、3、5得到的结果（1除外）。但在乘的过程中如何保证得到的一系列丑数是有序的方便我们找到第N个呢？
- 用三个指针分别指向当前乘以2、3、5的丑数，初始值都为0，代表第0个丑数1。例如，indexThree = 2表示，第二个丑数乘以3。
- 每次循环中，从三个指针的计算结果中选出最小的一个作为新的丑数，并将对应的指针加1，表示下次用更大的丑数乘以相应的因子。例如，第一次循环中，最小的丑数为2，所以将indexTwo加1，表示下次用第二个丑数2乘以2。
- 这样便可以得到一个有序的丑数序列。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index < 7) return index;
        vector<int> ans(index);
        ans[0] = 1;
        int indexTwo = 0,indexThree = 0,indexFive = 0;
        for(int i = 1;i<index;++i){
            int minNum = min(min(ans[indexTwo] * 2,ans[indexThree] * 3),ans[indexFive]* 5);
            if(minNum == ans[indexTwo] * 2) indexTwo++;
            if(minNum == ans[indexThree] * 3) indexThree++;
            if(minNum == ans[indexFive] * 5) indexFive++;
            ans[i] = minNum;
        }
        return ans[index - 1];
    }
};

法二

小顶堆 + 哈希表

用小顶堆记录丑数，用哈希表去重，数组记录2、3、5乘数因子。
1作为第一个丑数先入堆，后面的丑数都是其不断乘以2、3、5的结果。
每次从小顶堆中弹出最小的元素，一共弹出index次。
对于每个弹出的元素，用其构造后面的丑数，即分别乘以2、3、5，若是不重复，则加入堆中。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
        vector<int> fac = {2,3,5};
        priority_queue<long long,vector<long long>,greater<long long>> pq;
        unordered_set<long long> st;
        // 放入初始丑数1
        st.insert(1);
        pq.push(1);
        long long ans = 0;
        for(int i = 0;i<index;i++){
            ans = pq.top();
            pq.pop();
            for(int j = 0;j<3;j++){
                long long next = ans * fac[j];
                if(st.find(next) == st.end()){
                    st.insert(next);
                    pq.push(next);
                }
            }
        }
        return (int)ans;
    }
};

注：

在计算过程中会有数超过int范围，故哈希表和小根堆都要用long long。那么为什么法一不需要呢？
- 因为法一乘数因子是各自独立乘以属于自己的当前丑数。
- 而法二是找一个最小的丑数然后分别乘以2、3、5。
- 这时候就可能遇见这种情况：需要求第7个丑数，但是在第4个丑数乘以5的时候已经求到了第9个丑数，虽然第7个丑数还是int的范围内，但第9个丑数已经超过int的范围了。

34.第一个只出现一次的字符

第一个只出现一次的字符_牛客题霸_牛客网 (nowcoder.com)

法一

题目中说字符串只由字母组成，故不需要用哈希表来存储，直接用一个数组来充当一个简易的哈希表。所有的字母中ASCII码最小的是A（65），最大的是z（122），故需要一个大小为122-65+1=58的数组来记录这些字符出现的次数。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        vector<int> vec(58,0);
        for(auto& s : str)
            vec[s - 'A'] += 1;
        for(int i = 0;i<str.size();i++){
            if(vec[str[i] - 'A'] == 1) return i;
        }
        return -1;
    }
};

法二

如果记不清ASCII码最小的字符是A还是a，直接用哈希表来存也是一样的，只需要一个简单的替换。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char,int> mp;
        for(auto& s : str)
            mp[s]++;
        for(int i = 0;i<str.size();i++){
            if(mp[str[i]] == 1) return i;
        }
        return -1;
    }
};

35.数组中的逆序对

数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)

法一

直接暴力，果不其然超时了。

class Solution {
public:
    int InversePairs(vector<int>& nums) {
        int ans = 0;
        const int MOD = 1e9 + 7;
        for(int i = 0;i<nums.size();i++){
            for(int j = i + 1;j<nums.size();j++){
                if(nums[j] < nums[i]){
                    ans++;
                    ans %= MOD;
                }
            }
        }
        return ans;
    }
};

法二

归并排序与逆序对息息相关。

求nums的逆序对时，将nums从中间分为两部分。故nums的逆序对=（1）左半数组的逆序对 + （2）右半数组逆序对 + （3）左右两边的逆序对（右边数组中的数<左边数组时）。

其中（1）和（2）可以直接递归去算，直到递归出口（数组中只有一个元素，逆序对为0）。
（3）则需要在归并左右两个数组时进行计算。设排序时，左右两个数组当前索引分别为i，j，中间值为mid。此时只有j处的元素 < i处的元素时，会产生逆序对（从i开始到mid处，即mid - i + 1个）。

class Solution {
public:
    int InversePairs(vector<int>& nums) {
        vector<int> copy(nums.size());
        return MergeSort(nums,copy,0,nums.size() - 1);
    }
private:
    const int MOD = 1e9 + 7;
    int MergeSort(vector<int>& data,vector<int>& copy,int left,int right){
        if(left >= right) return 0; // 递归出口数组只有一个元素，不存在逆序对
        // 递归，分为左右两组分别归并
        int mid = left + (right - left) / 2;
        int ans = MergeSort(data, copy, left, mid )+ MergeSort(data, copy, mid + 1, right);
        ans %= MOD;
        // 合并
        int i = left,j = mid + 1; // 左右两个排好序的子数组的起始索引
        for(int k = left;k<=right;k++) copy[k] = data[k]; //暂时记录[left,right]间的顺序，开始合并
        for(int k = left;k<=right;k++){
            if(i == mid + 1) data[k] = copy[j++]; // 左边数组合并完了
            else if(j == right + 1) data[k] = copy[i++]; // 右边数组合并完了
            else if(copy[i] <= copy[j]) data[k] = copy[i++]; // 左边数组当前值<=右边数组
            else{       // 左边数组当前值大于右边数组
                data[k] = copy[j++];
                ans += (mid - i + 1);  // 将右边数组当前值归位时，增加了 mid - i + 1个逆序对（左边数组剩余元素）
                ans %= MOD;
            }
        }
        return ans;
    }
};

法三

法二在合并两个数组的过程中，设计到很多数据交换。例如，首先要将数据从data写入到copy，然后一边排序一边写回data。
可以换一种思路实现，每次都将data中的数据排序后写入到copy。
该方法交换次数减少，但可读性降低，慎用。

class Solution {
public:
    int InversePairs(vector<int>& nums) {
        vector<int> copy(nums);
        return MergeSort(nums,copy,0,nums.size()-1);
    }
private:
    const int MOD = 1e9 + 7;
    int MergeSort(vector<int>& data,vector<int>& copy,int left,int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        int ans = MergeSort(copy, data, left, mid) + MergeSort(copy,data, mid + 1, right);
        ans %= MOD;
        int i = left,j = mid + 1;
        for(int k = left;k<=right;k++){
            if(i == mid + 1) copy[k] = data[j++];
            else if(j == right + 1 || data[i] <= data[j]) copy[k] = data[i++];
            else {
                copy[k] = data[j++];
                ans += (mid + 1 - i);
                ans %= MOD;
            }
        }
        return ans;
    }
};

注：

data理解为原有乱序数组，copy理解为排好序的数组，归并过程就是要将data中的数据排序后放在copy中。即该法的思路是将data中的数据排序后放在copy中，表现在代码中就是与法二相比归并过程中copy成为了左值。
在每一次递归调用中，data 和 copy 两个数组的角色在递归间调换。一个数组在一次递归中作为源数组，而在下一次递归中作为目标数组。这样，每一次递归都是将有序的部分从一个数组复制到另一个数组中，而无需进行元素的实际交换。
由于该方法中copy数组不需要一次次的交换数据，故一开始其数据必须和nums一致。vector<int> copy(nums);不可以用 vector<int> copy(nums.size());代替。
MergeSort(copy, data, left, mid)该函数中copy与data参数交换了一下。
if(j == right + 1 || data[i] <= data[j])由于两个条件的执行语句一样将其放在一起写了。

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

两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

法一

需要找的是公共节点（该节点之后两条链表变为一条），要与值相同的链表区分。

计算两条链表的长度，cnt1和cnt2。
将两条链表末尾对齐，（长的链表往后走diff（|cnt1 - cnt2|）步）。因为如果存在公共节点的话一定是从一个交汇节点到链表末尾都一样。
开始遍历对齐后的链表，找到一样的返回，找不到表示不存在。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		ListNode* cur1 = pHead1;
		ListNode* cur2 = pHead2;
		int cnt1 = 0,cnt2 = 0;
		while(cur1){
			cur1 = cur1->next;
			cnt1++;
		}
		while(cur2){
			cur2 = cur2->next;
			cnt2++;
		}
		cur1 = pHead1,cur2 = pHead2;
		if(cnt1 < cnt2){
			swap(cur1,cur2);
			swap(cnt1,cnt2);
		}
		int diff = cnt1 - cnt2;
		while(diff--) cur1 = cur1->next;
		while(cur1 && cur2){
			if(cur1 == cur2) return cur1;
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
		return nullptr;
    }
};

法二

该题最大的问题是在于两条链表的长度可能不同，

若两条链表长度相同，则一个循环直接边遍历边比较即可，找不到就是不存在。
若长度不同，可以在指针到了链表结尾后指向另一条链表的头。这样便抹平了长度差（两个链表上的所有元素都要被指针走一趟），这样结束的时候要么两个指针都指向nullptr，要么都指向公共节点。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* cur1 = pHead1;
				ListNode* cur2 = pHead2;
				while(cur1 != cur2){
					cur1 = (cur1 == nullptr ? pHead2 : cur1->next);
					cur2 = (cur2 == nullptr ? pHead1 : cur2->next);
				}
				return cur1;
    }
};

37.统计一个数字在排序数组中出现的次数

数字在升序数组中出现的次数_牛客题霸_牛客网 (nowcoder.com)

法一

很直接的想法，题目怎么说，我就怎么来。

class Solution {
public:
    int GetNumberOfK(vector<int>& nums, int k) {
        int cnt = 0;
        for(auto& i : nums){
            if(i == k) cnt++;
        }
        return cnt;
    }
};

法二

由于是非降序数组，可以利用二分法寻找k的后一个元素和k的前一个元素的索引位置，两者相减就是k出现的次数。

class Solution {
public:
    int BinarySearch(vector<int>& data,float k){
        int left = 0,right = data.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(data[mid] < k) left = mid + 1;
            else right = mid -1;
        }
        return left;
    }
    int GetNumberOfK(vector<int>& nums, int k) {
        return BinarySearch(nums,k + 0.5) - BinarySearch(nums,k - 0.5);
    }
};

注：

自己写的二分查找中k需要用浮点数，否则无法通过加减0.5找到与k相连的元素。
二分查找过程中不需要考虑data[mid]==k，因为k一定不是整数，而data数组里都是整数，两者不会相等。
BinarySearch返回值返回left和right都可。因为所求结果是一个差值，而不是一个精确的位置，在跳出while循环时，right永远比left大1。

38.二叉树的深度

二叉树的深度_牛客题霸_牛客网 (nowcoder.com)

法一

树的问题归根结底就是遍历问题，求深度可以用层序遍历，遍历一层cnt加一即可。

class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
		int cnt = 0;
		queue<TreeNode*> que;
		if(pRoot != nullptr) que.push(pRoot);
		while(!que.empty()){
			int size = que.size();
			cnt++;
			for(int i = 0;i<size;i++){
				TreeNode* node = que.front();
				que.pop();
				if(node->left) que.push(node->left);
				if(node->right) que.push(node->right);
			}
		}
		return cnt;
    }
};

法二

递归的逻辑也很容易梳理出来

递归出口为根节点为0，return 0。

递归公式为，一棵树的深度等于左右子树的最大深度 + 1。

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

39.判断是不是平衡二叉树

判断是不是平衡二叉树_牛客题霸_牛客网 (nowcoder.com)

法一

一个很直观的想法就是递归。平衡二叉树就是任何子树的左右子树之间的深度差小于等于1。结合38题的代码，遍历一遍节点看看是否符合条件即可。

class Solution {
public:
    int MaxDepth(TreeNode* root){
        if(root == nullptr) return 0;
        return max(MaxDepth(root->left),MaxDepth(root->right)) + 1;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        if(root == nullptr) return true;
        return abs(MaxDepth(root->left) - MaxDepth(root->right)) <= 1 && IsBalanced_Solution(root->left) && IsBalanced_Solution(root->right);
    }
};

法二

法一的冗余计算太多了，在遍历上层节点时会多次重复遍历下层的节点。可以更换一种遍历方式，由下往上遍历。遍历过程中，若该子树的平衡树返回树的深度，不是则返回-1。

class Solution {
public:
    int GetDepth(TreeNode* root){
        if(root == nullptr) return 0;
        int left = GetDepth(root->left);   // 左
        if(left == -1) return -1;  // 左子树不是平衡树
        int right = GetDepth(root->right);  // 右
        if(right == -1) return -1;  // 右子树不是平衡树
        if(abs(left - right) > 1) return -1;  //不是平衡树，中
        return max(left,right) + 1;  
    }
    bool IsBalanced_Solution(TreeNode* root) {
        if(root == nullptr) return true;
        return GetDepth(root)!= -1;
    }
};

40.数组中只出现一次的数字

数组中只出现一次的数字_牛客题霸_牛客网 (nowcoder.com)

法一

初看此题有点惊讶，因为要找到两个数字，而c++不能直接返回两个数，所以给定参数采用了两个指针来保存结果，这也是需要返回多个结果时的一种常见方式。

第一印象还是直接按照题目说的来，题目怎么说我就怎么写。遍历一遍数一数每个数字出现了几次，然后再遍历一次，数两个只出现一次的就可以了。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        unordered_map<int, int> mp;
        for(auto& num : data) mp[num]++;
        auto it = mp.begin();
        while(it != mp.end()){
            if(it->second == 1){
                *num1 = it->first;
                it++;
                break;
            }
            it++;
        }
        while(it != mp.end()){
            if(it->second == 1){
                *num2 = it->first;
                it++;
                break;
            }
            it++;
        }
        return ;
    }
};

法二

A ^ A = 0，所以如果只有一个数字出现了一次的话，直接把数组中的数全异或一次就得到结果了。但该题里右两个那么全异或一次，得到的结果就是A ^ B。该数的1表示A与B不同的位，0表示相同的位。

所以，可以知道A和B的哪一位是不同的。根据这一点将数组分为两组。每组里面自己全部异或一遍得到的就是两个不同的数。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int totalNum = 0;
        for(auto& num : data) totalNum ^= num;
        int sign = 0;
				// get A ^ B
        while(totalNum){
            if(totalNum & (1 << sign)) break;
            sign++;
        }
        num1[0] = 0;
        num2[0] = 0;
        for(auto& i :  data){   // 分组异或
            if(i & (1 << sign)){
                num1[0] ^= i;
            }else{
                num2[0] ^= i;
            }
        }
        return ;
    }
};

41.和为S的连续正数序列

和为S的连续正数序列_牛客题霸_牛客网 (nowcoder.com)

法一

暴力数一数。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ans;
        for(int i = 1;i <= sum / 2  ;i++){
            vector<int> vec;
            int temp = 0;
            for(int j = i ;j < sum ;j++ ){
                temp += j;
                vec.push_back(j);
                if(temp == sum){
                    ans.push_back(vec);
                    break;
                }
            }
        }
        return ans;
    }
};

法二

滑动窗口

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> ans;
        int low = 1, high = 2;  // 初始窗口
        while(low < high){
            int temp = (low + high) * (high - low + 1) / 2;  //等差数列求和公式，（首项 + 尾项）* 项数 / 2
            if(temp == sum){  // 窗口内正好是符合条件的一列数
                vector<int> vec;
                for(int i = low;i<=high;i++) vec.push_back(i);
                ans.push_back(vec);
                low++;
            }else if(temp < sum){  // 窗口内值太小，需要大一点，所以窗口右端右移动
                high++;
            }
            else{   // 窗口太大，需要小一点，就窗口左端左移，减少一个数
                low++;
            }
        }
        return ans;
    }
};

42.和为S的两个数字

和为S的两个数字_牛客题霸_牛客网 (nowcoder.com)

法一

经典两数之和。

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        unordered_set<int> st;
        for(auto& num : array){
            if(st.find(sum - num) != st.end()) return {num,sum - num};
            st.insert(num);
        }
        return {};
    }
};

法二

由于是升序数据，可以利用滑动窗口。

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int low = 0, high = array.size() - 1;
        while(low <= high){
            int temp = array[low] + array[high]; 
            if( temp == sum) return {array[low],array[high]};
            else if(temp < sum) low++;
            else high--;
        }
        return {};
    }
};

43.左旋转字符串

左旋转字符串_牛客题霸_牛客网 (nowcoder.com)

法一

经典方法，三次反转。

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if(n == 0 || str.size() == 0) return str; 
        n = n % str.size();
        reverse(str.begin(),str.begin() + n);
        reverse(str.begin()+ n ,str.end());
        reverse(str.begin(),str.end());
        return str;
    }
};

法二

拼接以后，直接截取后半部分。

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if(len == 0 || n == 0) return str;
        n %= len;
        str += str;
        return str.substr(n,len);
    }
};

44.反转单词序列

法一

题目怎么说，我就怎么写。说是反转，我就直接倒着数。不过倒过来倒过去的看顺序还是有点麻烦。

class Solution {
public:
    string ReverseSentence(string str) {
        string ans,temp;
        for(int i = str.size() - 1; i>=0 ;i--){
            if(str[i] == ' '){
                ans = ans + temp + " ";
                temp = "";
            }else{
                temp = str[i] + temp;
            }
        }
        if(temp.size()) ans += temp;
        return ans;
    }
};

法二

看到反转，倒叙可以想到栈；然后单词之间是用空格分割的可以想到利用流的特性完成句子的分割。

class Solution {
public:
    string ReverseSentence(string str) {
        string temp;
        istringstream is(str);
        stack<string> st;
        while(is>>temp){
            st.push(temp);
        }
        string ans;
        while(!st.empty()){
            temp = st.top();
            st.pop();
            ans += temp;
            ans += ' ';
        }
        return ans.substr(0,ans.size() - 1);
    }
};

法三

其实，如果是python或者JAVA可以直接用split分割之后整体反转一下再加起来就行了。C++没有split可以自己手搓一个。

class Solution {
public:
    vector<string> split(const string& input,const char& reg){
        stringstream ss(input);
        vector<string> ans;
        string token;
        while(getline(ss,token,reg)){
            ans.push_back(token);
        }
        return ans;
    }
    string ReverseSentence(string str) {
        vector<string> vec = split(str,' ');
        reverse(vec.begin(),vec.end());
        string ans;
        for(auto& s : vec){
            ans += s;
            ans += " ";
        }
        return ans.substr(0,ans.size() - 1);
    }
};

45.扑克牌顺子

扑克牌顺子_牛客题霸_牛客网 (nowcoder.com)

法一

顺子的特点：

除了0以外，不能有相同的牌。
两张牌之间的间隔必须为1，如果不为1需要用0补齐。需要补的0的个数记为inner。
如果0的个数小于inner，则可以补成顺子，否则不行。

class Solution {
public:
    bool IsContinuous(vector<int>& numbers) {
        sort(numbers.begin(),numbers.end());
        int zero = 0, inner = 0;
        for(int i = 0 ;i<numbers.size() - 1;i++){
            if(numbers[i] == 0) zero++;
            else if(numbers[i] == numbers[i + 1]) return false;
            else
                inner += numbers[i + 1] - numbers[i] - 1;
        }
        if(zero < inner) return false;
        return true;
    }
};

虽然顺子里只有两张王（只有两个0），但有个样例是[1,0,0,5,0]如果输出为false无法通过。所以代码中不需要添加对0个数是否小于2的判断。
ps. 以前做过一次类似的，通过率一直差一点百思不得其解，做这个的时候突然顿悟，当时没想到不能有重复的牌。

法二

原理同上，换种写法。

class Solution {
public:
    bool IsContinuous(vector<int>& numbers) {
        sort(numbers.begin(),numbers.end());
        int zero = 0;
        int i = 0;
        while(numbers[i] == 0) zero++, i++;
        int inner = 0;
        for(;i<numbers.size() - 1;i++){
            if(numbers[i] == numbers[i + 1]) return false;
            inner += numbers[i + 1] - numbers[i] - 1;
        }
        if(zero < inner) return false;
        return true;
    }
};

46.孩子们的游戏(圆圈中最后剩下的数)

孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (nowcoder.com)

法一

题目怎么说，那就怎么写。

n个人就搞一个容量为n的数组。
每m个重新开始报数，也需要一个变量来记录是否到了m个。到了的话，就把vec[m]设为-1表示孩子出局了。
报数就用一个i变量来记录，如果vec[i]==-1表示这个孩子出局了，直接跳过。由于要从0开始报数，所以i初始化为1。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        vector<int> vec(n,0);
        int i = -1 ,cnt = n;
        int step = 0;
        while(cnt > 0){
            i++;
            if(i >= vec.size()) i = 0;
            if(vec[i] == -1) continue;
            step++;
            if(step == m){
                vec[i] = -1;
                step = 0;
                cnt--;
            }
        }
        return i;
    }
};

法二

利用约瑟夫环的公式。

约瑟夫问题–五种变式 - 小又又

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

47.求1+2+3+…+n

求1+2+3+…+n_牛客题霸_牛客网 (nowcoder.com)

初看好简单，仔细一看不能使用乘除和判断，也就是说只能用加法和条件判断，故不能用求和公式，那就基本只能用位运算进行条件判断了。

原式 = n +( 0 +1 + 2 + 3 + …)
与运算有“短路”作用

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

48.不用加减乘除做加法

一眼位运算。

异或运算可以得到两数相加后各二进制位的非进位信息。（两数不同则是1，不同的话肯定一个0一个1，结果肯定是1）
与运算可以得到进位信息。（与运算只有在两个数都是1的时候才会是1，即进位）

class Solution {
public:
    int Add(int num1, int num2) {
        int carry = num2;
        int sum = num1;
        while(carry){
            int temp = sum ^ carry;
            carry = (sum & carry) <<1;
            sum = temp;
        }
        return sum;
    }
};

49.把字符串转换成整数

把字符串转换成整数_牛客题霸_牛客网 (nowcoder.com)

题目怎么说就怎么写，一位一位的数，遇见不对的直接返回0。

class Solution {
  public:
    int StrToInt(string str) {
        int i = 0;
        bool flag = true;
        int ans = 0;
        if (str[i] == '+') i++;
        else if (str[i] == '-') {
            flag = false;
            i++;
        }
        while (i < str.size()) {
            if ('0' <= str[i] && str[i] <= '9') {
                ans *= 10;
                ans += str[i] - '0';
                i++;
                // cout << ans << endl;
            } else {
                return 0;
            }
        }
        if (!flag) ans = -ans;
        return ans;
    }
};

50.数组中重复的数字

数组中重复的数字_牛客题霸_牛客网 (nowcoder.com)

题中给出的代码模板有一种C的味道。

法一

找第一个重复的数字，那就从头开始数，一边数一边用unordered_map记下来。

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        unordered_map<int,int> mp;
        for(int i = 0;i<length;i++){
            if(mp.count(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }
            mp[numbers[i]]++;
        }
        return false;
    }
};

法二

用vector来实现一个简化的哈希表也是个不错的方法

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        vector<bool> vec(length,false);
        for(int i = 0;i<length;i++){
            if(vec[numbers[i]] == false) vec[numbers[i]] = true;
            else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
};

法三

数组中所有数都在0~n-1范围内。
在遍历过程中，将对应索引位置的数＋n。同时，只要遍历过程中遇见一个位置的数>=n就表明，该位置对应的数重复了。
可以这么做的原因是数组中所有数的范围是0~n-1，所以只要在遍历过程中对length取余就可以得到原始数据。而原始数据 + n相当于添加标志位类比于法二中的辅助数组。
举例，{1,2,1,3}中，n = 4。
- 第一次循环index = 1，num[1] = 2 + 4 = 6。
- 第二次循环index = 2, num[2] = 1 + 4 = 5。
- 第三次循环index = 1， num[1] > length。所以1重复了。

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i = 0;i<length;i++){
            int index = numbers[i] % length;  // 获取原始数值
            if(numbers[index] >= length){
                duplication[0] = index;
                return true; 
            }
            numbers[index] += length;
        }
        return false;
    }
};

51.构建乘积数组

构建乘积数组_牛客题霸_牛客网 (nowcoder.com)

第一印象是求数组全部元素的乘积，然后每个位置都除以自己即可。但题目要求无法使用除法，只能另寻他法。

法一

啥也不管了，先暴力吧。

class Solution {
public:
    vector<int> multiply(vector<int>& A) {
        vector<int> ans(A.size(),0);
        for(int i = 0;i<A.size();i++){
            int mul = 1;
            for(int j = 0;j<A.size();j++){
                if(j != i) mul *= A[j];
            }
            ans[i] = mul;
        }
        return ans;
    }
};

法二

两次遍历。

乍看好像毫无头绪，但是细细琢磨发现b[i]等于a中除a[i]外所有元素的乘积，即b[i] = i左边的元素乘积 * i右边的元素乘积。而在一次遍历过程中左边或右边单独的乘积是可以累计的。

故，

首先将b数组全部初始化为1。
第一次遍历，用temp记录遍历过程中从左开始的a中元素的累积，并将结果与b[i]相乘。
第二次遍历，依然用temp记录从右开始的a中元素的累积，并将结果与b[i]相乘。
得到最终结果。

class Solution {
public:
    vector<int> multiply(vector<int>& A) {
        int len = A.size();
        vector<int> ans(len,1);
        int temp = 1;
        for(int i = 1;i<len;i++){
            temp *= A[i - 1];
            ans[i] *= temp;
        }
        temp = 1;
        for(int i = len - 2;i >= 0;i--){
            temp *= A[i + 1];
            ans[i] *= temp;
        }
        return ans;
    }
};

52.正则表达式匹配

正则表达式匹配_牛客题霸_牛客网 (nowcoder.com)

看起来就是实现正则表达式里的.和*。想不到怎么搞。

法一

C++11支持正则表达式了，但是牛客这里必须自己引入头文件，应该是后台的万能头文件不包括正则吧。

#include<regex>
class Solution {
public:
    bool match(string str, string pattern) {
        return regex_match(str,regex(pattern));
    }
};

法二

直接开抄

首先，.就代表一个万能字符做特殊判定即可，困难的是*。

假设，abc与c*abc进行匹配，在从左向右匹配的过程中，首先a与c不匹配，发现不同但并不能做出“不匹配的判断”因为c后面还有一个*，代表字符可以出现任意次。所以，是否匹配还和当前字符后面跟着的符号有关。还需要去分情况讨论，很是困难。

但是，如果反过来看。从右边往左边匹配困难就少很多了。

假设str = aab，pattern = c*a*b。每次匹配过程，结果只和当前匹配的字符和左边的字符有关，不需要考虑右边是否还跟着其他字符。需要讨论的情况就少了很多，而且问题可以转换为子问题——当前字符是否匹配 + 之前的串是否匹配。可以考虑动规。

dp[i][j]：长度为i的str与长度为j的pattern是否匹配。

之后需要分情况讨论（分类依据是p中当前匹配字符是否是*，因为如果其是普通字符或者.可以直接比较）：

p[i-1]!= '*'
1. 当前字符匹配成功，即s[i-1]==p[j-1] || p[j -1] == '*'，此时dp[i][j] = dp[i-1][j-1]（当前字符匹配成功，问题转换为之前的字符串是否匹配成功）
2. 匹配不成功，dp[i][j] = false;
p[i-1]== '*'比较s[i-1]与p[j -2]（*前的字符）
1. 不匹配，即s[i - 1] != p[j - 2] && p[j - 2] != '.'，此时dp[i][j] = dp[i][j - 2];（跳过p中不匹配的部分继续匹配）
2. 匹配，又有三种情况
  1. 假设匹配0次，即匹配到了假装没匹配到直接跳过。此时dp[i][j] = dp[i][j - 2];
  2. 假设匹配1次，此时dp[i][j] = dp[i][j - 1];此时相当于p中多了一个*，其余可以直接匹配，故直接跳过*即可。
  3. 假设匹配多次，此时dp[i][j] = dp[i-1][j];相当于p中有a，代表aaa。匹配过程中假设s[i-1]为可以匹配到的最后一个a，故直接跳过s[i-1]继续去比。

class Solution {
public:
    bool match(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<vector<bool>> dp(n + 1,vector<bool>(m + 1,false));
        dp[0][0] = true;
        dp[0][1] = false;
        for(int j = 2;j<=m;j++){
            if(p[j - 1] == '*') dp[0][j] = dp[0][j - 2];
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(p[j - 1] != '*'){
                    if(s[i - 1] == p[j - 1] || p[j - 1] == '.') dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = false;
                }else{      //p[j - 1] == '*'
                    if(s[i - 1] != p[j - 2] && p[j - 2] != '.') dp[i][j] = dp[i][j - 2];
                    else dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }
};

代码中，凡是出现在dp后面的i和j都表示字符串长度，凡是s和p后面的则都表示索引。

53.表示数值的字符串

LCR 138. 有效数字 - 力扣（LeetCode）

看不懂，直接开抄。

有效数字（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
若干空格

将所有能正确表示数值的字符串的形势总结如下：

空格只能出现在开头和结尾。
.出现的正确情况：只出现一次，且出现在e的前面。
e出现的正确情况：只出现一次，且出现前有数字。
+-出现的正确情况：只能在开头或e后一位。

class Solution {
public:
    bool validNumber(string s) {
        // 去掉首尾空格
        int start = s.find_first_not_of(' ');
        if (start == string::npos) return false;
        int end = s.find_last_not_of(' ');
        s = s.substr(start, end - start + 1);

        bool numFlag = false;
        bool dotFlag = false;
        bool eFlag = false;

        for (int i = 0; i < s.size(); i++) {
            if (isdigit(s[i])) {
                numFlag = true;
            } 
            //判断'.'的出现是否合法
            else if (s[i] == '.' && !dotFlag && !eFlag) {
                dotFlag = true;    
            } 
            // 判断'e'的出现是否合法
            else if ((s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false; // 'e'后面必须跟着整数
            } 
            // 判断正负号出现是否合法
            else if ((s[i] == '+' || s[i] == '-') && (i == 0 || s[i - 1] == 'e' || s[i - 1] == 'E')) {
                // 正确的位置不做处理
            } 
            // 其他情况都不合法
            else {
                return false;
            }
        }
        // 确保'e'或'E'后有数字
        return numFlag;
    }
};

54.字符流中第一个不重复的字符

字符流中第一个不重复的字符_牛客题霸_牛客网 (nowcoder.com)

初看懵逼的很，不明白insert这个函数有啥好用。后来才发现，这个是把字符串当作字符流。用insert在遍历字符串的同时，不断显示第一个不重复字符。

这就好说了。

法一

巧用库函数

class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch) {
         vec.push_back(ch);
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        if(vec.empty()) return '#';
        for(auto& ch : vec){
            if(count(vec.begin(),vec.end(),ch) == 1) return ch;
        }
        return '#';
    }
private:
    vector<int> vec;

};

法二

不用库函数，用哈希表自己数。空间复杂度会高一点，但应该会稍微快一点。

class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch) {
         vec.push_back(ch);
         mp[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        if(vec.empty()) return '#';
        for(auto& ch : vec){
            if(mp[ch] == 1) return ch;
        }
        return '#';
    }
private:
    vector<int> vec;
    unordered_map<char, int> mp;

};

55.链表中环的入口结点

LCR 022. 环形链表 II - 力扣（LeetCode）

直接开抄。代码随想录 (programmercarl.com)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};

56.删除链表中重复的节点

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

法一：

与83. 删除排序链表中的重复元素 - 力扣（LeetCode）很像。只不过本题重复的节点一个也不保留。这时候需要考虑第一个元素的处理问题。因为如果保留一个重复节点的话，第一个元素即使是重复的也需要保留，就不需要考虑了。但如果一个也不保留的话，第一个节点也有需要删除的可能性。

这时候，只要在原来代码的基础上新增加一个虚拟头节点，这样第一个节点就成了第二个，两个问题就统一起来了。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next && cur->next->next){
            if(cur->next->val == cur->next->next->val){
                int temp = cur->next->val;
                while( cur->next && cur->next->val == temp){
                    cur->next = cur->next->next;
                }
            }else{
                cur = cur->next;
            }
        }
        return dummyHead->next;
    }
};

法二：

迭代法。将问题分解为当前节点的去留问题和后继链表的去除重复节点问题。

递归出口：当前节点为空或没有后继节点。
递归问题：
- 当前节点值与后继节点值不一致：当前节点需要保留，故head->next = deleteDuplicates(head->next);然后返回。
- 当前节点值与后继节点值一样：当前节点不需要保留，需要找到与当前节点值不一样的某个后继节点，从该节点开始继续迭代 deleteDuplicates(temp)。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        if(head->val != head->next->val){
            head->next = deleteDuplicates(head->next);
            return head;
        }else{
            ListNode* temp = head->next;
            while( temp && temp->val == head->val){
                temp = temp->next;
            }
            return deleteDuplicates(temp);
        }   
        return nullptr;
    }
};

57.二叉树的下一个结点

面试题 04.06. 后继者 - 力扣（LeetCode）

法一：

很直观的一种写法。找中序遍历的下一个节点，那就中序遍历一次，把遍历顺序存在一个数组里，之后遍历一次数组就找到下一个了。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        inorder(root);
        for(int i = 0;i<nodes.size();i++){
            if(nodes[i] == p && i + 1 < nodes.size()) return nodes[i + 1]; 
        }
        return nullptr;
    }
    void inorder(TreeNode* root){
        if(root == nullptr) return ;
        inorder(root->left);
        nodes.push_back(root);
        inorder(root->right);
    }
private:
    vector<TreeNode*> nodes;
};

法二：

法一好像有点浪费空间，其实不需要把所有的遍历结果都存一遍，只要记录两个就行了。pre和cur。若pre == p，那么cur就是后继。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> st;
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur != nullptr){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                if(pre == p) return cur;
                pre = cur;
                cur = cur->right;
            }
        }
        return nullptr;
    }
};

二叉树的下一个结点_牛客题霸_牛客网 (nowcoder.com)

牛课上这个差不多的题目给出的形式还不一样。牛客只给了一个节点，没有给出根节点所以不能直接遍历。但牛客上的树有一个next指针指向父亲节点，所以也好办。直接分情况讨论即可：

p是空节点：返回nullptr
p有右孩子：中序遍历，所以有右孩子的话，下一个节点就是从右节点作为基准，开始找最左边的孩子。
p没有右孩子：
- 若p的父亲节点是根节点的话：直接返回其父亲节点即可。
- 若p的父亲节点不是根节点的话：此时，按照左根右的遍历顺序来看，p的父亲节点一定是已经遍历过了。需要找到当前节点是其父节点的左子节点的那个父节点。（左根右体遍历顺序中，假设父亲节点为pre，当前节点为p。只要p是pre的右孩子，pre就一定已经遍历过了。当p是pre的左孩子时，p的下一个就是pre。）

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* p) {
        if( p == nullptr) return p;
        if(p->right != nullptr){
            TreeLinkNode* cur = p->right;
            while(cur->left)
                cur = cur->left;
            return cur;
        }
        while(p->next != nullptr){
            TreeLinkNode* pre = p->next;
            if(pre->left == p) return pre;
            p = p->next;
        }
        return nullptr;
    }
};

58.判断对称的二叉树

LCR 145. 判断对称二叉树 - 力扣（LeetCode）

比较简单的一道题。注意对称判定的时候是左孩子的左子树和右孩子的右子树判定（其他类推）即可。

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        if(left == nullptr && right == nullptr) return true;
        else if(left == nullptr || right == nullptr) return false;
        else if(left->val != right->val) return false;
        else{
            return compare(left->left,right->right) && compare(left->right,right->left); 
        }
    }
    bool checkSymmetricTree(TreeNode* root) {
        if(root == nullptr) return true;
        return compare(root->left,root->right);
    }
};

59.按之字形顺序打印二叉树

按之字形顺序打印二叉树_牛客题霸_牛客网 (nowcoder.com)

法一

第一印象，直接层序遍历，然后将偶数位置的数组翻转一下。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(vec);
        }
        for(int i = 1;i<ans.size();i+=2){
            reverse(ans[i].begin(),ans[i].end());
        }
        return ans;
    }
};

法二

也可以用一个标志位，在插入时就直接改变插入方向。这里就用odd作为奇数行标志位

class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root) que.push(root);
        bool odd = true;
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();
                if(odd)
                    vec.push_back(node->val);
                else
                    vec.insert(vec.begin(), node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            odd = !odd;  // 遍历完一行了，标志一下方向变了
            ans.push_back(vec);
        }
        return ans;
    }
};

60.把二叉树打印成多行

把二叉树打印成多行_牛客题霸_牛客网 (nowcoder.com)

这不是一个标标准准的层序遍历吗

class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(vec);
        }
        return ans;
    }
};

61.序列化二叉树

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

直接开抄。

二叉树的序列化最大的问题是如何唯一的表示一棵树。

单独的前中后序遍历都无法唯一表示一棵树。（前+ 后这种的才能确定一棵树）
如果要唯一表示，可以采用层序遍历，然后遍历过程中将nullptr节点也记录下来，这里记做null。

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == nullptr) return "null";
        return to_string(root->val) + ',' + serialize(root->left) + ',' + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> que;
        stringstream ss(data);
        string item;
        while(getline(ss,item,',')){
            que.push(item);
        }
        return deserializeHelper(que);
    }
private:
    TreeNode* deserializeHelper(queue<string>& que){
        string val = que.front();
        que.pop();
        if(val == "null") return nullptr;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserializeHelper(que);
        node->right = deserializeHelper(que);
        return node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

62.二叉搜索树中第k小的元素

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

由于是二叉搜索树，中序遍历的顺序就是从小到大的顺序。所以直接用迭代法遍历一次，每遍历一个数k减1，k减为0时就找到了第k小的元素。

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur != nullptr){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                k--;
                if(k == 0) return cur->val;
                cur = cur->right;
            }
        }
        return -1;
    }
};

63.数据流中的中位数

数据流中的中位数_牛客题霸_牛客网 (nowcoder.com)

295. 数据流的中位数 - 力扣（LeetCode）

涉及到数据流的题目，牛客和力扣的表现形式好像都不太一致。但本质是一样的。

法一

本分老实人，说求中位数那就求，直接求。但是力扣上有规模特别大的数据，这样搞会超时。

class Solution {
public:
    void Insert(int num) {
        vec.push_back(num);
    }

    double GetMedian() { 
        sort(vec.begin(),vec.end());
        int len = vec.size();
        if(len % 2 == 0){
            return (double)(vec[len / 2] + vec[len / 2 - 1])/ 2;
        }else{
            return vec[len / 2]; 
        }
    }
private:
    vector<int> vec;
};

法二

需要进行优化。法一最大的时间消耗就是每次GetMedian都需要进行排序，数据量大的时候很浪费时间。

如果能在插入数据时，使数组中的元素保持有序就不需要排序了。
可以在插入的时候用二分搜索找到插入位置。

这样优化以后力扣能多过一点数据了，但还是不能全过去，21个用例，过了20个。

class Solution {
public:
    void Insert(int num) {
        int pos = getPos(num);
        vec.insert(vec.begin() + pos, num);
    }

    double GetMedian() { 
        int len = vec.size();
        if(len % 2 == 0){
            return (double)(vec[len / 2] + vec[len / 2 - 1])/ 2;
        }else{
            return vec[len / 2]; 
        }
    }
private:
    vector<int> vec;
    int getPos(int num){
        int left = 0, right = vec.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(num < vec[mid]) right = mid - 1;
            else if(num > vec[mid]) left = mid + 1;
            else{
                left = mid;
                break;
            }
        }
        return left;
    }
};

法三

继续优化，感觉vector这个数据结构能换一换，每次在vector中间插入元素，从插入位置开始后面所有元素都要移动，这个是O(N)的。

可以用multiset来代替vector，它是基于红黑树实现的，插入时间复杂度是O(logn)。

这个在两个平台都通过了。

class Solution {
public:
    Solution():mid(mst.end()){};
    void Insert(int num) {
        int n = mst.size();
        mst.insert(num);
        if(!n)   // 若multiset为空，设置mid为begin迭代器
            mid = mst.begin();
        else if(num < *mid)  // num小于中位数：若n为奇数，mid不变；若n是偶数，mid向前移动。
            mid = (n & 1) ? mid : prev(mid);
        else        // num大于等于中位数：若n为奇数，mid向后移动；若n是偶数，mid不变
            mid = (n & 1) ? next(mid) : mid;
        
    }

    double GetMedian() { 
        int n = mst.size();
        // 若n是奇数，next(mid,n %2 - 1) 返回mid本身，若n是偶数，则返回mid前一个元素
        return ((double)(*mid) + *next(mid,n %2 - 1)) / 2;
    }
private:
    multiset<int> mst;
    multiset<int>::iterator mid;
};

法四

经典的大小堆算法。

数据结构
- 用一个小顶堆存储右半部分，right。
- 用一个大顶堆存储左半部分，left。
数据个数关系：假设元素数量为N。
- 如果N为偶数，left和right中元素数量相同。
- 如果N为奇数，right中元素数量要比left中多一。(人为规定，可以反过来)
插入时，假设left中有m个元素，right中有n个元素。
- m = n：（N为偶数）需要向right中添加一个元素。实现：将新元素num添加到left，再将left堆顶元素插入到right。
  - 不能直接插入到right中，因为num大小未知，若其比较小，则其位置应该在left的中间。
  - 先往小的里面插，然后把小的里面的最大的插到大的里面去。如果一开始就插大的，后来发现很小那就直接错了。
- m != n：（N为奇数）这时候需要向left里插入一个元素。实现方法：将新元素插入到right，再将right的堆顶元素插入到left。
添加一个数字的时间复杂度是O(logn)，查找中位数的时间复杂度是O(1)。

class Solution {
public:
    void Insert(int num) {
        if(left.size() != right.size()){  // 奇数
            right.push(num);
            left.push(right.top());
            right.pop();
        }else{      // 偶数
            left.push(num);
            right.push(left.top());
            left.pop();
        }
    }

    double GetMedian() { 
        return (right.size() != left.size()) ? right.top() : (double)(right.top() + left.top()) / 2;
    }
private:
    priority_queue<int,vector<int>, greater<int>> right;  // 小顶堆，数组右半边
    priority_queue<int,vector<int>,less<int>> left;   // 大顶堆，数组左半边
};

64.滑动窗口的最大值

滑动窗口的最大值_牛客题霸_牛客网 (nowcoder.com)

239. 滑动窗口最大值 - 力扣（LeetCode）

法一

滑动窗口需要从左边删除数据，还需要从右边插入数据，所以用双端队列最为合适。
还需要动态求最大值，可以想到“求下一个最大的值”的单调栈思想。
- 对于窗口中的两个位置i和j。i< j，如果i对应的元素不大于j对应的元素。那么在窗口滑动的过程中，只要i还存在，nums[i]一定不是滑动窗口中最大值。（在队列中遍历时只需要保留一个最大值就好了）。这时候i这个位置是没必要保存的。
实现原理：
1. 使用deque存储有潜力成为最大值的元素索引。
2. 遍历nums，遍历过程中
  1. 先检查头部元素（存的是索引），若其与当前元素索引之差等于窗口大小说明该元素已经不再窗口里了，需要移除。——这就是在插入元素时，只把比当前元素小的元素pop出去的原因。如果插入元素比队列中元素小，那么一旦删除了队头元素，该元素就可能成为窗口中的最大值。
  2. 之后检查尾部元素，将队列中索引值对应的元素值小于当前元素的都pop出去，既然比当前元素小，只要当前元素在窗口内，这些元素永无出头之日。
  3. 将当前元素插入队列尾部。
3. 继续遍历nums，知道遍历完整个数组。遍历过程中，不要忘记存储最大值，用作最后返回。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> deq;
        vector<int> ans;
        for(int i = 0;i<nums.size();i++){
            // 移除不在滑动窗口内的元素索引
            if(!deq.empty() && deq.front() == i - k) deq.pop_front();
            // 移除队列中小于当前元素nums[i]的索引
            // 队列中元素代表滑动窗口内元素，若是其小于nums[i]表示其肯定不可能是最大值了
            while(!deq.empty() && nums[deq.back()] < nums[i]) deq.pop_back();
            // 当前元素加入队列
            deq.push_back(i);
            // 窗口形成后，将最大值（队列头部）加入结果
            if(i >= k - 1){
                ans.push_back(nums[deq.front()]);
            }
        }
        return ans;
    }
};

法二

相当于从第k个元素开始不断求当前窗口内的最大值。

很容易可以想到用优先队列可以动态维护一个最大值。但是，优先队列无法记录当前最大值在原数组中是第几个。
优先队列中的元素用pair<元素，索引>，这样就可以在动态维护最大值的同时，记录当前最大值对应的索引元素，在该索引下的元素滑出窗口时将其出队。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> pq;  //大顶堆，存放{元素，索引}
        for(int i = 0;i<k;i++) pq.push({nums[i],i}); // 把前n个元素放入大顶堆
        vector<int> ans = {pq.top().first}; // 直接将第一个元素放入结果数组
        for(int i = k;i<nums.size();i++){
            pq.push({nums[i],i});
            while(pq.top().second < i - k + 1) 
								pq.pop();  // 将已经不在窗口内的最大值去除
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

65.矩阵中的路径

矩阵中的路径_牛客题霸_牛客网 (nowcoder.com)

79. 单词搜索 - 力扣（LeetCode）

直接暴力回溯。但是牛客上给出的代码模板没有用vector，只有char*的字符串，一个比较好的方法就是拿到以前先将其转换成vector<vector<char>>，有STL为啥不用呢。

class Solution {
public:
    bool check(vector<vector<char>>& board,const string& word,int i ,int j ,int k){
        if(i >= board.size() || i < 0
            || j >= board[0].size() || j < 0
            || word[k] != board[i][j]) return false;  // 排除越界和字母不相等的情况
        if(k == word.size() - 1) return true;  // 找到单词了，直接返回true
        board[i][j] = '\0'; // 同一单元格的字母不允许重复使用，所以已经用过的要标记一下
        bool ans = check(board,word,i + 1,j,k + 1) || check(board,word,i,j + 1,k + 1)
                || check(board,word,i - 1,j, k + 1) || check(board,word,i,j - 1,k + 1);
        board[i][j] = word[k]; // 恢复现场，本轮遍历已经结果，要把原来的数组恢复到原来的样子否则会影响下一次判断
        return ans; 
    }
    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size();
        for(int i = 0;i<h;i++)
            for(int j = 0;j<w;j++)
                if(check(board,word,i,j,0)) return true;
        return false;
    }
};

66.机器人的运动范围

机器人的运动范围_牛客题霸_牛客网 (nowcoder.com)

LCR 130. 衣橱整理 - 力扣（LeetCode）

力扣上的题目不一样，但就是换了个皮，内核一样，还是直接暴力。

class Solution {
public:
    int getDigit(int x){
        int sum =  0;
        while(x){
            sum += x % 10 ;
            x /= 10;
        }
        return sum;
    }
    int dfs(int i,int j,int m,int n,int cnt,vector<vector<bool>>& visited){
        if(i < 0 || i >= m || j < 0 || j >= n
        || visited[i][j]   // has visited
        || getDigit(i) + getDigit(j) > cnt)  // don't need calc 
            return false;
        visited[i][j] = true;
        return 1 +  dfs(i + 1,j,m,n,cnt,visited) + dfs(i ,j + 1,m ,n,cnt,visited) + 
                    dfs(i- 1,j,m,n,cnt,visited) + dfs(i ,j - 1,m,n,cnt,visited);
    }
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<bool>> visited(m,vector<bool>(n,false));
        return dfs(0,0,m,n,cnt,visited);
    }
};

67.剪绳子

剪绳子_牛客题霸_牛客网 (nowcoder.com)

343. 整数拆分 - 力扣（LeetCode）

法一

使用dp。

定义dp[i]表示拆分i后得到的最大乘积。
递推公式：dp[i] = max(dp[i],dp[j]*dp[i - j])
- 表面上看只是拆分为了两部分，但是dp[i]代表的是i拆分后得到的最大乘积而不是i本身。
- 其代表的不是一个数而是一个最大乘积积，是一个或多个数的乘积。例如，dp[8]可以拆分为dp[1]和dp[7]。而dp[7]并不等于7，其等于dp[3]*dp[4]。
初始化。初始化过程中要首先2和3需要特殊判定。因为这两个数拆分后的乘积是比自己小的。所以其需要单独return，而在dp数组中dp[2]和dp[3]都应该以2和3的身份出现
- 因为题目要求至少拆分为两项，在递推公式中已经保证了将整数至少拆分为两项。
- 所以，这里2和3这里不需要拆分，直接以本身的形式出现保证最后取得的乘积最大。

class Solution {
public:
    int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 3;i<=n;i++){
            for(int j = 1;j <= i / 2;j++){  // 拆分后的所有结果是对称的只要取一半就行了
                dp[i] = max(dp[i],dp[j] * dp[i - j]);
            }
        }
        return dp[n];
    }
};

法二

法一的写法很直观，但对于2和3需要有个特判，不太统一显得不是特别优雅。

此外，对于dp[2]和dp[3]表示的也不是dp[i]拆分后的最大乘积了，与最初dp[i]的定义略有不符，所以有点不太美观。

其实，上面这些不统一的本质在于2和3拆分后的乘积比本身要小。所以，我们递推公式写成这样dp[i] = max(dp[i],max(j* (i - j),j * dp[i - j]));

其中j * (i - j)是单纯将i拆分为两个整数来乘，j * dp[i - j]则是拆分为两个以及两个以上是数来成。而j本身又考虑了所有可能的情况，所以已经覆盖了所有可能的情况。
注意j * dp[i - j]不能写成dp[j]* dp[i - j]。因为改完后貌似将j又进一步进行了拆分考虑的情况更完全了，但其在面对j > dp[j]情况时得到的结果是比j * dp[i - j]小的就会忽略掉真正的最大乘积。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for(int i = 3;i<=n;i++){
            for(int j = 1;j<= i / 2;j++){
                dp[i] = max(dp[i],max(j* (i - j),j * dp[i - j]));
            }
        }
        return dp[n];
    }
};