2018-12-04

今天没有怎么刷题，看了一些面经，有一些有意思的题目记录一些吧

LeetCode Balanced Binary Tree

这题比较strightforward，首先理解balanced binary tree的定义，然后实现一个method去发现每个node的左右节点的depth，然后verify是否这个节点符合定义，整体使用recursion实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)   return true;
        if (Math.abs(findDepth(root.left, 0)-findDepth(root.right, 0)) > 1) return false;
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int findDepth(TreeNode root, int depth) {
        if (root == null)   return depth;
        return Math.max(findDepth(root.left, depth+1), findDepth(root.right, depth+1));
    }
}

LeetCode LRU

这题基本解法是运用 DoubleLinkedList + HashMap来解决，这里使用了Deque来代替doubleLinkedList来简化代码，大大提高了时间复杂度是O(N), 因为Deque 不支持index access to element，如果是使用DoubleLinkedList，时间复杂度应该是O(1)

class LRUCache {

    Map<Integer, Integer> map;
    Deque<Integer> deque;
    int capacity;
    
    public LRUCache(int capacity) {
        map = new HashMap<Integer, Integer>();
        deque = new ArrayDeque<Integer>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            deque.remove(key);
            deque.addFirst(key);
            return map.get(key);
        }else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (map.size() < capacity) {
            if (map.containsKey(key)) {
                deque.remove(key);                 
            }
        }else {
            if (map.containsKey(key)) {
                deque.remove(key);
            }else {
                int x = deque.removeLast();
                map.remove(x); 
            }          
        }  
        deque.addFirst(key);
        map.put(key, value);
    }
}