Leetcode force buckle (Sword finger offer 36-39) 36 Binary search tree and bidirectional linked list 37 Serialize binary tree 38 Arrangement of strings 39 Numbers that appear more than half of the tim

The finger of the sword Offer 36. Binary search tree and double linked list

Answer key ：

The idea is simple , It is a medium order traversal , Connect nodes while traversing .

Code ：

class Solution {
public:
    Node  *pre,*head;
    void dfs(Node* root){
        if(root==nullptr) return;
        dfs(root->left);
        if(pre==nullptr) head=root;// This is a header node 
        else 
            pre->right=root;
        root->left=pre;
        pre=root;
        dfs(root->right);
    }

    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;
        dfs(root);
        head->left=pre;
        pre->right=head;
        return head;
    }
};

result ：

The finger of the sword Offer 37. Serialize binary tree

Answer key ：

Serialization generally adopts pre order , Middle preface , In the following order , Here we use the preface .

serialize , Use preorder traversal to save the nodes of the binary tree into a string , Between each node ’,‘ separate . It is worth noting that , In the process of traversal, we need to treat the binary tree as a full binary tree , Blank nodes with ’null‘ Express .

Deserialization , Put the string in the queue que in , use ’,‘ Judge and push into the queue . Traverse through the preamble , While traversing the preorder, establish a binary tree node .

Code ：

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

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
  
        queue<string> que;
        string str;
        for(auto i:data){
            if(i==','){
                que.push(str);
                str.clear();
            }
            else
                str.push_back(i);
        }

        return rdeserialize(que);
    }

    TreeNode* rdeserialize(queue<string> &que){
         if (que.front() == "null") {
            que.pop();
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(que.front()));
        que.pop();
        root->left = rdeserialize(que);
        root->right = rdeserialize(que);
        return root;
    }
};

result ：

 

The finger of the sword Offer 38. Arrangement of strings

Answer key ：

The key is to repeat , Because there are repeated characters . You can use a flag bit , Judge whether the current character appears in the previous string .

Code ：

class Solution {
public:
    vector<string> res;
    void dfs(string &s,int sz,int pos){
        if(pos==sz) res.push_back(s);
        for(int i=pos;i<sz;++i){
            bool flag=true;
            for(int j=pos;j<i;++j){
                if(s[j]==s[i]) flag=false;
            } 
            if(flag){
                swap(s[i],s[pos]);
                dfs(s,sz,pos+1);
                swap(s[i],s[pos]);
            }      
        }
    }
    vector<string> permutation(string s) {
        dfs(s,s.size(),0);
        return res;
    }
};

result ：

 

The finger of the sword Offer 39. A number that appears more than half the times in an array

There is a number in an array that appears more than half the length of the array , Please find out the number .

You can assume that the array is not empty , And there are always many elements in a given array .

Answer key ：

Method 1 ： Sort

If there are more than half of the repeated characters , After sorting, it must be in the middle of the array .

Code ：

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

result ：

  Method 2 ： Hash

Store with hash , Once the value is greater than half the length of the array, the value is returned .

Code ：

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

result ：