拿捏几道经典的字符串模拟问题

希望本篇对你有所帮助

我发现这种字符串的问题其实写起来很麻烦，可能思路不难多少都能想到一些，主要就是代码的处理，细节问题。太考验代码编写的能力了。这两天写了好多道字符串，模拟之类的问题，今天就分享分享吧

刚开始刷题的朋友开卷有益啊

输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释: 
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。 
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"）， 
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。

首先读懂题意：

几个关键点

答案是唯一的
在做判断的时候不区分大小写，意思就是AOB等于aob
再者要在禁用列表里面找是不是禁用的单词
自动忽略标点符号，意思就是bob?或者bob.或者bob, 这些都按照bob这个单词去处理
拿到这题肯定第一反应就是用哈希表来映射，这是没问题的，那么就需要我们在里面做一个处理，我们记录的单词不能带标点

大致思路就出来了，定义一个map去记录各个单词映射，然后很多题解是把原来的这个字符串paragraph存到了一个字符串数组里面，这样方便遍历，然后把禁用列表用一个set再去存一下方便去find

不过这样我感觉空间就有了开销，我是这样写的

遍历整个字符串paragraph，用一个word去记录每次遇到的字母，只要是正常的字母我们就添加到word上面，如果遇到了空格或者标点了就说明我们这个单词记录完毕了，在单词列表里用find去查询此时记录的word，如果没找到说明可以把它记在map里面，然后每次做完这个判断就把word置为“”，用来进行下一个单词的组装

这样的话就用一个word来回组装，一遍遍历完成了给map的映射，最后再去map里面找最大的就行

代码如下：

 string mostCommonWord(string paragraph, vector<string>& banned) {unordered_map<string,int>mp;//用来记录单词出现的次数string word="";for(int i=0;i<paragraph.size();++i){//因为不区分大小写，所以要做if判断if(paragraph[i]>='A'&&paragraph[i]<='Z'){//如果是大写，要转成小写//word+=tolower(paragraph[i]);word+=paragraph[i]-'A'+'a';}else if(islower(paragraph[i]))//如果是小写{word+=paragraph[i];}else if(word!="")//其实就是判断了是各种标点或者空格了{                 //走到这就说明word已经加成了一个完整的单词//就要开始判断在不在禁用列表中if(find(banned.begin(),banned.end(),word)==banned.end())//没找到{mp[word]++;}word="";}}int maxlen=1;//遍历map，找出现次数最多的那个for(auto &x:mp){if(maxlen<=x.second){maxlen=x.second;word=x.first;}}return word;}

----------------------------------

再来一道叫做亲密的字符串，让我们看看他有多亲密啊

示例 1：

输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。

示例 2：

输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。

示例 3：

输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

拿到这题我最早想着就直接暴力，两个for循环两两交换去比较

pa的一下很快啊，代码出来了，很顺利啊，没有ac啊，超时了家人们，太慢了

我当初写的时候也是抱着侥幸心理哈哈哈，果然超时了

既然暴力走不通那么就好好审题，找找规律看看都有什么情况我们要做处理，反正我当初愣是没想到要记录下标到数组，废了老大功夫去做。

如果读完题你能想到，map和记录下标，那么这个题就没问题了

看看力扣给的示例我们ab和ba，我们会发现两个字符串的两个位置都不相同，且交换之后就相同了；示例ab和ab他本身相同，但是一交换就不相同了；示例aa和aa，本身相同且相同的字母有多个，意思就是aa是重复的，我们交换了，最终两个结果还是一样

这道题就是必须要交换一次，且只能交换一次

分析完三个示例，就能得到下面的规律：

两种情况
s和goal有两个位置不相同，且这两个位置交换之后，就相等了
如果s和goal不相同的位置大于2了，肯定就不相同了
s和goal完全相同，并且s有多余相同的字符，这样的话s和goal才能返回true
什么意思？ab 和ab都相同但是，交换就会有问题
aab和aab相同 a有多余交换aa还是不变的，就说明可以返回true

看到这，我们就有思路了呀，定义一个map去记录s各个字母出现的次数，如果s里有多余出现的字母，我们就做个标记。在遍历s的时候如果当前位置的s字母和goal字母不一样了，说明有一个位置了，我们把这个位置保存在下标数组里面；我们定义下标数组的时候这个数组其实最终要么为空要么为2，为2就说明两处不一样可以去交换了，如果大于2了那么肯定一次交换是不行的，结果肯定就是false了。

思路如下：

统计字符串s，goal中字符不匹配的下标。

不匹配的下标个数不等于 0 或 2 时，不能由s得到goal。

不匹配的下标个数等于0时，s与goal中字符完全相同，还需要s中有重复字符。

不匹配的下标个数等于2时，判断交换两对字符后是否匹配。

这样pa的一下啊代码又出来了

    bool buddyStrings(string s, string goal) {if(s.size()!=goal.size())return false;int flg=0;//有多余相同字母的标记for(int i=0;i<s.size();++i){if(s[i]!=goal[i]){index.push_back(i);}if(index.size()>2)return false;//大于2个位置不一样了mp[s[i]]++;if(mp[s[i]]>1)//说明有重复的{flg=1;}}//有两个不相同if(index.size()==2&&s[index[0]]==goal[index[1]]&&s[index[1]]==goal[index[0]]){return true;}//都相同 且有重复字符if(index.size()==0&&flg){return true;}//还有一种写法 不用map，和flg标记//当index的size等于0的时候，用s来构建一个set//unordered_set<char>set(s.begin(),s.end());//return set.size()<s.size();如果s里面有重复的那么set的长度肯定小于s长度return false;}

数组啊字符串很多题都是考能不能找到规律的问题，需要双指针，滑动窗口，map这些都是这一类题常见的解题技巧。

蹬蹬补充一道题：不是字符串的题，不过当初自己写的时候感觉蛮有意思（就是自己菜，没找到简单的规律），单独给这个题记录一篇博客，感觉太水了，我就浅浅加在这一篇吧。

看到就是赚到！！

这个思路是最最最简单的，反正我也是看了题解才知道OO~~哦可以这样

找到开头连续的0，找到结尾连续的0，再找中间连续的最大0

返回这三个里面最长的就行

 int maxDistToClosest(vector<int>& seats) {//找到开头连续0个数，结尾连续0//中间连续0，取最大int kaitou=0,jiewei=0,mid=0;int i=0,j=seats.size();while(i<j&&seats[i]==0){kaitou++;i++;}while(j>0&&seats[j-1]==0){jiewei++;j--;}int temp=0;//记录一下中间每次连着0的个数for(int k=i+1;k<j;++k){if(seats[k]==0){temp++;}else{mid=max(temp,mid);temp=0;}}return max(max(kaitou,jiewei),(mid+1)/2);}

其实写了很多题，好题太多了，我就挑一些不错的给大家分享分享~