LeetCode刷题笔记——腾讯面试精选50题（4）

二叉树

二叉树的最大深度

思路：使用深度优先搜索递归求解。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

二叉搜索树的最近公共祖先

思路：利用二叉搜索树的特性：每个节点的大小一定介于左孩子和右孩子之间，递归求解。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left, p, q);
        else if (root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right, p, q);
        else return root;
    }
}

二叉搜索树中第K小的元素

思路：二叉搜索树的中序遍历是有序序列，使用递归进行中序遍历时，当计数到k时提前终止递归，返回当前的值。

class Solution {

    private int index = 0;
    private int res = 0;

    public int kthSmallest(TreeNode root, int k) {
        if (root==null || k<0) return 0;
        inOrder(root, k);
        return res;
    }

    public void inOrder(TreeNode root, int k) {
        if (root==null) return;
        inOrder(root.left, k);
        index++;
        if (index==k) {
            res = root.val;
            return;
        }
        inOrder(root.right, k);
    }
}

二叉树的最近公共祖先

思路：使用递归的思想：如果根结点是p或q中的一个，那么它就是所求的最近公共祖先；然后搜索左右子树，如果p和q分别位于当前根结点的左右两边，那么此时的根结点就是最近公共祖先；如果p和q同时位于该节点的左子树或右子树，那么递归搜索那边的子树，直到找到公共祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root;
        else if (l != null) return l;
        else if (r != null) return r;
        else return null;
    }
}

二叉树中的最大路径和

思路：对于一个根节点，如果最大和路径包含这个节点，有如下三种情况：

1. 根节点与左子树、右子树的和，这种情况就是完整的路径无法递归，直接与当前记录的最大值比较
2. 根节点与左子树之和
3. 根节点与右子树之和

对左右子树使用递归求其路径最大值。

class Solution {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        getPathSum(root);
        return max;
    }

    public int getPathSum(TreeNode root) {
        if (root==null) return 0;
        int maxLeft = Math.max(getPathSum(root.left), 0);
        int maxRight = Math.max(getPathSum(root.right), 0);
        int maxPath = root.val + Math.max(maxLeft, maxRight);
        int maxRoot = root.val + maxLeft + maxRight;
        max = Math.max(max, Math.max(maxRoot, maxPath));
        return maxPath;
    }
}

栈和队列

最小栈

思路：用一个辅助栈保存最小值。当有新值入栈时，检查该值是否比辅助栈栈顶值小，若是，则改值压入辅助栈，否则复制辅助栈栈顶值压入辅助栈。这样就保证辅助栈栈顶永远是最小值。

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> helper;

    public MinStack() {
        stack = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (helper.isEmpty() || x<helper.peek()) {
            helper.push(x);
        } else helper.push(helper.peek());
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            helper.pop();
        } else throw new RuntimeException("Stack is empty");
    }

    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        } else throw new RuntimeException("Stack is empty");
    }

    public int getMin() {
        if (!stack.isEmpty()) {
            return helper.peek();
        } else throw new RuntimeException("Stack is empty");
    }
}

有效的括号

思路：使用栈的后进先出思想：遇到左括号则入栈，遇到右括号如果则弹出栈顶，比较其是否成对。最后如果栈为空则返回true。

class Solution {
    public boolean isValid(String s) {
        if (s=="") return true;
        char[] c = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char ch: c) {
            if (ch=='(') stack.push(')');
            else if (ch=='[') stack.push(']');
            else if (ch=='{') stack.push('}');
            else if (stack.isEmpty() || ch!= stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}

哈希表

LRU缓存机制

思路：Java语言的LinkedHashMap实现了可以用LRU排序的哈希表功能。它本质上是由哈希表+双向链表实现的。维护一个双向链表用于保持记录按照最近访问顺序排序，和一个哈希表来保存映射关系。若有读写操作，在双向链表中删除原节点，在头部插入新的节点；当加入新元素后会超过容量时，删除双向链表尾部的节点，同时在哈希表中删除对应的键值对，然后加入新元素。

import java.util.HashMap;

class LRUCache {

    // 构造双向链表的节点
    class Node {

        public int key;
        public int val;
        public Node prev;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    // 构造双向链表数据结构
    class DLinkedNode {

        private Node head;
        private Node tail;
        private int size;
        // 创建头尾哑节点
        public DLinkedNode() {
            this.head = new Node(-1, -1);
            this.tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
            this.size = 0;
        }
        // 在头部添加元素，时间复杂度O(1)
        public void add(Node x) {
            x.prev = head;
            x.next = head.next;
            head.next.prev = x;
            head.next = x;
            size++;
        }
        // 删除某一个节点，时间复杂度O(1)
        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }
        // 删除尾部的节点，并返回这个节点，时间复杂度O(1)
        public Node removeLast() {
            if (tail.prev==head) return null;
            Node last = tail.prev;
            remove(last);
            return last;
        }
        // 获取链表长度
        public int size() {
            return this.size;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> map;
    private DLinkedNode cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DLinkedNode();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            int val = map.get(key).val;
            put(key, val);
            return val;
        }
    }

    public void put(int key, int value) {
        Node node = new Node(key, value);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
        } else if (cache.size()==capacity) {
            Node last = cache.removeLast();
            map.remove(last.key);
        }
        cache.add(node);
        map.put(key, node);
    }
}