常见编程模式

看了一篇推文，整理一下，未完

滑动窗口

概念

一种高级双指针技巧的算法框架，用于在给定数组或链表的特定窗口上执行所需的操作，可以将嵌套的循环问题，转化为单循环问题，降低时间复杂度
一半从第一个元素开始滑动，并且逐个元素向右滑，并且根据所求的问题来调整窗口的长度（也就是移动左指针）

特点

• 问题的输入是一种线性结构，比如链表、数组或者字符串
• 被要求查找最长，最短的子字符串，子数组或所需要的值，往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

常见问题

• 大小为K的子数组的最大和
• 带有K个不同字符的最长子字符串
• 寻找字符相同，但是排序不一样的字符串

示例

最小覆盖子串 hard

给定一个字符串S，字符串T，在字符串S中找到，包含T所有字母的最小子串

• （寻找解）不断增加right指针扩大窗口，直到窗口的字符串符合要求（包含了T中的所有字符）
• （优化解）停止增加right，不断增加left缩小窗口，直到不再符合要求
• 重复上面两个步骤，直到right到达了字符串S的尽头

public String minWindow(String s, String t) {
  if(s.length()<t.length()){
    return "";
  }
  int left = 0;
  int right = 0;
  int resL = s.length()+1;
  Map<Character, Integer> needs = new HashMap<>();
  Map<Character, Integer> window = new HashMap<>();
  String res = new String(s);
  for (int i = 0; i < t.length(); i++) {
    needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
  }
  while (right < s.length()) {
    window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
    while (satisfied(needs, window) && left <= right) {
      if (right - left + 1 < resL) {
        res = s.substring(left, right + 1);
        resL = res.length();
      }
      window.put(s.charAt(left), window.getOrDefault(s.charAt(left), 0) - 1);
      left++;
    }
    right++;
  }
  // 没有更新过
  if (resL == s.length()+1){
    return "";
  }
  return res;
}

public boolean satisfied(Map<Character, Integer> needs, Map<Character, Integer> window) {
  for (Character c : needs.keySet()) {
    // 注意是大于等于
    if (needs.get(c).intValue() > window.getOrDefault(c, 0)) {
      return false;
    }
  }
  return true;
}

• 可以用两个map来记录需要的字符和当前已有的字符，分别为need和window

爱生气的书店老板 Medium

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

• 简单的滑动窗口，窗口长度恒定为X
• 先计算初始化X可以带来的收益，然后不断移动

public int maxSatisfied(int[] customers, int[] grumpy, int X) {
    int total = 0;
    int n = customers.length;
    // 先得到基础的顾客满意数量
    for (int i = 0; i < n; i++) {
        if (grumpy[i] == 0) {
            total += customers[i];
        }
    }
    int increase = 0;
    // 初始化窗口，应该增加的量
    for (int i = 0; i < X; i++) {
        increase += customers[i] * grumpy[i];
    }
    int maxIncrease = increase;
    for (int i = X; i < n; i++) {
        // 上述过程可以看成维护一个长度为 X 的滑动窗口。
        // 当滑动窗口从下标范围 [i-X,i-1]移动到下标范围 [i-X+1,i] 时，下标 i-X 从窗口中移出，下标 i 进入到窗口内。
        increase = increase - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i];
        maxIncrease = Math.max(maxIncrease, increase);
    }
    return total + maxIncrease;
}

找到字符串中所有字母异位词 Medium

给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的初始索引

• hard题的简化版，固定了窗口的大小

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> resultList = new ArrayList<>();
    // 计算字符串p中各元素的出现次数
    int[] pFreq = new int[26];
    for(int i = 0; i < p.length(); i++) {
        pFreq[p.charAt(i)-'a']++;
    }
    // 窗口区间为[start,end]
    int start = 0, end = -1;
    while (start <s.length()) {
        if (end+1 < s.length() && end-start+1 <p.length()) {
            end++;
        }else {
            start++;
        }
        if (end-start+1 == p.length() && isAnagrams(s.substring(start,end+1), pFreq)) {
            resultList.add(start);
        }
    }
    return resultList;
}
// 判断当前子串是不是字符串p的字母异位词
private boolean isAnagrams(String window, int[] pFreq) {
    // 计算窗口内字符串各元素的出现次数
    int[] windowFreq = new int[26];
    for(int i = 0; i < window.length(); i++) {
        windowFreq[window.charAt(i)-'a']++;
    }
    for(int j = 0; j < 26; j++) {
        if (windowFreq[j] != pFreq[j]) {
            return false;
        }
    }
    return true;
}

无重复最长子串

不含有重复字符的最长子串的长度

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> dic = new HashMap<>();
    int i = -1, res = 0;
    for(int j = 0; j < s.length(); j++) {
        if(dic.containsKey(s.charAt(j)))
            i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
        dic.put(s.charAt(j), j); // 哈希表记录
        res = Math.max(res, j - i); // 更新结果
    }
    return res;
}。

至多包含两个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t 。

int lengthOfLongestSubstringTwoDistinct(string s) {
    unordered_map<char, int> m;
    int cnt = 0;                // 不同字符个数
    int left = 0, right = 0;    // right指向的是窗口外的下一个字符
    int maxLen = 0;
    while(right < s.size()){
        if(m[s[right]] == 0)
            cnt ++;             // 出现新字符
        m[s[right++]]++;        // 计数+1并右移
        while(cnt > 2){         // 当窗口元素大于2，窗口缩小
            m[s[left]]--;       // 计数-1
            if(m[s[left++]] == 0){
                cnt --;         // 字符计数减为0
            }
        }
        maxLen = max(maxLen, right - left); // 满足条件的窗口长度
    }
    return maxLen;
}

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回每个滑动窗口中的最大值。

// 优先队列
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
      	// 大堆
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
      	// 这里的i是右端点
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
          	// 移除不在当前窗口的元素
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

public int[] maxSlidingWindow(int[] nums, int k) {
  int n = nums.length;
  // 双端队列
  Deque<Integer> deque = new LinkedList<Integer>();
  // 这套流程过后 deque里面放的最大的元素的index
  for (int i = 0; i < k; ++i) {
    while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
      deque.pollLast();
    }
    deque.offerLast(i);
  }

  int[] ans = new int[n - k + 1];
  ans[0] = nums[deque.peekFirst()];
  for (int i = k; i < n; ++i) {
    while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
      deque.pollLast();
    }
    deque.offerLast(i);
    while (deque.peekFirst() <= i - k) {
      deque.pollFirst();
    }
    ans[i - k + 1] = nums[deque.peekFirst()];
  }
  return ans;
}

总结

int left = 0, right = 0;

while (right < s.size()) {
    window.add(s[right]);
    right++;
    
    while (valid) {
        window.remove(s[left]);
        left++;
    }
}

二指针

概念

两个指针以一前一后的模式在数据结构中进行迭代，直到一个或者两个指针达到了某种特定的条件，比如你必须将一个数组的每个元素与其他元素做比对的时候

特点

• 处理排序数组并且需要查找满足某些条件的一组元素的问题
• 数组中的元素集是配对，三元组甚至是子数组
• 快慢指针

常见问题

三数之和

在数组中找到三元组，其中元素个数之和为0

• 先排序，方便去除重复
• 先确定一个元素，然后定好target，在剩下的元素中找

public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
    List<List<Integer>> ans = new ArrayList<>();
    if (nums == null || nums.length <= 2) return ans;

    Arrays.sort(nums); // O(nlogn)

    for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
        if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
        int target = -nums[i];
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                
                // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                left++; right--; // 首先无论如何先要进行加减操作
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {  // nums[left] + nums[right] > target
                right--;
            }
        }
    }
    return ans;
}

四数之和

• 先固定两个

public List<List<Integer>> fourSum(int[] nums, int target) {
    //排序+双指针
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    if(nums==null || nums.length<=3){
        return res;
    }
    int len = nums.length;
    for(int i = 0;i<len;i++){
        if(i-1>=0 && nums[i]==nums[i-1]){
            continue;
        }
        for(int j=i+1;j<len;j++){
            if(j-1>=i+1 && nums[j-1]==nums[j]){
                continue;
            }
            int tr = target - nums[i] - nums[j];
            int left = j+1,right = len-1;
            while(left<right){
                if(nums[left]+nums[right]==tr){
                    List<Integer> tp = new ArrayList<>();
                    tp.add(nums[i]);
                    tp.add(nums[j]);
                    tp.add(nums[left]);
                    tp.add(nums[right]);
                    res.add(tp);
                    while(left<right && nums[left]==nums[++left]);
                    while(left<right && nums[right]==nums[--right]);
                }else if(nums[left]+nums[right]>tr){
                    right--;
                }else{
                    left++;
                }
            }
        }
    }
    return res;
}

比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

• 从后往前遍历

public boolean backspaceCompare(String S, String T) {
    int i = S.length() - 1, j = T.length() - 1;
    int skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (S.charAt(i) == '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        while (j >= 0) {
            if (T.charAt(j) == '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }
        if (i >= 0 && j >= 0) {
            if (S.charAt(i) != T.charAt(j)) {
                return false;
            }
        } else {
            if (i >= 0 || j >= 0) {
                return false;
            }
        }
        i--;
        j--;
    }
    return true;
}

大餐记数

在数组中，找到一个二元组，其中元素的和是2的幂，可以重复

• 边遍历边添加，添加的是之前已经遍历过的

public int countPairs(int[] deliciousness) {
    Map<Integer,Integer> map = new HashMap<>();
    long ans = 0;
    for (int i = 0;i < deliciousness.length;++i){
        for (int j = 0;j < 22;++j){
            int target = (int)Math.pow(2,j);
            if (target - deliciousness[i] < 0) continue;
            if (map.containsKey(target - deliciousness[i])){
                ans += map.get(target - deliciousness[i]);
            }
        }
        map.put(deliciousness[i],map.getOrDefault(deliciousness[i],0) + 1);
    }
    ans %= (1e9 + 7);
    return (int)ans;
}

字符串相加

两个字符串，模拟加法

不禁会想起当年写ALU的时候

public String addStrings(String num1, String num2) {
    StringBuilder res = new StringBuilder("");
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
    while(i >= 0 || j >= 0){
        int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
        int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        int tmp = n1 + n2 + carry;
        carry = tmp / 10;
        res.append(tmp % 10);
        i--; j--;
    }
    if(carry == 1) res.append(1);
    return res.reverse().toString();
}

链表翻转

如题

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

快慢指针

概念

使用两个在数组，字符串或者链表中以不同速度移动的指针，在处理循环链表或者数组的时候非常有用
通过以不同速度（人为规定的速度，或者一定的间距）进行移动，比如在一个循环链表中，只要这两个指针在同一个循环中，快速指针就会追赶上慢速指针，并且在环中相遇

特点

• 当我们需要处理链表或者数组中的循环问题
• 当我们需要直到特定元素的位置或者链表的总长度的时候

什么时候快慢指针而不是二指针呢

• 在不能反向移动的单链接链表

常见问题

• 链表循环
• 回文链表
• 环形数组中的循环

示例

环形链表

给定一个链表，判断链表中是否有环。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

环形链表2

判断一个环路开始的位置

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next == null ) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    // 找到相遇点z （对应上图）
    while(true) {
        if(fast == null || fast.next == null) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    // 想到 cycle起点y （对应上图）
    slow = head;
    while(fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
    
}

寻找重复的数字

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

• 由于数字都在1-n之间，可不可以理解成，这是一个用数组表示的图
• 那么就相当于在图中找环的入口
• floyed算法，两个指针在有环的情况下一定会相遇

public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    // 会在环中相遇，多走了n步，这n步都是在环里循环，说明n%c(环长) = 0
    int finder = 0;
    while (slow != finder) {
        slow = nums[slow];
        finder = nums[finder];
    }
    // 相遇的时候，slow一共走了n+m步，finder走了m步，slow在环内前进的距离刚好就是n步，从而m也是起点到入口的长度
    return slow;
    }

回文链表

判断一个链表是否是回文链表

public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) {
        return true;
    }
    // fast走两步，slow走一步，当fast走到头的时候，slow肯定在中间位置
    ListNode fast = head.next;
    ListNode slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // 2。从中点位置后的第一个元素开始反转后面的链表
    slow = slow.next;
    ListNode p = slow;
    ListNode q = p.next;
    while(q!= null) {
        ListNode tmp = q.next;
        q.next = p;
        p = q;
        q= tmp;
    }
    slow.next = null;
   // 3。 只要后面的元素和前半部分都相等， 则链表是回文链表
    while(p!= null){
        if(p.val != head.val) {
            return false;
        }
        p = p.next;
        head = head.next;
    }
    return true;
}

删除链表倒数N个节点

如题

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = head;
    ListNode second = dummy;
    for (int i = 0; i < n; ++i) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    ListNode ans = dummy.next;
    return ans;
}

重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

• 快满指针找到链表的中点
• 将后半部分翻转
• 前半部分和后半部分合并

public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }
    ListNode mid = middleNode(head);
    ListNode l1 = head;
    ListNode l2 = mid.next;
    // 两个部分分开
    mid.next = null;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

public void mergeList(ListNode l1, ListNode l2) {
    ListNode l1_tmp;
    ListNode l2_tmp;
    while (l1 != null && l2 != null) {
        l1_tmp = l1.next;
        l2_tmp = l2.next;

        l1.next = l2;
        l1 = l1_tmp;

        l2.next = l1;
        l2 = l2_tmp;
    }
}

合并区间

概念

合并区间模式是一种处理重叠区间的有效技术。在很多涉及区间的问题中，你既需要找到重叠的区间，也需要在这些区间重叠时合并它们。

• a和b对应的区间不重叠
• 重叠一部分，并且b在a后面，（1，4）和（2，5）
• 重叠一部分，并且a在b后面，（2，5）和（1，4）
• a完全包含b，（1，4）和（2，3）
• b完全包含a

特点

• 如果被要求得到一个仅包含互斥区间的列表
• 如果你听到了术语重叠区间

常见问题

• 区间交叉
• 最大CPU负载

示例

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

• 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
• 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][2];
    }
    // 按照起始index排序
	Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    List<int[]> merged = new ArrayList<int[]>();
    for (int i = 0; i < intervals.length; ++i) {
        int L = intervals[i][0], R = intervals[i][1];
        if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
            // 不会重合或者答案区间数组是空
            merged.add(new int[]{L, R});
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

插入区间

给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然 有序且不重叠（如果有必要的话，可以 合并区间）。

• 首先将新区间左边且相离的区间加入结果集（遍历时，如果当前区间的结束位置小于新区间的开始位置，说明当前区间在新区间的左边且相离）；
• 接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，将最终合并后的新区间加入结果集；
• 最后将新区间右边且相离的区间加入结果集。

public int[][] insert(int[][] intervals, int[] newInterval) {
    int[][] res = new int[intervals.length + 1][2];
    int idx = 0;
    // 遍历区间列表：
    // 首先将新区间左边且相离的区间加入结果集
    int i = 0;
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        res[idx++] = intervals[i++];
    }
    // 接着判断接下来的区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
    // 将最终合并后的新区间加入结果集
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
        i++;
    }
    res[idx++] = newInterval;
    // 最后将新区间右边且相离的区间加入结果集
    while (i < intervals.length) {
        res[idx++] = intervals[i++];
    }
	// 只取indx长度的res
    return Arrays.copyOf(res, idx);
}

会议室

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

public boolean canAttendMeetings(int[][] intervals) {
    // 将区间按照会议开始实现升序排序
    Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    // 遍历会议，如果下一个会议在前一个会议结束之前就开始了，返回 false。
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }
    return true;
}

删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。在完成所有删除操作后，请你返回列表中剩余区间的数目。（对于区间 [a, b) 和区间 [c, d)，若 c <= a 且 d >= b ，则区间 [a, b) 被区间 [c, d) 覆盖）

• 本题和本文第一题的做法一样，首先按照区间起始端点进行排序，然后遍历区间，将第一题的判断区间是否重叠改为判断区间是否覆盖即可。

public int removeCoveredIntervals(int[][] intervals) {
    // 在start相同的情况下，end小的放在后面
    Arrays.sort(intervals, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[0] == o2[0] ? o2[1] - o1[1]: o1[0] - o2[0];
      }
    });
    int count = 0;
    // prev_end记录之前最大的end
    int end, prev_end = 0;
    for (int[] curr : intervals) {
      end = curr[1];
      if (prev_end < end) {
        ++count;
        prev_end = end;
      }
    }
    return count;
}

俄罗斯套娃信封

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

public int maxEnvelopes(int[][] envelopes) {
    // 先排序，在长度相同的情况下，宽度小的放在后面，排除同宽度的干扰
    Arrays.sort(envelopes, new Comparator<int[]>() {
        public int compare(int[] arr1, int[] arr2) {
            if (arr1[0] == arr2[0]) {
                return arr2[1] - arr1[1];
            } else {
                return arr1[0] - arr2[0];
            }
        }
    });
    // extract the second dimension and run LIS
    int[] secondDim = new int[envelopes.length];
    for (int i = 0; i < envelopes.length; ++i) secondDim[i] = envelopes[i][1];
    return lengthOfLIS(secondDim);
} 
// 如果宽度是严格单增的，说明长度也是严格单增
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    int len = 0;
    for (int num : nums) {
        int i = Arrays.binarySearch(dp, 0, len, num);
        if (i < 0) {
            i = -(i + 1);
        }
        dp[i] = num;
        if (i == len) {
            len++;
        }
    }
    return len;
}

最长子序列

• 不要求连续但是要求顺序不变

public int lengthOfLIS(int[] nums) {
    if(nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    int res = 0;
    Arrays.fill(dp, 1);
    for(int i = 0; i < nums.length; i++) {
        for(int j = 0; j < i; j++) {
           // 注意这里是dp[j]+1，dp[j]就表示以j结尾的最长的单增子序列 
            if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

循环排序

https://zhuanlan.zhihu.com/p/117347353

概念

这一模式描述了一种有趣的方法，处理的是涉及包含给定范围内数值的数组的问题。循环排序模式一次会在数组上迭代一个数值，如果所迭代的当前数值不在正确的索引处，就将其与其正确索引处的数值交换。你可以尝试替换其正确索引处的数值，但这会带来 O(n^2) 的复杂度，这不是最优的，因此要用循环排序模式。

特点

• 问题涉及到 数组需要在给定范围内进行数值排序
• 问题要求在一个排序，旋转的数组中找到确实的值/重复的值/最小的值

常见问题

• 找到缺失值
• 找到最小的缺失的正数值

举例

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数

• 把每个数字换到应该存在的位置上去，比如5就该放到nums[4]
• 如果这个数字大于length了，就不管，反正最后要检查

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。（本应该有n+1个数字）

• 与上面的题差不多
• 也可以用异或来做，nums中所有的数和0-n一共n+1个数异或，最后得到的数就是需要的数

数组中重复的数据

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

• 也可以交换，放到合适的位置

   public List<Integer> findDuplicates(int[] nums) {
       List<Integer> res = new ArrayList<>();
       int len = nums.length;
       if (len == 0) {
           return res;
       }
       for (int i = 0; i < len; i++) {
           while (nums[nums[i] - 1] != nums[i]) {
               swap(nums, i, nums[i] - 1);
           }
       }
       for (int i = 0; i < len; i++) {
           if (nums[i] - 1 != i) {
               res.add(nums[i]);
           }
       }
       return res;
   }

// 用异或实现的交换
   private void swap(int[] nums, int index1, int index2) {
       if (index1 == index2) {
           return;
       }
       nums[index1] = nums[index1] ^ nums[index2];
       nums[index2] = nums[index1] ^ nums[index2];
       nums[index1] = nums[index1] ^ nums[index2];
   }

原地翻转列表

概念

在很多问题中，你可能会被要求反转一个链表中一组节点之间的链接。通常而言，你需要原地完成这一任务，即使用已有的节点对象且不占用额外的内存。

该模式会从一个指向链表头的变量（current）开始一次反转一个节点，然后一个变量（previous）将指向已经处理过的前一个节点。以锁步的方式，在移动到下一个节点之前将其指向前一个节点，可实现对当前节点的反转。

另外，也将更新变量「previous」，使其总是指向已经处理过的前一个节点。

特点

• 类似与双指针问题
• 一般要求不使用额外内存的前提下反转链表

常见问题

• 反转子列表
• 反转每个K个元素的子列表

例题

反转链表

• 迭代如下

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

• 递归如下

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

反转链表II

反转index为m-n的子链表

• 迭代如下

public ListNode reverseBetween(ListNode head, int m, int n) {

    // Empty list
    if (head == null) {
        return null;
    }
    // 让cur为m，prev为m-1
    ListNode cur = head, prev = null;
    while (m > 1) {
        prev = cur;
        cur = cur.next;
        m--;
        n--;
    }

    // The two pointers that will fix the final connections.
    ListNode con = prev, tail = cur;

    // Iteratively reverse the nodes until n becomes 0.
    ListNode third = null;
    // 反转n-m次，之前n已经减过了m次了
    while (n > 0) {
        third = cur.next;
        cur.next = prev;
        prev = cur;
        cur = third;
        n--;
    }

    // Adjust the final connections as explained in the algorithm
    if (con != null) {
        con.next = prev;
    } else {
        head = prev;
    }

    tail.next = cur;
    return head;
}

• 递归如下

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    // 直到找到第m个节点，翻转后面的n-m个节点，因为之前n减去了m，所以直接传入n
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点，不需要翻转的节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转后 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    // 现在head.next指向的就是被反转后的节点的最后一个节点
    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
} 

树的宽度优先搜索

概念

基于宽度有限搜索技术，遍历一个树，并且使用一个队列来跟踪一个层级的所有节点，任何涉及到以逐层级方式遍历树的问题的都可以使用这种方法有效解决

工作模式：将根节点加入到队列中，然后连续迭代直到队列为空，在每次迭代中，移除队列头部的节点并且访问这个节点，然后将其所有自节点插入到队列当中

特点

所有需要层次遍历树的问题

常见问题

• 层次遍历
• 之字型遍历

示例

从上到下打印二叉树

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    if(root != null) queue.add(root);
    while(!queue.isEmpty()) {
        List<Integer> tmp = new ArrayList<>();
        for(int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        res.add(tmp);
    }
    return res;
}

特定深度节点链表

public ListNode[] listOfDepth(TreeNode tree) {
     Queue<TreeNode> queue=new LinkedList<>();
    List<List<Integer>> lists=new ArrayList<>();
    if(tree != null){
        queue.add(tree);
    }
    while(!queue.isEmpty()){
        List<Integer> list=new ArrayList<>();
        for(int i=queue.size();i>0;i--){
                TreeNode tmp=queue.poll();
                list.add(tmp.val);
                if(tmp.left !=null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
        }
        lists.add(list);
    }
    // 以上就是层次遍历
    // 下面就是把TreeNode移动到ListNode里面
    ListNode[] a=new ListNode[lists.size()];
    for(int i=0;i<lists.size();i++){
        ListNode l=new ListNode(0);
        ListNode ll=l;
        for(int j=0;j<lists.get(i).size();j++){
            ListNode tmp=new ListNode(lists.get(i).get(j));
            l.next=tmp;
            l=l.next;
        }
        a[i]=ll.next;
    }
    return a;
}

二叉树的锯齿形层序遍历

Z形层次遍历

• 层次遍历
• 记录当前遍历行数
• 下面是DFS

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    travel(root, res, 0);
    return res;
}

private void travel(TreeNode cur, List<List<Integer>> res, int level) {
    if (cur == null)
        return;
    //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
    if (res.size() <= level) {
        List<Integer> newLevel = new LinkedList<>();
        res.add(newLevel);
    }
    //遍历到第几层我们就操作第几层的数据
    List<Integer> list = res.get(level);
    //这里默认根节点是第0层，偶数层相当于从左往右遍历，
    // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
    // 要把数据添加到集合的开头
    if (level % 2 == 0)
        list.add(cur.val);
    else
        list.add(0, cur.val);
    //分别遍历左右两个子节点，到下一层了，所以层数要加1
    travel(cur.left, res, level + 1);
    travel(cur.right, res, level + 1);
}

• 下面是BFS

    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    if (root == null) {
        return ans;
    }

    Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
    nodeQueue.offer(root);
    boolean isOrderLeft = true;

    while (!nodeQueue.isEmpty()) {
        Deque<Integer> levelList = new LinkedList<Integer>();
        int size = nodeQueue.size();
        for (int i = 0; i < size; ++i) {
            TreeNode curNode = nodeQueue.poll();
            if (isOrderLeft) {
                levelList.offerLast(curNode.val);
            } else {
                levelList.offerFirst(curNode.val);
            }
            if (curNode.left != null) {
                nodeQueue.offer(curNode.left);
            }
            if (curNode.right != null) {
                nodeQueue.offer(curNode.right);
            }
        }
        ans.add(new LinkedList<Integer>(levelList));
        isOrderLeft = !isOrderLeft;
    }

    return ans;
}

二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

• 层次遍历，每一层的最后一个

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                res.add(node.val);
            }
        }
    }
    return res;
}

• 根节点→右子树→左子树

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (depth == res.size()) {   // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

树的深度优先搜索

概念

Tree DFS 是基于深度优先搜索（DFS）技术来遍历树。

你可以使用递归（或该迭代方法的技术栈）来在遍历期间保持对所有之前的（父）节点的跟踪。

Tree DFS 模式的工作方式是从树的根部开始，如果这个节点不是一个叶节点，则需要做三件事：

• 决定现在是处理当前的节点（pre-order），或是在处理两个子节点之间（in-order），还是在处理两个子节点之后（post-order）
• 为当前节点的两个子节点执行两次递归调用以处理它们

特点

• 如果你被要求用 in-order、pre-order 或 post-order DFS 来遍历一个树
• 如果问题需要搜索其中节点更接近叶节点的东西

常见问题

• 路径数量之和（中等）
• 一个和的所有路径（中等）

示例

具有最深节点的最小子树

返回最靠近叶的子树的根节点，让他满足左右子树包含最深的节点

• 如果 node 没有左右子树，返回 node。
• 如果 node 左右子树的后代中都有最深节点，返回 node。
• 如果只有左子树或右子树中有且拥有所有的最深节点，返回这棵子树的根节点（即 node 的左/右孩子）。
• 否则，当前子树中不存在答案。

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    // Return the result of the subtree at this node.
    public Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);
        Result L = dfs(node.left),
               R = dfs(node.right);
        if (L.dist > R.dist) return new Result(L.node, L.dist + 1);
        if (L.dist < R.dist) return new Result(R.node, R.dist + 1);
        // 左右子树深度相同，返回自己
        return new Result(node, L.dist + 1);
    }
class Result {
    TreeNode node;
    int dist;
    Result(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}

监控二叉树

返回能够监控二叉树需要的最小的摄像头数量

• 每个节点一共维持三种类型的状态
• 状态0: 自己没有摄像头，自节点也没有
• 状态1: 自己有摄像头
• 状态2: 子节点有摄像头

//子节点没有，自己也没有
private final int NO_CAMERA = 0;
//自己有一个
private final int HAS_CAMERA_SELF = 1;
//子节点有
private final int HAS_CAMERA_CHILD = 2;
//null节点
private final int NULL = 3;
private int res = 0;   
public int minCameraCover(TreeNode root) {
  if (root == null) {
    return 0;
  }
  if (dfs(root) == NO_CAMERA) {
    res++;
  }
  return res;
}

// 返回当前节点的状态
public int dfs(TreeNode root) {
  if (root == null) {
    return NULL;
  }
  int left = dfs(root.left), right = dfs(root.right);
  if (left == NO_CAMERA || right == NO_CAMERA) {
    res++;
    return HAS_CAMERA_SELF;
  }
  if (left == HAS_CAMERA_SELF || right == HAS_CAMERA_SELF) {
    return HAS_CAMERA_CHILD;
  }
  if (left == NULL && right == NULL) {
    return NO_CAMERA;
  }
  return NO_CAMERA;
}

电话号码的字母组合

给定一串数字，单个数字范围为0-9，返回在九宫格输入法下能打印的所有字母序列

• 其实也能理解成遍历树的所有路径

class Solution {
    // 深度优先
	private String letterMap[] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };

    private ArrayList<String> res;

    public List<String> letterCombinations(String digits) {

        res = new ArrayList<String>();
        if(digits.equals(""))
            return res;

        findCombination(digits, 0, "");
        return res;
    }

    private void findCombination(String digits, int index, String s){

        if(index == digits.length()){
            res.add(s);
            return;
        }

        Character c = digits.charAt(index);
        String letters = letterMap[c - '0'];
        for(int i = 0 ; i < letters.length() ; i ++){
            findCombination(digits, index+1, s + letters.charAt(i));
        }

        return;
    }
    // 这个是回溯，但其实跟上面是一模一样的
    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
    }};
    List<String> combinations = new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return combinations;
        }
        backtrack(digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            for (int i = 0; i < letters.length(); i++) {
                // 这个传的引用，空间消耗小一点
                combination.append(letters.charAt(i));
                backtrack(digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

验证二叉搜索树

给定一个二叉树，判断是否是一个有效的二叉搜索树

• 递归就好

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode node, long lower, long upper) {
    if (node == null) {
        return true;
    }
    if (node.val <= lower || node.val >= upper) {
        return false;
    }
    return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}

对称二叉树

判断一个二叉树是不是镜像对称

• 两个指针，往相反的方向移动
• 下面是递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

• 用队列实现递归到迭代的改变

public boolean isSymmetric(TreeNode root) {
    return check(root, root);
}

public boolean check(TreeNode u, TreeNode v) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(u);
    q.offer(v);
    while (!q.isEmpty()) {
        u = q.poll();
        v = q.poll();
        if (u == null && v == null) {
            continue;
        }
        if ((u == null || v == null) || (u.val != v.val)) {
            return false;
        }

        q.offer(u.left);
        q.offer(v.right);

        q.offer(u.right);
        q.offer(v.left);
    }
    return true;
}

二叉树的最大深度

• 递归，深度优先

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

• 广度优先

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    int ans = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
        ans++;
    }
    return ans;
}

二叉树的遍历

先序遍历

• 递归

public void getPreorder(TreeNode root) {
  if (root == null) {
    return;
  }
  System.out.print(root.element + " ");
  getPreorder(root.left);
  getPreorder(root.right);
}

• 非递归

public void getPreorder(TreeNode root) {
  Deque<TreeNode> stack = new LinkerList<>();
  TreeNode p = root;
  while (p != null || !stack.isEmpty()) {
    if (p != null) {
      System.out.println(p.getElement());
      stack.push(p);
      p = p.left;
    } else {
      p = stack.pop().right;
    }
  }
}

中序遍历

• 递归

public void getInorder(TreeNode root) {
  if (root == null) {
    return;
  }
  getInorder(root.left);
  System.out.print(root.element + " ");
  getInorder(root.right);
}

• 非递归

public void getInorder(TreeNode<T> root) {
  Deque<TreeNode> stack = new LinkedList<>();
  TreeNode p = root;
  while (p != null || !stack.isEmpty()) {
    if (p != null) {
      stack.push(p);
      p = p.left;
    } else {
      TreeNode temp = stack.pop();
      System.out.println(temp.getElement());
      p = temp.right;
    }
  }
}

后序遍历

• 递归

private void getPostorder(TreeNode root) {
  if (root == null) {
    return;
  }
  getPostorder(root.left);
  getPostorder(root.right);
  System.out.println(root.element);
}

• 非递归

public void getPostorder(TreeNode root) {
  Deque<TreeNode> stack = new LinkedList<>();
  TreeNode p = root;
  while (p != null || !stack.isEmpty()) {
    if (p != null) {
      stack.push(p);
      p = p.left;
    } else {
      TreeNode temp = stack.pop();
      if (第一次被pop出来){
        stack.push(temp);
        p = temp.right;
      }
      else {
        System.out.println(temp.getElement());
      }
    }
  }
}

二叉树的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

• 每条路径肯定有一个父节点，这个父节点的两侧肯定没有分叉
• 最大贡献值：空节点为0，非空节点为自己+子节点中的最大贡献值
• 先递归计算每个节点的最大贡献值
• 对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

Two Heaps

概念

在很多问题中，我们要将给定的一组元素分为两部分。
为了求解这个问题，我们感兴趣的是了解一部分的最小元素以及另一部分的最大元素。
这一模式是求解这类问题的一种有效方法。该模式要使用两个堆（heap）：一个用于寻找最小元素的 Min Heap 和一个用于寻找最大元素的 Max Heap。
该模式的工作方式是：先将前一半的数值存储到 Max Heap，这是由于你要寻找前一半中的最大数值。然后再将另一半存储到 Min Heap，因为你要寻找第二半的最小数值。
在任何时候，当前数值列表的中位数都可以根据这两个 heap 的顶部元素计算得到。

特点

• 优先级队列，调度等场景
• 需要找到一个集合的最小，最大，中间元素
• 有时候可以用于二叉树结构的问题

常见问题

• 查找一个数值流的中间值

示例

数据流的中位数

class MedianFinder {

    /**
     * 当前大顶堆和小顶堆的元素个数之和
     */
    private int count;
    // 顶部的是最大的元素
    private PriorityQueue<Integer> maxheap;
    // 顶部的是最小的元素
    private PriorityQueue<Integer> minheap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        count = 0;
        maxheap = new PriorityQueue<>((x, y) -> y - x);
        minheap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        count += 1;
        maxheap.offer(num);
        minheap.add(maxheap.poll());
        // 如果两个堆合起来的元素个数是奇数，小顶堆要拿出堆顶元素给大顶堆,相反也可以，上两行代码也要换顺序，主要是维持两个heap数量相差在1以内     
        if ((count & 1) != 0) {
            maxheap.add(minheap.poll());
        }
    }

    public double findMedian() {
        if ((count & 1) == 0) {
            // 如果两个堆合起来的元素个数是偶数，数据流的中位数就是各自堆顶元素的平均值
            return (double) (maxheap.peek() + minheap.peek()) / 2;
        } else {
            // 如果两个堆合起来的元素个数是奇数，数据流的中位数大顶堆的堆顶元素
            return (double) maxheap.peek();
        }
    }
}

滑动窗口中位数

• 不用大小堆，只是二分查找旧的替换新的，然后冒泡放在该防的位置

public double[] medianSlidingWindow(int[] nums, int k) {
    double[] res = new double[nums.length - k + 1];
    int[] window = new int[k];
    //添加初始值
    for (int i = 0; i < k; i++) {
        window[i] = nums[i];
    }
    //初始的快排，懒得写直接调用
    Arrays.sort(window);
    res[0] = getMid(window);
    //窗口滑动
    for (int i = 0; i < nums.length - k; i++) {
        //需要删除的数
        int index = search(window, nums[i]);
        //替换为需要插入的数
        window[index] = nums[i + k];
        //向后冒泡
        while (index < window.length - 1 && window[index] > window[index + 1]) {
            swap(window, index, index + 1);
            index++;
        }
        //向前冒泡
        while (index > 0 && window[index] < window[index - 1]) {
            swap(window, index, index - 1);
            index--;
        }
        res[i + 1] = getMid(window);
    }
    return res;
}

//交换
private void swap(int[] window, int i, int j) {
    int temp = window[i];
    window[i] = window[j];
    window[j] = temp;
}

//求数组的中位数
private double getMid(int[] window) {
    int len = window.length;
    if (window.length % 2 == 0) {
        //避免溢出
        return window[len / 2] / 2.0 + window[len / 2 - 1] / 2.0;
    } else {
        return window[len / 2];
    }
}

//最简单的二分查找
private int search(int[] window, int target) {
    int start = 0;
    int end = window.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (window[mid] > target) {
            end = mid - 1;
        } else if (window[mid] < target) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

子集

概念

很多编程面试问题都涉及到处理给定元素集合的排列和组合。子集（Subsets）模式描述了一种用于有效处理所有这些问题的宽度优先搜索（BFS）方法。

特点

当你需要找到给定集合的组合或者排列的问题

常见问题

• 带有重复项的子集
• 通过改变大小写的字符串排列

示例

括号生成

• 其实是深度优先

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }
        dfs("", n, n, res);
        return res;
    }
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }

        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}

public class Solution {
    // 同样的道理
	public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

组合总和

给定一个数组和一个目标数，找出数组元素的所有组合，满足和为目标数字

class Solution {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(path,candidates,target,0,0);
        return res;
    }

    private void backtrack(List<Integer> path,int[] candidates,int target,int sum,int index) {
        if(sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index;i < candidates.length;i++) {
            int newSum = candidates[i] + sum;
            if(rs <= target) {
                path.add(candidates[i]);
                backtrack(path,candidates,target,newSum,i);
                path.remove(path.size()-1);
            } else {
                break;
            }
        }
    }
}

组合总和2

组合需要去重复

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    int len = candidates.length;
    List<List<Integer>> res = new ArrayList<>();
    if (len == 0) {
        return res;
    }
    Arrays.sort(candidates);
    Deque<Integer> path = new ArrayDeque<>(len);
    dfs(candidates, len, 0, target, path, res);
    return res;
}
private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = begin; i < len; i++) {
        if (target - candidates[i] < 0) {
            break;
        }
        // 避免了重复组合的出现，但是没有避免一个组合中有相同元素的出现
        if (i > begin && candidates[i] == candidates[i - 1]) {
            continue;
        }
        path.addLast(candidates[i]);
        dfs(candidates, len, i + 1, target - candidates[i], path, res);
        path.removeLast();
    }
}

动态规划

不属于原文的一部分，但我刷题觉得用的太多了

概念

用空间换时间，先统计出已经计算过的数值，方便下一步使用

示例

最长回文子串

给定一个字符串，找到最长的回文子串

class Solution {
public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;
        int maxEnd = 0;  
        int maxLen = 1;

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                // r-l<=2的时候中间只有一个元素或者没有元素 肯定是回文串
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);
    }
}

• 也可以使用中心扩展的方法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
          	// 这样扩展的长度奇数
            int len1 = expandAroundCenter(s, i, i);
          	// 这样扩展的长度是偶数
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

• 也可以得到一个倒序的字符串，然后返回正反字符串的最长公共子串

最长回文子序列

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。

class Solution {
  public int longestPalindromeSubseq(String s) {
    int length = s.length();
    int[][] dp = new int[length][length];
    for (int i = length - 1; i >= 0; i--) {
      dp[i][i] = 1;
      for (int j = i+1; j < length; j += 1) {
        if (s.charAt(i) == s.charAt(j)) {
          // 要确保i+1和j-1都是被计算过的
          dp[i][j] = dp[i + 1][j - 1] + 2;
        }
        else {
          dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[0][length - 1];
  }
}

最长公共子串

给出两个字符串的最长公共子串

public static int getLCS(String s1, String s2) {
  // 也可以不用转化为char数组
  char[] a = s1.toCharArray();
  char[] b = s2.toCharArray();
  // a.length行，b.length列
  int[][] result = new int[a.length + 1][b.length + 1];
  int max = 0;
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      if (a[i] == b[j]) {
        // result[0][0]永远为0，result[1][1] = 1代表两个字符串的第一个元素相等
        result[i + 1][j + 1] = result[i][j] + 1;
        // 最终答案并不一定在最后一个格子里面
        max = Math.max(max, result[i + 1][j + 1]);
      }
    }
  }
  return max;
}

最长公共子序列

和最长公共子串类似，只不过子序列是可以不连续的。

public static int getLCS(String s1, String s2) {
  char[] a = s1.toCharArray();
  char[] b = s2.toCharArray();
  // a.length行，b.length列
  int[][] result = new int[a.length + 1][b.length + 1];
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      if (a[i] == b[j]) {
        result[i + 1][j + 1] = result[i][j] + 1;
      } else {
        result[i + 1][j + 1] = Math.max(result[i][j + 1], result[i + 1][j]);
      }
    }
  }
  return result[a.length][b.length];

打家劫舍

一个数组，代表每个房屋存放的金额的非负整数数组，不能相邻被偷

class Solution {
  	// 由于只用到了dp[i-1]和dp[i-2]那么我们可以只用两个变量来记录
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) 
          	// 要么偷这一家 要么这家不投 投到这家时候的收益就等于偷到上一家的收益
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

打家劫舍II

一个数组，代表每个房子存放的金额，不能相邻被偷，房子是连在一起的

• 两个打家劫舍的问题：从第一间偷到倒数第二间，从第二间偷到倒数第一间

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), 
                        myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for(int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

打家劫舍III

所有房屋的排列类似于一颗二叉树，两个直接相连的房子在同一天晚上被打劫，自动报警

• 每一个节点存储两个值，自己不偷能得到的钱result[0]和自己偷能得到的钱result[1]

class Solution {
    public int rob(TreeNode root) {
        int[] result = robInternal(root);
        return Math.max(result[0], result[1]);
    }

    public int[] robInternal(TreeNode root) {
        if (root == null) return new int[2];
        int[] result = new int[2];

        int[] left = robInternal(root.left);
        int[] right = robInternal(root.right);

        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = left[0] + right[0] + root.val;

        return result;
    }
}