60.Permutation Sequence-Leetcode

基础回顾

String

头文件中必须包括<string>

string的声明初始化

    string s1 = "abcdefg";  //初始化方式1  
    string s2("abcdefg");   //初始化方式2  
    string s3 = s2;         //通过拷贝构造函数 初始化s3  
    string s4(7,'s');       //初始化7个s的字符串  

遍历

1.str[i]
2.迭代器: 
    for(string::iterator it = s1.begin(); it!= s1.end(); it++)  
    {  
        cout << *it << " ";  
    }
3.str.at[i]//此方式可以在越界时抛出异常

string与char*

//字符指针和字符串的转换  
void strConvert()  
{  
    cout << "字符指针和字符串的转换:"  <<endl;  
    string s1 = "abcdefg";  //初始化字符串  
  
    cout << "string转换为char*:"  <<endl;  
    //string转换为char*  
    cout << s1.c_str() <<endl;  //s1.c_str()即为s1的char *形式  
  
    cout << "char*获取string内容:"  <<endl;  
    //char*获取string内容  
    char buf[64] = {0};  
    s1.copy(buf, 7);//复制7个元素  
    cout << buf <<endl;  
} 

字符串连接

s1.append(s2);
s1+=s2;

string与int转化(注意stringstream)

//int与char*
char* n=a+'0'
itoa(num, str, 10); //stdlib.h中的函数
//int to string,其余类型之间转换也可参考类似的方法stringstream可以stringstream可以吞下任何类型,根据实际需要吐出不同的类型。
stringstream stream;//<sstream>
stream<<n;
stream.str();//stream>>str;
//string to int
n = atoi(str.c_str())

我的算法(受nextPermutation影响大,算法效率低)

nextPermutation算法思想:

https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

#右数第一个非降序序列的前一个元素下标pivot
#右数第一个大于s[pivot]的值的下标设为successor
#交换successor与pivot对应的元素
#将pivot右边的所有元素逆序
class Solution {
    //初始化s,后根据k进行循环限制,每次都取下一个排列数(根据NextPermutation的算法):效率很低
public:
    string getPermutation(int n, int k) {
        int i,j=0;
        for(i=1;i<=n;i++)
        {
            j=j*10+i;
        }
        n=j;
        stringstream ss;
        string begin;
        ss<<n;
        begin=ss.str();
        if(n==1 ||k==1)
        {
            return begin;
        }
        
        for(i=2;i<=k;i++)
        {
            begin=NextPermutation(begin);
        }
        
        return begin;
    }
     string NextPermutation(string s){
         int len=s.length();
         int i=len-1;
         while(s[i]<=s[i-1] && i-1>=0)
         {
             i-=1;
         }
         int pivot=i-1;     #右数第一个非降序序列的前一个元素下标pivot
         int successor;
         for(i=len-1;i>pivot;i--)
         {
             if(s[i]>s[pivot])
             {
                 successor=i;
                 break;    #右数第一个大于s[pivot]的值的下标
             }
         }
         char middle=s[successor];
         s[successor]=s[pivot];
         s[pivot]=middle;  #交换successor与pivot对应的元素
         int j;
         for (i=pivot+1,j=len-1;i<j;i++,j--)
         {                        #将pivot右边的所有元素逆序
            middle=s[i];
            s[i]=s[j];
            s[j]=middle;
         }

        return s;
     }
};

最优解法

http://blog.csdn.net/cinderella_niu/article/details/42927119
主要思想是按阶乘表示可能的组合种类:
1,2,3,… , n构建的全排列中,返回第k个排列。
题目告诉我们:对于n个数可以有n!种排列;那么n-1个数就有(n-1)!种排列。
那么对于n位数来说,如果除去最高位不看,后面的n-1位就有 (n-1)!种排列。
所以,还是对于n位数来说,每一个不同的最高位数,后面可以拼接(n-1)!种排列。
所以你就可以看成是按照每组(n-1)!个这样分组。
利用 k/(n-1)! 可以取得最高位在数列中的index。这样第k个排列的最高位就能从数列中的index位取得,此时还要把这个数从数列中删除。
然后,新的k就可以有k%(n-1)!获得。循环n次即可。

class Solution {
public:
    string getPermutation(int n, int k) {
        string ret;
        vector<int> factorial(n,1);     #计算阶乘
        vector<char> num(n,1);
        
        for(int i=1; i<n; i++) 
            factorial[i] = factorial[i-1]*i;
        
        for(int i=0; i<n; i++)
            num[i] = (i+1)+'0';
        
        k--;
        for(int i=n; i>=1; i--) {
            int j = k/factorial[i-1];
            k %= factorial[i-1];
            ret.push_back(num[j]);
            num.erase(num.begin()+j); //删除第j个元素,同时调整元素排序关系
        }
        
        return ret;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,539评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,911评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,337评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,723评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,795评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,762评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,742评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,508评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,954评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,104评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,736评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2 352