Leetcode second round 8/23 (LRU)

second round 到目前为止进行了1个星期，应该说每天都有按一定量的题目在做，一天大概15题左右，接连做几天会有点枯燥，有点觉得灰心，觉得会做的题目还是会做，但是可能脱离这些题目就还是不会，所以鸡血慢慢就减少，但是通过上星期五晚上那节课发现，同样一个题目可能你觉得你的做法是好的，但是其实还有更好的方法，更多的方法，而那些之前没有想到的方法现在去接触去理解其实就是对自己算法的提升。 可能在做的时候不能想到这些方法，但是一个题目只有把之前自己的方法自己会的方法弄懂并且做到闭着眼睛都能写出来才能有精力去吸收理解新的方法和思想，所以对于这些题目多做几遍还是很有益的，所以不要放弃，也不要太盲目去做，而是每个题目多想想其他更好的方法，但是也不要因为一时不能想到更好的方法而难过，怪自己笨，不可能一天成天才，慢慢积累，多做几遍，相信每一遍都会有很大的收获。 一个星期过去了，下个星期继续！

这里把上个星期没有完成的几个题目做完：

1. LRU cache
采用的是 hashmap + Double linked list ==> hash map里面存的是 key ： key, value： Key对应的node,  double linked list里面是各个node，hash map的主要作用是通过Key, 快速查找cache里面的值,  double linked list最大的好处是可以做到delete 一个node和insert一个node的时间都是O(1),
class ListNodeN {
public:
    int val;
    int key;
    ListNodeN* pre;
    ListNodeN* next;
    ListNodeN(int key, int val) {
        this->val = val;
        this->key = key;
        pre = NULL;
        next = NULL;
    }
};
class LRUCache{
private:
    int maxSize;
    ListNodeN* cache;
    ListNodeN* tail;
    int size;
    unordered_map<int, ListNodeN*> cmap;
    ListNodeN* deleteNode(ListNodeN* head, ListNodeN* &tail, ListNodeN* node) {
        if (node == head) {
            head = node->next;
            node->next = NULL;
            if (head) head->pre = NULL;
        } else if (node->next == NULL) { //node is tail
            tail = node->pre;
            node->pre->next = NULL;
            node->pre = NULL;
        } else {
            node->pre->next = node->next;
            node->next->pre = node->pre;
        }
        return head;
    }
    ListNodeN* deleteTail(ListNodeN* head, ListNodeN* &tail, unordered_map<int, ListNodeN*> &cmap) {
        ListNodeN* cur = tail;
        if (cur == head) {
            head = NULL;
            tail = head;
            cmap[cur->key] = NULL;
            return head;
        }
        tail = cur->pre;
        cur->pre->next = NULL;
        cur->pre = NULL;
        cmap[cur->key] = NULL;
        return head;
    }
    ListNodeN* insertHead(ListNodeN* head,  ListNodeN* &tail,ListNodeN* node) {
        if (head == NULL) {
            head = node;
            tail = head;
        } else {
            head->pre = node;
            node->next = head;
            head = node;
        }
        node->pre = NULL;
        return head;
    }
public:
    LRUCache(int capacity) {
        maxSize = capacity;
        size = 0;
        cache = NULL;
        tail = NULL;
    }
   
    int get(int key) {
        //case1: the key is in cache
        if (cmap[key] != NULL) {
            ListNodeN* hit = cmap[key];
            cache = deleteNode(cache,tail, hit);
            cache = insertHead(cache, tail, hit);
            return hit->val;
        } else {
           //case2: the key is not in cache
           return -1;
        }
    }
   
    void set(int key, int value) {
        //case 1: the key is not in cache
        if (cmap[key] == NULL) {
            ListNodeN* newNode = new ListNodeN(key, value);
            cmap[key] = newNode;
            if (size >= maxSize) {
                cache = deleteTail(cache, tail, cmap);
                cache = insertHead(cache, tail, newNode);
            } else {
                size++;
                cache = insertHead(cache, tail, newNode);
            }
           
        } else {
            //case 2: the key is in cache
            ListNodeN* hit = cmap[key];
            hit->val = value;
            cache = deleteNode(cache,tail, hit);
            cache = insertHead(cache, tail, hit);
        }
    }
};


2. preorder traversal iterative method

preorder 的iterative的方法是最容易写的，只要理解逻辑

      1. 每次遇到一个node, 直接print 它的值，然后从stack中弹出
      2. 由于Preorder每次都是要先输出left subtree，然后是right subtree, 而且root已经从stack中弹出来了，所以我们需要先保存root的right node, 先把right node 入stack, 在root的left subtree都遍历完了之后，就可以通过之前保存的right node来遍历右子树了。
循环结束条件是 stack 不为空。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rst;
        if (root == NULL) return rst;
        stack<TreeNode*> buf;
        TreeNode* cur = root;
        buf.push(cur);
        while (!buf.empty()) {
            TreeNode* tmp = buf.top();
            rst.push_back(tmp->val);
            buf.pop();
            if (tmp->right) buf.push(tmp->right);
            if (tmp->left) buf.push(tmp->left);
        }
        return rst;
    }
};

3. inorder traversal iterative method

inorder的思路跟preorder相似，我们的遍历顺序是 左中右，所以我们在遍历左子树之前需要保存root的值，当左子树完全遍历之后可以输出root的值，然后可以开始遍历右子树，但是如何去判断左子树已经完全遍历完了呢？ 可以用一个helper node来表明左子树已经遍历完了，当helper node == NULL的时候，说明左子树遍历完了，可以开始pop root,并且开始遍历右子树了。其实helper node含义是当前正在遍历的节点，当helper == NULL means stack.top()的root left subtree已经遍历完了。 可以开始遍历其right subtree.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> rst;
        if (root == NULL) return rst;
        stack<TreeNode*> buf;
        TreeNode* cur = root;
        while (!buf.empty() || cur) {
            if (cur != NULL) {
                buf.push(cur);
                cur = cur->left;
            } else {
                rst.push_back(buf.top()->val);
                cur = buf.top();
                buf.pop();
                cur = cur->right;
            }
        }
        return rst;
    }
};

4.postorder traversal iterative method

postorder的写法下面的wikipedia的写法是最高效的。





5.