目录
零、写在前面
一、主要知识点
1.字符记数
二、课后习题
面试题 01.01. 判定字符是否唯一
剑指 Offer 50. 第一个只出现一次的字符
383. 赎金信
771. 宝石与石头
面试题 01.02. 判定是否互为字符重排
1941. 检查是否所有字符出现次数相同
242. 有效的字母异位词
剑指 Offer II 032. 有效的变位词
1832. 判断句子是否为全字母句
2053. 数组中第 K 个独一无二的字符串
写在最后
零、写在前面
这是打卡的第二十四天，今天题目好多好多啊，主要知识点在
《算法零基础100讲》(第24讲) 字符串算法(四) - 字符计数法
https://blog.csdn.net/WhereIsHeroFrom/article/details/121295716
一、主要知识点
1.字符记数
可以利用hash表来记录字符串的数量，如果字符串只包含小写字母，还可以进一步压缩。
int hash[26] ={0}; //hash表顺带初始化 for(int i = 0;s[i];++i) hash[s[i] - 'a']++; //统计数量
二、课后习题
面试题 01.01. 判定字符是否唯一
面试题 01.01. 判定字符是否唯一
https://leetcode-cn.com/problems/is-unique-lcci/
思路
利用hash表，扫到扫过的字母就直接返回假，如果全扫完也没遇到就返回真。
bool isUnique(char* astr){ bool hash[256]; memset(hash,0,sizeof(hash)); for(int i = 0;astr[i];++i) if(!hash[astr[i]]) hash[astr[i]]++; else return false; return true; }
结果分析
凑合玩玩
剑指 Offer 50. 第一个只出现一次的字符
剑指 Offer 50. 第一个只出现一次的字符
https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
思路
先用hash表统计所有字母的出现次数，再扫描hash表，如果有等于1就的返回
没有就返回空格。
这道题返回的是一个字符！所以可以直接返回一个值！
char firstUniqChar(char* s){ int hash[26] ={0}; //hash表+初始化 for(int i = 0;s[i];++i) //记录hash值 hash[s[i] - 'a']++; for(int i = 0;s[i];++i) //遍历hash表 if(hash[s[i] - 'a'] == 1) return s[i]; return ' '; //没找到返回空格 }
结果分析
说的过去
383. 赎金信
383. 赎金信
https://leetcode-cn.com/problems/ransom-note/
思路
这次其实只是更新hash表的方式不同
首先，扫描magazine将所有出现的元素和个数都插入hash表内
然后，扫描ransom，扫到一个字符将对应的hash表值减1.
bool canConstruct(char * ransomNote, char * magazine){ int hash[256] = {0}; //hash表 for(int i = 0;magazine[i];++i)//扫描magazine更新hash表 hash[magazine[i]] ++; for(int i = 0;ransomNote[i];++i) //扫描ransom更新hash表 if(!hash[ransomNote[i]]) return false;//对应元素不够用？ else hash[ransomNote[i]]--; return true; }
结果分析
还是可以的
771. 宝石与石头
771. 宝石与石头
https://leetcode-cn.com/problems/jewels-and-stones/
思路
先扫描J中所有元素，然后根据hash表判断s中元素进行统计。
int numJewelsInStones(char * jewels, char * stones){ bool has[256] = {0}; //hash表 int ans = 0; for(int i = 0; jewels[i]; ++i) //更新hash表 if(has[jewels[i]] == 0) has[jewels[i]] = 1; for(int i = 0; stones[i]; ++i)//根据hash统计 if(has[stones[i]] == 1) ans++; return ans; }
结果分析
还可以的
