题解 | #牛群排队#
牛群排队
https://www.nowcoder.com/practice/8d8ae3937cd5466eb330ca484ca5ed80
考察的知识点:回溯,递归;
解答方法分析:
- 对给定的数组进行排序,以确保生成的排列是按照递增顺序排列的。
- 定义一个全局变量res,用于保存生成的排列结果。
- 定义一个backTracking函数,该函数负责生成排列。它接受两个参数:index表示当前生成排列的位置,list用于存储已经选择的数字。
- 在backTracking函数中,使用循环遍历数组中的每个数字。如果该数字已经被选择过,则跳过该数字的选择。
- 如果该数字尚未选择,则将其加入list中,并判断当前list的大小是否等于数组的大小。如果相等,说明已经生成了一个完整的排列,将list的副本加入到res中,否则,递归调用backTracking函数,继续生成下一个数字的选择。
- 在递归调用结束后,需要将list的最后一个数字移除,以继续下一轮的选择。
- 最后,将res中的结果转换成二维数组形式,返回给调用者。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: vector<vector<int>> res; vector<int> nums; vector<vector<int>> cow_permute(vector<int> num) { sort(num.begin(), num.end()); nums = num; backTracking(0, vector<int>()); vector<vector<int>> ans(res.size(), vector<int>(nums.size())); for (int i = 0; i < res.size(); i++) { for (int j = 0; j < nums.size(); j++) { ans[i][j] = res[i][j]; } } return ans; } void backTracking(int index, vector<int> list) { for (int i = nums.size() - 1; i >= 0; i--) { if (find(list.begin(), list.end(), nums[i]) != list.end()) { continue; } list.push_back(nums[i]); if (list.size() == nums.size()) { res.push_back(list); } else { backTracking(index + 1, list); } list.pop_back(); } } };