768. 最多能完成排序的块 II 分治

768. 最多能完成排序的块 II

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

• t 是字符串 s 的一个子序列。
• t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

示例 1：

输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。

示例 2：

输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。

提示：

• 1 <= s.length <= 1e5
• 0 <= k <= 25
• s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-ideal-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 做题结果

成功，简单的分治

方法：分治

1. 把数组平均分成前后两个部分

2. 把两个部分合并完之后再进行两个链表的合并

3. 返回合并后的结果

4. 处理递归末尾：如果只有一个元素，返回该元素

5. 坑：空列表，列表中的空链表，这两个地方需要特判处理

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null||lists.length == 0) return null;
        return merge(lists,0,lists.length-1);
    }
 
    private ListNode merge(ListNode[] lists, int start, int end){
        if(start == end) return lists[start];
        int mid = (end-start)/2+start;
        ListNode a = merge(lists,start,mid);
        ListNode b = merge(lists,mid+1,end);
        return mergeTwo(a,b);
    }
 
    private ListNode mergeTwo(ListNode a, ListNode b){
        if(a==null) return b;
        if(b==null) return a;
        ListNode head = new ListNode(0);
        ListNode curr = head;
        while (a!=null&&b!=null){
            if(a.val
                curr.next = a;
                a = a.next;
            }else{
                curr.next = b;
                b = b.next;
            }
            curr = curr.next;
        }
 
        curr.next = a!=null?a:b;
        return head.next;
    }
}