NOIR@ZH · NOTES & STORIES
我们逃去看海吧
记录算法与代码，也收藏游戏、故事和沿途的想法。
浏览全部文章 →
最近更新
29 篇记录
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; } };
↗
↗
暮色四合，寒鸦声渐，一阵冷风吹过，将火光中冒出的热气吹远，又慢慢沉降，我和她围绕着一团明亮的火焰相伴而坐。“这样就可以了”，她将手中的纸张送进那团光亮之中，那里的火焰迅速升腾而起，不消几秒又在一声轻微的爆鸣声中沉降，我看着火中翻飞着的纸屑，“一切就结束了吧”，纸张有序地一点点送进火中，“这只是某个阶段的结束…它们只是到了应该离开的时候了”，“可是这些只有你自己看过”，火光映照着她面无表情的脸庞，“所以就足够了，这些写出来就是给自己看的”，火中升腾而起的不只有光与热，也有灰黑色的碎屑。
“真可惜，就像是卡夫卡一样”，我半开玩笑地说，她看着那团似乎永远也不会熄灭的希望，“很多人都在我们看不到的地方痛苦地做着一些所谓被社会边缘化的东西，我们需要深刻的批判和思考，但是思考的刀不能落在我们的头上”，火继续燃烧，风一刻不停，此时只有沉默，就像是之前的数次一样，写满了字的纸张在火中卷曲湮灭，尚能认清的只言片语凑不出来整齐的脉络。“就像是碌碌无为的天才”，“你说卡夫卡？”，“这盆火。”，劈啪作响的声音将时间不断拉长，沉默被一声沉闷的声音打破，砸进火中的是一个厚重的本子，看起来被使用得十分充分，它将火焰压了下去，我刚想要做什么，“没事的，马上就会起来的。”，如她所说，在黯淡了几秒之后，那个本子弯曲焦黑，升腾起一阵亮眼的光，“可是那个”，“它们已经完成了一切，只会留下刺耳的呼啸。”，就这样，我和她看着那本陪伴了她三年的故事集化成灰白的碎屑，和一阵浓烟，呛鼻，但不至于落泪。手上的重量一点点减少，光亮明灭，将暮色照清又隐去，她模糊的脸庞并没有别的表情，火光在她的眼中跳跃，清晰明亮。“就这样，把它们全扔进去”，我们的手中什么都没有了，只有那一盆刺眼的猛烈燃烧的焰火，“眼睛疼吗”，我摇摇头，“那就再看一眼吧”。失去了维持的火光跃动，隐去了身形，只余下几枚零星的火星，如同萤火虫，在逐渐深沉的夜色之中飞走。终于是一切结束，我们将这一切收拢妥当，如从未发生过什么一样。走在如墨的夜色之中，她说过，这种景色只应沉默。在归途之上，她哼唱着那首不知名的曲调，我们也在其中隐去了身形。
我沾染上了这个坏习惯。在很久之后，在现在，我再也没办法忽视它们带来的聒噪的声音。当那一切变的空白的时候，我想，我大概是懂得了一些。暮色四合，此时只应沉默。
↗
思路 根据题意可知全局倒置包含局部倒置，对于本题如果有 非局部倒置 的全局倒置，则返回false，不然就返回true 很容易相出用暴力去搜索自己2位之后的数组元素中是否有比自己小的，时间复杂度:$O(n^2)$ 倒置是根据的是递增数组出现的，也就是说我们得到的数组实际上是对递增数组进行过几次置换的数组 根据定义可以知道局部倒置的实质就是将相邻的数组元素进行的交换，所以要做的就是与原数组进行比较 位置不变的跳过 位置变化的判断是否和原数组相邻位置的值相等，相等则跳过 不满足上述两个条件的就是全局置换，返回false 代码 class Solution { public: bool isIdealPermutation(vector<int>& nums) { int n=nums.size()-1; int i=0; while (i<n){ if (nums[i]==i) i++; else if (nums[i]==i+1&&nums[i+1]==i) i+=2; else return false; } return true; } };
↗
来自这里
尝试学习一些markdown语法,以及一些效果,但是换成HTML之后可能就糊掉了,想不到解决方法
基础部分 typora能够实时渲染,所以记得开源代码显示器
标题 这个我不用多说吧
段落 除了这个回车之外
还有这个 换行或者shift+entet我 我
我
风格 以下代码能够实现换行,大概,放在最后一行
分割线 这样或者
这样
项 无序项 及其连环套 简单吧 有序 同理 项 引用 引用
和交叉引用
很简单
对吧
层数
强调 包括加粗和斜体甚至可以这样
辅助线 删除和下划线
字体 使用 <font> 标签的修改字体 这里是默认字体
这里是黑体
这里是楷体
这里是扩展字体
使用 <font> 标签的修改字号 这里是默认正文字号
1号字 最小
2号字
3号字 默认
4号字
5号字
6号字
7号字 最大
前景色和背景色 使用 <font> 的标签的修改文字前景色 红色 绿色 蓝色
使用 rgb 颜色值
使用十六进制颜色值
使用 style 属性修改文字的背景色 红色 绿色 蓝色
使用 rgb 颜色值
使用十六进制颜色值
更丰富背景样式 I wish you a Merry Christmas 使用图片作背景
↗