当前位置：首页 > news >正文

惠州做网站的郑州网站推广培训

news 2026/4/7 1:10:51

惠州做网站的,郑州网站推广培训,企业网站源码,如何做网站首页的psd图一、前言 1、题目描述和代码仅供参考，如果有问题欢迎指出 2、解题代码采用acm模式（自己处理输入输出），不采用核心代码模式（只编程核心函数） 3、解题代码采用C语言（ai一键翻译任意语言&#xff…

一、前言

1、题目描述和代码仅供参考，如果有问题欢迎指出
2、解题代码采用acm模式（自己处理输入输出），不采用核心代码模式（只编程核心函数）
3、解题代码采用C++语言（ai一键翻译任意语言，或者cpp转Java等任意语言）

二、题目说明

题目：
给你一个整数集合 nums ，按任意顺序返回它所有不重复的全排列。
举例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

三、DFS回溯法（递归编程实现）

解题思路：
定义一个f()函数求可行的全排列解，如果到叶子节点时该路径可行就记录，否则回溯求解；
f(123) = 1 + f(23)，
f(23）= 2 + f(3),
f(3）= 3

解题代码：

#include <iostream>
#include <vector>using namespace std;// end参数可以用nums.size()代替，但是这里为了方便理解所以加上
void permute(vector<int>& nums, int start, int end, vector<vector<int>>& result) {if (start == end) {result.push_back(nums);//到达叶子节点，记录结果return;}for (int i = start; i <= end; i++) {swap(nums[start], nums[i]);// 将第i个元素和第start个元素交换位置，固定第start个元素permute(nums, start + 1, end, result);// 递归调用，固定[start+1, end]这个区间的元素swap(nums[start], nums[i]); // 回溯恢复原来的数组顺序，用于下一次循环}
}int main() {vector<int> nums = { 1, 2, 3 };vector<vector<int>> result;permute(nums, 0, nums.size() - 1, result);for (auto& v : result) {for (int num : v) {cout << num << " ";}cout << endl;}return 0;
}

四、有重复元素时的解法：STL库函数实现

题目说明：
当 nums有重复元素时，如果采用回溯法，nums有重复元素就用hash记录被选择的数字，如果已经被选择过就跳过，这当然可以解决问题，不过我们有更优雅的解法，那就是STL中的库函数，这里写出来是因为面试官可能不让你直接调库函数；

解题思路：
两个函数next_permutation和prev_permutation，分别用于生成下一个排列和上一个排列。

next_permutation函数的工作原理是找到从右到左第一个升序对（即nums[i] < nums[i+1]），然后找到这个升序对右边第一个大于它的元素（即nums[j] > nums[i]），交换这两个元素的位置，最后将升序对右边的元素反转。这样就得到了下一个排列。

prev_permutation函数的工作原理类似，只是它是找升序对，然后找到这个升序对左边第一个小于它的元素，交换这两个元素的位置，最后将升序对左边的元素反转。这样就得到了上一个排列。

在main函数中，首先调用prev_permutation函数生成所有的上一个排列，然后调用next_permutation函数生成所有的下一个排列。这样就可以得到所有的排列，而且由于next_permutation函数会跳过所有重复的排列，所以可以避免重复。

原理很详细的一篇文章：https://blog.csdn.net/myRealization/article/details/104803834

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;bool next_permutation(vector<int>& nums) {int i = nums.size() - 2;while (i >= 0 && nums[i] >= nums[i + 1]) --i;if (i == -1) return false;int j = nums.size() - 1;while (nums[j] <= nums[i]) --j;swap(nums[i], nums[j]);reverse(nums.begin() + i + 1, nums.end());return true;
}bool prev_permutation(vector<int>& nums) {int i = 0;while (i < nums.size() - 1 && nums[i] <= nums[i + 1]) ++i;if (i == nums.size() - 1) return false;int j = nums.size() - 1;while (nums[j] >= nums[i]) --j;swap(nums[i], nums[j]);reverse(nums.begin(), nums.begin() + i + 1);return true;
}int main() {vector<int> nums = {1, 2, 3};vector<vector<int>> result;while (prev_permutation(nums)){};//O(n)时间复杂度，而sort是nlog n do {result.push_back(nums);} while (next_permutation(nums));for(auto i: result){for(auto j : i)cout << j << " ";cout << endl;}return 0;
}

如此时间复杂度就是O（n），空间复杂度O（1），如果这样面试还是过不了的话，那就不是你的问题了…

迭代器版本实现

template<typename Iterator>
bool myNextPermutation(Iterator start, Iterator end) { //[start,end)Iterator cur = end - 1, pre = cur - 1; //pre指向partitionNumber while (cur > start && *pre >= *cur) --cur, --pre; //从右到左进行扫描，发现第一个违背非递减趋势的数字if (cur <= start) return false; //整个排列逆序， 不存在更大的排列 //从右到左进行扫描，发现第一个比partitionNumber大的数for (cur = end - 1; *cur <= *pre; --cur); //cur指向changeNumber  std::iter_swap(pre, cur);std::reverse(pre + 1, end); //将尾部的逆序变成正序 return true; 
}template<typename Iterator>
bool myPrevPermutation(Iterator start, Iterator end) { //[start,end)Iterator cur = end - 1, pre = cur - 1; //pre指向partitionNumber while (cur > start && *pre <= *cur) --cur, --pre; //从右到左进行扫描，发现第一个违背非递增趋势的数字if (cur <= start) return false; //整个排列逆序， 不存在更小的排列 //从右到左进行扫描，发现第一个比partitionNumber小的数for (cur = end - 1; *cur >= *pre; --cur); //cur指向changeNumber  std::iter_swap(pre, cur);std::reverse(pre + 1, end); //将尾部的逆序变成正序 return true; 
}