问题陈述给定一个由不同整数组成的数组，返回所有可能的排列 您可以按任何顺序返回答案，接下来我们就来聊聊关于leetcode 基础算法?以下内容大家不妨参考一二希望能帮到您!
leetcode 基础算法
问题陈述
给定一个由不同整数组成的数组，返回所有可能的排列。 您可以按任何顺序返回答案。
示例 1：
Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
示例 2:
Input: nums = [0, 1]
Output: [[0, 1], [1, 0]]
示例 3:
Input: nums = [1]
Output: [[1]]
约束:
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
解释
回溯
当我们需要生成排列或序列时，递归是最好的使用方法。 与标准递归方法相比，此问题的递归将有所不同。
解决此问题的一种方法是跟踪我们访问过的元素并为其余数组元素生成排列。 但是，我们可以通过交换数组元素来解决这个问题。
让我们跳到算法以更好地理解它。
- set result = [[]]- call _getPermutations(result, nums, 0, nums.length - 1)- return result// _getPermutations(result, nums, l, r)
- if l == r
- push the current nums permutation in the result
- result.push(nums)
- else
- loop for i = l; i <= r; i
- swap(nums[l], nums[i]) - _getPermutations(result, nums, l 1, r) - swap(nums[l], nums[i])
- end if
让我们在 C 、Golang 和 Javascript 中检查我们的算法。
C 解决方案
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result; _getPermutations(result, nums, 0, nums.size() - 1);
return result;
} void _getPermutations(vector<vector<int>>& result, vector<int> nums, int l, int r){
if(l == r){
result.push_back(nums);
return;
} else {
for(int i = l; i <= r; i ){
swap(nums[l], nums[i]); _getPermutations(result, nums, l 1, r); swap(nums[l], nums[i]);
}
}
}
};
Golang 解决方案
func permute(nums []int) [][]int {
result := [][]int{} _getPermutations(&result, nums, 0, len(nums) - 1) return result
}func _getPermutations(result *[][]int, nums []int, l, r int) {
if l == r {
cp := make([]int, len(nums))
copy(cp, nums)
*result = append(*result, cp)
} else {
for i := l; i <= r; i {
nums[l], nums[i] = nums[i], nums[l] _getPermutations(result, nums, l 1, r) nums[l], nums[i] = nums[i], nums[l]
}
}
}
Javascript 解决方案
var permute = function(nums) {
const result = []; _getPermutations(result, nums, 0, nums.length - 1); return result;
};function _getPermutations(result, nums, l, r) {
if(l === r) {
result.push(nums.slice(0));
return;
} else {
for(let i = l; i <= r; i ) {
[nums[l], nums[i]] = [nums[i], nums[l]]; _getPermutations(result, nums, l 1, r); [nums[l], nums[i]] = [nums[i], nums[l]];
}
}
}
让我们为示例 1 试运行我们的算法。
Input: nums = [1, 2, 3]// in permute function
Step 1: vector<vector<int>> resultStep 2: _getPermutations(result, nums, 0, nums.size() - 1)
_getPermutations(result, nums, 0, 2)// in _getPermutations function
Step 3: if l == r
0 == 2
false else
loop for i = l; i <= r
i = 0
0 <= 2
true swap(nums[l], nums[i])
swap(nums[0], nums[0])
nums = [1, 2, 3] _getPermutations(result, nums, l 1, r)
_getPermutations(result, nums, 0 1, 2)
_getPermutations(result, nums, 1, 2)Step 4: if l == r
1 == 2
false else
loop for i = l; i <= r
i = 1
1 <= 2
true swap(nums[l], nums[i])
swap(nums[1], nums[1])
nums = [1, 2, 3] _getPermutations(result, nums, l 1, r)
_getPermutations(result, nums, 1 1, 2)
_getPermutations(result, nums, 2, 2)Step 5: if l == r
2 == 2
true
result.push_back(nums)
result = [[1, 2, 3]]
return // We return to step 4Step 6: swap(nums[l], nums[i])
swap(nums[1], nums[1])
nums = [1, 2, 3] i
i = 2
loop for i <= r
i = 2
2 <= 2
true swap(nums[l], nums[i])
swap(nums[1], nums[2])
nums = [1, 3, 2] _getPermutations(result, nums, l 1, r)
_getPermutations(result, nums, 1 1, 2)
_getPermutations(result, nums, 2, 2)Step 7: if l == r
2 == 2
true
result.push_back(nums)
result = [[1, 2, 3], [1, 3, 2]]
return // We return to step 6Step 8: swap(nums[l], nums[i])
swap(nums[1], nums[2])
nums = [1, 2, 3] i
i = 3
loop for i <= r
i = 3
3 <= 2
false // we backtrack to step 3Step 9: swap(nums[l], nums[i])
swap(nums[0], nums[0])
nums = [1, 2, 3] i
i = 1
loop for i <= r
i = 1
1 <= 2
true swap(nums[l], nums[i])
swap(nums[0], nums[1])
nums = [2, 1, 3] _getPermutations(result, nums, l 1, r)
_getPermutations(result, nums, 0 1, 2)
_getPermutations(result, nums, 1, 2)Step 10: if l == r
1 == 2
false else
for i = l; i <= r
i = 1
1 <= 2
true swap(nums[l], nums[i])
swap(nums[1], nums[1])
nums = [2, 1, 3] _getPermutations(result, nums, l 1, r)
_getPermutations(result, nums, 1 1, 2)
_getPermutations(result, nums, 2, 2)Step 11: if l == r
2 == 2
true
result.push_back(nums)
result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
return // We return to step 10We similarly backtrack to generate the rest of the solution
We return the solution as[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
关注七爪网，获取更多APP/小程序/网站源码资源！
