hiho一下第243周《hiho字符串》题目分析

3
0

《hiho字符串》题目分析

本题是一道比较常见的双指针(或滑动窗口)题目

首先值得注意的是题目要求找到S的子串“恰好”包含2个h、1个i和1个o,不是“至少”包含。

本题的思路就是枚举子串的起点位置L=0, 1, 2, ... |S|-1, O(|S|); 然后找到一个最短的,也就是右端点R最小的、使得S[L..R]“至少”包含2个h、1个i和1个o。

然后判断S[L..R]是不是“恰好”包含2个h、1个i和1个o;如果是,我们就找到了一个答案,就用R-L+1更新当前最短的答案。

本题可以用双指针(或滑动窗口),奥妙就在于,当我们要枚举下一个起点L时,即令L=i变成L=i+1时,新的R(i+1)一定在R(i)的右边。

这样R不用从L+1开始计算,总的复杂度就是O(|S|)的了。

2 answer(s)

0

package test2; import java.util.Scanner; public class Test{

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int res = solve(s);
    System.out.println(res);    
}

private static int solve(String s) {
    char a[] = s.toCharArray();
    int j = 0;
    int len = Integer.MAX_VALUE;
    int begin = 0;
    int end = -1;
    for(int i = 0;i<s.length();i++){
        char c = a[i];
        if(!check(c))continue;
        if(j==0)j=i+1;

                if(j-i+1>=4&&j<a.length&&containAll(a,i,j)){
            if(check(a,i,j)&&j-i+1<len){
                len = j - i + 1;
                begin = i;
                end = j;
            }
        }
        while(j<a.length){
            c = a[j];
            if(!check(c)){
                j++;
                continue;
            }
            if(containAll(a,i,j)){
                if(check(a,i,j)&&j-i+1<len){
                    len = j - i + 1;
                    begin = i;
                    end = j;
                }
                break;
            }
                          j++;
        }
    }
        //print(a,begin,end);
    return len==Integer.MAX_VALUE?-1:len;
}

private static void print(char[] a, int begin, int end) {
    System.out.print(begin+" "+end);
    for(int i = begin;i<=end;i++){
        System.out.print(a[i]);
    }    
}

private static boolean check(char[] a, int i, int j) {
       int c1 = 0,c2 = 0,c3 = 0;
    for(int k = i;k<=j;k++){
        if(a[k]=='h')c1++;
        if(a[k]=='i')c2++;
        if(a[k]=='o')c3++;
    }
    return c1==2&&c2==1&&c3==1;
}

private static boolean containAll(char[] a, int i, int j) {
    int c1 = 0,c2 = 0,c3 = 0;
    for(int k = i;k<=j;k++){
        if(a[k]=='h')c1++;
        if(a[k]=='i')c2++;
        if(a[k]=='o')c3++;
    }
    return c1>=2&&c2>=1&&c3>=1;
}

private static boolean check(char c) {
    return c=='h'||c=='i'||c=='o';
}

}

0

public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); int res = solve(s); System.out.println(res);
}

private static int solve(String s) { char a[] = s.toCharArray(); int j = 0; int len = Integer.MAX_VALUE; int begin = 0; int end = -1; for(int i = 0;i

            if(j-i+1>=4&&j<a.length&&containAll(a,i,j)){
        if(check(a,i,j)&&j-i+1<len){
            len = j - i + 1;
            begin = i;
            end = j;
        }
    }
    while(j<a.length){
        c = a[j];
        if(!check(c)){
            j++;
            continue;
        }
        if(containAll(a,i,j)){
            if(check(a,i,j)&&j-i+1<len){
                len = j - i + 1;
                begin = i;
                end = j;
            }
            break;
        }
                      j++;
    }
}
    //print(a,begin,end);
return len==Integer.MAX_VALUE?-1:len;

}

private static void print(char[] a, int begin, int end) { System.out.print(begin+" "+end); for(int i = begin;i<=end;i++){ System.out.print(a[i]); }
}

private static boolean check(char[] a, int i, int j) { int c1 = 0,c2 = 0,c3 = 0; for(int k = i;k<=j;k++){ if(a[k]=='h')c1++; if(a[k]=='i')c2++; if(a[k]=='o')c3++; } return c1==2&&c2==1&&c3==1; }

private static boolean containAll(char[] a, int i, int j) { int c1 = 0,c2 = 0,c3 = 0; for(int k = i;k<=j;k++){ if(a[k]=='h')c1++; if(a[k]=='i')c2++; if(a[k]=='o')c3++; } return c1>=2&&c2>=1&&c3>=1; }

private static boolean check(char c) { return c=='h'||c=='i'||c=='o'; }

write answer 切换为英文 切换为中文


转发分享