Day10/11 递归 / 回溯

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;

        ListNode mergeList = new ListNode();
        ListNode res = mergeList;
        ListNode p = list1;
        ListNode q = list2;

        while(p != null && q != null){
            if(p.val < q.val){
                mergeList.next = p;
                mergeList = mergeList.next;
                p = p.next;
            }else{
                mergeList.next = q;
                mergeList = mergeList.next;
                q = q.next;
            }
        }

        if(p == null && q == null)
            return res;

        while(p != null){
            mergeList.next = p;
            mergeList = mergeList.next;
            p = p.next;
        }

        while(q != null){
            mergeList.next = q;
            mergeList = mergeList.next;
            q = q.next;
        }

        return res.next;
    }
}

注：自己采用的归并的思想，但是这道题本身还是以递归的思路去做较为合适，这篇文章的题解很好。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return head;
        
        ListNode p = new ListNode(head.val, null);
        while(head.next != null){
            ListNode q = new ListNode(head.next.val, null);
            q.next = p;
            p = q;
            head = head.next;
        }

        return p;
    }
}

注：第一想法就是头插法，也实现了；看了下题解，递归好重要。

class Solution {
    public List> combine(int n, int k) {
        List> res = new ArrayList<>();

        if(k <= 0 || k > n)
            return res;

        // 从1开始搜索
        Deque path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque path, List> res){
        // 确定递归的终止条件：栈内长度达到组合长度时
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历所有的搜索起点
        for(int i = begin; i <= n - (k - path.size()) + 1; i++){
            // 向路径变量中添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }
}

注：这个大佬的回溯题解好好学。

class Solution {
    public List> permute(int[] nums) {
        int len = nums.length;
        List> res = new ArrayList<>();
        if(len == 0)
            return res;

        // 记录每一次排列中元素进path的信息
        boolean[] used = new boolean[len];
        List path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, List path, boolean[] used, List> res){
        // 递归终止条件：depth==len，也就是说所有的数已经取完
        if(depth == len){
            res.add(new ArrayList<>(path));
            return;
        }

        // 在还未选择的数中依次选择一个元素作为下一个位置的元素
        for(int i = 0; i < len; i++){
            // 如果该元素并未进path
            if(!used[i]){
                path.add(nums[i]);
                used[i] = true;

                // 继续向下搜索直至path满为止
                dfs(nums, len, depth + 1, path, used, res);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }

    }
}

注：题解好好看。

class Solution {
    public List letterCasePermutation(String s) {
        List res = new ArrayList<>();
        char[] path = new char[s.length()];
        dfs(0, s.toCharArray(), res);
        return res;
    }

    private void dfs(int index, char[] s, List res){
        if(index == s.length){
            res.add(new String(s));
            return;
        }

        if(Character.isLetter(s[index])) { //用Character.isLetter()判断是否为字母，很方便
            s[index] = Character.toLowerCase(s[index]);
            dfs(index + 1, s, res); //对于字母保证生成小写的和大写的两种情况
            s[index] = Character.toUpperCase(s[index]);
        } //分别用Character.toLowerCase()和Character.toUpperCase()转化大小写字母，再也不用写判断手动转化啦

        dfs(index + 1, s, res); //不管是数字还是字母都要进入下一个字符
    }
}

注：这道题的细节没搞清楚，题解在此。

感觉不管是递归还是回溯问题，都有一定的模板，等刷完所有的题型回来复习这些题，猛刷同类型。