Chapter06-Phylogenetic Trees Inherited（POJ 2414）（状态压缩DP）
浏览数：161 /
时间：2015年06月09日
编写一个函数，删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。 格式说明： 字符串只包含字母，不可能为空串，不包含空格，单词只由小写英文字母组成，输入的字符串长度不会超过20个char 。
算法思路:
（1）定义一个长度为26的整型数组
下标从0-25分别表示a-z这26个小写字母，用来保存字符串中各个字符出现的次数
（因为‘a’-‘a’=0，‘z’-‘a’=25刚好与数组的下标对应）
“abcdddeeffffxxyz”各个字符出现的次数如下图所示：
（2）求出数组中的最小值即字符串中字符出现的最小次数min（找出数组中第一个不为零的值，从前往后去比较大小，找出最小值）。
（3）定义一个空字符数组用来保存新字符串（将出现次数大于min的字符按照顺序存入空数组中，并在末尾加上字符串结束标志‘\0‘）。
（4）算法结束。
#include <stdio.h>
#include <string.h>
#include <malloc.h>
char * change(char *str){
int alpha[26]={0}; //定义并初始化长度为26的字符数组，用来保存各个小写字母出现的次数
int len = strlen(str); //字符串的长度
for(int i = 0 ; i< len ; i++){ //遍历字符串中的字符
int index = str[i]-‘a‘; //字符在alpha数组中的下标
alpha[index]++; //次数+1
}
//经过以上代码，已经将各个小写字母出现的次数保存在alpha数组中
int min = 0;
for(i = 0 ; i < len ; i++){ //求出数组中第一个不为零的值
if(alpha[i]!=0)
min = alpha[i];
}
for(i = 0 ; i < 26 ; i++){ //求出alpha数组中最小元素即小写字母中出现的最小次数
if(alpha[i]!=0 && alpha[i]<min){
min = alpha[i];
}
}
char * newStr = (char *)malloc(sizeof(char) * len); //用来保存改变后的字符串
char *p = str;
int num=0;
while(*p){ //遍历字符串，将出现次数大于min的字符串保存到newStr中
int index2 = *p-‘a‘;
if(alpha[index2]!=min){
newStr[num] = *p;
num++;
}
p++;
}
newStr[num]=‘\0‘;
return newStr;
}
void main(){
char str[100]; //保存输入的字符串
gets(str); //从键盘输入字符串
char *res = change(str);
puts(res);
free(res);
}
Chapter06-Phylogenetic Trees Inherited（POJ 2414）（状态压缩DP）,古老的榕树,5-wow.com
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
