LeetCode总结

目录

心法宝典

双指针

1. 序列

// [i, j), 无重复的时候j++, 有重复的时候i++
public int lengthOfLongestSubstring(String s) {
 Set<Character> set = new HashSet<>(); // int[] dic = new int[256];
 int i = 0, j = 0;
 int ret = 0;
 while (j < s.length() && i <= j) {
 // 是否存在重复字符
 if (!set.contains(s.charAt(j))) {
 set.add(s.charAt(j));
 j++;
 ret = Math.max(ret, j-i); // 注意此处没+1,因为j先自增了
 } else {
 set.remove(s.charAt(i));
 i++;
 }
 }
 return ret;
}

public int maxArea(int[] height) {
 int i = 0, j = height.length-1;
 int maxValue = 0;
 while (j - i >= 1) {
 System.out.println((j-i) * Math.min(height[i], height[j]));
 maxValue = Math.max(maxValue, (j-i) * Math.min(height[i], height[j]));
 if (height[i] < height[j]) {
 i++;
 } else {
 j--;
 }
 }
 return maxValue;
}

// 难点: 三数之和 -> 两数之和(哈希、排序+双指针); 排除重复
// 排序+双指针 : val<target时low++; val>target时 high--; val==target时low++ & high--
// 如何跳过重复
public List<List<Integer>> threeSum(int[] nums) {
 List<List<Integer>> ret = new LinkedList<>();
 Integer iPre = null;
 Arrays.sort(nums);
 for (int i = 0; i < nums.length-2; i++) {
 if (nums[i] > 0) break;
 int j = i+1, k = nums.length-1, sum = 0 - nums[i];
 Integer jPre = null, kPre = null;
 if (iPre != null && iPre == nums[i]) continue; // 去重
 iPre = nums[i];
 while (j < k) {
 if (nums[j] + nums[k] < sum) {
 j++;
 }
 else if (nums[j] + nums[k] > sum) {
 k--;
 } else {
 if (jPre == null || (jPre != nums[j] && kPre != nums[k])) {
 ret.add(Arrays.asList(nums[i], nums[j], nums[k]));
 }
 jPre = nums[j];
 kPre = nums[k];
 j++;
 k--;
 }
 }
 }
 return ret;
}

// 本题假定只有 一个答案,所以不用去重了
// 和第15题思路一模一样
public int threeSumClosest(int[] nums, int target) {
 // nums.length > 3
 Arrays.sort(nums);
 int ret = nums[0]+nums[1]+nums[2];
 for (int i = 0; i < nums.length-2; i++) {
 int j = i+1, k = nums.length-1, sum;
 while (j < k) {
 sum = nums[i] + nums[j] + nums[k];
 if (Math.abs(sum-target) < Math.abs(ret-target)) {
 ret = sum;
 }
 if (sum == target) {
 return target;
 } else if (sum > target) {
 k--;
 } else {
 j++;
 }
 }
 }
 return ret;
}

// 双指针 + 去重
public List<List<Integer>> fourSum(int[] nums, int target) {
 List<List<Integer>> ret = new LinkedList<>();
 Integer aPre = null;
 Arrays.sort(nums);
 for (int a = 0; a < nums.length-3; a++) {
 if (nums[a] > 0 && nums[a] > target) break; // 注意一定要加nums[a] > 0
 if (aPre != null && aPre == nums[a]) continue;
 aPre = nums[a];
 Integer bPre = null;
 for (int b = a+1; b < nums.length-2; b++) {
 if (nums[b] > 0 && nums[a] + nums[b] > target) break;
 if (bPre != null && bPre == nums[b]) continue; // 去重
 bPre = nums[b];
 int c = b+1, d = nums.length-1, sum = target - (nums[a] + nums[b]);
 Integer cPre = null, dPre = null;
 while (c < d) {
 if (nums[c] + nums[d] < sum) c++;
 else if (nums[c] + nums[d] > sum) d--;
 else {
 if (cPre == null || (cPre != nums[c] && dPre != nums[d])) {
 ret.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
 }
 cPre = nums[c];
 dPre = nums[d];
 c++;
 d--;
 }
 }
 }
 }
 return ret;
}

public int removeDuplicates(int[] nums) {
 int i = 0, len = nums.length;
 for (int j = 0; j < len; j++) {
 if (j+1 < len && nums[j] != nums[j+1]) {
 nums[i++] = nums[j];
 }
 }
 if (len > 0) nums[i++] = nums[len-1];
 return i;
}

// 2. 当要移动的很多时候
public int removeElement(int[] nums, int val) {
 if (nums == null || nums.length == 0) return 0;
 int i = 0, j = nums.length-1;
 while (i <= j) {
 while (i <= j && nums[i] != val) i++;
 while (i <= j && nums[j] == val) j--;
 
 if (j > i) nums[i++] = nums[j--];
 }
 // if (nums[i] == val) return i;
 return j+1;
}
// 2.2 只和最后一个元素交换
public int removeElement2(int[] nums, int val) {
 if (nums == null || nums.length == 0) return 0;
 int i = 0, n = nums.length;
 while (i < n) {
 if (nums[i] == val) {
 nums[i] = nums[n-1];
 n--;
 } else {
 i++;
 }
 }
 // if (nums[i] == val) return i;
 return n;
}

// Sunday算法:如果当前窗口不匹配,比较窗口下一个字符串;下一个字符串在shift数组中的位置,就是窗口要偏移的距离
// 先计算shift数组 every char : len(needle) - max(char) otherwise: len+1
public int strStr(String haystack, String needle) {
 // 使用 HashMap 实现shift数组
 HashMap<Character, Integer> shiftMap = new HashMap<>();
 int len = needle.length();
 for (int i = 0; i < len; i++) {
 Character character = needle.charAt(i);
 if (!shiftMap.containsKey(character)) {
 for (int j = len-1; j >= 0; j--) {
 if (needle.charAt(j) == character) {
 shiftMap.put(character, len-j);
 break;
 }
 }
 }
 }
 int p = 0;
 while (p + len <= haystack.length()) {
 int i;
 for (i = 0; i < len; i++) {
 if (haystack.charAt(p+i) != needle.charAt(i)) break;
 }
 if (i == len) return p;
 else if (p+len == haystack.length()) return -1;
 else p += shiftMap.getOrDefault(haystack.charAt(p+len), len+1);
 }
 return -1;
}

private void swap(int[] nums, int i, int j) {
 if (nums[i] == nums[j]) return;
 int temp = nums[i];
 nums[i] = nums[j];
 nums[j] = temp;
}
public void sortColors(int[] nums) {
 int p0 = 0, p2 = nums.length-1;
 int cur = 0;
 while (cur <= p2) {
 if (nums[cur] == 0) swap(nums, cur++, p0++);
 else if (nums[cur] == 2) swap(nums, cur, p2--);
 else cur++;
 }
}

public void merge(int[] nums1, int m, int[] nums2, int n) {
 int i = m-1, j = n-1, k = m+n-1;
 while (i >= 0 && j >= 0) {
 if (nums1[i] < nums2[j]) {
 nums1[k--] = nums2[j--];
 } else {
 nums1[k--] = nums1[i--];
 }
 }
 while (j >= 0) {
 nums1[k--] = nums2[j--];
 }
}

public boolean searchMatrix(int[][] matrix, int target) {
 if (matrix.length == 0 || matrix[0].length == 0) return false;
 int m = matrix.length, n = matrix[0].length, row = 0, col = n-1;
 while (row < m && col >= 0) {
 if (matrix[row][col] < target) row++;
 else if (matrix[row][col] > target) col--;
 else return true;
 }
 return false;
}

private void swap(int[] nums, int i, int j) {
 int temp = nums[i];
 nums[i] = nums[j];
 nums[j] = temp;
}
public void moveZeroes(int[] nums) {
 int zeroPos = 0;
 for (int i = 0; i < nums.length; i++) {
 if (nums[i] != 0) {
 swap(nums, zeroPos++, i);
 }
 }
}

2. 快慢指针

// 使用哈希表,将每个指针地址存入,然后判断,空间复杂度 O(n)
// 快慢指针 类似于两人跑步(慢指针每次1步,快指针每次2步),那么 环形部分/1 = 循环迭代的次数
public boolean hasCycle(ListNode head) {
 ListNode slow = head, fast = head;
 while (fast != null && fast.next != null) {
 slow = slow.next;
 fast = fast.next;
 fast = fast.next;
 if (slow == fast) return true;
 }
 return false;
}

// 是否有环,注意返回的不是入口节点哦, 实际上是获得的环形部分的数目!!!
public ListNode hasCycle(ListNode head) {
 ListNode slow = head, fast = head;
 while (fast != null && fast.next != null) {
 slow = slow.next;
 fast = fast.next;
 fast = fast.next;
 if (slow == fast) return slow;
 }
 return null;
}
// 有环,找环的入口地点,然后同步走,就会走到环的入口处
public ListNode detectCycle(ListNode head) {
 ListNode node1 = head;
 ListNode node2 = hasCycle(head);
 if (node2 == null) return null;
 while (node1 != node2) {
 node1 = node1.next;
 node2 = node2.next;
 }
 return node1;
}

 // 方法2:如何找到两个链表的差距? 快的指针走到头后,回到长的链表头部;慢的指针走到头,回到短的链表头部,这样就抵消了 差距
 public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
 if (headA == null || headB == null) return null;
 ListNode p = headA, q = headB;
 while (p != q) {
 p = (p == null) ? headB : p.next;
 q = (q == null) ? headA : q.next;
 }
 return p;
 }

// 寻找mid,翻转后半部分,最后比较
public boolean isPalindrome(ListNode head) {
 if (head == null || head.next == null) return true;
 ListNode slow = head, fast = head;
 while (fast != null && fast.next != null) {
 slow = slow.next;
 fast = fast.next.next;
 }
 // 偶数时,slow指向后半部分的开头,奇数时,slow指向正中间(让slow再多走一个)
 if (fast != null) slow = slow.next;
 slow = reverse(slow);
 fast = head;
 while (slow != null) {
 if (fast.val != slow.val) return false;
 slow = slow.next;
 fast = fast.next;
 }
 return true;
}
private ListNode reverse(ListNode head) {
 if (head == null || head.next == null) return head;
 ListNode pre = null, p = head, q;
 while (p != null) {
 q = p.next;
 p.next = pre;
 pre = p;
 p = q;
 }
 return pre;
}

3. 滑动窗口

public int minSubArrayLen(int s, int[] nums) {
 int n = nums.length, res = n + 1;
 int i = 0, j;
 for (j = 0; j < n; j++) {
 s -= nums[j];
 while (s <= 0) {
 res = Math.min(res, j-i+1);
 s += nums[i++];
 }
 }
 return res % (n + 1); // res == n+1 说明不存在,返回0
}

链表

基本操作

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 ListNode head = new ListNode(-1); // 初始创建一个头指针,就可以避免判断当前指针是否为空
 ListNode cur = head;
 int sum = 0; // 余数、和使用一个变量来表示
 while (l1 != null || l2 != null || sum != 0) {
 if (l1 != null) {
 sum += l1.val;
 l1 = l1.next;
 }
 if (l2 != null) {
 sum += l2.val;
 l2 = l2.next;
 }
 cur.next = new ListNode(sum % 10); // 使用取余和取整
 cur = cur.next;
 sum = sum / 10;
 }
 return head.next;
}

// 优化
public ListNode insertionSortListOpt(ListNode head) {
 ListNode dummy = new ListNode(Integer.MIN_VALUE);
 ListNode cur = head, p = null, next;
 while (cur != null) {
 // p = dummy; 每次都把 p 置在了头部位置
 if (p == null || p.val >= cur.val) p = dummy; // 优化: 有时候不必将 p 移动至 头部位置
 next = cur.next;
 while (p.next != null && cur.val > p.next.val) {
 p = p.next;
 }
 // 注意以下两行代码
 cur.next = p.next;
 p.next = cur;
 cur = next;
 }
 return dummy.next;
}

// 不修改输入链表
// 难点:1. 预先不只是位数 2. 进位不清楚 3. 计算顺序是从后往前的
// 使用栈 时间和空间复杂度 O(m+n)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 Stack<Integer> stack1 = new Stack<>();
 Stack<Integer> stack2 = new Stack<>();
 while (l1 != null) {
 stack1.push(l1.val);
 l1 = l1.next;
 }
 while (l2 != null) {
 stack2.push(l2.val);
 l2 = l2.next;
 }
 ListNode head= null, cur;
 int sum = 0;
 while (!stack1.empty() || !stack2.empty() || sum != 0) {
 if (!stack1.empty()) sum += stack1.pop();
 if (!stack2.empty()) sum += stack2.pop();
 cur = new ListNode(sum % 10);
 cur.next = head;
 head = cur;
 sum = sum / 10;
 }
 return head;
}

删除

// 简化:使用dummy,不用pre指针,直接slow指向要删除的节点的前面位置,使用 n 递减计数
public ListNode removeNthFromEnd2(ListNode head, int n) {
 if (head == null) return null;
 ListNode dummy = new ListNode(-1);
 dummy.next = head;
 ListNode fast = dummy, slow = dummy;
 while (fast.next != null) {
 if (n <= 0) slow = slow.next;
 fast = fast.next;
 n--;
 }
 slow.next = slow.next.next;
 return dummy.next;
}

public ListNode deleteDuplicates(ListNode head) {
 if(head == null) return null;
 ListNode dummy = new ListNode(-1);
 dummy.next = head;
 ListNode pre = dummy, p = head;
 while (p != null) {
 if (p.next == null || p.next.val != p.val) {
 if (pre.next == p) pre = p;
 else pre.next = p.next;
 }
 p = p.next;
 }
 return dummy.next;
}

public ListNode deleteDuplicates(ListNode head) {
 if(head == null) return null;
 ListNode dummy = new ListNode(-1);
 dummy.next = head;
 ListNode p = head;
 while(p != null && p.next != null) {
 if(p.val == p.next.val) {
 p.next = p.next.next;
 } else {
 p = p.next;
 }
 }
 return dummy.next;
}

public ListNode removeElements(ListNode head, int val) {
 if(head == null) return null;
 int temp = (val == -1) ? -2 : -1;
 ListNode dummy = new ListNode(temp);
 dummy.next = head;
 ListNode p = dummy;
 while(p.next != null) {
 if(p.next.val == val) {
 p.next = p.next.next;
 } else {
 p = p.next;
 }
 }
 return dummy.next;
}

旋转

// 节点的移动(三个节点)
public ListNode swapPairs(ListNode head) {
 if (head == null || head.next == null) return head;
 ListNode dummy = new ListNode(-1);
 dummy.next = head;
 ListNode cur = dummy, swap1, swap2;
 while (cur.next != null && cur.next.next != null) {
 swap1 = cur.next;
 swap2 = cur.next.next;
 cur.next = swap2;
 swap1.next = swap2.next;
 swap2.next = swap1;
 cur = swap1;
 }
 return dummy.next;
}
// 递归写法(考虑两个节点)
public ListNode swapPairsRecursive(ListNode head) {
 if(head == null || head.next == null) return head;
 ListNode nextNode = head.next;
 head.next = swapPairsRecursive(nextNode.next);
 nextNode.next = head;
 return nextNode;
}

public ListNode reverseKGroup(ListNode head, int k) {
 ListNode p = head, q = head;
 // 找到 第 k-1个结点p
 for (int i = 0; i < k; i++) {
 if (p == null) return head;
 q = p;
 p = p.next;
 }
 q.next = null;
 ListNode newHead = reverse(head);
 head.next = reverseKGroup(p, k);
 return newHead;
}
private ListNode reverse(ListNode head) {
 if (head == null || head.next == null) return head;
 ListNode ret = reverse(head.next);
 head.next.next = head;
 head.next = null;
 return ret;
}

// 快指针先走k-1步, 若快指针先为null说明链表长度小于k, 则快指针走 k%n
// 最终慢指针为新头结点,快指针.next = head
public ListNode rotateRight(ListNode head, int k) {
 if (head == null) return null;
 ListNode slow = head, fast = head, ret = null;
 int i = 0;
 for (i = 0; i < k; i++) {
 if (fast == null) break;
 fast = fast.next;
 }
 // k== 链表长度
 if (i == k && fast == null) return head;
 if (i < k) {
 k = k % i;
 fast = head;
 for (i = 0; i < k; i++) {
 fast = fast.next;
 } 
 }
 while (fast.next != null) {
 slow = slow.next;
 fast = fast.next;
 }
 fast.next = head;
 ret = slow.next;
 slow.next = null;
 return ret;
}

// 设置DummyNode
public ListNode reverseBetween2(ListNode head, int m, int n) {
 ListNode dummy = new ListNode(-1);
 dummy.next = head;
 ListNode oldLast = dummy, before = null, cur, after;
 
 for (int i = 1; i < m; i++) {
 oldLast = oldLast.next;
 }
 ListNode reverseLast = oldLast.next;
 cur = reverseLast;
 for (int i = m; i <= n; i++) {
 after = cur.next;
 cur.next = before;
 before = cur;
 cur = after;
 }
 reverseLast.next = cur;
 oldLast.next = before;
 return dummy.next;
}

// 迭代(循环版本)
public ListNode reverseList(ListNode head) {
 ListNode front = null, cur = head, back;
 while (cur != null) {
 back = cur.next;
 cur.next = front;
 front = cur;
 cur = back;
 }
 return front;
}
// 递归版本
public ListNode reverseList2(ListNode head) {
 if (head == null || head.next == null) return head;
 ListNode p = reverseList(head.next);
 head.next.next = head;
 head.next = null;
 return p;
}

拆分

private class Node {
 public int val;
 public Node next;
 public Node random;
 public Node() {}
 public Node(int _val, Node _next, Node _random) {
 val = _val;
 next = _next;
 random = _random;
 }
}
// 拆开链表的地方有点不一样
public Node copyRandomList(Node head) {
 if (head == null) return null;
 Node p = head, newNode, q;
 // 交叉排列
 while (p != null) {
 newNode = new Node(p.val, null, null);
 newNode.next = p.next;
 p.next = newNode;
 p = newNode.next;
 }
 // 赋值新节点的 random
 p = head;
 while (p != null) {
 p.next.random = (p.random != null ? p.random.next : null);
 p = p.next.next;
 }
 // 拆开链表(拆解方法 2)
 p = head;
 q = head.next;
 newNode = p.next;
 while (p.next != null && p.next.next != null) {
 p.next = p.next.next;
 q.next = q.next.next;
 p = p.next;
 q = q.next;
 }
 p.next = null; // 注意封尾操作,详细的拆分 参见 328题
 return newNode;
}

public static ListNode oddEvenList(ListNode head) {
 if (head == null || head.next == null || head.next.next == null) return head;
 ListNode p = head, q = head.next;
 ListNode evenHead = head.next;
 while (p.next != null && p.next.next != null) { // 判断条件是 p.next,也就是说,是 到 链表的最后一个元素,这个时候需要进行封尾操作
 p.next = p.next.next;
 q.next = q.next.next;
 p = p.next;
 q = p.next;
 }
 p.next = evenHead; // 封尾操作(该题比较特殊,如果是单纯的将一个链表拆成一个,需要进行封尾)
 // 因为 p.next == null 跳出循环, p
 return head;
}

归并

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 ListNode head = new ListNode(-1);
 ListNode p = head;
 while(l1 != null && l2 != null) {
 if (l1.val <= l2.val) {
 p.next = l1;
 l1 = l1.next;
 } else {
 p.next = l2;
 l2 = l2.next;
 }
 p = p.next;
 }
 // 直接接到 剩余的链表即可
 if (l1 != null) p.next = l1;
 if (l2 != null) p.next = l2;
 return head.next;
}
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 if (l1.val <= l2.val) {
 l1.next = mergeTwoListsRecursive(l1.next, l2);
 return l1;
 } else {
 l2.next = mergeTwoListsRecursive(l1, l2.next);
 return l2;
 }
}

// 使用堆
public ListNode mergeKLists(ListNode[] lists) {
 int k = lists.length;
 if (k == 0) return null;
 PriorityQueue<ListNode> priorityQueue = new PriorityQueue<ListNode>(k, new Comparator<ListNode>() {
 @Override
 public int compare(ListNode o1, ListNode o2) {
 return o1.val - o2.val;
 }
 });
 ListNode head = new ListNode(-1);
 ListNode p = head, temp;
 boolean hasNode = true;
 while (hasNode) {
 hasNode = false;
 for (int i = 0; i < k; i++) {
 if (lists[i] != null) {
 // 这里也要注意
 temp = lists[i];
 lists[i] = lists[i].next;
 priorityQueue.add(temp);
 hasNode = true;
 }
 }
 }
 while (!priorityQueue.isEmpty()) {
 p.next = priorityQueue.poll();
 p = p.next;
 }
 p.next = null; // 必须加这个封尾操作,有可能会出现环
 return head.next;
}
// 不使用堆
public ListNode mergeKLists2(ListNode[] lists) {
 return mergeKLists2(lists, 0, lists.length - 1);
}
public ListNode mergeKLists2(ListNode[] lists, int start, int end) {
 if (start == end) return lists[start];
 else if (start < end) {
 int mid = start + (end - start) / 2;
 ListNode left = mergeKLists2(lists, start, mid);
 ListNode right = mergeKLists2(lists, mid+1, end);
 return mergeTwoListsRecursive(left, right);
 } else return null;
}
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 if (l1.val <= l2.val) {
 l1.next = mergeTwoListsRecursive(l1.next, l2);
 return l1;
 } else {
 l2.next = mergeTwoListsRecursive(l1, l2.next);
 return l2;
 }
}

// 递归版本 (自顶向下)
public ListNode sortList(ListNode head) {
 if (head == null || head.next == null) return head;
 // 将链表分为两段
 ListNode p = head, q = head, pre = head;
 while (q != null && q.next != null) {
 pre = p;
 p = p.next;
 q = q.next.next;
 }
 pre.next = null; // 截断链表
 ListNode left = sortList(head);
 ListNode right = sortList(p);
 return mergeTwoListsRecursive(left, right);
}
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 if (l1.val <= l2.val) {
 l1.next = mergeTwoListsRecursive(l1.next, l2);
 return l1;
 } else {
 l2.next = mergeTwoListsRecursive(l1, l2.next);
 return l2;
 }
}
// 非递归版本(迭代)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 ListNode dummy = new ListNode(-1), cur = dummy;
 while (l1 != null && l2 != null) {
 if (l1.val < l2.val) {
 cur.next = l1;
 l1 = l1.next;
 } else {
 cur.next = l2;
 l2 = l2.next;
 }
 cur = cur.next;
 }
 if (l1 == null) {
 cur.next = l2;
 } else {
 cur.next = l1;
 } 
 return dummy.next;
}

树

遍历

public void inorder(TreeNode root, List<Integer> ret) {
 if (root == null) return;
 inorder(root.left, ret);
 ret.add(root.val);
 inorder(root.right, ret);
}

List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
stack.add(cur);
while (!stack.isEmpty()) {
 cur = stack.pop();
 if (cur != null) {
 ret.add(cur.val);
 stack.add(cur.right);
 stack.add(cur.left);
 }
}
return ret;

List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
 while (cur != null) {
 stack.add(cur);
 cur = cur.left;
 }
 cur = stack.pop();
 ret.add(cur.val);
 cur = cur.right;
}
return ret;

// 使用LinkedList的头插,让结果倒序
LinkedList<Integer> ret = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
stack.add(cur);
while (!stack.empty()) {
 cur = stack.pop();
 if (cur != null) {
 ret.addFirst(cur.val); // 头插法,让结果倒序
 stack.add(cur.left);
 stack.add(cur.right);
 }
}
return ret;

// 难点:如何在数组上分区域
// 方案:递归的在子数组上进行操作
public TreeNode buildTree(int[] preorder, int[] inorder) {
 return helper(0, 0, inorder.length-1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
 if (preStart >= preorder.length || inStart > inEnd) return null;
 // 当前根节点
 TreeNode root = new TreeNode(preorder[preStart]);
 // 中序遍历中找到当前的 根节点,划分左右区域(为了加速可以使用 HashMap,O(1)时间找到inIndex)
 int inIndex = 0;
 for (int i = inStart; i <= inEnd; i++) {
 if (inorder[i] == root.val) {
 inIndex = i;
 break;
 }
 }
 // 划分区域
 root.left = helper(preStart+1, inStart, inIndex-1, preorder, inorder);
 root.right = helper(preStart+inIndex-inStart+1, inIndex+1, inEnd, preorder, inorder);
 return root;
}

public TreeNode buildTree(int[] inorder, int[] postorder) {
 return helper(postorder.length-1, 0, inorder.length-1, postorder, inorder);
}
public TreeNode helper(int postStart, int inStart, int inEnd, int[] postorder, int[] inorder) {
 if (postStart < 0 || inStart > inEnd) return null;
 // 当前根节点
 TreeNode root = new TreeNode(postorder[postStart]);
 // 后序遍历中从后往前找到当前根节点,划分左右区域(为了加速可以使用 HashMap,O(1)时间找到inIndex)
 int inIndex = 0;
 for (int i = inStart; i <= inEnd; i++) {
 if (inorder[i] == root.val) {
 inIndex = i;
 break;
 }
 }
 // 划分区域(难点)
 root.left = helper(postStart-(inEnd-inIndex+1), inStart, inIndex-1, postorder, inorder);
 root.right = helper(postStart-1, inIndex+1, inEnd, postorder, inorder);
 return root;
}

TreeNode pre = null;
public TreeNode convert(TreeNode root) {
 if (root == null) return null;
 this.pre = null;
 convertHelper(root);
 TreeNode p = root;
 while(p.left != null) p = p.left;
 return p;
}
// 中序遍历 记录前一个访问的节点
// 使用全局变量保存pre,在convertHelper中传pre的值不行
public void convertHelper(TreeNode cur) {
 if (cur == null) return;
 convertHelper(cur.left);
 cur.left = this.pre;
 if (pre != null) this.pre.right = cur;
 this.pre = cur;
 convertHelper(cur.right);
}

深度

// 递归思路:二叉树的最大深度 = max(左子树深度,右子树深度)
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;
}

// 在104的思路基础上修改:先计算树的高度,如果发现当前的节点高度差大于1了
// 那么就直接返回-1
private int recursive(TreeNode root) {
 if (root == null) return 0;
 int left = recursive(root.left);
 if (left == -1) return -1;
 int right = recursive(root.right);
 if (right == -1) return -1;
 if (Math.abs(left-right)>1) return -1;
 return Math.max(left, right) + 1;
}
public boolean isBalanced(TreeNode root) {
 return recursive(root) != -1;
}

// 难点:当二叉树退化成单侧时
public int minDepth(TreeNode root) {
 if (root == null) return 0;
 int left = minDepth(root.left);
 int right = minDepth(root.right);
 // 下面两句是和Max Depth不一样的地方
 if (root.left == null) return right+1;
 if (root.right == null) return left+1;
 return Math.min(left, right)+1;
}

层序

// 使用一个队列,下一层元素数目等于当前队列中元素的数目
public List<List<Integer>> levelOrder(TreeNode root) {
 List<List<Integer>> ret = new ArrayList<>();
 if (root == null) return ret;
 Queue<TreeNode> queue = new LinkedList<>();
 queue.add(root);
 while (!queue.isEmpty()) {
 int nodeCount = queue.size(); // Key
 List<Integer> level = new ArrayList<>(nodeCount);
 for (int i = 0; i < nodeCount; i++) {
 TreeNode node = queue.poll();
 level.add(node.val);
 // 锯齿形层次遍历 使用flag判断是否反转
 // if (!flag) level.add(node.val);
 // else level.addFirst(node.val);
 if (node.left != null) queue.add(node.left);
 if (node.right != null) queue.add(node.right);
 }
 ret.add(level); // 107题: ret.addFirst(level);
 }
 return ret;
}
// 递归写法(深度优先遍历),参数包括(node, level, resList),然后将第 K 层放到第K个 List
// 重点:什么时候初始化List
private void helper(TreeNode root, int level, List<List<Integer>> res) {
 if (root == null) return;
 // Key
 if (level >= res.size()) res.add(new LinkedList<>());
 res.get(level).add(root.val);
 // 103题锯齿形层次遍历:奇数时候头部插入结果List,偶数时候尾部插入
 // if(level % 2 == 0) res.get(level).add(root.val);
 // else ((LinkedList)res.get(level)).addFirst(root.val);
 helper(root.left, level+1, res);
 helper(root.right, level+1, res);
}
public List<List<Integer>> levelOrderRecursive(TreeNode root) {
 List<List<Integer>> res = new LinkedList<>();
 helper(root, 0, res);
 return res;
}

结构

public boolean isSameTree2(TreeNode p, TreeNode q) {
// if (p == null && q == null) return true; // 同时为空
// if (p == null || q == null) return false; // 不同时为空
 if (p == null || q == null) return p == q; // 更精简的写法
 if (p.val != q.val) return false; // 都不为空
 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

private boolean recursive(TreeNode tree1, TreeNode tree2) {
 if (tree1 == null || tree2 == null) return tree1 == tree2;
 if (tree1.val != tree2.val) return false;
 return recursive(tree1.left, tree2.right) && recursive(tree1.right, tree2.left);
}
public boolean isSymmetric(TreeNode root) {
 return iterative(root, root);
}

public TreeNode invertTree(TreeNode root) {
 if (root == null) return null;
 TreeNode left = invertTree(root.left);
 TreeNode right = invertTree(root.right);
 root.left = right;
 root.right = left;
 return root;
}

public boolean isSubtree(TreeNode s, TreeNode t) {
 if (t == null) {
 return true;
 }
 if (s == null) {
 return false;
 }
 if (s.val == t.val && isSame(s, t)) {
 return true;
 }
 return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode tree1, TreeNode tree2) {
 if (tree1 == null || tree2 == null) {
 return tree1 == tree2;
 }
 return tree1.val == tree2.val && isSame(tree1.left, tree2.left) && isSame(tree1.right, tree2.right);
}

路径

public boolean hasPathSum(TreeNode root, int sum) {
 if (root == null) return false;
 // if (root.left == null && root.right == null && root.val == sum) return true;
 if (root.left == null && root.right == null) return root.val == sum;
 return hasPathSum(root.left, sum-root.val) || hasPathSum (root.right, sum-root.val); 
}

// 难点:如何保存结果,回溯法!!!
private void findPath(TreeNode root, int sum, LinkedList<Integer> path, List<List<Integer>> res) {
 if (root == null) return;
 path.add(root.val);
 if (root.left == null && root.right == null) {
 // 注意必须new一个新的list
 if (root.val == sum) res.add(new LinkedList<>(path));
 }
 findPath(root.left, sum-root.val, path, res);
 findPath(root.right, sum-root.val, path, res);
 path.removeLast();
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
 LinkedList path = new LinkedList();
 List<List<Integer>> res = new ArrayList<>();
 findPath(root, sum, path, res);
 return res;
}

private int sum;
public int sumNumbers(TreeNode root) {
 sum = 0;
 helper(root, 0);
 return sum;
}
private void helper(TreeNode root, int pre) {
 if (root == null) return;
 pre = pre * 10 + root.val;
 if (root.left == null && root.right == null) {
 sum += pre;
 return;
 }
 helper(root.left, pre);
 helper(root.right, pre);
}

// 该题求BST的最近公共祖先,难度显著降低,BST有明显的特点
// 遍历树,如果p,q都在左(右)子树,那么就从左(右)子树进行递归,否则就找到了LCA
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 if (root == null) return null;
 if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
 if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
 return root;
}

// 递归:对每个节点对应的子树,若该子树不含有p或q,返回nullptr;
// 否则,如果p和q分别位于当前子树根节点两侧,则返回当前节点,
// 否则(p和q在同一侧,或者只有某一侧有p或q)返回来自左边或右边的LCA。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 if (root == null || p == root || q == root) return root;
 // 左边存在p或者q
 TreeNode left = lowestCommonAncestor(root.left, p, q);
 // 右边存在p或者q
 TreeNode right = lowestCommonAncestor(root.right, p, q);
 // p,q分别位于两侧
 if (left != null && right != null) return root;
 return (left == null) ? right : left;
}

private int maxSum;
public int maxPathSum(TreeNode root) {
 if (root == null) return 0;
 maxSum = root.val;
 arrowMaxPath(root);
 return maxSum;
}
private int arrowMaxPath(TreeNode root) {
 if (root == null) return 0;
 int left = arrowMaxPath(root.left);
 int right = arrowMaxPath(root.right);
 // 如何 累加值
 left = (left > 0 ? left + root.val : root.val);
 right = (right > 0 ? right + root.val : root.val);
 maxSum = Math.max(maxSum, left+right-root.val);
 return Math.max(left, right);
}

int max;
public int diameterOfBinaryTree(TreeNode root) {
 max = 0;
 helper(root);
 return max;
}
private int helper(TreeNode root) {
 if (root == null) {
 return -1;
 }
 if (root.left == null && root.right == null) {
 return 0;
 }
 int left = helper(root.left) + 1;
 int right = helper(root.right) + 1;
 max = Math.max(max, left+right);
 return Math.max(left, right);
}

// 这种路径是 1.左子树最长同值路径(单箭头路径) 2. 右子树最长同值路径(单箭头路径) 的 最大值
private int longest = 0;
public int longestUnivaluePath(TreeNode root) {
 longest = 0;
 arrowPath(root);
 return longest;
}
private int arrowPath(TreeNode root) {
 if (root == null) return 0;
 int left = arrowPath(root.left);
 int right = arrowPath(root.right);
 int arrowLeft = 0, arrowRight = 0;
 if (root.left != null && root.left.val == root.val) arrowLeft = left + 1;
 if (root.right != null && root.right.val == root.val) arrowRight = right + 1;
 // 更新最终结果是双向的
 longest = Math.max(longest, arrowLeft + arrowRight);
 // 返回的是单向的
 return Math.max(arrowLeft, arrowRight);
}

剪枝

// 重点在于如何剪枝,如何调整节点
// 参考思路:< L , 只保留二叉树的右子树
// > R, 只保留二叉树的左子树
public TreeNode trimBST(TreeNode root, int L, int R) {
 if (root == null) return null;
 // 调整节点(难点)
 // < L, 只保留二叉树的右子树(结果肯定在右边)
 if (root.val < L) return trimBST(root.right, L, R);
 
 // > R, 只保留二叉树的左子树(结果肯定在左边)
 if (root.val > R) return trimBST(root.left, L, R);
 
 root.left = trimBST(root.left, L, R);
 root.right = trimBST(root.right, L, R);
 return root;
}

// 判断是否含有1
private boolean hasOne(TreeNode root) {
 if (root == null) return false;
 if (root.val == 1) return true;
 return hasOne(root.left) || hasOne(root.right);
}
public TreeNode pruneTree(TreeNode root) {
 if (!hasOne(root)) return null;
 root.left = pruneTree(root.left);
 root.right = pruneTree(root.right);
 return root;
}
// 后续遍历写法
public TreeNode pruneTree2(TreeNode root) {
 if (root == null) return null;
 root.left = pruneTree(root.left);
 root.right = pruneTree(root.right);
 if (root.val == 0 && root.left == null && root.right == null)
 return null;
 return root;
}

二叉搜索树

TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
 if (root == null ) {
 return true;
 }
 if (!isValidBST(root.left)) {
 return false;
 }
 if (pre != null && root.val <= pre.val) {
 return false;
 } 
 pre = root;
 return isValidBST(root.right);
}

// 难点:找到这两个错误的节点
// 有序的序列,交换两个元素,会导致增长序列出现两个(或者一个)下降点
// 两个下降点: first是第一个下降点处较大的元素;second是第二个下降点处较小的元素
// 一个下降点: first下降点处较大元素;second是下降点处较小元素
private TreeNode first = null;
private TreeNode second = null;
private TreeNode pre;
public void recoverTree(TreeNode root) {
 first = null;
 second = null;
 pre = null;
 traverse(root);
 // 交换 first 和 second
 int temp = first.val;
 first.val = second.val;
 second.val = temp;
}
private void traverse(TreeNode root) {
 if (root == null) return;
 traverse(root.left);
 if (pre != null && pre.val > root.val) {
 // 此处是重点
 if (first == null) {
 first = pre;
 second = root; // 注意此处(只有一个下降点时)
 } else second = root;
 }
 pre = root;
 traverse(root.right);
}

// 树尽量平衡 —— 要求数组尽量划分均等(二分)(使用下标进行划分,注意数目的奇偶)
// 0 1 2 3 4 5
public TreeNode sortedArrayToBST(int[] nums) {
 TreeNode root = helper(nums, 0, nums.length-1);
 return root;
}
private TreeNode helper(int[] nums, int i, int j) {
 if (i < 0 || j >= nums.length || i > j) return null;
 int mid = (i+j)/2;
 TreeNode node = new TreeNode(nums[mid]);
 node.left = helper(nums, i, mid-1);
 node.right = helper(nums, mid+1, j);
 return node;
}

public TreeNode sortedListToBST(ListNode head) {
 // while (tail.next != null) tail = tail.next;
 return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode tail) { // 左闭右开
 if (head == tail) return null;
 if (head.next == tail) return new TreeNode(head.val);
 ListNode slow = head, fast = head;
 
 while (fast != tail && fast.next != tail) {
 slow = slow.next;
 fast = fast.next.next;
 }
 TreeNode root = new TreeNode(slow.val);
 root.left = helper(head, slow); 
 root.right = helper(slow.next, tail);
 return root;
}

int count = 0;
public int kthSmallest(TreeNode root, int k) {
 if (root == null) {
 return -1;
 }
 int left = kthSmallest(root.left, k);
 if (left != -1) {
 return left;
 }
 count++;
 if (count == k) {
 return root.val;
 }
 return kthSmallest(root.right, k);
}

public TreeNode deleteNode(TreeNode root, int key) {
 if (root == null) {
 return null;
 }
 if (root.val != key) {
 if (root.val > key) {
 root.left = deleteNode(root.left, key);
 } else {
 root.right = deleteNode(root.right, key);
 }
 } else {
 if (root.left == null) {
 return root.right;
 }
 if (root.right == null) {
 return root.left;
 }
 // 难点
 TreeNode rightMaxNode = findRightMax(root); // 找到右侧最大值
 root.val = rightMaxNode.val; // 与当前值交换
 rightMaxNode.val = key;
 root.right = deleteNode(root.right, key); // 在右侧递归
 }
 return root;
}
private TreeNode findRightMax(TreeNode root) {
 TreeNode p = root.right;
 while (p != null && p.left != null) {
 p = p.left;
 }
 return p;
}

public TreeNode insertIntoBST(TreeNode root, int val) {
 if (root == null) return new TreeNode(val);
 if (root.val > val) {
 root.left = insertIntoBST(root.left, val);
 } else {
 root.right = insertIntoBST(root.right, val);
 }
 return root;
}

动态规划

单序列DP

子序列/子串问题

经典股票题

多状态的DP

未分类

双序列DP

棋盘类DP

背包问题

游戏(博弈)DP

划分型DP