头像

梵高先生


访客:983

离线:18天前



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        map<ListNode *, ListNode *> m;
        m[NULL] = NULL;
        if(!head) return NULL;
        ListNode * t , *t1, *h, *h1;
        h = head;
        h1 = h;
        t = new ListNode(0);
        t1 = t;
        //cout << "1" <<endl;
        while(h1){
            ListNode * temp = new ListNode(h1->val);
            m[h1] = temp;
            t1->next = temp;

            h1 = h1->next;
            t1 = t1->next;
            //cout << m[h1] << " ";
        }
        t1 = t->next;
        h1 = h;
        while(h1){
            t1->random = m[h1->random];
            h1 = h1->next;
            t1 = t1->next;
            //cout << m[h1->random] << " ";
        }
        return t->next;
    }
};




//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        if(root == NULL) return res;
        dfs(root,sum);
        return res;
    }
    void dfs(TreeNode * r, int sum){
        if(r->left == NULL && r->right == NULL){
            sum -= r->val;
            temp.push_back(r->val);
            if(sum == 0){
                res.push_back(temp);
            }
            //回溯
            temp.pop_back();
            return ;
        } 
        //非叶子节点
        sum -= r->val;
        temp.push_back(r->val);
        if(r->left) dfs(r->left,sum);
        if(r->right) dfs(r->right,sum);
        temp.pop_back();
        return ;
    }
};



C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        if(root == NULL) return res;
        dfs(root,sum);
        return res;
    }
    void dfs(TreeNode * r, int sum){
        if(r->left == NULL && r->right == NULL){
            sum -= r->val;
            temp.push_back(r->val);
            if(sum == 0){
                res.push_back(temp);
            }
            //回溯
            temp.pop_back();
            return ;
        } 
        //非叶子节点
        sum -= r->val;
        temp.push_back(r->val);
        if(r->left) dfs(r->left,sum);
        if(r->right) dfs(r->right,sum);
        temp.pop_back();
        return ;
    }
};


活动打卡代码 AcWing 50. 序列化二叉树

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "#!";

        string res = "";

        res += to_string(root->val);
        res += "!";

        res += serialize(root->left);
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //cout <<data<<endl;
        queue<string> q;
        string temp = "";

        for(int i = 0 ; i < data.size(); i ++){
            if(data[i] != '!'){
                temp += data[i];
            }
            else{
                q.push(temp);
                //cout <<temp<<" ";
                temp = "";
            }
        }

        return buildtree(q);
    }
    TreeNode * buildtree(queue<string> &q){
        string temp = q.front();
        q.pop();

        if(temp == "#"){
            return NULL;
        }
        else{
            TreeNode * t = new TreeNode(stoi(temp));
            t->left = buildtree(q);
            t->right = buildtree(q);
            return t;
        }
    }
};






正反序列化 C++代码

对于处理负数的问题,我只想说使用库函数,省时省力考虑还周全,何乐而不为?

class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "#!";

        string res = "";

        res += to_string(root->val);
        res += "!";

        res += serialize(root->left);
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //cout <<data<<endl;
        queue<string> q;
        string temp = "";

        for(int i = 0 ; i < data.size(); i ++){
            if(data[i] != '!'){
                temp += data[i];
            }
            else{
                q.push(temp);
                //cout <<temp<<" ";
                temp = "";
            }
        }

        return buildtree(q);
    }
    TreeNode * buildtree(queue<string> &q){ //注意此处的引用
        string temp = q.front();
        q.pop();

        if(temp == "#"){
            return NULL;
        }
        else{
            TreeNode * t = new TreeNode(stoi(temp));
            t->left = buildtree(q);
            t->right = buildtree(q);
            return t;
        }
    }
};




//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    vector<int> s;
    bool verifySequenceOfBST(vector<int> sequence) {
        s = sequence;
        return fun(0,s.size()-1);
    }
    bool fun(int l, int r){
        if(r-l <= 1)return true;
        int mid = s[r];
        //int flag = 0;
        for(int i = l ; i < r; i++){
            if(s[i] < mid) continue;
            else{//s[i] > mid
                for(int j = i ; j < r; j++){
                    if(s[j] < mid){
                        return false;
                    }
                }
                return fun(l,i-1)&&fun(i,r-1);
            }
        }
        return fun(l,r-1);
    }
};



C++ 代码

class Solution {
public:
    vector<int> s;
    bool verifySequenceOfBST(vector<int> sequence) {
        s = sequence;
        return fun(0,s.size()-1);
    }
    bool fun(int l, int r){
        if(r-l <= 1)return true;
        int mid = s[r];
        //int flag = 0;
        for(int i = l ; i < r; i++){
            if(s[i] < mid) continue;
            else{//s[i] > mid
                for(int j = i ; j < r; j++){
                    if(s[j] < mid){
                        return false;
                    }
                }
                return fun(l,i-1)&&fun(i,r-1);
            }
        }
        return fun(l,r-1);
    }
};



C++ 代码 姑且称之为遍历即可

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size() == 0 || matrix[0].size() == 0) return res;
        int n = matrix.size();  // 行
        int m = matrix[0].size(); //列

        vector<vector<bool>> b(n,vector<bool>(m,false));

        int d[4][2] = {
            {0,1}, //right
            {1,0}, // down
            {0,-1}, //left
            {-1,0} //up
        };

        int x = 0 , y = 0;
        int k = 0; //k:0-3

        res.push_back(matrix[0][0]);
        b[0][0] = true;

        for(int i = 0; i < m*n - 1; i++){
            x += d[k][0];
            y += d[k][1];

            if(x >= 0 && x < n && y >= 0 && y < m && (!b[x][y])){
                res.push_back(matrix[x][y]);
                b[x][y] = true;
            }
            else{//回退
                x -= d[k][0];
                y -= d[k][1];    
                k = (k + 1) % 4;
                i--;
            }
        }

        return res;
    }
};






//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size() == 0 || matrix[0].size() == 0) return res;
        int n = matrix.size();  // 行
        int m = matrix[0].size(); //列

        vector<vector<bool>> b(n,vector<bool>(m,false));

        int d[4][2] = {
            {0,1}, //right
            {1,0}, // down
            {0,-1}, //left
            {-1,0} //up
        };

        int x = 0 , y = 0;
        int k = 0; //k:0-3
        res.push_back(matrix[0][0]);
        b[0][0] = true;

        for(int i = 0; i < m*n - 1; i++){
            x += d[k][0];
            y += d[k][1];

            if(x >= 0 && x < n && y >= 0 && y < m && (!b[x][y])){
                res.push_back(matrix[x][y]);
                b[x][y] = true;
            }
            else{
                x -= d[k][0];
                y -= d[k][1];    
                k = (k + 1) % 4;
                i--;
            }
        }
        return res;
    }
};






//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {

        queue<TreeNode *> q;
        vector<vector<int>> res;
        vector<int> temp;

        if(root == NULL) return res;        
        q.push(root);
        q.push(NULL);

        while(!q.empty()){
            TreeNode* t = q.front();
            q.pop();
            if(t){//t != NULL
                temp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            else{ //t == NULL
                res.push_back(temp);
                temp.clear();
                if(!q.empty()) q.push(NULL);
            }
        }
        //翻转奇数行
        for(int i = 0; i < res.size(); i++){
            if(i%2 == 1){//翻转res[i][0] ---res[i][k]
                int j = 0;
                int k = res[i].size() - 1;
                while(j < k){
                    swap(res[i][j++],res[i][k--]);
                }
            }
        }
        return res;
    }
};