輸入:一個(gè)序列s,該序列里面可能會(huì)有同樣的字符,不一定有序 和 一個(gè)整數(shù)k
輸出:該序列往后計(jì)算第k個(gè)序列,所有序列是以字典序排序的
如果會(huì)有序搜索的童鞋自然而然能立刻做出來(lái)第一個(gè)題目,可是第二個(gè)題目在s較長(zhǎng)的情況下,卻需要用模擬而不是搜索...
大家都知道STL里面有個(gè)泛函模版, prev_permutation和next_permutation,用法也很簡(jiǎn)單,實(shí)現(xiàn)的就是題目2的功能...
但是算法最好得靠自己想出來(lái),自己想出來(lái)的才是自己的,碰到新的問(wèn)題才能產(chǎn)生思想的火花...
廢話少說(shuō),題目1的解法就是深搜,不過(guò)需要加上一個(gè)bool數(shù)組標(biāo)記和一個(gè)函數(shù)確定不同字符之間的大小(有可能這個(gè)大小還不是Ascii碼就能決定的),
大致描述下搜索過(guò)程,比如輸入序列是12345,那么我搜索的過(guò)程大致是第一層按順序選取1-5,進(jìn)入第二層的時(shí)候也是按順序選取1-5,
以此類推,但是每一層里面都只能選前面的層次沒(méi)有選過(guò)的數(shù),而且因?yàn)橛兄貜?fù)字符,算法還必須保證每一層里面按順序選取的字符必須是升序的,
熟悉順序搜索和回溯的同學(xué),很自然就會(huì)產(chǎn)生這樣的想法...
POJ - 1256的代碼如下:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <algorithm>
#define MAX (13 + 10)
using namespace std;
bool bUsed[MAX];
char szAns[MAX];
char szInput[MAX];
bool CmpChar(char chOne, char chTwo)
{
if (abs(chOne - chTwo) != 'a' - 'A')
{
return tolower(chOne) - tolower(chTwo) < 0;
}
return chOne - chTwo < 0;
}
bool Greater(char chOne, char chTwo)
{
if (abs(chOne - chTwo) != 'a' - 'A')
{
return tolower(chOne) - tolower(chTwo) > 0;
}
return chOne - chTwo > 0;
}
void Gen(int nDepth, int nLen)
{
if (nDepth == nLen)
{
szAns[nLen] = '\0';
printf("%s\n", szAns);
return;
}
char chLast = '\0';
for (int i = 0; i < nLen; ++i)
{
if (!bUsed[i] && Greater(szInput[i], chLast))
{
bUsed[i] = true;
szAns[nDepth] = szInput[i];
Gen(nDepth + 1, nLen);
bUsed[i] = false;
chLast = szInput[i];
}
}
}
int main()
{
int nCases;
scanf("%d", &nCases);
while (nCases--)
{
scanf("%s", szInput);
int nLen = strlen(szInput);
sort(szInput, szInput + nLen, CmpChar);
Gen(0, nLen);
}
return 0;
}
題目2的解法是模擬,功能類似與STL的那2個(gè)泛型模版函數(shù),算法的大致過(guò)程是想辦法從當(dāng)前序列進(jìn)入下一個(gè)剛好比其大或者剛好比其小的序列...很自然我們想到要把序列后面大的字符交和前面小的字符交換就會(huì)使序列變大,為了使其剛好變大,可以把交換后的字符從交換位置起至最后都排序一下,現(xiàn)在的問(wèn)題是我們?nèi)绾芜x取2個(gè)字符交換...正確的想法是,我們從最后面開(kāi)始往前面看,尋找一個(gè)最長(zhǎng)的遞增序列,找到之后,我們只需要選取遞增序列前面的那個(gè)字符chBefore和遞增序列里面的一個(gè)最小的比chBefore大的字符交換即可...交換之后,將新的遞增序列排序一下即可...
為什么這樣做了,因?yàn)閺暮笸翱吹倪f增序列,是不能交換2個(gè)字符讓當(dāng)前序列變大的,所以必須選取最長(zhǎng)遞增序列前面的那個(gè)字符交換...
POJ百練 - 1833 的代碼如下:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX (1024 + 10)
using namespace std;
int nInput[MAX];
void GetNext(int* nInput, int nLen)
{
int i = nLen - 2;
while (i >= 0)
{
if (nInput[i] >= nInput[i + 1])
{
--i;
}
else
{
int k = i + 1;
for (int j = nLen - 1; j > i; --j)
{
if (nInput[j] > nInput[i] && nInput[j] < nInput[k])
{
k = j;
}
}
swap(nInput[i], nInput[k]);
sort(nInput + i + 1, nInput + nLen);
return;
}
}
sort(nInput, nInput + nLen);
}
int main()
{
int nCases;
scanf("%d", &nCases);
while (nCases--)
{
int nLen;
int nK;
scanf("%d%d", &nLen, &nK);
for (int i = 0; i < nLen; ++i)
{
scanf("%d", &nInput[i]);
}
for (int i = 0; i < nK; ++i)
{
GetNext(nInput, nLen);
}
for (int i = 0; i < nLen; ++i)
{
printf("%d%s", nInput[i], i == nLen - 1 ? "\n" : " ");
}
}
return 0;
}