LeetCode探索（回溯、归并）

前言

探索卡片终于做到了回溯的部分，我一直对回溯算法不太了解，所以借此机会总结一下回溯算法的具体写法和框架。
本文参考LeetCode用户labuladong的文章：回溯算法解题套路框架
后半部分顺便总结之前使用的归并排序。

回溯

框架

一个回溯问题，主要要考虑清楚三个部分：

• 路径
• 选择列表
• 结束条件

基于这三个部分，可以给出算法框架。

List<> res;
public void backtrack(路径,选择列表){
	if(满足结束条件){
		res.add(路径);
		return;
	}
	for(选择:选择列表){
		做选择;
		backtrack(新的路径,新的选择列表)
		撤销选择;
	}
}

可以看到回溯算法的框架和我们熟悉的树的遍历是相似的。

全排列

题目：https://leetcode-cn.com/problems/permutations/
题目大意：给出一个没有重复数字的序列，返回其所有可能的排序。

我们按照刚才给出的思路和框架解决一下这个问题。
可以看出基本就是按照上面所描述的框架写的。

class Solution {
	//结果
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<>();
        if(nums == null || nums.length == 0)
            return res;
        LinkedList<Integer> path = new LinkedList<>();
        backtrack(nums,path);
        return res;
    }
    public void backtrack(int[]nums,LinkedList<Integer> path){
    	//满足结束条件
        if(path.size() == nums.length){
        	//注意复制一个新的列表过去，
        	//不然你会惊喜的发现res里面的列表全是空的
            res.add(new LinkedList<>(path));
            return;
        }
        //遍历选择列表
        for(int i:nums){
        	//不在选择列表中的直接跳过
            if(path.contains(i))
                continue;
            //做选择
            path.add(i);
            //进入下一个选择列表
            backtrack(nums,path);
            //撤销选择
            path.removeLast();
        }
    }
}

二叉树中和为某一值的路径

题目：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
题目大意：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

我们再来回顾一下剑指offer上的题目，可以看到这次代码有一些不同。

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new LinkedList<>();
        if(root == null)
            return res;
        LinkedList<Integer> path = new LinkedList<>();
        backtrace(root,path,sum);
        return res;
    }
    public void backtrace(TreeNode node,LinkedList<Integer> path,int target){
        if(node == null)
            return;
        //做选择
        path.add(node.val);
        target -= node.val;
        //这次的终止条件出现在了这里
        if(target == 0 && node.left == null && node.right == null)
            res.add(new LinkedList<>(path));
        backtrace(node.left,path,target);
        backtrace(node.right,path,target);
        //撤销选择
        path.removeLast();
    }
}

电话号码的字母组合

题目：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode/
题目大意：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。
图是手机上的九键，这里就不列出来了。

使用刚才的模板，我们可以得出以下代码，但是其中还是有一些细节需要注意一下。

class Solution {
    List<String> res;
    //map在初始化的时候赋值
    HashMap<Character,String> map = new HashMap(){
        {
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }
    };
    public List<String> letterCombinations(String digits) {
        res = new LinkedList<>();
        if(digits == null || digits.length() == 0)
            return res;
        //使用StringBuilder方便添加和删除
        StringBuilder sb = new StringBuilder();
        backtrace(digits,sb,0);
        return res;
    }
    public void backtrace(String digits,StringBuilder sb,int index){
        if(index == digits.length()){
            res.add(sb.toString());
            return;
        }
        char[] chars = map.get(digits.charAt(index)).toCharArray();
        for(char c:chars){
            sb.append(c);
            backtrace(digits,sb,index+1);
            //注意这里，StringBuilder的删除不是removeLast
            //而是deleteCharAt(int index)
            //或者delete(int start,int end)
            sb.deleteCharAt(index);
        }
    }
}

归并

框架

归并排序的思想就是先把数组两两划分，然后再两两排序合并。
那么如果将数组两两划分呢？
这就要使用到之前总结过的二分了。

public merge(int[] nums,int left,int right){
	//区间为1，我们使用的是左闭右闭的区间
	if(left >= right)
		return;
	//找出中点
	int mid = left+(right-left)/2;
	//对左边进行划分并排序
	merge(nums,left,mid);
	//对右边进行划分并排序
	merge(nums,mid+1,right);
	//合并这两个区间
	sort(nums,left,mid,right);
}

合并k个排序链表

既然已经是排序链表了，我们自然很容易想到归并的方法。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left == right)
            return lists[left];
        int mid = left + (right-left)/2;
        ListNode leftList = merge(lists,left,mid);
        ListNode rightList = merge(lists,mid+1,right);
        return mergeTwoList(leftList,rightList);
    }
    public ListNode mergeTwoList(ListNode l1,ListNode l2){
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoList(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoList(l1,l2.next);
            return l2;
        }
        
    }
}