百度笔试题之字符串包含

判断字符串 b 的所有字符是否都再字符串 a 中出现过，a,b都是可能包含汉字的字符串。b中重复出现的汉字，那么a中也要至少出现相同的次数。

汉字使用gbk编码（简单的所，用两个字节表示一个汉字，高字节最高位为1的代表汉字，低字节最高位可以不为1）。

int is_include(char *a  ,  char *b)

返回0 表示没有都出现过，返回1表示都出现过。

 

我这人根据个人理解把题目变换为字符也至少出现同样的次数...

 

首先我想到的把汉字做成hash.hash的我明天写出...今天暂时就是用链表搞的...字符要是只有可以预见的字符比如a-z and A-Z的话,可以直接

char ch = *b;

a[ch-'0']++;

这样可以省去很多事...这些升级的技巧的明天再给你程序,以及我个人理解的为了用这些技巧的题目

下面的程序时在dev c++下将近1.5小时的劳动成果...

大概就是遍历b的时候 创建一个字符链表 和 一个汉字链表,遇到一个字符或者一个汉字就+1;

遍历a的时候 遇到一个字符或者一个汉字就-1;

自己写的不讲效率的程序  应该还是比较好懂.

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct is_char
{
   char ch;
   int num;
   struct is_char* next;
  }IS_CHAR;
  
typedef struct is_china
{
   char china[3];
   int num;
   struct is_china* next;
  }IS_CHINA;

IS_CHAR* init_charhead()
{
  IS_CHAR* head = (IS_CHAR*)malloc(sizeof(IS_CHAR));
  if(head == NULL)
   {
     printf("char head malloc error\n");
     return NULL;
    }
   head->next = NULL;
   return head;
}

IS_CHINA* init_chinahead()
{
  IS_CHINA* head = (IS_CHINA*)malloc(sizeof(IS_CHINA));
  if(head == NULL)
   {
     printf("china head malloc error\n");
     return NULL;
    }
   head->next = NULL;
   return head;
}

int is_in_char(IS_CHAR* char_head, char ch, int flag)
{
  assert(char_head != NULL);
  IS_CHAR* p = char_head->next;
  while(p != NULL)
   {
     if( p->ch==ch )
      {
        if(flag == 0)
          p->num++;
        else
        {
           if(p->num > 0)
              p->num--;
         }
          
        return 1;
       }
       p = p->next;
    }
    return 0;
}

int is_in_china(IS_CHINA* china_head, char* chinese, int flag)
{
  assert(china_head != NULL);
  IS_CHINA* p = china_head->next;
  while(p != NULL)
   {
     if(strcmp(p->china,chinese) == 0)
      {
        if(flag == 0)
          p->num++;
        else
         {
          if(p->num > 0)
            p->num--;
         }
           
        return 1;
       }
       p = p->next;
    }
    return 0;
}

void my_print_char(IS_CHAR* char_head)
{
  printf("\n char \n");
  IS_CHAR* p = char_head->next;
  while(p != NULL)
   {
     printf("char %c num %d\n",p->ch,p->num);
     p = p->next;
    }
}

void my_print_china(IS_CHINA* china_head)
{
  printf("\n chinese \n");
  IS_CHINA* p = china_head->next;
  while(p != NULL)
   {
     printf("str %s num %d\n",p->china,p->num);
     p = p->next;
    }
}

     
int is_include(const char *a, const char *b)
{
  char* t = (char*)a;
  char* s = (char*)b;
  
  printf("t is %s\n s is %s\n",t,s);
  char chinese[3];
  int res = 1;
  
  IS_CHAR* char_head = init_charhead();
  IS_CHINA* china_head = init_chinahead();
  
  while(*s != '\0')
   {
       if(*s&0x80)
        {
           chinese[0] = *s;
           s++;
           chinese[1] = *s;
           s++;
           chinese[2] = '\0';
           if(is_in_china(china_head, chinese, 0) == 0)
             {
              printf("now add %s\n",chinese);
              IS_CHINA* china_p = (IS_CHINA*)malloc(sizeof(IS_CHINA));
              china_p->num = 1;
              sprintf(china_p->china,"%s",chinese);
              china_p->next = china_head->next;
              china_head->next = china_p;
             }
         }
        else
         {
           if(is_in_char(char_head, *s, 0) == 0)
            {
              printf("now add %c\n",*s);
              IS_CHAR* char_p = (IS_CHAR*)malloc(sizeof(IS_CHAR));
              char_p->num = 1;
              char_p->ch = *s;
              char_p->next = char_head->next;
              char_head->next = char_p;
             }
              s++;
         }
    }
    
    printf("s is over\n");
    my_print_char(char_head);
    my_print_china(china_head);
     
    while(*t != '\0')
    {
      if(*t & 0x80)
        {
           chinese[0] = *t;
           t++;
           chinese[1] = *t;
           t++;
           chinese[2] = '\0';
           is_in_china(china_head, chinese, 1);
         }
        else
         {
           is_in_char(char_head, *t, 1);
           t++;
         }
     }
     
    printf("t is over\n");
    my_print_char(char_head);
    my_print_china(china_head);
     
     IS_CHAR* char_tmp1 = char_head->next;
     IS_CHAR* char_tmp2 = char_tmp1;
     while( char_tmp1!=NULL )
     {
       if(char_tmp1->num != 0)
        res = 0;
        
       char_tmp2 = char_tmp1->next;
       free(char_tmp1);
       char_tmp1 = char_tmp2;
      }
      free(char_head);
      char_head = NULL;
      
     IS_CHINA* china_tmp1 = china_head->next;
     IS_CHINA* china_tmp2 = china_tmp1;
     while( china_tmp1!=NULL )
     {
       if(china_tmp1->num != 0)
        res = 0;
        
       china_tmp2 = china_tmp1->next;
       free(china_tmp1);
       china_tmp1 = china_tmp2;
      }
      free(china_head);
      china_head = NULL;
      
      return res;
}

int main(int argc, char *argv[])
{
  char* a = "acac我是我我是123123zjzxxtxlzjzxxtxl";
  char* b = "ac我我是123zjzxxtxl";
  
  
  printf("str:%s\nand str:%s\n",a,b);
  is_include(a, b) ? printf("included\n") : printf("not included\n");
   
  system("PAUSE");    
  return 0;
}