题目描述：
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 'a'、b?个字母 'b'、c 个字母 'c' 。
s 中只含有 'a'、'b' 、'c' 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例：
输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。
输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。
输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。
解答描述：
因为题目要求找出一个尽可能长的快乐字符串，考虑贪心策略。
贪心策略如下：
1）因为快乐字符串的要求是不能有三个及以上的连续相同字符，最多两个连续，那就每次选择当前数量最多的来连续。
2）为了将连续的字符隔开，需要另一种字符作为隔开符，选择当前数量第二多的来隔开。?
3）当没有可用于隔开的字符时，说明此时已经是最长的快乐字符串了，结束贪心，返回结果。
?注意：需要额外记录每次用的隔开符，因为有可能隔开符对应的字符数目在下轮是最多的，此时，它最多还只能再放一个，而不是两个。eg:4 4 3。
代码：
typedef struct {
int num;//a,b,c的数值
char cc;//对应字符'a','b','c'
}mystruct;
int max(int x,int y)
{
return x>y?x:y;
}
int comp(const void*a,const void*b)//比较函数
{
return ((mystruct*)b)->num - ((mystruct*)a)->num;
}
char * longestDiverseString(int a, int b, int c){
char *ans=(char*)malloc(sizeof(char) * (a+b+c+1));
mystruct st[3];//用结构表示字符
st[0].num=a; st[0].cc='a';
st[1].num=b; st[1].cc='b';
st[2].num=c; st[2].cc='c';
int k=0;
char prev='0';
while(1)
{
qsort(st,3,sizeof(st[0]),comp);
int round=(prev==st[0].cc)?1:0;//如果当前数目最多的之前出现过，现在只能再放一个
while(st[0].num>0 && round<2)//先放当前数目最多的额
{
ans[k++]=st[0].cc;
st[0].num--;
round++;
}
if(st[1].num>0)//当还有隔开符时，用一个隔开
{
ans[k++]=st[1].cc;
st[1].num--;
prev=st[1].cc;//记录当前字符串的最后一个字符
}
else
{
break;
}
}
ans[k]='\0';
return ans;
}
|