首页 > 试题广场 >

怕npy的牛牛

[编程题]怕npy的牛牛
  • 热度指数:180 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x,求字符串中不同时含有n,p,y三个字母的最长字串的长度是多少?。(对于字符串”abc”来说,”c”,”ab”都是原串的子串,但”ac”不是原串子串)


示例1

输入

"abcdefghijklmn"

输出

14

说明

因为所有子串都不同时含有n,p,y,所以最长子串的长度即为字符串x的长度14。

示例2

输入

"ynp"

输出

2

说明

长度为2的字串”yn”,”np”都符合题意,不存在长度>=3的符合条件的子串。

示例3

输入

"ypknnbpiyc"

输出

7

说明

“pknnbpi”为其符合条件的最长子串,长度为7。


备注:

对于的数据

对于的数据

函数共有一个参数,即题目描述中的字符串x,保证字符串中字母均为小写字母
注意,所给字符串不含引号
双指针做法,不断检查[left, right]子串中是否同时包含npy三个字符:
(1) 不同时包含则右移右指针;
(2) 同时包含则右移左指针,直到不同时包含npy为止。
每次到(1)的情况,都需要更新此时的最长子串长度
class Solution:
    def Maximumlength(self , x ):
        # write code here
        left, right = 0, 0
        res = 0
        counter = dict(n=0, p=0, y=0)
        while right < len(x):
            if x[right] in "npy":
                counter[x[right]] += 1
            while counter['n'] and counter['p'] and counter['y']:
                if x[left] in "npy" and counter[x[left]]:
                    counter[x[left]] -= 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

编辑于 2021-05-18 18:52:30 回复(0)
public class Solution {
    public int Maximumlength (String x) {
        // write code here
        int max = 0;
        int left = 0,right = 0;
        int n = 0,p = 0,y = 0;
        while(right < x.length()){
            if(x.charAt(right) == 'n') n ++;
            else if(x.charAt(right) == 'p') p ++;
            else if(x.charAt(right) == 'y') y ++;
            if(n >= 1 && p >= 1 && y >= 1){
                if(x.charAt(left) == 'n') n --;
                else if(x.charAt(left) == 'p') p --;
                else if(x.charAt(left) == 'y') y --;
                left ++;
            }
            right ++;
            max = Math.max(max,right - left);
        }
        return max;
    }
}

发表于 2021-07-14 21:19:49 回复(0)
主要思路就是:
1、用set集合记录经过了多少个n、p、y,只要不重复的经历个数不到3,是可以一直计算下去的,直到字符串结尾;一旦不重复的个数达到3个则表示计算结束,继续进行下一次遍历。
2、遍历之前需要判断剩下的子串中还能不能找到大于目前最大的符合要求的子串长度,减少遍历次数
public static int npy(String str) {
        int max = 0;
        //用来存放途经的n、p、y,因为集合不能重复,所以经过重复的n、p、y也只能算一个
        Set<Character> set = new HashSet<>();
        //转换成字符数组
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int count = 0;
            //最大可能长度都不可能大于最大长度了就没必要再进行测试下去了
            if (chars.length-i<=max){
                break;
            }
            for (int j = i; j < chars.length; j++) {
                //只要不是n、p、y直接加1
                if (chars[j] != 'n' && chars[j] != 'p' && chars[j] != 'y') {
                    count++;
                } else {
                    //是n、p、y其中一个直接加入set,然后看是不是已经把n、p、y全部途经了,没有继续加以
                    set.add(chars[j]);
                    if (set.size() == 3) {
                        break;
                    } else {
                        count++;
                    }
                }
            }
            if (count > max) {
                max = count;
            }
            //清空集合数据,重新计算途经的n、p、y个数
            set.clear();
        }
        return max;
    }


编辑于 2021-05-20 20:09:13 回复(0)