Posts

将有序数组转换为二叉搜索树 题目 思路 A height-balance BST is achieved by always picking the middle element as the root. The left and right subtree sizes differ by at most 1. ...

验证二叉搜索树 题目 思路 root starts with (-inf, +inf) left child inherits (min, root.val) right child inherits (root.val, max) Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean dfs(TreeNode node, long low, long high) { if (node == null) { return true; } long v = node.val; if (v <= low || v >= high) { return false; } return dfs(node.left, low, v) && dfs(node.right, v, high); } }

题目 思路 找中点并每次拆分链表 递归排序 合并两个有序链表 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode mid = splitMid(head); ListNode left = sortList(head); ListNode right = sortList(mid); return merge(left, right); } private ListNode splitMid(ListNode head) { ListNode slow = head, fast = head, prev = null; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; return slow; } private ListNode merge(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), p = dummy; while (a != null && b != null) { if (a.val <= b.val) { p.next = a; a = a.next; } else { p.next = b; b = b.next; } p = p.next; } p.next = (a != null) ? a : b; return dummy.next; } }

题目 思路 O(1) 查询 (哈希表) 记录最近使用顺序 (链表) 需要组合哈希表 + 双向链表 Java 解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 class LRUCache { private static class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } } private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); private final Node head = new Node(0, 0); private final Node tail = new Node(0, 0); public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) { return -1; } moveToHead(node); return node.val; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { node.val = value; moveToHead(node); return; } Node n = new Node(key, value); map.put(key, n); addAfterHead(n); if (map.size() > capacity) { Node lru = removeTail(); map.remove(lru.key); } } private void moveToHead(Node node) { remove(node); addAfterHead(node); } private void addAfterHead(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private Node removeTail() { Node node = tail.prev; remove(node); return node; } }

题目 思路 dfs 值相等，且 left.left 对 right.right，left.right 对 right.left bfs ...

题目 思路 递归解法 递归遍历左子树 访问当前答案 递归遍历右子树 迭代 + 栈解法 ...

题目 思路 最大深度 = max(左子树深度, 右子树深度) + 1 ...

题目 思路 对于任意节点 先翻转左子树 再翻转右子树 交换左右孩子节点 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } }

题目 思路 如何高效地选择最小节点 1.1. 归并排序 1.2. 小顶堆 Java 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode node : lists) { if (node != null) { pq.offer(node); } } ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode min = pq.poll(); tail.next = min; tail = min; if (min.next != null) { pq.offer(min.next); } } tail.next = null; return dummy.next; } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return mergeRange(lists, 0, lists.length - 1); } private ListNode mergeRange(ListNode[] lists, int l, int r) { if (l == r) { return lists[l]; } int m = l + (r - l) / 2; ListNode left = mergeRange(lists, l, m); ListNode right = mergeRange(lists, m + 1, r); return mergeTwo(left, right); } private ListNode mergeTwo(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; return dummy.next; } }

两数相加 题目 思路 同时遍历两个链表 + 维护一个进位 carry。 ...