>source

import java.util.Scanner;
class Motu
 {
    //Returns length of the longest subsequence
    //of the form 0*1*0*
    public static int longestSubseq(String s)
    {
        int n= s.length();
        //Precomputing values in three arrays
        //pre_count_0[i] is going to store count
        //of 0s in prefix str[0..i-1]
        //pre_count_1[i] is going to store count
        //of 1s in prefix str[0..i-1]
        //post_count_0[i] is going to store count
        //of 0s in suffix str[i-1..n-1]
        //int[] pre_count_0= new int[n + 2];
        int[] count_1= new int[n + 1];
        count_1[0]= 0;
        for (int j= 1; j <= n; j++)
         {
            count_1[j]= count_1[j -1];
            if (s.charAt(j -1) != '0')
                 count_1[j]++;
         }
        //Compute result using precomputed values
        int ans= 0;
        for (int i= 1; i <= n; i++)
            for (int j= i; j <= n; j++)
                ans= Math.max(count_1[j] -count_1[i -1] , ans);
        return ans;
     }
    //Driver code
    public static void main(String[] args)
    {
        @SuppressWarnings("resource")
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        System.out.println(longestSubseq(s));
    }
}

0과 &를 포함하는 문자열에서 최대 시퀀스 1을 얻기 위해 프로그램을 만들려고 합니다. 1.하지만 그것에 대한 논리를 만들 수 없습니다. 내 프로그램은 내가 원하는 출력이 아닌 문자열에 1의 번호를 인쇄합니다.

Sample input:-0011100111100
output:-4

1을 찾으면 각 문자에 대해 반복해야 하며 0을 찾을 때 계산을 시작해야 합니다. 새 카운트가 이전 카운트보다 높으면 카운터를 재설정하고 "최대" 변수를 업데이트해야 합니다.

Jawad El Fou2021-11-20 19:09:11

귀하의 의견은 code와 관련이 없습니다. 예를 들어 pre_count_0 및 post_count_0 변수가 없습니다. 어쨌든 code를 단순화하는 것이 좋습니다. 이 문제를 어떻게 해결할 수 있을지 머릿속으로 상상해 보십시오. 가장 긴 시퀀스가 ​​무엇인지 알기 위해 0의 모든 부분 시퀀스의 길이를 알아야 합니까? 1000자리의 시퀀스로도 그렇게 할 수 있고 0의 각 하위 시퀀스 길이를 마음에 저장하지 않기 때문이 아니라고 생각합니다. 따라서 code에 동일한 논리를 적용해 보십시오. code가 훨씬 이해하기 쉬울 것입니다.

Davide Lorenzo MARINO2021-11-20 19:09:11
  • 답변 # 1

    생성기를 사용하여 연속 1의 롤링 카운트를 유지할 수 있습니다. 카운터는 0을 찾으면 재설정됩니다. 마지막에 다음 시퀀스의 최대값을 취합니다.

    def count_sequence(s):
        m= int(s[0])
        for i in range(1, len(s)):
            this_int= int(s[i])
            m= m + this_int if this_int > 0 else 0
            yield m
    s= "0011100111100"
    print(max([x for x in max_sequence(s)]))
    

  • 답변 # 2

    당신은 꽤 훌륭하지만 한 가지를 놓치고 있습니다.'0': 카운터를 0으로 재설정

    for (int j= 1; j <= n; j++) {
        if (s.charAt(j -1) != '0')
            count_1[j]= count_1[j -1] + 1;
        else
            count_1[j]= 0;
    }
    


    하지만 이는 하나의 루프에서만 수행할 수 있습니다.정수, 최대값을 추적합니다.

    public static int longestSubseq(String s) {
        int ans= 0;
        int count= 0;
        for (char c : s.toCharArray()) {
            if (c== '1')
                count++;
            else
                count= 0;
            ans= Math.max(ans, count);
        }
        return ans;
    }
    

    @azro 제안 주셔서 감사합니다. 카운터를 0으로 재설정하는 else 문을 추가했습니다. 프로그램이 제대로 작동하고 있습니다.

    Mahesh Divate2021-11-20 19:09:11

    @ScaryWombat은 가장 긴 하위 시퀀스를 추적합니까?

    azro2021-11-20 19:09:11
  • 답변 # 3

    for 루프와 함께 작동하는 다른 답변에 대한 대안:

    정규식을 사용하여 시퀀스를 그룹으로 나눌 수 있습니다. 다음으로, 그룹의 길이가 이전 길이보다 큰 경우 그룹을 반복하고 개수를 업데이트합니다.

    첫 번째 그룹은111그리고 다음1111. 따라서 처음에는 3이 된 다음 4로 업데이트됩니다.

    import java.util.regex.Pattern;
    import java.util.regex.Matcher;
    public class CountSubsequence {
         public static void main(String []args){
            String sequence= "0011100111100";
            Pattern pattern= Pattern.compile("(1+)");
            Matcher matcher= pattern.matcher(sequence);
            int count= 0;
            while (matcher.find()) {
                int currentLength= matcher.group().length();
                if (currentLength > count) count= currentLength;
            }
            System.out.println(count); //4
         }
    }
    

    정규식은 성능이 좋지 않기 때문에 성능에 관심이 있는 경우 for 루프를 사용하는 것이 좋습니다. 하지만 많이 실행하는 경우에만 중요합니다.

  • 답변 # 4

    입력 문자열은 아닌문자로 분할될 수 있습니다.1(따라서 1이 아닌 모든 문자는 무시되고 1개만 포함하는 하위 시퀀스가 ​​남음) 나머지 부분의 최대 길이는 Stream API를 사용하여 찾을 수 있습니다.

    public static int longestSubSequence(String str, char ch) {
        return Arrays.stream(str.split("[^" + ch + "]"))
                     .mapToInt(String::length)
                     .max()
                     .orElse(0);
    }
    

    마찬가지로 일치하는패턴을 생성할 수 있으며 그룹의 최대 길이를 찾을 수 있습니다.

    public static int longestSubSequence(String str, char ch) {
        return Pattern.compile(ch + "+")
                .matcher(str)
                .results()
                .map(MatchResult::group)
                .mapToInt(String::length)
                .max()
                .orElse(0);
    }
    

    테스트:

    System.out.println(longestSubSequence("00111011001111", '1')); //4
    

    이외의 캐릭터는 언급할 가치가 있습니다.'0'그리고'1'입력 문자열에 존재할 수 있으며, 주어진 char의 하위 시퀀스만 계산됩니다.

  • 답변 # 5

    public static int longestSubSequence(String str, char ch) {
        int res= 0;
        int count= 0;
        for (int i= 0; i < str.length(); i++) {
            count= str.charAt(i)== ch ? count + 1 : 0;
            res= Math.max(res, count);
        }
        return res;
    }
    

  • 이전 laravel : 필수 매개변수가 누락되었습니다.
  • 다음 javascript : jquery에서 다른 라디오 버튼을 선택한 후 텍스트 상자 지우기