牛客竞赛小白试炼（20201205 怕npy的牛牛）
程序员文章站
2022-07-09 13:48:21
...
文章目录
一、题目
1. 题目描述
牛牛非常怕他的女朋友，怕到了走火入魔的程度，以至于每当他看到一个字符串同时含有n,p,y三个字母他都害怕的不行。现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x，牛牛想知道能令他不害怕的最长子串的长度是多少。（对于字符串”abc”来说，”c”,”ab”都是原串的子串，但”ac”不是原串子串）
2. 示例
示例1
输入：“abcdefghijklmn”
输出：14
示例2
输入：“ynp”
输出：2
示例3
输入：“ypknnbpiyc”
输出：7
3. 题目解析
要注意本题要求找的子串是相邻字符组成的，若整个字符串都符合则可以直接返回原字符串。
二、个人解法
1. 代码
想到了用双指针法来解决，但是没想好如何处理指针的移动，忘记保存失败代码。
2. 失败反思
for循环不好考虑的问题可以转换到while循环中来考虑，可能条理能清晰些。
三、官网高星解法
1. 双指针滑动窗口
（1）解法分析
- 使用while循环在字符串上移动hou指针，每次移动都应该有一个符合条件的目前最长子串，遍历结束后返回最长即为所求。
- 每次hou移动的当前子串，可能会同时包含npy，因此需要再来一个qian指针，从头开始遍历，使得子串符合条件。
- 使用一个长度为3的数组，来存储当前子串中npy三个字符出现数量，这样比直接判断npy要省事。
（2）代码
/**
* 滑动窗口
* @param x
* @return
*/
public int Maximunlength(String x) {
int[] npy = new int[3];
int qian = 0;
int hou = 0;
int len = 0;
// 后指针不断往后走
while (hou < x.length()) {
// 遇到npy，分别给他们计数
if (x.charAt(hou) == 'n') {
npy[0]++;
}
if (x.charAt(hou) == 'p') {
npy[1]++;
}
if (x.charAt(hou) == 'y') {
npy[2]++;
}
// hou指针每走一步，应该都会产生一个目前的最长子串，qian指针从前往后遍历找前边界
while (qian < x.length() && (npy[0] > 0 && npy[1] > 0 && npy[2] > 0)) {
if (x.charAt(qian) == 'n') {
npy[0]--;
}
if (x.charAt(qian) == 'p') {
npy[1]--;
}
if (x.charAt(qian) == 'y') {
npy[2]--;
}
qian++;
}
//计算以当前的hou结尾的最长子串长度
len = Math.max(len, hou - qian + 1);
hou++;
}
return len;
}
（3）算法分析
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
（4）提交截图
2. 分割法
（1）解法分析
因为要求找的子串是不同时含有npy，那我们分别以n p y作为分割点来分割我们的字符串，在产生的所有子串中，肯定不会同时有npy出现，我们只需要在所有子串中寻找长度最大的即可。
（2）代码
public int Maximunlength(String x) {
String[] ns = x.split("n");
String[] ps = x.split("p");
String[] ys = x.split("y");
int len = 0;
for (int i = 0; i < ns.length; i++) {
if (len < ns[i].length()) {
len = ns[i].length();
}
}
for (int i = 0; i < ps.length; i++) {
if (len < ps[i].length()) {
len = ps[i].length();
}
}
for (int i = 0; i < ys.length; i++) {
if (len < ys[i].length()) {
len = ys[i].length();
}
}
return len;
}
（3）算法分析
这种方法肯定比第一种方法耗费空间和时间，但是量级没有发生改变，代码写起来轻松。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
（4） 提交截图
可发现运行时间和占用内存均比第一种方法高。