LeetCode【剑指offer】系列（字符串篇）

剑指offer05.替换空格

题目链接

题目：假定一段路径记作字符串path，其中以 “.” 作为分隔符。现需将路径加密，加密方法为将path中的分隔符替换为空格" "，请返回加密后的字符串。

思路：遍历即可。

通过代码：

class Solution {
public:
    string pathEncryption(string path) {
        replace(path.begin(), path.end(), '.', ' ');
        return path;
    }
};

剑指offer20.表示数值的字符串

题目链接

题目：有效数字（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
若干空格

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
1. 至少一位数字，后面跟着一个点 '.'
2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
至少一位数字

部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串s，如果s是一个有效数字，请返回true 。

思路一：模拟。详见代码注释。

通过代码：

class Solution {
public:
    bool zhengshu(string s){
        for(char c : s)
            if(!isdigit(c))
                return false;
        return true;
    }

    bool validNumber(string s) {
        // 去除首尾空格
        s.erase(0, s.find_first_not_of(' '));
        s.erase(s.find_last_not_of(' ') + 1);
        if(s.size() == 0)
            return false;

        // 如果第一位有符号，去掉符号
        if(s[0] == '+' || s[0] == '-')
            s = s.substr(1);
        
        // 先处理指数部分
        int e_pos = s.find('e');
        if(e_pos == s.npos)
            e_pos = s.find('E');
        
        if(e_pos != s.npos)
        {
            string str = s.substr(e_pos + 1); // 截取出e之后的数
            if(str.size() > 0 && (str[0] == '+' || str[0] == '-'))
                str = str.substr(1); // 如果有符号，去掉符号
            if(str.size() == 0 || !zhengshu(str))
                return false;
            s = s.substr(0, e_pos); // 指数部分判断完就扔掉
        }
        
        int point = s.find('.');
        if(point == s.npos) // 处理整数部分
            return s.size() > 0 && zhengshu(s);
        else // 处理小数部分
        {
            string str1 = s.substr(0, point); // 小数点之前的数
            string str2 = s.substr(point + 1); // 小数点之后的数
            if(str1.size() == 0 && str2.size() == 0)
                return false;
            return zhengshu(str1) && zhengshu(str2);
        }
    }
};

思路二：有限状态自动机。

通过代码：

class Solution {
public:
    enum State {
        STATE_INITIAL,
        STATE_INT_SIGN,
        STATE_INTEGER,
        STATE_POINT,
        STATE_POINT_WITHOUT_INT,
        STATE_FRACTION,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END
    };

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_SPACE,
        CHAR_ILLEGAL
    };

    CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9')
            return CHAR_NUMBER;
        else if (ch == 'e' || ch == 'E')
            return CHAR_EXP;
        else if (ch == '.')
            return CHAR_POINT;
        else if (ch == '+' || ch == '-')
            return CHAR_SIGN;
        else if (ch == ' ')
            return CHAR_SPACE;
        else
            return CHAR_ILLEGAL;
    }

    bool validNumber(string s) {
        unordered_map<State, unordered_map<CharType, State>> transfer{
            {STATE_INITIAL,
             {{CHAR_SPACE, STATE_INITIAL},
              {CHAR_NUMBER, STATE_INTEGER},
              {CHAR_POINT, STATE_POINT_WITHOUT_INT},
              {CHAR_SIGN, STATE_INT_SIGN}}},
            {STATE_INT_SIGN,
             {{CHAR_NUMBER, STATE_INTEGER},
              {CHAR_POINT, STATE_POINT_WITHOUT_INT}}},
            {STATE_INTEGER,
             {{CHAR_NUMBER, STATE_INTEGER},
              {CHAR_EXP, STATE_EXP},
              {CHAR_POINT, STATE_POINT},
              {CHAR_SPACE, STATE_END}}},
            {STATE_POINT,
             {{CHAR_NUMBER, STATE_FRACTION},
              {CHAR_EXP, STATE_EXP},
              {CHAR_SPACE, STATE_END}}},
            {STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}}},
            {STATE_FRACTION,
             {{CHAR_NUMBER, STATE_FRACTION},
              {CHAR_EXP, STATE_EXP},
              {CHAR_SPACE, STATE_END}}},
            {STATE_EXP,
             {{CHAR_NUMBER, STATE_EXP_NUMBER}, {CHAR_SIGN, STATE_EXP_SIGN}}},
            {STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}}},
            {STATE_EXP_NUMBER,
             {{CHAR_NUMBER, STATE_EXP_NUMBER}, {CHAR_SPACE, STATE_END}}},
            {STATE_END, {{CHAR_SPACE, STATE_END}}}};

        int len = s.length();
        State st = STATE_INITIAL;

        for (int i = 0; i < len; i++) {
            CharType typ = toCharType(s[i]);
            if (transfer[st].find(typ) == transfer[st].end()) {
                return false;
            } else {
                st = transfer[st][typ];
            }
        }
        return st == STATE_INTEGER || st == STATE_POINT ||
               st == STATE_FRACTION || st == STATE_EXP_NUMBER ||
               st == STATE_END;
    }
};

剑指offer38.字符串的排列

题目链接

题目：某店铺将用于组成套餐的商品记作字符串goods，其中goods[i]表示对应商品。请返回该套餐内所含商品的全部排列方式。

返回结果无顺序要求，但不能含有重复的元素。

思路：深搜+回溯。搜索遍历的时候通过排序去重，如果当前字符和前一个字符一样，并且前一个字符没有用过，就说明这是在同一个递归层中，可以跳过。类似《代码随想录》中的全排列II。

通过代码：

class Solution {
public:
    vector<string> res;
    string str;

    void dfs(int n, string goods, vector<bool>& vis) {
        if (n == goods.size()) {
            res.push_back(str);
            return;
        }
        for (int i = 0; i < goods.size(); i++) {
            if (vis[i] || (i > 0 && !vis[i - 1] && goods[i] == goods[i - 1]))
                continue;

            vis[i] = true;
            str.push_back(goods[i]);
            dfs(n + 1, goods, vis);
            str.pop_back();
            vis[i] = false;
        }
    }

    vector<string> goodsOrder(string goods) {
        vector<bool> vis(goods.size(), false);
        sort(goods.begin(), goods.end());
        dfs(0, goods, vis);
        return res;
    }
};

剑指offer48.最长不含重复字符的子字符串

题目链接

题目：某套连招动作记作序列arr，其中arr[i]为第i个招式的名字。请返回arr中最多可以出连续不重复的多少个招式。

思路：滑动窗口+哈希表。用右边界去遍历字符，遍历的时候用一个哈希表存当前已经遍历过的字符最后出现的下标。如果某个字符已经在哈希表中了，说明左边界要移动到表中记录的下标的后一个位置。左右边界的闭区间就是不重复的字符序列，然后更新最大的长度到res里即可。

通过代码：

class Solution {
public:
    int dismantlingAction(string arr) {
        int res = 0;
        unordered_map<char, int> dic;
        int i = 0;
        for(int j = 0; j < arr.size(); j++)
        {
            if(dic.find(arr[j]) != dic.end())
                i = max(i, dic[arr[j]] + 1);
            dic[arr[j]] = j;
            res = max(res, j - i + 1);
        }
        return res;
    }
};

剑指offer50.第一个只出现一次的字符

题目链接

题目：某套连招动作记作仅由小写字母组成的序列arr，其中arr[i]第i个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。

思路：很明显用哈希表存一下出现的次数。下面是用数组实现的哈希。

通过代码：

class Solution {
public:
    char dismantlingAction(string arr) {
        vector<int> vec(26, 0);
        for(char c : arr)
            vec[c - 'a']++;
        for(char c : arr)
            if(vec[c - 'a'] == 1)
                return c;
        return ' ';
    }
};

但是如果哈希表也能够有顺序就好了，就不用再遍历整个字符串了。由于C++中不提供有序哈希表，所以可能需要再用一个vector存一下哈希表中键的顺序。

class Solution {
public:
    char dismantlingAction(string arr) {
        vector<int> vec(26, 0);
        vector<char> keys;
        for(char c : arr)
        {
            int idx = c - 'a';
            if(vec[idx] == 0)
                keys.push_back(c);
            vec[idx]++;
        }
            
        for(char c : keys)
            if(vec[c - 'a'] == 1)
                return c;
        return ' ';
    }
};

剑指offer58-I.反转单词顺序

题目链接

题目：你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息message转换为正常语序。

注意：输入字符串message中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

思路：由于追求原地解法（空间复杂度O(1)），所以先把整个字符串反转过来，然后依次反转其中每个单词，并处理空格问题（单词前移）。如果不追求原地，新开一个字符串，将原字符串的单词从后往前截取并添加进新字符串即可。

通过代码：

class Solution {
public:
    string reverseMessage(string message) {
        reverse(message.begin(), message.end());
        int idx = 0;
        for(int i = 0; i < message.size(); i++)
        {
            if(message[i] == ' ')
                continue;
            if(idx > 0)
                message[idx++] = ' ';
            int start = idx;
            while(i < message.size() && message[i] != ' ')
                message[idx++] = message[i++];
            reverse(message.begin() + start, message.begin() + idx);
        }
        message.resize(idx);
        return message;
    }
};

剑指offer58-II.左旋转字符串

题目链接

题目：某公司门禁密码使用动态口令技术。初始密码为字符串password，密码更新均遵循以下步骤：

设定一个正整数目标值target
将password前target个字符按原顺序移动至字符串末尾

请返回更新后的密码字符串。

思路：字符串分割后再拼接即可。

通过代码：

class Solution {
public:
    string dynamicPassword(string password, int target) {
        return password.substr(target) + password.substr(0, target);
    }
};

剑指offer67.把字符串转换成整数

题目链接

题目：请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个32位有符号整数（类似C/C++ 中的atoi函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为0 。必要时更改符号（从步骤2开始）。
如果整数数超过32位有符号整数范围[−2^31, 2^31 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−2^31的整数应该被固定为−2^31，大于2^31 − 1的整数应该被固定为2^31 − 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

思路：模拟即可。判断越界的时候不等式里的乘法（加法）移到另一边变成除法（减法）。

通过代码：

class Solution {
public:
    int myAtoi(string str) {
        int UP = pow(2, 31) - 1;
        int DOWN = -pow(2, 31);
        int res = 0, k = 1;
        int i = 0;
        while (i < str.length() && str[i] == ' ')
            i++;
        if (i >= str.length())
            return 0;
        if (str[i] == '-') {
            k = -1;
            i++;
        } else if (str[i] == '+')
            i++;
        while (i < str.length() && str[i] >= '0' && str[i] <= '9') {
            int num = str[i] - '0';
            if (k == 1 && res > UP / 10)
                return UP;
            if (k == -1 && res < DOWN / 10)
                return DOWN;
            res *= 10;
            if(k == 1 && res >= UP - k * num)
                return UP;
            if(k == -1 && res <= DOWN - k * num)
                return DOWN;
            res += k * num;
            i++;
        }
        return res;
    }
};