Leetcode 4.18

Leetcode

1.无重复字符的最长子串
2.最长回文子串
3.整数反转
4.字符串转换整数 (atoi)
5.正则表达式匹配

1.无重复字符的最长子串

无重复字符的最长子串
滑动窗口，先让右指针右移，如果发现这个子串有元素和右指针当前元素重复。
则：

左指针右移，直到移除重复元素为止。
怎么计算是否有重复？用unordered_map维护子串个数，删除的话数量响应减少，如果count == 0 则将元素erase
随时更新ans长度，用mp.size()可以轻松算出长度

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        if (s.size() <= 1) return s.size();
        int l = 0, r = 0;
        unordered_map<char, int> mp;
        while (l <= r && r < s.size()) {
            //当有重复元素时，移动左指针，直到删除了左侧重复元素
            while (mp.count(s[r]) != 0) {
                //重复元素左侧元素都得依次删除
                mp[s[l]]--;
                if (mp[s[l]] == 0) mp.erase(s[l]);
                l++;
            }

            //添加右侧元素，此时已经不重复了
            mp[s[r]]++;
            ans = max(ans, (int)mp.size());  
            r++;
        }
        return ans;
    }
};

2.最长回文子串

最长回文子串
两个要点：

判断是否为回文串 —> 分奇偶数，l,r指针分别指向头尾，观察r–,l++是否相等
是否为最长—> 可以用ans维护最长的个数

暴力解法：可以双重循环，依次判断是否为回文串。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string ans = s.substr(0, 1);
        if (n <= 1) return s;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (j - i + 1 > ans.size() && ispalindorme(s, i ,j)) {
                    ans = s.substr(i, j - i + 1);
                }
            }
        }
        return ans;
    }
    bool ispalindorme(string s, int l, int r) {
        while (r >= l) {
            if (s[l] != s[r]) {
                return false;
            }
            l++, r--;
        }
        return true;
    }
};

中心扩散法:
给定一个字符串，从中间到两边扩散，判断从左到右范围内最长的回文子串长度。
考虑到奇偶数的不同情况，需要调用两次中心扩散函数。

class Solution {
public:
    string res;
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;
        for (int i = 0; i < n; i++) {
            extandformmid(s, i, i);
            extandformmid(s, i, i+1);
        }
        return res;
    }

    void extandformmid(string& str, int left, int right) {
        while (left >= 0 && right < str.size() && str[left] == str[right]) {
            left--;
            right++;
        }
        if (right - left - 1 > res.size()) {
            res = str.substr(left + 1, right - left - 1);
        }
    }
};

3.整数反转

整数反转
用ans保存反转后的答案。
在处理数字的过程中判断ans是否有溢出情况发生。
在这里插入图片描述

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while (x) {
            if (ans < INT_MIN / 10 || ans > INT_MAX / 10) {
                return 0;
            }
            ans = ans * 10 + (x % 10);
            x= x / 10;
        }
        return ans;
    }
};

4.字符串转换整数 (atoi)

字符串转换整数 (atoi)
去除前导空格—> while删除
检查正负号—> 有则按照符号，无则为正
读入字符—> ans = ans * 10 + digt
整数范围—>如果下一次ans * 10会溢出，则直接返回这次的结果

class Solution {
public:
    int myAtoi(string s) {
        int ans = 0; int flag = 1;
        int index = 0, n = s.size();
        //删除空格
        while (index < n && s[index] == ' ') index++;
        //检查符号
        if (index < n) {
            if (s[index] == '-') {
                flag = -1;
                index++;
            } else if (s[index] == '+'){
                flag = 1;
                index++;
            }
        }
        //读入字符
        while (index < n && isdigit(s[index])) {
            int dig = s[index] - '0';
            //注意这里严格按照推理所得的公式计算
            if (ans > (INT_MAX - dig) / 10) {
                return flag == 1 ? INT_MAX : INT_MIN;
            }
            ans = ans * 10 + dig;
            index++;
        }
        return ans * flag;
    }
};

5.正则表达式匹配

正则表达式匹配
子串匹配的题目，不由自主的先想DP。

DP分两步：
定义状态
定义状态转移方程

状态
dp[i][j]表示s[…i]与p[…j]是否能够匹配。dp[s.size()-1][p.size()-1]即为本题答案。
状态转移
- 当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true：
  - dp[i][j - 2]：即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配。
  - dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配。
  - dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配。
- 当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true
  - dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]：即让字符 p[j - 1] 多出现一次时，能否匹配。
  - dp[i - 1][j - 1] 且 p[j - 1] = '.'：即将字符 . 看作字符 s[i - 1] 时，能否匹配。

p[j-1] == '*'的情况下
1. dp[i][j-2] == True # * 匹配0次，然后s不变，让p[(j-1)-1]匹配0次，相当于消除了一个字符，这里之所以用 [j-2] 是因为相当于 *号和它前面的个字符被丢掉了
2. p[j-2] == s[i-1] and dp[i-1][j] == True # * 匹配多次，这里的多次是可以让前面的1次累加起来的，所以相当于让 * 匹配1次，这里之所以是dp[i-1][j]是因为匹配了一次s中的最后一个字符，所以可以相当于丢掉s中的字符，但是p中的 *和它前面的字符并没有被消耗掉，因为*号可以匹配任意次
3. p[j-2] == '.' and dp[i-1][j] == True # 这里要注意这里表示*号前面是个'.' 而 '.'可以匹配任意字符，所以'.*'可以表示成 … 是上面2中的 p[j-2] == s[i-1] 一种特例
在这里插入图片描述

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size() + 1, m = p.size() + 1;
        vector<vector<bool>> dp(n, vector<bool> (m, false));
        int i = 1, j = 1;
        //空字符串可以匹配
        dp[0][0] = true;

        // 初始化首行
        for(int j = 2; j < m; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';


        for(int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (p[j - 1] == '*') {
                    if (dp[i - 1][j] && s[i - 1] == p[j - 2]) {
                        dp[i][j] = true;
                    //上上个元素为. ， 让.多出现几次
                    } else if (dp[i - 1][j] && p[j - 2] == '.') {
                        dp[i][j] = true;
                    //j - 2，指上一个元素为0
                    } else if (dp[i][j - 2]) {
                        dp[i][j] = true;
                    }
                } else {
                    //匹配上了
                    if (dp[i - 1][j - 1] && s[i - 1] == p[j - 1]) {
                        dp[i][j] = true;
                    //是'.'
                    } else if (dp[i - 1][j - 1] && p[j - 1] == '.') {
                        dp[i][j] = true;
                    }
                }
            }
        }
        //
        return dp[n - 1][m - 1];
    }
};