Leetcode 4.18

本文主要是介绍Leetcode 4.18，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

1. 左指针右移，直到移除重复元素为止。
2. 怎么计算是否有重复？用unordered_map维护子串个数，删除的话数量响应减少，如果count == 0 则将元素erase
3. 随时更新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.最长回文子串

最长回文子串
两个要点：

1. 判断是否为回文串 —> 分奇偶数，l,r指针分别指向头尾，观察r–,l++是否相等
2. 是否为最长—> 可以用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];}
};

这篇关于Leetcode 4.18的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---