第一题 500. 键盘行
好家伙，我读成 了键盘侠…。本题的将字母映射为行号的想法可以浅积累一下
题目描述
解题报告
① 首先进行预处理吧，获取每个英文字母所在的行，比如字母a在第一行，字母b在第二行，有点打表的思想吧。解题区看到一个纯打表的佬，浅记录一下。
② 获得到当前准备遍历的字符串的首字母所在的行号，用它作为比较的参考，将符合条件的字符串统计起来
参考代码(C++版本)
class Solution { public: vector<string> findWords(vector<string>& words) { //预处理，获取每个英文字母所在的行 string rowIndex = "12210111011122000010020202"; vector<string>ans; //取出字符数组中的每个字符串 for(auto &word : words) { //在统一转换为小写字母的情况下，获取首字母所在的行号 char index = rowIndex[tolower(word[0])-'a']; //遍历当前这个字符串 bool flag = true; for(int i = 1; i < word.size();i++) if(rowIndex[tolower(word[i])-'a'] != index) { flag = false; break; } if(flag) ans.push_back(word); } return ans; } };
第二题 1160. 拼写单词
使用映射的思想处理字符串，使用数组模拟哈希表来统计个数
题目描述
解题报告
看到数据范围是1000。我想直接暴力的，但是发现写了三个for循环，默默放弃了自己的念想，可能可以优化吧~
常规的解法了，是将字母表中有的字母通过减去字符a来实现映射，将映射的结果使用一个数组来统计。
比如这个数组叫做nums，此时这个数组了，其实是模拟的一个哈希表，比如说将字符c映射成2了，此时数组中索引为2的数据num[2]就是字符c，因为数组是一块内存空间，最终是要落实到存储一个数据的，比如存储的是4，那么就代表字符c出现了四次。
按照上述的思想，我们只是需要将本题的字母表chars和词汇表words分别这种处理，要能够凑数相应词汇的前提要求就是，对于某个词汇而言，组成这个词汇的每个字母的数量必须小于等于单词表中对应的字母的数量，不然就凑不出来。
参考代码(C++版本）
class Solution { public: int countCharacters(vector<string>& words, string chars) { //三重暴力超时 int ans = 0;//统计符合要求的字符串的长度 int cnt_chars[26]; memset(cnt_chars,0,sizeof(cnt_chars)); for(char c: chars) ++cnt_chars[c-'a'];//进行一步映射，统计字母表中有的字母的个数 int cnt_word[26];//这个数组统计的是当前处理的字符串中的字母的个数 for(string word : words) { //每次使用前需要置零 memset(cnt_word,0,sizeof (cnt_word)); for(char c:word) ++cnt_word[c-'a']; bool flag = true; for(int i = 0;i < 26;i++) //如果说词汇中出现的字母的数目比字母表中多，那就是组成不了 if(cnt_word[i] > cnt_chars[i]) { flag = false; break; } //符合要求的字符串，统计答案 if(flag) ans += word.size(); } return ans; } };
第三题 1047. 删除字符串中的所有相邻重复项
栈的思想
题目描述
解题报告
参考代码(C++版本)
class Solution { public: string removeDuplicates(string s) { string stk; int len = s.size(); for(int i = 0;i < len;i++ ) { //倘若此时栈不空，而且栈顶等于要进栈的元素，就把栈顶弹出 if(!stk.empty() && stk.back() == s[i]) stk.pop_back(); else stk.push_back(s[i]); } return stk; } };
第四题 1935. 可以输入的最大单词数
题目描述
解题报告
这个也是可以使用哈希表来统计的，用哈希表统计键位坏了的字符。算是一步预处理吧，再去遍历现有的单词，假如遇到了哈希表中统计的字符，就可以判定是无法使用键盘完全输入的单词了。
参考代码(C++版本)
class Solution { public: int canBeTypedWords(string text, string brokenLetters) { //这个也是可以使用哈希表的思想来做的 int m[26]; //brokenLetters 由 互不相同 的小写英文字母组成 memset(m,0,sizeof(m)); for(auto ch : brokenLetters) m[ch-'a']++; bool flag = true; int ans = 0; int len = text.size(); //注意字符数组的结尾是\0 for(int i = 0; i <= len;i++) { //遍历结束，或者遍历到空格了,统计答案 if(text[i] == ' ' || text[i] == '\0') { //统计结果 if(flag) ans ++; //重置之前因为故障被修改过的flag flag = true; } else if(m[text[i] - 'a'])//如果遇到键位是坏的字符了 flag = false; } return ans; } };
总结
就今天的题而言了，很多时候直接处理字符串了，可能不太方便，
但是咱可以通过当前字符 - 字符a来实现映射
