Safe Or Unsafe

青旅半醒 2022-03-22 07:40 150阅读 0赞

### 题目描述： ###

Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容–哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？  
Input  
输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！  
Output  
如果字符串的编码值小于等于给定的值则输出yes，否则输出no。  
Sample Input  
2  
12  
helloworld  
66  
ithinkyoucandoit  
Sample Output  
no  
题意：给你一个字符串如：12 helloworld统计出其中d:1个，e：1个，h:1个，l：3个，o：2个，r:1个，w：1个,然后用一个数组保存起来a\[7\]=\{1,1,1,1,1,2,3\};然后就是用哈夫曼树的思想求出新建的非叶子节点的权值之和：sum与12相比较如果sum小于等于12的话就输出yes否则输出no，此案例求出的sum=27；所以输出no。

##### 分析： #####

基本的思路是建造一颗赫夫曼树。然后在求出sum的值。  
在以下代码中，没有采用链表来建造一颗树。而是利用一个结点数组。这种方法其实可以用于很多情况，我们在建造一颗二叉树的时候也是可以用这种方法的。  
我在建造树的时候，同时利用SUM将权值相加。不过包括了叶子结点。所以需要判断的时候需要减去。  
参考博客：[https://www.cnblogs.com/jiangjing/archive/2013/01/16/2862657.html][https_www.cnblogs.com_jiangjing_archive_2013_01_16_2862657.html]

#include"stdio.h"
    #include"string.h"
    //树的结点的基本信息 
    typedef struct NODE
    {
        int value;
        int left;//保存这个结点的左子结点所在的下标位置
        int right;//保存这个结点的右子结点所在的下标位置 
        int mark;//标识当前结点是否已被使用 
        int parent;//这个结点的父结点的所在的下标位置 
    }NODE;
    //这个函数时求字符频率的函数，返回值为多少个不同的字符
    int Frequency(int frequency[],char word[])
    {
        int i,len,count;
        len=strlen(word);
        for(i=0;i<len;i++)
            {
                frequency[word[i]-'a']++;
            }
        for(i=0,count=0;i<26;i++)
            if(frequency[i]!=0)
                count++;
        return count;
    }
    //正式建树
    int CreateBiTree(NODE node[],int frequency[],int count)
    {
        int min1,min2,sum,S=0;
        int i,j,k=0;
        for(i=0;i<26;i++)
            if(frequency[i]!=0)
               node[k++].value=frequency[i];
    
        while(1)
        {
            min1=99999;min2=99999;
            //找到当前未被使用的最小的和第二次的结点下标 
            for(i=0;i<count;i++)
            {
                if(node[i].mark==0&&(min1==99999||node[min1].value>node[i].value))
                {
    
                    min1=i;
    
                }
            }
    
            if(min1!=99999)
            {
                node[min1].mark=1;//将找到的结点的mark赋值为1，表已被使用
    
            }
            for(i=0;i<count;i++)
            {
                if(node[i].mark==0&&(min2==99999||node[min2].value>node[i].value))
                {
                    min2=i;
    
                }
            }
            if(min2!=99999)
            {
                node[min2].mark=1;//将找到的结点的mark赋值为1，表已被使用
    
            }
    
            if(min1==99999||min2==99999)//如果只找到一个，
             // 就表示树已建造完成（注意，下的一个其实未加入树中，不过在此题中不需要考虑。）
                break;
          
            sum=node[min1].value+node[min2].value;//将两个最小的值相加
            //下面的是将新的结点加入到node数组中 同时对左右结点和父节点的下标位置的更新
            node[count++].value=sum;
            node[min1].parent=count-1;
            node[min2].parent=count-1;
            node[count-1].left=min1;
            node[count-1].right=min2;
    
    
    
            S+=sum;//权值相加 
    
        }
        //注意要把剩下的那个结点也加上
        if(min1!=99999)
            S+=node[min1].value;
        else
            S+=node[min2].value;
        return S;
    }
    int main()
    {
        NODE node[10000];
        int N,i,S,sum;
        int MAX,count;
        char word[10000];
        int frequency[27];
        while(~scanf("%d",&N))
        {
            while(N--)
            {
                scanf("%d",&MAX);
                scanf("%s",word);
                for(i=0;i<10000;i++)
                {
                    node[i].value=-1;
                    node[i].left=-1;
                    node[i].right=-1;
                    node[i].mark=0;
                    node[i].parent=-1;
                }
                memset(frequency,0,sizeof(frequency));
                count=Frequency(frequency,word);
               //这里是考虑只有一个字符的时候的情况
               //如 5 nnnnn 是输出yes
                if(count==1)
                {
                    for(i=0;i<26;i++)
                        if(frequency[i]!=0)
                           sum=frequency[i];
                    if(sum>MAX)
                        printf("no\n");
                    else
                        printf("yes\n");
                    continue;
                }
    
                S=CreateBiTree(node,frequency,count);
                for(i=0,sum=0;i<26;i++)//将所有叶子结点的值相加 
                    if(frequency[i]!=0)
                        sum+=frequency[i];
                S-=sum;//减去sum并进行判断
                if(S<=MAX)
                    printf("yes\n");
                else
                    printf("no\n");
    
            }
        }
    }

[https_www.cnblogs.com_jiangjing_archive_2013_01_16_2862657.html]: https://www.cnblogs.com/jiangjing/archive/2013/01/16/2862657.html