Day9 把数组排成最小的数+树的子结构+和为s的连续正数序列

TODO：

1. 仔细再做一遍把数组排成最小的数(sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });)
2. 重做树的子结构
3. 稍微回顾一下和为s的连续正数序列

一、剑指 Offer 45. 把数组排成最小的数(中等)

拼凑出来的位数都一样，就觉得可能按照桶排序再链接起来就是答案。
但是这样还得遍历每个数字时间复杂度就会很高。
于是就又看了题解，将x < y，定义为x该排y的右边，再用快排(很有意思！⭐)/内置排序 对数字们进行排序最后组合起来。

方法一 内置函数：

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(int i = 0; i < nums.size(); i++)
            strs.push_back(to_string(nums[i]));
        sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });
        for(int i = 0; i < strs.size(); i++)
            res.append(strs[i]);
        return res;
    }
};

方法二 快排：

class Solution {
public:
    string minNumber(vector<int>& nums) {
        if(nums.size() == 0) return "";
        vector<string> strs;
        for(auto it:nums){
            strs.push_back(to_string(it));
        }
        quickSort(strs,0,nums.size()-1);
        string ans;
        for(auto it:strs){
            ans.append(it);
        }
        return ans;
    }
    void quickSort(vector<string>& strs,  int l, int r){
        if(l >= r) return ;
        int i = l;
        int j = r;
        while(i < j){
            while(((strs[j]+strs[l]) >= (strs[l]+strs[j]) )&& i <j) j--;
            while(((strs[i]+strs[l]) <= (strs[l] +strs[i])) && i <j) i++;
            swap(strs[i],strs[j]);
        }
        swap(strs[l],strs[i]);
        quickSort(strs,l,i-1);
        quickSort(strs,i+1,r);
    }
};

二、剑指 Offer 26. 树的子结构(中等)

😭 写了好久好久好久！！
要先想清楚再写，① 空子树不为任何子树的子树 ②探究B是否为A的子树时，首先在A中找出与B根相同的结点，再进行递归判断。
这道题做错好多遍说明对递归还是掌握的不好。

class Solution {
public:
    bool recur(TreeNode* A, TreeNode* B){
        if(A ==nullptr && B == nullptr) return true;
        if(A == nullptr) return false;
        if(B == nullptr) return true;
        if(B->val != A->val) return false;
        return  recur(A->left,B->left) && recur(A->right,B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(B == nullptr || A==nullptr) return false;
        return ((A->val == B->val) && recur(A,B)) || isSubStructure(A->left,B) || isSubStructure(A->right,B) ;

    }
};

三、 剑指 Offer 57 - II. 和为s的连续正数序列(简单)

以为不会做结果还是能写出来，开心😊

class Solution {
public:
    void save(vector<vector<int>>& res, int small, int big){
        vector<int> temp(big - small + 1);
        for(int j = 0, i = small; i <= big; i++,j++){
            temp[j] = i; 
        }
        res.emplace_back(temp);
    }
    vector<vector<int>> findContinuousSequence(int target) {
        if(target < 3) return {};
        int small = 1;
        int big = 2;
        int sum = 3;
        vector<vector<int>> res;
        while(small < big && big < target){
            if(sum  == target) {save(res,small,big); sum-=small; small+=1;}
            else if(sum < target) {big+=1; sum+=big;}
            else if(sum > target) {sum-=small;small+=1;}
        }
        return res;

    }
};