Chapter06-Phylogenetic Trees Inherited(POJ 2414)(状态压缩DP)

编写一个函数,删除字符串中出现次数最少的字符,若多个字符出现次数一样,则都删除。输出删除这些单词后的字符串,字符串中其它字符保持原来的顺序。 格式说明: 字符串只包含字母,不可能为空串,不包含空格,单词只由小写英文字母组成,输入的字符串长度不会超过20char 


算法思路:

(1)定义一个长度为26的整型数组

下标从0-25分别表示a-z26个小写字母,用来保存字符串中各个字符出现的次数

(因为‘a’-‘a’=0,‘z’-‘a’=25刚好与数组的下标对应)

“abcdddeeffffxxyz”各个字符出现的次数如下图所示:

Chapter06-Phylogenetic Trees Inherited(POJ 2414)(状态压缩DP)

(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),布布扣,bubuko.com

Chapter06-Phylogenetic Trees Inherited(POJ 2414)(状态压缩DP)

上一篇:css样式高级技巧-选择器


下一篇:[转]jQuery实现图片轮播效果,jQuery实现焦点新闻