輸入:一個序列s,該序列里面可能會有同樣的字符,不一定有序 和 一個整數k
輸出:該序列往后計算第k個序列,所有序列是以字典序排序的
如果會有序搜索的童鞋自然而然能立刻做出來第一個題目,可是第二個題目在s較長的情況下,卻需要用模擬而不是搜索...
大家都知道STL里面有個泛函模版, prev_permutation和next_permutation,用法也很簡單,實現的就是題目2的功能...
但是算法最好得靠自己想出來,自己想出來的才是自己的,碰到新的問題才能產生思想的火花...
廢話少說,題目1的解法就是深搜,不過需要加上一個bool數組標記和一個函數確定不同字符之間的大小(有可能這個大小還不是Ascii碼就能決定的),
大致描述下搜索過程,比如輸入序列是12345,那么我搜索的過程大致是第一層按順序選取1-5,進入第二層的時候也是按順序選取1-5,
以此類推,但是每一層里面都只能選前面的層次沒有選過的數,而且因為有重復字符,算法還必須保證每一層里面按順序選取的字符必須是升序的,
熟悉順序搜索和回溯的同學,很自然就會產生這樣的想法...
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個泛型模版函數,算法的大致過程是想辦法從當前序列進入下一個剛好比其大或者剛好比其小的序列...很自然我們想到要把序列后面大的字符交和前面小的字符交換就會使序列變大,為了使其剛好變大,可以把交換后的字符從交換位置起至最后都排序一下,現在的問題是我們如何選取2個字符交換...正確的想法是,我們從最后面開始往前面看,尋找一個最長的遞增序列,找到之后,我們只需要選取遞增序列前面的那個字符chBefore和遞增序列里面的一個最小的比chBefore大的字符交換即可...交換之后,將新的遞增序列排序一下即可...
為什么這樣做了,因為從后往前看的遞增序列,是不能交換2個字符讓當前序列變大的,所以必須選取最長遞增序列前面的那個字符交換...
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;
}