文章目录

• 知识讲解
• 课后习题
• • 1. 判定字符是否唯一
  • 2. 第一个只出现一次的字符
  • 3. 赎金信
  • 4. 宝石与石头
  • 5. 判定是否互为字符重排
  • 6. 检查是否所有字符出现次数相同
  • 7. 242. 有效的字母异位词
  • 8. 有效的变位词
  • 9. 判断句子是否为全字母句
  • 10. 数组中第 K 个独一无二的字符串

知识讲解

  字符计数法的方法和原理都很简单，原理就是对ASCLL码的引用。
使用方法：
例如我们要统计一个字符串里，小写字母出现的个数

int count(char *s){
	int Hash[26] = { 0 };
	int n = strlen(s);
	for(int i = 0; i < n; i++){
		Hash[s[i] - 'a']++;
	}
}

通过下标来(0~25)表示26个小写字母(a ~ z)。

课后习题

1. 判定字符是否唯一

题目链接：
面试题 01.01. 判定字符是否唯一
这道题我们只需用数组统计每个字母的出现次数，找出只出现过一次的字母即可。

代码如下：

bool isUnique(char* astr){
    int Hash[26] = { 0 };
    int n = strlen(astr);
    for(int i = 0; i < n; i++){
        if(astr[i] >= 'a'){
            Hash[astr[i]- 'a']++;
        }
        else{
            Hash[astr[i]- 'A']++;
        }
        
    }
    for(int i = 0; i < 26; i++){
        if(Hash[i] > 1){
            return false;
        }
    }
    return true;
}

这种写法可以过力扣上的全部例子，但是有一种特殊情况不行

所以正确的写法应该如下：

bool isUnique(char* astr){
    int Hash[256] = { 0 };
    int n = strlen(astr);
    for(int i = 0; i < n; i++){
        Hash[astr[i]]++;
    }
    for(int i = 0; i < 256; i++){
        if(Hash[i] > 1){
            return false;
        }
    }
    return true;
}

2. 第一个只出现一次的字符

题目链接：
剑指 Offer 50. 第一个只出现一次的字符
思路分析：
  由于我们字符串中只有小写字母，所以我们只需考虑小写的情况即可。

代码如下：

char firstUniqChar(char* s){
    int Hash[26] = { 0 };
    int n = strlen(s);

    for(int i = 0; i < n; i++){
        Hash[s[i] - 'a']++;
    }
    for(int i = 0; i < n; i++){
        if(Hash[s[i] - 'a'] == 1){
            return s[i];
        }
    }
    return ' ';
}

3. 赎金信

题目链接：
383. 赎金信
思路分析：
  这道题其实就是让我们判断是否能用magazine中的字符来表示ransomNota中的字符，所以我们只需要统计两个字符串中的字符类型与个数，然后进行比较，如果ransomNota中有的magazine中都有，则返回true；
代码如下：

bool canConstruct(char * ransomNote, char * magazine){
    int n1 = strlen(ransomNote);
	int n2 = strlen(magazine);
	int arr1[26] = { 0 };
	int arr2[26] = { 0 };
	for (int i = 0; i < n1; i++){
		arr1[ransomNote[i] - 'a']++;
	}
	for (int i = 0; i < n2; i++){
		arr2[magazine[i] - 'a']++;
	}
	for (int i = 0; i < 26; i++){
		if (arr2[i] < arr1[i]){
			return false;
		}
	}
	return true;
}

4. 宝石与石头

题目链接：
771. 宝石与石头
思路分析：
  这道题很简单，我们只需要将 j 中出现的字母用下标对应的方法记录下来，然后再遍历字符串 s，计算s中有多少个属于 j 中的字母。
代码如下：

int numJewelsInStones(char * jewels, char * stones){
    int num = 0;
    int n = strlen(jewels);
    int Hash[123] = { 0 };
    //标记宝石
    for(int i = 0; i < n; i++){
        Hash[jewels[i]]++;
    }
    int m = strlen(stones);
    for(int i = 0; i < m; i++){
    	//判断是否是宝石
        if(Hash[stones[i]] > 0){
            num++;
        }
    }
    return num;
}

5. 判定是否互为字符重排

题目链接：
面试题 01.02. 判定是否互为字符重排
思路分析：
  这道题和之前的方法都一样，用数组将s1和s2两个字符串的字符都记录下来，如果它们的字符种类和数目都相同，则s2可以通过重新排序得到s1。
代码如下：

bool CheckPermutation(char* s1, char* s2){
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    //判断特殊情况
    if(n1 != n2){
        return false;
    }
    int Hash1[123] = { 0 };
    int Hash2[123] = { 0 };
    for(int i = 0; i < n1; i++){
        //分别记录s1和s2的字符及个数
        Hash1[s1[i]]++;
        Hash2[s2[i]]++;
    }
    for(int i = 0; i < 123; i++){
        //判断字符数量是否相同
        if(Hash1[i] != Hash2[i]){
            return false;
        }
    }
    return true;
}

6. 检查是否所有字符出现次数相同

1941. 检查是否所有字符出现次数相同
思路分析：
  我们还是用数组的方式对字符串中的字符进行计算，并同时用一个变量记录其中某个字符的数量，然后再拿数组中的数据与其进行比较是否相同，如果出现不同的字符的数量则直接返回false。
代码如下：

bool areOccurrencesEqual(char * s){
    int arr[26] = { 0 };
    int len = strlen(s);
    int n = 0;
    for(int i = 0; i < len; i++){
        //计算每种字符的数量
        arr[s[i] - 'a']++;
        //记录某一个字符的数量
        n = arr[s[i] - 'a'];
    }
    
    for(int i = 0; i < 26; i++){
        //为0则说明没出现该字符，直接跳过
        if(arr[i] == 0){
            continue;
        }
        else if(arr[i] != n){
            return false;
        }

    }
    return true;
}

7. 242. 有效的字母异位词

题目链接：
242. 有效的字母异位词
这道题和判断是否为字符重排这道题的做法是一样的。
代码如下：

bool isAnagram(char * s, char * t){
    int n1 = strlen(s);
	int n2 = strlen(t);
    if(n1 != n2){
        return false;
    }
	int arr1[26] = { 0 };
	int arr2[26] = { 0 };
	for (int i = 0; i < n1; i++){
		arr1[s[i] - 'a']++;
        arr2[t[i] - 'a']++;
	}
	for (int i = 0; i < 26; i++){
		if (arr2[i] != arr1[i]){
			return false;
		}
	}
	return true;
}

8. 有效的变位词

题目链接：
剑指 Offer II 032. 有效的变位词

这道题和上面那道是相似的，就是多了一个条件：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
所以我们还需判断两个字符串是否为相同的字符串。
代码如下：

bool isAnagram(char * s, char * t){
    int n1 = strlen(s);
	int n2 = strlen(t);
    if(n1 != n2){
        return false;
    }
	int arr1[26] = { 0 };
	int arr2[26] = { 0 };
    int flag = 1;
	for (int i = 0; i < n1; i++){
        if(s[i] != t[i]){//判断是否有不相同的串
            flag = 0;
        }
		arr1[s[i] - 'a']++;
        arr2[t[i] - 'a']++;
	}
    if(flag){
        return false;
    }
	for (int i = 0; i < 26; i++){
		if (arr2[i] != arr1[i]){
			return false;
		}
	}
	return true;
}

9. 判断句子是否为全字母句

题目链接：
1832. 判断句子是否为全字母句
思路分析：
  题目要求是判断所给的句子是否为全字母句，而全字母句就是所有字母都至少出现过一次的句子，所以我们只需用数组记录句子中出现的字母，然后再遍历数组。

代码如下：

bool checkIfPangram(char * sentence){
    int n = strlen(sentence);
    //长度小于26的句子一定不是全字母句
    if(n < 26){
        return false;
    }
    int Hash[26] = { 0 };
    for(int i = 0; i < n; i++){
        Hash[sentence[i] - 'a']++;
    }
    for(int i = 0; i < 26; i++){
        if(Hash[i] == 0){
            return false;
        }
    }
    return true;
}

10. 数组中第 K 个独一无二的字符串

题目链接：
2053. 数组中第 K 个独一无二的字符串
这道题稍微有一点点难度
思路分析：
  我的解法还是比较暴力的

1. 首先我们需要定义一个数组dp用来记录所有只出现过一次的数组的位置。
2. 然后我们遍历所有的字符串，用strcmp进行比较，将重复出现的串用数组dp标记为0.
3. 最后我们遍历数组dp，找到第k个未被标记的下标，然后将该下标对应的串返回即可，如果没有则返回""

代码如下：

int dp[1001];
char * kthDistinct(char ** arr, int arrSize, int k){
    //初始化数组
    memset(dp, 1, sizeof(dp));
    //遍历所有数组，并将重复出现的串标记为0
    for(int i = 0; i < arrSize; i++){
        //如果dp[i] == 0说明以及比较过了
        if(dp[i] == 0){
            continue;
        }
        for(int j = 0; j < arrSize; j++){
            if(dp[j] == 0)continue;
            if(i == j)continue;
            if(strcmp(arr[i], arr[j]) == 0){
                dp[i] = 0;
                dp[j] = 0;
            }
        }
    }
    for(int i = 0; i < arrSize; i++){
        if(dp[i]){
            k--;
        }
        if(!k){
            return arr[i];
        }
    }
    return "";
}