剑指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 here
        int 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 stringstream
    void Insert(char ch) {
         str+=ch;
         ++hash[ch];
    }
  //return the first appearence once char in current stringstream
    char 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 stringstream
    void Insert(char ch) {
        //第一次出现加入队列中
        if(mp.find(ch) == mp.end()) 
            q.push(ch);
        //哈希表记录字符出现次数
        mp[ch]++; 
    }
    //return the first appearence once char in current stringstream
    char 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;
    }
};