Divide & Conquer

经典题目

23 Merge k Sorted Lists

Divide the input into the minimal parts which can not be divided anymore. Then merge the adjacent two lists and return the merged lists. Keep merging until we have only one list.

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return mergeKLists(lists, 0, lists.length - 1);
}
private ListNode mergeKLists(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode a = mergeKLists(lists, left, mid);
    ListNode b = mergeKLists(lists, mid + 1, right);
    return merge(a, b);
}
private ListNode merge(ListNode a, ListNode b) {
    if (a == null) return b;
    if (b == null) return a;
    ListNode dummyNode = new ListNode(0);
    ListNode cur = dummyNode;
    while (a != null && b != null) {
        if (a.val < b.val) {
            cur.next = a;
            a = a.next;
        } else {
            cur.next = b;
            b = b.next;
        }
        cur = cur.next;
    }
    if (a != null) cur.next = a;
    if (b != null) cur.next = b;
    return dummyNode.next;
}

395 Longest Substring with At Least K Repeating Characters

先扫一遍，找到freq < k的char，然后分成左右两边找，返回较大的那个。

helper function返回的是当前区间最长的substring with at least K repeating chars

Iterative

public int longestSubstring(String s, int k) {
    int ans = 0;
    for (int target = 1; target <= 26; target++) {
        int[] count = new int[26];
        int i = 0, j = 0;
        int unique = 0, noLessK = 0;
        
        while (j < s.length()) {
            if (unique <= target) {
                int index = s.charAt(j) - 'a';
                if (count[index] == 0) {
                    unique++;
                }
                count[index]++;
                if (count[index] == k) {
                    noLessK++;
                }
                j++;
            } else {
                int index = s.charAt(i) - 'a';
                if (count[index] == 1) {
                    unique--;
                }
                count[index]--;
                if (count[index] == k - 1) {
                    noLessK--;
                }
                i++;
            }
            if (unique == target && noLessK == unique) {
                ans = Math.max(ans, j - i);
            }
        }
    }
    return ans;
}

Recursion

public int longestSubstring(String s, int k) {
    char[] str = s.toCharArray();
    return helper(str,0,s.length(),k);
}
private int helper(char[] str, int start, int end, int k){
    if (end - start < k) return 0;//substring length shorter than k.
    int[] count = new int [26];
    for (int i = start; i<end; i++) {
        int idx = str[i] - 'a';
        count[idx]++;
    }
    for (int i=0; i<26; i++) {
        if (count[i] < k && count[i] > 0) { //count[i]=0 => i+'a' does not exist in the string, skip it.
            for (int j = start; j<end; j++) {
                if (str[j] == i+'a') {
                    int left = helper(str, start, j, k);
                    int right = helper(str, j+1, end, k);
                    return Math.max(left, right);
                }
            }
        }
    }
    return end - start;
}