LeetCodeDay52 —— 全排列★★★

46. 全排列 Permutations

描述
  • Given a collection of distinct integers, return all possible permutations.
示例
  Input: [1,2,3]
  Output:
  [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
  ]
思路:
  1. 递归全排列就是从第一个数字起每个数分别与它后面的数字交换。
  2. 去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。(交换的时候判断下是否已出现即可)
  3. 非递归全排列就是由后向前找替换数和替换点,然后由后向前找第一个比替换数大的数与替换数交换,最后颠倒替换点后的所有数据。(证明)
    (参考)
// 递归版本
class Solution_46_01 {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> ret;
    _permute(0, nums.size() - 1, nums, ret);
    return ret;
  }
  void _permute(int k, int size, vector<int>& nums, vector<vector<int>>& ret) {
    if (k == size) {
      ret.push_back(nums);
      return;
    }
    for (int i = k; i <= size; ++i) {
      swapNum(nums, k, i);
      _permute(k + 1, size, nums, ret);
      swapNum(nums, i, k);
    }
  }
  void swapNum(vector<int>& nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
  }
};

// 非递归版本,基于Stl的next_permutation
class Solution_46_02 {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    if (nums.empty()) return {};
    vector<vector<int>> ret;
    std::sort(nums.begin(), nums.end());
    ret.push_back(nums);
    while (next_permutation<vector<int>::iterator>(nums.begin(), nums.end())) {
      ret.push_back(nums);
    }
    return ret;
  }
  template <class BidirIt>
  bool next_permutation(BidirIt first, BidirIt last) {
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
    while (true) {
      BidirIt i1, i2;
      i1 = i;
      if (*--i < *i1) {
        i2 = last;
        while (!(*i < *--i2))
          ;
        std::iter_swap(i, i2);
        std::reverse(i1, last);
        return true;
      }
      if (i == first) {
        std::reverse(first, last);
        return false;
      }
    }
  }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,951评论 2 36
  • 本文内容为练习LeetCode题目时的解题思路和不同算法的记录,实现语言为C++,代码保存在Github,均已在L...
    SK木眠阅读 1,021评论 0 0
  • 我希望有个如你一般的人。如这山间清晨一般明亮清爽的人,如奔赴古城道路上阳光一般的人,温暖而不炙热,覆盖我所有肌肤。...
    Mr绍君阅读 510评论 2 4
  • 幼时便邂逅《红楼》,虽懵懂,仍为那座“天上人间诸景备”的大观园心动不已;及至年岁渐长,方领略《红楼》之美。以我浅薄...
    浅蘸烟芜阅读 345评论 0 2
  • 月初女儿不上学,我刚开始心慌,害怕,当我有意识把自己抽离开后,我发现我竟能够这样的安稳,不在心慌和恐...
    红红456阅读 272评论 4 3