2020-03-29 刷题2（栈和链表）

复杂链表的复制

这个题目的难点在于，由于random节点可能在当前节点的前面，也可能在后面，所以在第一遍拷贝的时候，是无法正确赋值random节点的。最简单的想法是第一轮构造next节点，第二轮遍历整个链表找到每个节点对应的random节点，这样每次迭代都是O(n)的时间复杂度，整体O(n^2).
第二种做法是设置一个哈希表，存放src节点到tgt节点的映射，第二轮每次只要O(1)的时间复杂度就可以找到random节点，总的时间复杂度O(n)，空间复杂度也是O(n).

/*
// 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) {
        int cnt = 0;
        map<Node*, Node*> sibling_map;
        if(head == nullptr)
            return nullptr;
        Node *nHead = new Node(0);
        Node *cur = nHead, *cur_src = head;
        while(cur_src){
            cur->next = new Node(cur_src->val);
            cur->next->random = cur_src->random;
            sibling_map[cur_src] = cur->next;
            cur = cur->next;
            cur_src = cur_src->next;
        }
        cur = nHead->next;
        while(cur){
            if(cur->random != nullptr){
                cur->random = sibling_map[cur->random];
            }
            cur = cur->next;
        }
        return nHead->next;
    }
};

第三种做法就非常机智了，整体分为三步：

• 1）创建新节点N‘，连在原节点N的后面
• 2）赋值random节点：src->next->random = src->random->next
• 3）将链表拆为两部分，单数是原链表，双数是拷贝的链表
  这种做法时间复杂度是O(n)，空间复杂度O(1)，还不会改变原链表的内容。

/*
// 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) {
        if(head == nullptr)
            return nullptr;
        // construct new nodes
        Node *src_cur = head;
        while(src_cur){
            Node *tmp = new Node(src_cur->val);
            tmp->next = src_cur->next;
            src_cur->next = tmp;
            src_cur = tmp->next;
        }
        // construct random
        src_cur = head;
        while(src_cur){
            if(src_cur->random != nullptr){
                src_cur->next->random = src_cur->random->next;
            }
            src_cur = src_cur->next->next;
        }
        //delete src node
        Node *nHead = head->next, *cur = nHead;
        src_cur = head;
        while(src_cur){
            src_cur->next = cur->next;
            src_cur = src_cur->next;
            cur->next = src_cur ? src_cur->next : nullptr;
            cur = cur->next;
        }
        return nHead;
    }
};

71 简化路径

使用栈，每次截取两个/之间的路径入栈，遇到'..'就pop栈顶元素，遇到'.'不执行操作。有一个样例是'/...'，这种三个点的，是一个自定义的路径名，不是相对路径，需要注意。

class Solution {
public:
    string find_path(string path, int &idx, int plen){
        string s = "";
        while(idx < plen && path[idx] != '/'){
            s += path[idx];
            idx++;
        }
        return s;
    }
    string simplifyPath(string path) {
        if(path.size() == 0) return "";
        stack<string> p;
        int p_len = path.size(), i = 0;
        while(i < p_len){
            if(i < p_len && path[i] == '/'){
                i++;
                continue;
            }
            else{
                string tmp = find_path(path, i, p_len);
                if(tmp == ".")
                    continue;
                if(tmp == ".."){
                    if(!p.empty())
                        p.pop();
                }
                else p.push(tmp);
            }
        }
        string simple_path = "";
        while(!p.empty()){
            simple_path = "/" + p.top() + simple_path;
            p.pop();
        }
        if(simple_path.size() == 0)
            return "/";
        else return simple_path;
    }
};