Day21 从上到下打印二叉树 + 复杂链表的复制 + 数组中数

TODO:

1. 理解数组中数字出现的次数的有限状态机方法。

一、 剑指 Offer 32 - III. 从上到下打印二叉树 III(中等)

方法一 自己搞的最朴素的方法，层序遍历

class Solution {
public:
   vector<vector<int>> levelOrder(TreeNode* root) {
       if(root == nullptr) return {};
       queue<TreeNode*> que;
       que.push(root);
       vector<vector<int>> res;
       bool flag = true;
       while(!que.empty()){
           int cnt = que.size();
           vector<int> temp;
           for(int i = 0; i < cnt; i++){
               TreeNode* node = que.front();
               que.pop();
               if(node->left){
                   que.push(node->left);
               }
               if(node->right){
                   que.push(node->right);
               }
               temp.push_back(node->val);
           }
           if(flag){
               res.push_back(temp);
           }else{
               reverse(temp.begin(),temp.end());
               res.push_back(temp);
           }
           flag = !flag;
       }
       return res; 

   }
};
//甚至可以根据res的个数推断出层数，从而能少设置一个变量

方法二三 栈或者双端队列

值得一看

二、剑指 Offer 35. 复杂链表的复制(中等)

方法一 哈希

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;    
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* newhead;
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        newhead = new Node(0);
        Node* res = newhead;
        unordered_map<Node*,Node*> hmap;
        Node* phead = head;
        unordered_set<Node*> s;
        while(phead){
            newhead->next = new Node(phead->val);
            newhead = newhead->next;
            if(!hmap.count(phead)){
                hmap[phead] = newhead;
            }
            phead = phead->next;
        }
        phead = head;
        newhead = res->next;
        while(newhead){
           if(phead->random != nullptr){
                newhead->random =hmap[phead->random];
            }
            newhead = newhead->next;
            phead = phead->next;
        }
        return res->next;
    }
};

方法二 拆分

1. 复制各节点，并构建拼接链表
2. 构建各新节点的 random 指向
3. 拆分两链表

三、 剑指 Offer 56 - II. 数组中数字出现的次数 II(中等)

方法一 瞎弄的排序后比较

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i =0; i < nums.size()-1; i++){
            if(nums[i]!=nums[i+1]){
                if(i ==0) return nums[i];
                else if(i+1==nums.size()-1) return nums[i+1];
                else if(nums[i] != nums[i-1] && nums[i]!=nums[i+1])return nums[i];
            }
        }
        return 0;

    }
};

方法二 有限状态机 (超级巧妙的一个方法)⭐

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for(auto it:nums){
            ones = ones^it&~twos;
            twos = twos^it&~ones;
        }
        return ones;

    }
};

简洁

class Solution {
public:
    Node* newhead;
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* p = head;
        unordered_map<Node*,Node*> hmap;

        while(p){
          hmap[p] = new Node(p->val);
          p = p->next;
        }
        p = head;

        while(p){
            hmap[p]->next = hmap[p->next];
            hmap[p]->random = hmap[p->random];
            p = p->next;
        }
        return hmap[head];
    }
};