字符串处理

字符串比较

165.比较版本号

这一题说实话想得复杂了，将一段纯数字字符串转换为正确的数字类型，只需要采取进位相加的方式就行了。一段确定一个数字

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int n = version1.size(), m = version2.size();
        int i = 0, j = 0;
        while(i < n || j < m){
            int num1 = 0;
            for(; i < n &&version1[i] != '.'; i++){
                num1 = num1*10 + version1[i] - '0';
            }
            i++;
            int num2 = 0;
            for(; j < m&&version2[j] != '.'; j++){
                num2 = num2*10 + version2[j] - '0';
            }
            j++;
            if(num1 != num2){
                return num1 > num2 ? 1 : -1;
            }
        }
        return 0;
    }
};

242. 有效的字母异位词（数组存储频率）、

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
        return false;
        vector<int> count(26);
        for(int i = 0; i < s.size(); i++){
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        for(int i = 0; i < 25; i++){
            if(count[i] != 0)
            return false;
        }
        return true;
    }
};

205. 同构字符串(数组)

• 也是用数组解决的

• 记录两个字符串每个位置的字符第一次出现的位置，如果两个字符串中相同位置的字符与它们第一次出现的位置一样，那么这两个字符串同构。

  class Solution {
  public:
    bool isIsomorphic(string s, string t) {
        vector<int> first1(128,0),first2(128, 0);
        for(int i = 0; i < s.length(); i ++){
            if(first1[s[i]] != first2[t[i]])
            return false;
            first1[s[i]] = first2[t[i]] = i + 1;//能走到这一步就代表前面的等式也成立了。
        }
        return true;
    }
  };

  696. 计数二进制子串

• 使用pre来记录前一个元素出现的次数，cur记录当前元素出现的次数

• 每次当pre大于或者等于前面元素出现的次数时，就记录下来

  class Solution {
  public:
    int countBinarySubstrings(string s) {
        int pre = 0, cur = 1, count = 0;
        for(int i = 1; i < s.size(); i++){
            if(s[i] == s[i-1]){
                ++cur;
            } else {
                pre = cur;
                cur = 1;
            }
            if(pre >= cur){
                ++count;
            }
        }
        return count;
    }
  };

  3. 无重复字符的最长子串(哈希表+滑动窗口)

• 简单哈希表，使用滑动窗口维护，哈希表的所有值都不能大于1

  class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ans = 0;
        if(n<2){
            return n;
        }
        unordered_map<char, int> hash;
        for(int i = 0, j = 0; i < n; i++){
                hash[s[i]]++;
                while(hash[s[i]]!=1&&j<i){
                    hash[s[j]]--;
                    j++;
                }
                ans = max(ans, i-j+1);
        }
        return ans;
    }
  };

  字符串理解

  227. 基本计算器 II（经典）

• 可以在字符串前面增加一个+号，然后将字符串分割成（运算符， 数字）形式，这样就可以从左往右处理了，

• 由于乘除的优先级高于加减，因此我们需要使用一个中间变量来存储高优先度的运算。
• 这里还需要考虑到两个连在一起的数字

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {//判断s[i]是不是数字
                num = num * 10 + int(s[i] - '0');//这里是计算多位数的情况
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {//如果是运算符，或者是最后一位，则计算num
            //千万注意，这里的运算符使用的是上一次的运算符
                switch (preSign) {
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;//这里因为乘法有优先级
                        break;
                    default:
                        stk.back() /= num;//出发也是一样。
                }
                preSign = s[i];//前一个符号
                num = 0;//当遇到一个符号之后前一个num置零
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};
//想法很好，如果是加号则直接入栈，减号则加负号入栈，乘除都是先计算后入栈、

409. 最长回文串（哈希表）

class Solution {
public:
    int longestPalindrome(string s) {
        int n = s.size(), ans = 0;
        unordered_map<char, int> hash;
        for(auto it : s){
            hash[it]++;
        }
        for(auto it: hash){
            if(it.second%2==0){
                ans+=it.second;
            } else {
                ans+=it.second-1;
            }
        }
        return ans<n? ans+1:ans;
    }
};

522. 最长特殊序列 II（脑筋急转弯）

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        auto is_subseq = [](const string& s, const string& t) -> bool {
            int pt_s = 0, pt_t = 0;
            while (pt_s < s.size() && pt_t < t.size()) {
                if (s[pt_s] == t[pt_t]) {
                    ++pt_s;
                }
                ++pt_t;
            }
            return pt_s == s.size();
        };
        int n = strs.size();
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            bool check = true;
            for (int j = 0; j < n; ++j) {
                if (i != j && is_subseq(strs[i], strs[j])) {//如果当前字符串不是其他任意字符串的子串，则一定为特殊字符串。因为如果子串是特殊字符串，那么当前字符串也一定是特殊字符串！！！
                //因为如果子串是特殊字符串那么，你在这个子串的基础上添加任何字符，也是特殊字符串。
                    check = false;
                    break;
                }
            }
            if (check) {
                ans = max(ans, static_cast<int>(strs[i].size()));
            }
        }
        return ans;
    }
};

556. 下一个更大元素 III（整数转字符串）

将整数转化为字符串，然后从后往前寻找并且交换，保持交换之后的字符串的后面是最小排序。

class Solution {
public:
    int nextGreaterElement(int n) {
        string tmp = to_string(n);
        int i = tmp.size()-1;
        while(i > 0&& tmp[i] <= tmp[i-1]) i--;//从后往前找到第一个比后面值小的位置，也就是可以交换的位置i-1。
        if(i > 0) {
            int j = tmp.size()-1;
            while(j > 0&& tmp[j] <= tmp[i-1]) j--;//从后往前找到第一个比i-1位置的值大的位置，也就是用于交换的值。
            swap(tmp[j], tmp[i-1]);//交换两个位置的值
            reverse(tmp.begin() + i, tmp.end());//将交换位置i-1之后的值应该就是后面排列的最大值，将它们反转，取最小值。
        } else {
            return -1;
        }
        auto ans = stol(tmp);
        return ans > INT_MAX ? -1 : ans;
    }
};

字符串匹配

KMP

参考连接：

https://www.zhihu.com/question/21923021/answer/281346746
https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

28. 实现 strStr()（KMP算法，多练习）

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        vector<int>next(m, -1);
        for(int i = 1, j = -1; i < m; i++) {
            while(j!=-1&&p[j+1]!= p[i]) j = next[j];
            if(p[i] == p[j+1]) j++;
            next[i] = j;
        }
        for(int j = -1, i = 0; i < n; i++) {
            while(j!=-1&&s[i]!=p[j+1]) j = next[j];
            if(s[i] == p[j+1]) j++;
            if(j == m-1) return i-m+1;
        }
        return -1;
    }
};

字符串模拟

388. 文件的最长绝对路径（恶心至极）

哈希表+模拟

class Solution {
public:
    int lengthLongestPath(string input) {
        int n = input.size();
        unordered_map<int, string> mp;//哈系表存储前面的每一级目录，键为目录，值为目录具体字符串。
        bool have;
        string str;
        int ans = 0, i = 0;
        while(i < n) {
            int cnt = 0;
            str = "";
            while(i < n && input[i] == '\t') {//有多少个\t就代表有几级目录，也就是最终字符串有几个反斜杠
                ++cnt;
                ++i;
            }
            have = false;
            while(i < n && input[i] != '\n') {
                if(input[i] == '.') have = true;//只有文件名才有点，have为true的时候代表到了末尾。
                str += input[i];
                ++i;
            }
            ++i;//这里的++i跳过\n
            mp[cnt] = str;//存入哈系表
            if(have) {
                int sum = str.size();
                for(int i = 0; i < cnt; ++i) {//前面的每一级目录，
                    sum += mp[i].size();
                }
                ans = max(ans, sum + cnt);//这里加上cnt是因为最终有多少个 \t就代表最终字符串有多少\。
            }
        }
        return ans;
    }
};