Counting Duplicates

xsir 2020-03-15 AM 98℃ 0条 1812字 Site load time is:6 ms 百度:已收录

题目的要求是写一个函数用来计算字符串中出现重复的字符的字符个数,如:"aAbbcde"重复的字符个数为2(字符a和b), "abcde"重复的字符个数为0, "123321"重复字符个数为3(字符123), 题目保证字符串的字符只包含字母(不区分大小写)和数字。

这题很简单,但看了网上大神的解法觉得还是有必要记录一下(因为实在太妙了)。

自己笨拙的代码:

/*
思路:
因为字符在计算机中是以ASCII码的形式存在(如:'0' -> 48, 'A' -> 65), 
所以直接用一个vis数组来记录字符的出现次数, 然后遍历vis数组,判断如果出现次数大于1, 则cnt++, 最后输出cnt即可。
需要注意的是要先把小写字母转大写字母
*/
size_t duplicateCount(const char* in) {
  int vis[128] = { 0 }, cnt = 0;
  std::string str = in;
  
  for(int i = 0; i < str.length(); ++i) {
    if( (str[i] >= '0' && str[i] <= '9') || 
        (str[i] >= 'A' && str[i] <= 'Z') || 
        (str[i] >= 'a' && str[i] <= 'z')) {
        
        if(str[i] >= 'a' && str[i] <= 'z') {
            str[i] -= 32;            // 小写转大写
        }
        
        vis[str[i]]++;
    }
  }

  for(int i = 0; i < 128; ++i) {
    if(vis[i] > 1) {
        cnt++;
    }
  }  

  return cnt;
}

大神精妙的代码:

size_t duplicateCount(const char* in) {   
    char cnt[37] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

    while(char c = *in++) {
        if( (c >= '0' && c <= '9' && !cnt[c - 47]--) || 
            (c >= 'a' && c <= 'z' && !cnt[c - 'a' + 11]--) || 
            (c >= 'A' && c <= 'Z' && !cnt[c - 54]--)) {
            (*cnt)++;
        }
    }

    return *cnt;
}

我刚开始看这代码的时候一脸懵逼,多看几遍就慢慢理解了。
现在开始解释代码:
光从char cnt[37]的定义就看出这大神是真的省空间,那么37是怎么来的呢?cnt[0]用来记录结果,cnt[1]到cnt[10]对应字符‘0’到‘9’,cnt[11]到cnt[36]对应字符‘a’到‘z’和‘A’到‘Z’。if语句里的!cnt[n]--是真的妙啊,因为一开始cnt[n]都是1,所以!cnt[n]为false,然后cnt[n]--,(cnt)++也就不会执行,当同一个字符出现第二次的时候,此时cnt[n]为0,执行(cnt)++,但是当同一个字符出现第三次以上时,因为cnt[n]<0,!cnt[n]为false,所以(*cnt)++不执行。也就是说只要一个字符出现了两次及以上就会进行一次计数。
这代码非常巧妙的利用了逻辑与(&&),逻辑非(!)以及自减运算符(--)的特性,真的太妙了!什么时候我也能写出这样的代码就好了~

标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~


召唤看板娘