剑指offer第2版：字符串

一、p284-JZ58 翻转字符串（双指针）

翻转单词序列_牛客题霸_牛客网

思路1：双指针  先局部翻转再整体翻转

#include <algorithm>
class Solution {
public:string ReverseSentence(string s) {int n=s.size();if(n<=1) return s;//这样就不用翻转了int i=0;int j=i;   //让i作为右边界 然后翻转while(i<n){while(i<n&&s[i]!=' ') ++i;reverse(s.begin()+j,s.begin()+i);while(i<n&&s[i]==' ') ++i;j=i;}reverse(s.begin(),s.end());return s;}
};

 思路2：我们可以用stringstream切割字符串,然后再利用栈后进先出的特性拼接

#include <algorithm>
#include <sstream>
class Solution {
public:string ReverseSentence(string s) {int n=s.size();if(n<=1) return s;//这样就不用翻转了stringstream is(s);stack<string> st;while(is>>s) st.push(s);string ret(st.top());st.pop();while(!st.empty()){ret+=' '+st.top();st.pop();}return ret;}
};

二、扩展p286-JZ58 左旋字符串

左旋转字符串_牛客题霸_牛客网

 思路1：循环n次每次往前挪一位

class Solution {
public:void moveleft(string&str){char temp=str[0];int i=0;for(;i<str.size()-1;++i) str[i]=str[i+1];str[i]=temp;}string LeftRotateString(string str, int n) { //先局部逆置 再整体逆置int len=str.size();if(len==0||n==0) return str;n%=len;for(int i=0;i<n;++i) moveleft(str);return str;}
};

思路2：先局部逆置再整体逆置

class Solution {
public:string LeftRotateString(string str, int n) { //先局部逆置 再整体逆置int len=str.size();if(len==0||n==0) return str;n%=len;reverse(str.begin(),str.begin()+n);//右边是闭的reverse(str.begin()+n,str.end());reverse(str.begin(),str.end());return str;}
};

思路3：两倍串  然后直接移动n位再截取

class Solution {
public:string LeftRotateString(string str, int n) { //先局部逆置 再整体逆置int len=str.size();if(len==0||n==0) return str;n%=len;str+=str;return str.substr(n,len);}
};

 三、p51-JZ5 替换空格

替换空格_牛客题霸_牛客网

       假如要求我们在原字符串上操作，我们如果直接遇到一个空格就向后挪。显然复杂度是n^2的，因此我们可以先统计一下空格的数量，然后就可以知道替换后字符串的总长度，然后给字符串扩容，让新指针指向扩容的尾部，让旧指针指向原串的尾部，然后将字符串从后往前挪到后面去（区分遇到普通字符和遇到‘ ’的情况处理）。此时的时间复杂度是n！！

class Solution {
public:string replaceSpace(string s) {// write code hereint count=0;for(auto&ch:s) if(ch==' ') ++count;//统计一下空格的位置//然后要开始从后往前去填 1换3 int oldsize=s.size();int newsize=oldsize+2*count;s.resize(newsize);oldsize--,newsize--;while(oldsize>=0&&newsize>=0)if(s[oldsize]!=' ')//如果不是空格 就赋值s[newsize--]=s[oldsize--];else {//如果是空格s[newsize--]='0';s[newsize--]='2';s[newsize--]='%';--oldsize;}return s;}
};

 根据第一题，我们其实可以在有分隔符的时候使用stringstream,但是该题可能会出现连续的空格，因此不适宜使用

四、p127-JZ20 表示数值的字符串（经典）

表示数值的字符串_牛客题霸_牛客网

1、遵循A[.[B]][e|EC]或者是.B[e|EC] 其中A是整数部分，B是小数部分 C是指数部分

2、小数里可能没有数值的整数部分，比如.123是0.123 整数不是必须的

3、其中A和C都可以用"+"和"-"作为开头 B是无符号整数

4、最多只能有一个.   .的前后或者后面可以有一边没有数字

5.  最多只能有一个E

6、要注意开头和结尾空格的跳过

7、最后检查是否走到结尾时为了确保后面没有出现多余的.和E

#include <cctype>
class Solution {
public:bool isNumeric(string str) {//遵循A[.[B]][e|EC]或者是.B[e|EC] 其中A是整数部分，B是小数部分 C是指数部分//小数里可能没有数值的整数部分，比如.123是0.123 整数不是必须的//其中A和C都可以用"+"和"-"作为开头 B是无符号整数//最多只能有一个.   .后面也可以没有数字 比如if(!str.size()) return false;int n=str.size();//首先要先检查A部分int pos=0;while(pos!=n&&str[pos]==' ')++pos;//处理开头的空格 bool check=checkint(str,pos);if(pos!=n&&str[pos]=='.'){//如果出现了.++pos;check=checkunsignint(str,pos)||check;//因为小数点前面可以没有数字，小数点后面也可以没有数字}if(pos!=n&&(str[pos]=='E'||str[pos]=='e')){++pos;check=check&&checkint(str,pos);}while(pos!=n&&str[pos]==' ')++pos;//处理结尾的空格 return check&&pos==n;//pos==n 是防止后面还有.或者是E }bool checkunsignint(string &str,int&pos){ //检查0-9的数字int before=pos;while(pos!=str.size()&&isdigit(str[pos])) ++pos;return pos>before;//有数字就是true}bool checkint(string &str,int&pos){//检查符号if(str.size()!=pos&&(str[pos]=='+'||str[pos]=='-')) ++pos;return checkunsignint(str,pos);}
};

五、p236-JZ48最长不含重复字符的子字符串（哈希+滑动窗口/动归）

最长不含重复字符的子字符串_牛客题霸_牛客网

一个长度为n的字符串有n^2的子串，去找重复字符有需要n，所以暴力的方法复杂度是n^3。 

解法1：该题因为是子串，我们可以考虑用滑动窗口，然后借助哈希来帮我们查重！！ 

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();if(n==0) return 0;//哈希+滑动窗口unordered_map<char,int>hash;//必须用map,因为该题可能有多重类型字符int ret=1;//记录最长无重复子串//没有出现重复数字就直接丢进去  如果遇见重复的数字，那就不断丢哈希表for(int left=0,right=0;right<n;++right){//表没有的话 就往里丢++hash[s[right]];//走到这说明已经遇到重复的了 那就窗口左移while(hash[s[right]]>1) --hash[s[left++]];//维护子串最大值ret=max(ret,right-left+1);}return ret;}
};

 解法2：动态规划  我们利用哈希表让我们存储出现字符下标的位置，只保存最接近的下标。然后如果我们遇到重复字符的时候，假设当前字符和前面重复字符的距离为d，如果d<=f[i-1]，那就说明f[i-1]的长度是包括这个重复字符的，因此我们只能取这个d作为结果，如果d>f[i-1]，说明f[i-1]不包括这个重复字符，因此我们还是dp[i-1]+1  所以我们发现无论哪种结果都是取d和f[i-1]+1的较小值，即min(dp[i-1]+1,i-hash[i])

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();if(n==0) return 0;//动归unordered_map<char,int>hash;//存的是字符和下标 我们只需要关注最近的上一个重复字符s=' '+s;int ret=1;//dp[i]表示以i位置为结尾时的最长不重复子串 空串有意义vector<int>dp (n+1,1);dp[0]=0;for(int i=1;i<=n;++i){if(hash.find(s[i])==hash.end())  dp[i]=dp[i-1]+1;//如果没有就说明不重复//如果上一个出现的字符距离超过了f[i-1] 那么就还是dp[i-1]+1//但如果上一个字符出现的距离小于或者等于f[i-1] abcabcbb 那距离就是从这个位置开始else dp[i]=min(dp[i-1]+1,i-hash[s[i]]);hash[s[i]]=i;//记录新的下标ret=max(ret,dp[i]);}return ret;}
};

六、p243-JZ50 第一个只出现一次的字符(哈希)

第一个只出现一次的字符_牛客题霸_牛客网

思路：哈希

遍历一次字符串，对于每个字符，放入哈希表中统计出现次数。

再次遍历字符串，对于每个字符，检查哈希表中出现次数是否为1，找到第一个即可。

遍历结束都没找到，那就是没有，返回-1.

class Solution {
public:int FirstNotRepeatingChar(string str) {int n=str.size();if(n==0) return -1;unordered_map<char,int> hash;for(auto&ch:str) ++hash[ch];for(int i=0;i<n;++i) if(hash[str[i]]==1) return i;return -1;}
};

七、扩展p247-JZ50 字符流中第一个出现的字符

字符流中第一个不重复的字符_牛客题霸_牛客网

解法1: 可以用哈希表来记录各个字符出现的次数，根据这样只要是字符串最前面且哈希表中次数为1的字符就是我们要找的。

具体做法：

• step 1：准备一个字符串来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
• step 2：在Insert函数中对输入的字符，加到字符串最后，然后统计出现次数。
• step 3：在FirstAppearingOnce函数遍历该字符串，对于每个字符查找哈希表，返回第一个计数为1的字符，如果遍历完字符串以后都没，则返回#。

class Solution
{
public://Insert one char from stringstreamvoid Insert(char ch) {str+=ch;++hash[ch];}//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {//第一个只出现一次的字符//遍历字符串找到第一个只出现一次的字符for(int i=0;i<str.size();++i)if(hash[str[i]]==1) return str[i];return '#';//没找到的话}
private:unordered_map<char,int> hash;string str;//记录保存的字符流
};

解法2：除了使用字符串记录字符流，还可以用队列记录字符流，每次插入的时候，只需要将第一次出现的字符加入到队列中，然后正常计数。

查找第一个不重复出现的字符的时候，从队首开始查询哈希表，如果出现次数为1，则返回该字符，如果不为1，则从队首将其弹出，因为反正后续也不可能是这个已经重复的字符了。

具体做法：

• step 1：准备一个队列来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
• step 2：在Insert函数中对输入的字符，加到队列最后，然后统计出现次数。
• step 3：在FirstAppearingOnce函数中，不断检查队首元素直到队列为空，队首出现次数为1次，就返回，队首出现次数不为1就弹出。

class Solution
{
public:unordered_map<char, int> mp;queue<char> q;//Insert one char from stringstreamvoid Insert(char ch) {//第一次出现加入队列中if(mp.find(ch) == mp.end()) q.push(ch);//哈希表记录字符出现次数mp[ch]++; }//return the first appearence once char in current stringstreamchar FirstAppearingOnce() {while(!q.empty()){//第一个不重复的字符if(mp[q.front()] == 1) return q.front();//弹出前面的已经重复的字符else q.pop();}//都重复了return '#'; }
};

八、p318-JZ67 把字符串转变成整数(重点看书上的面试细节)

把字符串转换成整数__牛客网

class Solution {
public:int StrToInt(string str) {int n=str.size();if(n==0) return 0;int pos=0;int symbol=1;//最后结果要乘这个表明正负int ret=0;//记录结果if(str[pos]=='-'||str[pos]=='+'){if(str[pos]=='-') symbol=-1;++pos;} while(pos<n&&isdigit(str[pos])) ret=ret*10+str[pos++]-'0';return pos==n?ret*symbol:0;}
};