一、题干
牛客网链接
https://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50
二、题解
1. 查表法（标记、哈希表）
题干规定了出现的字符均是 ascii 值小于127的字符，因而我们可以定义一个“标记数组”用于标记出现过的字符。
这就好像上课时老师点名用的花名册，名册原本就记录了一共127位学生的名字。点名时，哪位学生到了，就在他的名字后打个“√”。本题的思想也类似于此。
根据题干，我们将标记数组的大小定义127 ，然后将字符直接作为数组的下标，在数组中进行标记。注意：可打印的字符类型本身就能转换为数值（ASCII），这一点非常巧妙。若数组中该位置没有被标记过，则表示第一次出现，从而进行计数；否则表示重复字符，不进行计数。
示例
用查表法， "aca" ，首先把 a 字符 ( ascii 值为 97 ) 作为下标，将“标记数组”的第 97 位置为 1 ，下次如果还有 a 字符出现，到下标 'a' 或者 97 的位置一看是 1， 就表示 a 已经统计过了。
#include <stdio.h> int main() { char tmp[501] = {0}; //该数组用于输入字符串 while(~scanf("%s", tmp)) { //用于多组输入 char table[128] = {0}; //定义标记数组 char* ptr = tmp; //指针指向我们输入的字符串，用于字符串的遍历 int count = 0; while(*ptr != '\0') { if (table[*ptr] != 1) { //判断字符ascii值作为下标的位置是否被标记过，是否是重复字符 count++; //当前字符的位置没有被标记过，表示没有出现过，则计数+1 } table[*ptr++] = 1; //将字符ascii值作为下标的位置进行标记，置为1 } printf("%d\n", count); } return 0; }
2. 指针与区间划分（回头法)
这个方法的核心思路在于“回头查重”，每遍历到字符串中的一个字符，就回头对它前面的所有字符进行检查，看它之前是否出现过。如果出现过，说明有重复，则不计数；否则则进行计数。
我们用查重函数duplicateCheck来完成“判断是否有重复”这个任务，它的返回值是“是”或“否”，我们将函数的返回值定义为int类型。它的具体功能是：
传入在main函数中遍历到的字符*p（即ch），*p在字符串中的位置（用指针p表示），字符串本身的首元素地址arr
查重的范围是：字符串第一个字符 到 该字符本身 之间。我们用当前位置p减去首字符的位置arr来表示这个查重范围。
#include<stdio.h> int duplicateCheck(char* arr, char* p, char ch) { int size = p - arr; //查重范围框定，从首元素到当前元素之间 for (int i = 0; i < size; i++) { if (ch == arr[i]) { return 1; } } return 0; } int main() { unsigned char arr[500]; scanf("%s", arr); //没有用多组输入 int count = 0; char* p = arr; while (*p != '\0') { p++; //注意p++的位置，必须放在这里，不能放在while循环的最后，否则会因为continue的存在而死循环 if (duplicateCheck(arr, p, *p)) { continue; } else { count++; } } printf("%d", count); return 0; }
三、方法总结
1. 哈希表查找是一个很巧妙的方法，在去重、找重等题型中很常见也很适用。可以在牛客网【华为机试】组题中刷刷相关的题。
2. 在第二种方法中提到，while循环内部出现continue时，最好多留个心眼，检查一下它会不会出现死循环。在while与continue之间，应当有能改变循环变量的语句。
3. 需要多回顾。
