[关闭]
@linux1s1s 2015-05-05T13:07:13.000000Z 字数 781 阅读 1202

String 算法

C/C++


题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 分析:这道题是2006年google的一道笔试题。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main(int argc, char *argv[])
  4. {
  5. int i = 0;
  6. char* str = "abaccdeff";
  7. int ch[256];
  8. memset(ch,0,sizeof(ch));
  9. int len = strlen(str);
  10. //用来存放字符串某个字符出现的最后位置(从0开始)
  11. int chset[256];
  12. memset(chset,0,sizeof(chset));
  13. //把字符转化为USCII码,然后作为数组下标,如果出现多次,该下标数组值会累加,如果出现一次,那么就是1
  14. for(i=0; i<len; i++)
  15. {
  16. ch[str[i]-'0']++; //位图初始化全为0
  17. chset[str[i]-'0'] = i;
  18. }
  19. //添加哨兵 min
  20. int min = chset[str[0]-'0'];
  21. int k = 0;
  22. //遍历寻找数组ch值为1,并且出现的位置在chset数组中最小的字符
  23. for(i=0; i<len; i++)
  24. {
  25. if(ch[str[i]-'0'] == 1)
  26. {
  27. if(chset[str[i]-'0'] < min)
  28. {
  29. min = chset[str[i]-'0'];
  30. k = i;
  31. }
  32. }
  33. }
  34. printf("in str:%s\nfirst apprear once is %c\n",str,str[k]);
  35. system("PAUSE");
  36. return 0;
  37. }

之前有篇博客http://blog.chinaunix.net/uid-9950859-id-98760.html?page=2
给出的解决思路有个问题,字符串必须是顺序的,否则会出现bug,这里给出的算法,可以无视顺序这个问题。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注