如何实现LeetCode 46题的全排列算法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计697个文字，预计阅读时间需要3分钟。
使用回溯法解决此问题，对于每一个当前位置i，我们可以将其与后面的任意位置交换，然后继续处理位置i+1，直到处理到最后一个位置。为了防止每次遍历时都重新构建子数组，我们可以在遍历前创建一个存储每个位置可能值的数组。
使用回溯法解决此问题，对于每一个当前位置i，我们可以将其与之后的任意位置交换，然后继续处理位置i+1，直到处理到最后一位。为了防止我们每次遍历时都要新建一个子数组储存位置i之前已经交换好的数字，我们就利用回溯法，只对原数组进行修改，在递归完成后再修改回来。 一、题目大意标签: 搜索
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 在这天结束的时候完成
本文共计697个文字，预计阅读时间需要3分钟。
使用回溯法解决此问题，对于每一个当前位置i，我们可以将其与后面的任意位置交换，然后继续处理位置i+1，直到处理到最后一个位置。为了防止每次遍历时都重新构建子数组，我们可以在遍历前创建一个存储每个位置可能值的数组。
使用回溯法解决此问题，对于每一个当前位置i，我们可以将其与之后的任意位置交换，然后继续处理位置i+1，直到处理到最后一位。为了防止我们每次遍历时都要新建一个子数组储存位置i之前已经交换好的数字，我们就利用回溯法，只对原数组进行修改，在递归完成后再修改回来。 一、题目大意标签: 搜索
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 在这天结束的时候完成