8.13 哈希表中等 128 Longest Consecutive Sequence 138 Copy List with Random Pointer

128 Longest Consecutive Sequence

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //无序array整数数组，返回最长的连续的序列长度，首先这些数不按顺序
        //时间复杂度O(n)
        //使用哈希表，先存后遍历---->no map , set right
        if(nums.empty())return 0;
        unordered_map<int,int> hash;
        for(int x : nums){
            hash[x]++;
        }
        //unordered_set<int> hash(nums.begin(),nums.end())
        int ans = 0;
        for(const auto& pair : hash){
            int n = pair.first;
            if(hash.find(n-1) == hash.end()){//判断是否为起点
                int len  = 1;
                int current = n;
            
                while(hash.find(current + 1) != hash.end()){//找后续数字是否在哈希表中
                    current++;
                    len++;
                }
                
                ans = max(ans,len);
            }
        }
        return ans;
    }
};

c++代码学习 unordered_set和map的区别

上述代码中，将nums存入hash可以用下列的代码代替
unordered_set<int> hash(nums.begin(),nums.end());
遍历时也就是
for(int n : hash){
}

138 Copy List with Random Pointer【默写】

难点：搞清楚深拷贝： None of the pointers in the new list should point to nodes in the original list.
由于随即指针指向整个链表中的任一结点，所以可以确定先复制结点的val和next到新链表中，这个过程结束后，再复制random
random复制是否正确取决于是否搞清楚了深拷贝

/*
// 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* copyRandomList(Node* head) {
        //一个长度为n的链表，每一个结点包含一个额外的随机指针，可以指向链表中的任意结点或者为null
        //copy包括每个n分支的新结点
        if(!head) return nullptr;

        Node* dummy = new Node(0);
        Node* temp = dummy;
        Node* p = head;
        //正常复制链表后，再添加随即指针指向的内容
        unordered_map<Node* , Node*> hash;
        while(p){
            Node* newNode = new Node(p->val);
            hash[p] = newNode;//存储旧指针与新指针之间的映射关系
            temp->next = newNode;
            temp = temp->next;
            p = p->next;
        }
        //添加random
        p = head;
        temp = dummy->next;//上述过程中temp->next = newNode;
        while(p){
            if(p->random){
                temp->random = hash[p->random];//使用哈希表获取对应的random结点
            }
            temp = temp->next;
            p = p->next;
        }
        return dummy->next;
    }
};