专栏首页刷题笔记46. 全排列【回溯算法】

46. 全排列【回溯算法】

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

写好一个交换

然后开始谈思路,就是n从0开始递增,算第n个位置存的数,确定好之后存num进结果v

之后再swap原路恢复,进入下一种情况。

进行回溯

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> v;
        back(nums,v,0);
        return v;
    }
    void swap(int &a,int &b){
        int t=a;
        a=b;
        b=t;
    }
    void back(vector<int>& nums ,vector<vector<int>>& v,int  n){
        if(n==nums.size())v.push_back(nums);
        for(int i=n;i<nums.size();i++){
            swap(nums[i],nums[n]);
            back(nums,v,n+1);
            swap(nums[i],nums[n]);
        }
    }
};

LeetCode排名第一的代码

使用了栈和状态存储的bool值

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> ret;
		int len = nums.size();
		if (len == 0) {
			return ret;
		}
		bool visit[len] = {false};
		stack<int> s;
		dev(len, 0, ret, nums, visit, s);
		return ret;
	}

	void dev(int len, int current, vector<vector<int>>& ret, vector<int>& nums, bool *visit, stack<int> &s) {
		vector<int> temp;
		if (current == len) {
			int* end = &s.top() + 1;
			int* begin = end - s.size();
			vector<int> temp(begin, end);
			ret.push_back(temp);
            return;
		}
		for (int i = 0; i < len; i++) {
			if (!visit[i]) {
				s.push(nums[i]);
				visit[i] = true;
				dev(len, current + 1, ret, nums, visit, s);
				s.pop();
				visit[i] = false;
			}
		}
	}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【并查集】2-4 朋友圈 (25 分)

    某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的...

    韩旭051
  • 1045 快速排序 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【2019秋PAT乙级真题】7-3 缘分数 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • Day23-排序-快排&堆排&归并排序

    右指针--,直到找到比基准值小的元素,将左右指针指向的元素进行交换;

    BUPTrenyi
  • LeetCode题解-Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    卡尔曼和玻尔兹曼谁曼
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • Dimple在左耳听风ARTS打卡(第九期)

    所谓ARTS: 每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algor...

    程序员小跃
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 1022 D进制的A+B (20 分)

    输入两个非负 10 进制整数 A 和 B (≤230−1),输出 A+B 的 D (1<D≤10)进制数。

    可爱见见

扫码关注云+社区

领取腾讯云代金券