Day10/11 recursion / backtracking

1 21. Merge two ordered lists

1.1 subject

1.2 Answer key

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
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;
    }
}

notes ： The idea of merging adopted by oneself , But the problem itself is more appropriate to do it in a recursive way , Of this article Answer key very good .

2 206. Reverse a linked list

2.1 subject

2.2 Answer key

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = 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;
    }
}

notes ： The first idea is to insert the head , It has also been realized. ; Looked at the Answer key , Recursion is so important .

3 77. Combine

3.1 subject

3.2 Answer key

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

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

        //  from 1 Begin your search 
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res){
    
        //  Determine the termination condition of recursion ： When the stack length reaches the combined length 
        if(path.size() == k){
    
            res.add(new ArrayList<>(path));
            return;
        }

        //  Traverse all search starting points 
        for(int i = begin; i <= n - (k - path.size()) + 1; i++){
    
            //  Add a number to the path variable 
            path.addLast(i);
            //  Next round of search , Set the search starting point to add  1, Because duplicate elements are not allowed in Combinatorial Mathematics 
            dfs(n, k, i + 1, path, res);
            //  Focus on understanding here ： Depth first traversal has a backward process , So what did you do before recursion , After recursion, you need to do the reverse operation of the same operation 
            path.removeLast();
        }
    }
}

notes ： This big guy's Backtracking problem solving Study hard .

4 46. Full Permutation

4.1 subject

4.2 Answer key

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

        //  Record the prime progression of each permutation path Information about 
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res){
    
        //  Recursive termination condition ：depth==len, That is to say, all the numbers have been taken 
        if(depth == len){
    
            res.add(new ArrayList<>(path));
            return;
        }

        //  Among the unselected numbers, select one element in turn as the element of the next position 
        for(int i = 0; i < len; i++){
    
            //  If the element does not enter path
            if(!used[i]){
    
                path.add(nums[i]);
                used[i] = true;

                //  Continue to drill down until path Until it's full 
                dfs(nums, len, depth + 1, path, used, res);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }

    }
}

notes ： Answer key Take a good look at .

5 784. All the letters are in uppercase and lowercase

5.1 subject

5.2 Answer key

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

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

        if(Character.isLetter(s[index])) {
     // use Character.isLetter() Decide if it's a letter , Very convenient 
            s[index] = Character.toLowerCase(s[index]);
            dfs(index + 1, s, res); // For both cases where letters are guaranteed to be lowercase and uppercase 
            s[index] = Character.toUpperCase(s[index]);
        } // Use them separately Character.toLowerCase() and Character.toUpperCase() Convert upper and lower case letters , There is no need to write judgment to convert manually 

        dfs(index + 1, s, res); // Both numbers and letters go to the next character 
    }
}

notes ： The details of this problem are not clear , Answer key Here it is .

6 summary

It feels like whether it's a recursion or a backtracking problem , There are certain templates , Come back to review these questions after brushing all the questions , Sharp brush of the same type .