week15

141 - 环形链表

经典的快慢指针, 快指针每次走两步，慢指针每次走一步，如果他们能相遇说明一定有环；

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};

142 - 环形链表II

在上一题判断有没有环的基础上，找到入口 实际上就是要额外记录环的长度，这样让双指针中的一个指针提前与另一个指针环的长度，则他们再次相遇的时候一定是环的起点；

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        bool flag = false;
        // 1. 判断是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                flag = true;
                break;
            }
        }
        if(!flag) return nullptr;
        // 2. 记录环的长度 并让cur比head提前走 环那么长的指针
        // 这样他们再次相遇的时候一定就是起点
        ListNode* cur = head;
        do
        {
            slow = slow->next;
            cur = cur->next;
        }while(slow != fast);
        // 3. cur 比 head 提前了一整个环的长度 同时走 直到相遇 就是起点
        while(cur != head)
        {
            cur = cur->next;
            head = head->next;
        }
        return head;
    }
};

143 - 重排链表

注意的点就在这个如何保证左半段链表node个数大于等于右边上了

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        // 1. 找到中点 （注意这里的边界）-> 快慢指针
        ListNode* a = head, *b = head->next; // 在这
        while(b && b->next)
        {
            a = a->next;
            b = b->next->next;
        }
        b = a->next;
        // 2. 链表反转
        a->next = nullptr;
        while(b)
        {
            ListNode* tmp_b_next = b->next;
            b->next = a;
            a = b, b = tmp_b_next;
        } 
        // 3. 两个链表重排
        // 此时 一个头结点是head， 一个头结点是a
        b = head;
        while(a && b)
        {
            ListNode* tmp_b_next = b->next, *tmp_a_next = a->next;
            b->next = a;
            b = a->next = tmp_b_next;
            a = tmp_a_next;
        }
    }
};

144 - 二叉树的前序遍历

总结在后面

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                res.push_back(root->val);
                stk.push(root);
                root = root->left;
            }
            root = stk.top()->right;
            stk.pop();
        }
        return res;
    }
};

145 - 二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                res.push_back(root->val);
                stk.push(root);
                root = root->right;
            }
            root = stk.top()->left;
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

在这里复习一下迭代写法的二叉树前序 中序 后序遍历

前序遍历和中序遍历很像，前序：根左右， 中序：左根右

这里都是通过栈来模拟递归调用的过程，尽可能去遍历左子树， 只要有左子树就插入到栈内；

唯一的区别就是根节点是加入时处理 还是弹出时处理，这里要区分一下代码

+ 前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                // 直接处理root
                res.push_back(root->val);
                stk.push(root);
                root = root->left;
            }
            root = stk.top()->right;
            stk.pop();
        }
        return res;
    }
};

+ 中序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                stk.push(root);
                root = root->left;
            }
            root = stk.top()
            res.push_back(root->val);
            stk.pop();
            // 处理right
            root = root->right;
        }
        return res;
    }
};

后序遍历的实现就不太一样了 主要是有一个反序的过程；

这里利用前序遍历类似的方法，我们预先得到 根右左的遍历结果，再反序即可；

+ 后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while(root || stk.size())
        {
            while(root)
            {
                res.push_back(root->val);
                stk.push(root);
                root = root->right;
            }
            root = stk.top()->left;
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

146 - LRU 缓存机制

+ 这个题考的还挺多的

LRU （Least Recently Used）缓存机制

• 在缓存满的时候，删除缓存里最久未使用的数据，然后再放入新元素；

• 数据的访问时间很重要，访问时间距离现在最近，就最不容易被删除。

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组关键字-值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

这两个操作应该是o(1)的

用到的数据结构: 双链表

avatar

class LRUCache {
public:
    struct Node
    {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val) : key(_key), val(_val), left(nullptr), right(nullptr) {}
    }*L, *R;
    unordered_map<int, Node*> hash;
    int n;
public:
    LRUCache(int capacity) {
        n = capacity;
        // 双链表 定义两个左右端点
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->right = R, R->left = L;
    }
    
    int get(int key) {
        if(!hash.count(key)) return -1;
        Node* p = hash[key];
        remove(p); // 删除
        insert(p); // 插入到头部 
        return p->val;
    }
    
    void put(int key, int value) {
        if(hash.count(key))
        {
            Node* p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        }
        else
        {
            if(hash.size() == n)
            {
                Node* p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            Node* p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }

    void remove(Node* p)
    {
        p->right->left = p->left;
        p->left->right = p->right;
    }
    void insert(Node* p)
    {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }
};

147 - 对链表进行插入排序

模拟题， 找到第一个比当前值大的Node 插他前面

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        for(ListNode* p = head; p; )
        {
            auto cur = dummy, next = p->next;
            while(cur->next && cur->next->val <= p->val) cur = cur->next;
            p->next = cur->next;
            cur->next = p;
            p = next;
        }
        return dummy->next;
    }
};

148 - 排序链表

- 很复杂hh

就mergeSort 好了，题目要求的空间复杂度o(1) 只能用迭代方式完成，太麻烦就不写了

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;

        // 1. 找到中间节点
        ListNode* fast = head->next; // 这个找中点的额外处理
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2. 两段链表分开
        ListNode* b = slow->next;
        slow->next = nullptr;

        // 3. 递归排序
        ListNode*  left = sortList(head);
        ListNode* right = sortList(b);

        return mergeList(left, right);
    }

    ListNode* mergeList(ListNode* left, ListNode* right)
    {
        ListNode* dummy = new ListNode(), *cur = dummy;
        while(left && right)
        {
            if(left->val <= right->val)
            {
                cur = cur->next = left;
                left = left->next;
            }
            else
            {
                cur = cur->next = right;
                right = right->next;
            }
        }
        while(left)
        {
            cur = cur->next = left;
            left = left->next;
        }
        while(right)
        {
            cur = cur->next = right;
            right = right->next;
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

149 - 直线上最多的点数

枚举中心点 -> 枚举斜率

这里注意一下 垂直的情况（斜率为负无穷的情况） 和重复点的情况就好了

还有精度问题 -> long double

typedef long double LD;
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        // 枚举中心点
        int res = 0;
        for(vector<int>& point : points)
        {
            unordered_map<LD, int> kMap;
            int vertical = 0, same_center = 0, maxCnt = 0; // 斜率为0 单独处理
            int x = point[0], y = point[1];
            for(vector<int>& p : points)
            {
                if(p[0] == x && p[1] == y) same_center ++;
                else if (p[0] == x) vertical++;
                else
                {
                    LD k = static_cast<LD>(p[1] - y) / (p[0] - x);
                    // cout << x << ' ' << y << ' ' << p[0] << ' ' << p[1] << '-' << k << endl;
                    kMap[k]++;
                    maxCnt = max(maxCnt, kMap[k]);
                }
            }
            res = max(res, max(maxCnt, vertical) + same_center);
        }
        return res;
    }
};

150 - 逆波兰表达式求值

就按照题里描述的那样 用栈模拟就好了

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int res = 0;
        unordered_set<string> ops = {"+", "-", "*", "/"};
        for(string& s : tokens)
        {
            if(!ops.count(s)) stk.push(stoi(s));
            else
            {
                int a = stk.top();
                stk.pop();
                int b = stk.top();
                stk.pop(); 
                if(s == "*")
                    stk.push(a * b);
                else if (s == "/")
                    stk.push(static_cast<double>(b) / a);
                else if (s == "+")
                    stk.push(a + b);
                else
                    stk.push(b - a);
            }
        }
        return stk.top();
    }
};