Day11 0～n-1中缺失的数字+打印从1到最大的n位数+序列

TODO:

1. 全排列问题还是不大会
2. 重做序列化二叉树

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

虽然做出来了，但是开始想复杂了

class Solution {
public:

    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        int mid;
        while(left <= right){
            mid = left + (right-left);
            if(mid == nums[mid]){//用等于来判断会比用不等于好
                left = left+1;
            }else{
                right = right - 1;
            }
        }
        return left;
    }
};

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

不考虑越界问题特别简单，竟然也提交成功了。可是面试应该不允许这样

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

于是看了题解...
说，解决大数问题一般会用上字符串，那这个就变成了个全排列问题。(所以返回int

class Solution {
public:
    vector<int> ans;
    int pos = 0;
    vector<int> printNumbers(int n) {
        string s = "0123456789";
        string str = "";
        dfs(s, str, n);
        return ans;
    }
    void dfs(string &s, string &str, int k){
        if(str.length()== k){
            if(pos==0){pos=1;return;} //前导零的去除
            ans.push_back(atoi(str.c_str())); //但是atoi里转换的字符串表示的值若是超过int可能会出现问题
            return ;
        }
        for(int i=0; i<s.length();++i){
            str+=s[i];
            dfs(s, str, k);
            str.pop_back();
        }
    }
};

class Solution {
public:
    vector<int> ans;
    int firstZero = 1;
    vector<int> printNumbers(int n) {
        if(n ==0) return {};
        else if(n == 1) return {1,2,3,4,5,6,7,8,9};
        string dai = "0123456789";
        string str = "";
        dfs(dai,str,n);
        return ans;
    }
    void dfs(string&dai ,string& str, int n){
        if(str.size() == n){
            if(firstZero) {firstZero = 0; return ;}
            ans.push_back(atoi(str.c_str()));
            return ;
        }
        for(int i = 0; i < dai.size();i++){
            str += dai[i];
            dfs(dai,str,n);
            str.pop_back();
        }

    }
};

剑指 Offer 37. 序列化二叉树

感觉就像是一道简单递归题，但是它写的是困难，所以事情没有那么简单？
不会不会，值得再做

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res ="";
        dfs1(root,res);
        return res;
    }
    void dfs1(TreeNode* root, string&res){
        if(root == nullptr){
            res+="#,";
            return ;
        }
        res += (to_string(root->val)+",");
        dfs1(root->left,res);
        dfs1(root->right,res);
        
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs2(data,u);
        // return nullptr;     
    }
    TreeNode* dfs2(string&res,int& u){
        if(res[u] == '#'){
            u += 2;
            return nullptr;
        }
        int t = 0;
        int flag = 1;
        while(res[u] != ','){
            if(res[u]=='-')flag=0;
            else t = t*10 + res[u]-'0';
            u++;
        }
        u++;
        if(!flag) t = -t;
        TreeNode* root = new TreeNode(t);
        root->left = dfs2(res,u);
        root->right = dfs2(res,u);
        return root;
        
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));