字符串

题解-统计子串中的唯一字符-哈希表+栈，计算贡献

一个贡献问题的解法

[A=B]攻略-第三章

更加困难的游戏体验,以及更加活跃的解题体验

[A=B]攻略-第二章

游戏A=B的第二章的题解

[A=B]攻略-第一章

A=B的第一章的解法和解释

题解-移位字符串分组-哈希表

Problem: 249. 移位字符串分组 思路 类似于凯撒密码的归类方式,我们将所有能通过轮转得到的字符串放在一起,不难想到可以通过暴力来对每一个字符串匹配 对于字符串仔细观察可以发现每一个可以归类到一起的字符串的本质是相同的,不只是字符串长度,还有与左右字母之间的差值 综上,对于每一类字符串我们只需要将其转化为模板的样子就能判断是否能归类 我们的问题就是如何将字符转成一个标准的模板 考虑字符之间的相对关系, 我们设首位为0,后面的每一位对应的是字符串该位与前一位的差 如果小于0则加26,来保证模式字符串相等 解题方法 对于每一个字符串,计算其相对字符的模板字符串 查询哈希表,如果有则插入到相对的答案组中 没有就新开一个答案组 重复上述操作 复杂度 时间复杂度: 只遍历一次 $O(mn)$,m为字符串长度 空间复杂度: 运用了哈希表 $O(n)$ Code class Solution { public: vector<vector<string>> groupStrings(vector<string>& strings) { vector<vector<string>>res; unordered_map<string,int>hash;//模板字符串及其对应的在答案的行数 for (auto &iter:strings){ string tmp="0_"; char a=iter[0]; int now; for (int i=1;i<iter.size();i++){ now=iter[i]-a; if (now<0)//保证模板的一致性 now+=26; tmp+=to_string(now)+"_"; a=iter[i]; } if (hash.find(tmp)!=hash.end()){ res[hash[tmp]].emplace_back(iter); } else{ hash[tmp]=res.size(); res.emplace_back(vector<string>(1,iter)); } } return res; } };