当前位置 : 主页 > 编程语言 > 其它开发 >

leetcode 46. Permutations 全排列(中等)

来源:互联网 收集:自由互联 发布时间:2022-06-04
使用回溯法解决此问题,对于每一个当前位置i,我们可以将其与之后的任意位置交换,然后继续处理位置i+1,直到处理到最后一位。为了防止我们每次遍历时都要新建一个子数组储存位
使用回溯法解决此问题,对于每一个当前位置i,我们可以将其与之后的任意位置交换,然后继续处理位置i+1,直到处理到最后一位。为了防止我们每次遍历时都要新建一个子数组储存位置i之前已经交换好的数字,我们就利用回溯法,只对原数组进行修改,在递归完成后再修改回来。 一、题目大意

标签: 搜索

https://leetcode.cn/problems/permutations

给定一个不含重复数字的数组 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 中的所有整数 互不相同
二、解题思路

使用回溯法解决此问题,对于每一个当前位置i,我们可以将其与之后的任意位置交换,然后继续处理位置i+1,直到处理到最后一位。为了防止我们每次遍历时都要新建一个子数组储存位置i之前已经交换好的数字,我们就利用回溯法,只对原数组进行修改,在递归完成后再修改回来。

三、解题方法 3.1 Java实现
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backTracking(nums, 0, ans);
        return ans;
    }

    void backTracking(int[] nums, int level, List<List<Integer>> ans) {
        if (level == nums.length - 1) {
            ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            return;
        }
        for (int i = level; i < nums.length; i++) {
            // 修改当前节点状态
            swap(nums, i, level);
            // 递归子节点
            backTracking(nums, level + 1, ans);
            // 回改当前节点状态
            swap(nums, i, level);
        }
    }

    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
四、总结小记
  • 2022/6/3 在这天结束的时候完成
网友评论