算法入门第11天

开始接触到回溯算法，这玩意也是有套路的，主要解决一些排列组合之类的问题，回溯是暴力搜索。

77. 组合

/**
 77. 组合
 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

 你可以按 任何顺序 返回答案。



 示例 1：

 输入：n = 4, k = 2
 输出：
 [
 [2,4],
 [3,4],
 [2,3],
 [1,2],
 [1,3],
 [1,4],
 ]
 示例 2：

 输入：n = 1, k = 1
 输出：[[1]]


 提示：

 1 <= n <= 20
 1 <= k <= n

 * @author zeroheart
 * @since 2022/4/4
 */
public class Question77 {
    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();
    public List<List<Integer>> combine(int n, int k) {
        backtracing(1, n, k);
        return res;
    }

    private void backtracing(int start, int n, int k) {
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            System.out.println(path);
            return;
        }
        for(int i = start; i<=n; i++){
            path.add(i);
            backtracing(i+1, n, k);
            path.remove(path.size() - 1);
        }

    }

}

46. 全排列

这题和上面的组合是同一个套路，不过全排列不管顺序，所以从0开始，并且如果是访问的节点，不会重复添加，不会出现111，112这样的排列

/**
 46. 全排列
 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。



 示例 1：

 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 示例 2：

 输入：nums = [0,1]
 输出：[[0,1],[1,0]]
 示例 3：

 输入：nums = [1]
 输出：[[1]]


 提示：

 1 <= nums.length <= 6
 -10 <= nums[i] <= 10
 nums 中的所有整数 互不相同

 * @author zeroheart
 * @since 2022/4/4
 */
public class Question46 {
    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();
    boolean[] visited = null;
    public List<List<Integer>> permute(int[] nums) {
        int k = nums.length;
        visited = new boolean[nums.length];
        backtracing(nums, k);
        return res;
    }

    private void backtracing(int[] nums, int k) {
        if(path.size() == k){
            res.add(new ArrayList(path));
            System.out.println(path);
            return;
        }

        for(int j = 0; j < k; j++){
            if(visited[j]) continue;
            visited[j] = true;
            path.add(nums[j]);
            backtracing(nums, k);
            visited[j] = false;
            path.remove(path.size() - 1);
        }


    }


    public static void main(String[] args) {
        new Question46().permute(new int[]{1,2,3});
    }


}

784. 字母大小写全排列

这题是不改变顺序的，所以不需要循环处理，也不需要弹出最后的字母，因为长度总是不变，只是替换其中的大小写。

/**
 784. 字母大小写全排列
 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。



 示例 1：

 输入：s = "a1b2"
 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 示例 2:

 输入: s = "3z4"
 输出: ["3z4","3Z4"]


 提示:

 1 <= s.length <= 12
 s 由小写英文字母、大写英文字母和数字组成


 * @author zeroheart
 * @since 2022/4/4
 */
public class Question784 {
    List<String> res = new ArrayList();
    public List<String> letterCasePermutation(String s) {
        char[] chars = s.toCharArray();
        backtracing(chars, 0);
        return res;
    }

    private void backtracing(char[] chars, int idx) {
        if(idx == chars.length){
            String s = new String(chars);
            res.add(s);
            System.out.println(s);
            return;
        }

        if(!Character.isDigit(chars[idx])) {
            char aChar = chars[idx];
            chars[idx] = Character.toLowerCase(aChar);
            backtracing(chars, idx + 1);
            chars[idx] = Character.toUpperCase(aChar);
            backtracing(chars, idx + 1);
        }
        backtracing(chars, idx + 1);
    }


    public static void main(String[] args) {
    }


}