一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 743|回复: 7
收起左侧

[算法题] 一道permutation的题求教~~~~

[复制链接] |试试Instant~ |关注本帖
JEM 发表于 2016-2-12 10:38:21 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 JEM 于 2016-2-12 12:46 编辑

小弟最近在转cs刷leetcode,碰到permutation这题了。。 (不是permutation 2 ,仅仅只是1 )原题是给你一串int(没有重复),找出它的所有全排列。 例如给出 1,2,3, 就要返回(1,2,3),(1,3,2),(2,1,3),(2,3,1),
(3,1,2),(3,2,1)


recursive看得有点懵逼。。。 实际上我最怕碰到loop里面套recursive的了,根本不知道它在干嘛啊。

先贴上别人的代码吧:(c++)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        create(nums,res,0);
        return res;
    }

    void create(vector<int>& nums,vector<vector<int>> &res,int n)
    {
        if(n==nums.size()-1)
            res.push_back(nums);
        else
        {
            for(int i=n;i<nums.size();i++)
            {
                swap(nums,nums[n]);
                create(nums,res,n+1);
                swap(nums,nums[n]);
            }
        }
    }

    void swap(int &a,int &b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
};

有哪位大神可以帮忙解释一下recursive在干嘛吗。。 还有能顺便说一下碰到此类问题应该如何写递归吗,真心对这种题很无语啊。。


luofeidream 发表于 2016-2-12 10:44:19 | 显示全部楼层
代码写错了吧,swap里面参数应该是nums[i]..
回复 支持 反对

使用道具 举报

 楼主| JEM 发表于 2016-2-12 12:36:18 | 显示全部楼层
luofeidream 发表于 2016-2-12 10:44
代码写错了吧,swap里面参数应该是nums..

哦哦对的。。。 应该是粘贴的时候出了点问题,已经改正了,谢谢提醒!
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-2-12 12:40:59 | 显示全部楼层
JEM 发表于 2016-2-12 12:36
哦哦对的。。。 应该是粘贴的时候出了点问题,已经改正了,谢谢提醒!

这个recursive的意思是每次换一个“头”,然后递归的把剩余的所有元素的permutation加到这个“头”后面,比如1 2 3,先产生1 2 3, 然后 2 3里面把“头”换成3,产生1 3 2, 接着把1 换成2产生2 1 3 2 3 1等等……
回复 支持 反对

使用道具 举报

 楼主| JEM 发表于 2016-2-12 15:34:22 | 显示全部楼层
luofeidream 发表于 2016-2-12 12:40
这个recursive的意思是每次换一个“头”,然后递归的把剩余的所有元素的permutation加到这个“头”后面, ...

能不能麻烦你讲一下两个swap放在那是在干嘛啊? 还有就是recursive为什么要放在两个swap中间?
回复 支持 反对

使用道具 举报

excellent5 发表于 2016-2-12 16:15:46 | 显示全部楼层
JEM 发表于 2016-2-12 15:34
能不能麻烦你讲一下两个swap放在那是在干嘛啊? 还有就是recursive为什么要放在两个swap中间?

首先想清楚create这个方法是算出所有nums从第n位到最后一位的全排列。
在create方法中,我们拿第一层递归n=0,以及i=1的情况举例,它的做法是先把1和2换位,然后递归求出1,3的全排列,然后把1换回原位好在下个循环和3换位。
回复 支持 反对

使用道具 举报

 楼主| JEM 发表于 2016-2-13 11:13:31 | 显示全部楼层
excellent5 发表于 2016-2-12 16:15
首先想清楚create这个方法是算出所有nums从第n位到最后一位的全排列。
在create方法中,我们拿第一层递 ...

这样说的话可不可以这么理解,就拿第一层递归的那一个for loop来说,先是1和自己换,求后面的全排列,然后1和2换,2作为第一个数,求一次全排列,然后求完换回来,然后1和3换,3作为第一个数,求一次全排列。所以这样1,2,3作为第一个数的所有全排列就都求出来了。 是这样理解吗?
回复 支持 反对

使用道具 举报

excellent5 发表于 2016-2-13 13:17:01 | 显示全部楼层
JEM 发表于 2016-2-13 11:13
这样说的话可不可以这么理解,就拿第一层递归的那一个for loop来说,先是1和自己换,求后面的全排列,然 ...

嗯,我认为就是这样的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表