题解 | #牛群排队#

牛群排队

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();
        }
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-25 17:55
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
写不来代码的小黑:这么小的城市能有做it的公司也不容易
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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