C++实现LeetCode(159.最多有两个不同字符的最长子串)
作者:Grandyang 发布时间:2023-06-20 22:39:46
[LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:
Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.
Example 2:
Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.
这道题给我们一个字符串,让求最多有两个不同字符的最长子串。那么首先想到的是用 HashMap 来做,HashMap 记录每个字符的出现次数,然后如果 HashMap 中的映射数量超过两个的时候,这里需要删掉一个映射,比如此时 HashMap 中e有2个,c有1个,此时把b也存入了 HashMap,那么就有三对映射了,这时 left 是0,先从e开始,映射值减1,此时e还有1个,不删除,left 自增1。这时 HashMap 里还有三对映射,此时 left 是1,那么到c了,映射值减1,此时e映射为0,将e从 HashMap 中删除,left 自增1,然后更新结果为 i - left + 1,以此类推直至遍历完整个字符串,参见代码如下:
解法一:
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int res = 0, left = 0;
unordered_map<char, int> m;
for (int i = 0; i < s.size(); ++i) {
++m[s[i]];
while (m.size() > 2) {
if (--m[s[left]] == 0) m.erase(s[left]);
++left;
}
res = max(res, i - left + 1);
}
return res;
}
};
我们除了用 HashMap 来映射字符出现的个数,还可以映射每个字符最新的坐标,比如题目中的例子 "eceba",遇到第一个e,映射其坐标0,遇到c,映射其坐标1,遇到第二个e时,映射其坐标2,当遇到b时,映射其坐标3,每次都判断当前 HashMap 中的映射数,如果大于2的时候,那么需要删掉一个映射,还是从 left=0 时开始向右找,看每个字符在 HashMap 中的映射值是否等于当前坐标 left,比如第一个e,HashMap 此时映射值为2,不等于 left 的0,那么 left 自增1,遇到c的时候,HashMap 中c的映射值是1,和此时的 left 相同,那么我们把c删掉,left 自增1,再更新结果,以此类推直至遍历完整个字符串,参见代码如下:
解法二:
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int res = 0, left = 0;
unordered_map<char, int> m;
for (int i = 0; i < s.size(); ++i) {
m[s[i]] = i;
while (m.size() > 2) {
if (m[s[left]] == left) m.erase(s[left]);
++left;
}
res = max(res, i - left + 1);
}
return res;
}
};
后来又在网上看到了一种解法,这种解法是维护一个 sliding window,指针 left 指向起始位置,right 指向 window 的最后一个位置,用于定位 left 的下一个跳转位置,思路如下:
1. 若当前字符和前一个字符相同,继续循环。
2. 若不同,看当前字符和 right 指的字符是否相同
(1) 若相同,left 不变,右边跳到 i - 1
(2) 若不同,更新结果,left 变为 right+1,right 变为 i - 1
最后需要注意在循环结束后,还要比较结果 res 和 s.size() - left 的大小,返回大的,这是由于如果字符串是 "ecebaaa",那么当 left=3 时,i=5,6 的时候,都是继续循环,当i加到7时,跳出了循环,而此时正确答案应为 "baaa" 这4个字符,而我们的结果 res 只更新到了 "ece" 这3个字符,所以最后要判断 s.size() - left 和结果 res 的大小。
另外需要说明的是这种解法仅适用于于不同字符数为2个的情况,如果为k个的话,还是需要用上面两种解法。
解法三:
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int left = 0, right = -1, res = 0;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == s[i - 1]) continue;
if (right >= 0 && s[right] != s[i]) {
res = max(res, i - left);
left = right + 1;
}
right = i - 1;
}
return max(s.size() - left, res);
}
};
还有一种不使用 HashMap 的解法,是在做 Fruit Into Baskets 这道题的时候在论坛上看到的,其实这两道题除了背景设定之外没有任何的区别,代码基本上都可以拷来直接用的。这里使用若干的变量,其中 cur 为当前最长子串的长度,first 和 second 为当前候选子串中的两个不同的字符,cntLast 为 second 字符的连续长度。遍历所有字符,假如遇到的字符是 first 和 second 中的任意一个,那么 cur 可以自增1,否则 cntLast 自增1,因为若是新字符的话,默认已经将 first 字符淘汰了,此时候选字符串由 second 字符和这个新字符构成,所以当前长度是 cntLast+1。然后再来更新 cntLast,假如当前字符等于 second 的话,cntLast 自增1,否则均重置为1,因为 cntLast 统计的就是 second 字符的连续长度。然后再来判断若当前字符不等于 second,则此时 first 赋值为 second, second 赋值为新字符。最后不要忘了用 cur 来更新结果 res,参见代码如下:
解法四:
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int res = 0, cur = 0, cntLast = 0;
char first, second;
for (char c : s) {
cur = (c == first || c == second) ? cur + 1 : cntLast + 1;
cntLast = (c == second) ? cntLast + 1 : 1;
if (c != second) {
first = second; second = c;
}
res = max(res, cur);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/159
类似题目:
Fruit Into Baskets
Longest Substring Without Repeating Characters
Sliding Window Maximum
Longest Substring with At Most K Distinct Characters
Subarrays with K Different Integers
参考资料:
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49759/Share-my-c%2B%2B-solution
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49687/Clean-11-lines-AC-answer-O(1)-space-O(n)-time.
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49682/Simple-O(n)-java-solution-easily-extend-to-k-characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/discuss/49708/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.
来源:https://www.cnblogs.com/grandyang/p/5185561.html
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- java调用Rsync并发迁移数据并执行校验java代码如下RsyncFile.javaimport lombok.NoArgsConstr
- 缘起经过前面三章的入门,我们大概了解了Mybatis的主线逻辑是什么样子的,在本章中,我们将正式进入Mybatis的源码海洋。Mybatis
- 指针是什么?指针(Pointer)是一个特殊的变量,它里面存储的数值被解释成为内存里的一个地址。换句话说就是可以通过指针找到以它为地址的内存
- 点九图片的拉伸区域不难理解,显示内容区域是怎样的?.9 ,是andriod平台的应用软件开发里的一种特殊的图片形式,文件扩展名为:.9.pn
- 目录 * 仓库的配置1、 下载sonatype Nexus来搭建 * 2 安装nexus服务3、创建 * 仓库4、配置 * 信息中央仓库的配置三个仓
- SQLite是Android自带的关系型数据库,是一个基于文件的轻量级数据库。Android提供了3种操作数据的方式,SharedPrefe
- public interface AttributeSet { /** * Retur
- java常量池技术java中常量池技术说的通俗点就是java级别的缓存技术,方便快捷的创建一个对象。当需要一个对象时,从池中去获取(如果池中
- 新建项目IDEA上方工具栏点击:文件->新建->模块此时的目录结构:需要在main文件夹下补全两个文件夹,点击main,右键-&
- 1.基本介绍代码块又称为初始化块,属于类中的成员(类的一部分),类似于方法,讲逻辑语句封装在方法体中,用{}抱起来;但和方法不同,没有方法名
- 用JAVA实现一个简单的电话本管理系统,能存储100个人的姓名、性别、年龄、电话等信息,并能对此系统进行增删改查的操作。部分代码如下:pub
- 读取resources下文件的方法网上有问答如下:问:new FileInputStream("src/main/resource
- 获取网络信息需要在AndroidManifest.xml文件中加入相应的权限。 <uses-permission android:na
- 前言:上午写代码时还好好的,下午不知道怎么回事突然就不显示logcat日志了,觉得很奇怪,于是开始找各种解决办法!现象如图所示,logcat
- 获取Android的ROOT权限其实很简单,只要在Runtime下执行命令"su"就可以了。// 获取ROOT权限pub
- 本文实例讲述了Android实现ListView数据动态加载的方法。分享给大家供大家参考,具体如下:list.setOnScrollList
- 英文意思随机数可以做什么?生成一些随机的数字用途非常的广泛, 例如随机抽取数据库的一条记录,把生成的数字给变量,某一个时间点执行一些代码,随
- 1、文件分为ASCII文件和二进制文件,ASCII文件也称文本文件,由一系列字符组成,文件中存储的是每个字符的ASCII码值。2、FILE
- 用函数指针变量调用函数指针变量也可以指向一个函数。一个函数在编译时被分配给一个入口地址。这个函数入口地址就称为函数的指针。可以用一个指针变量
- 1.Semaphore的概述public class Semaphore extends Object implements Seriali