题解 | #牛群排队#

牛群排队

https://www.nowcoder.com/practice/8d8ae3937cd5466eb330ca484ca5ed80

考察的知识点:回溯,递归;

解答方法分析:

  1. 对给定的数组进行排序,以确保生成的排列是按照递增顺序排列的。
  2. 定义一个全局变量res,用于保存生成的排列结果。
  3. 定义一个backTracking函数,该函数负责生成排列。它接受两个参数:index表示当前生成排列的位置,list用于存储已经选择的数字。
  4. 在backTracking函数中,使用循环遍历数组中的每个数字。如果该数字已经被选择过,则跳过该数字的选择。
  5. 如果该数字尚未选择,则将其加入list中,并判断当前list的大小是否等于数组的大小。如果相等,说明已经生成了一个完整的排列,将list的副本加入到res中,否则,递归调用backTracking函数,继续生成下一个数字的选择。
  6. 在递归调用结束后,需要将list的最后一个数字移除,以继续下一轮的选择。
  7. 最后,将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();
        }
    }
};

全部评论

相关推荐

屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务