მაქსიმალური ქულა სტრიქონის Leetcode ამოხსნის გაყოფის შემდეგ


Რთული ტური Easy
ხშირად ეკითხებიან Google
სიმებიანი

პრობლემა მაქსიმალური ქულა გაყოფის შემდეგ a სიმებიანი Leetcode Solution– მა მოგვაწოდა სიმებიანი. მოცემული სტრიქონი შეიცავს მხოლოდ 0-ს და 1-ს. ასე რომ, ის ასევე შეიძლება განვიხილოთ როგორც ორობითი თანმიმდევრობა. შემდეგ პრობლემამ მოგვმართა სტრიქონის გაყოფის შემდეგ მისაღწევი მაქსიმალური ქულა. სტრიქონის გაყოფის შემდეგ, ქულა შეფასებულია, როგორც მარცხენა ნაწილში 0-ების და მარჯვენა ნახევარში 1-ების რიცხვი. ასე ჩვეულებრივად, ხსნარში ჩაყვინთვამდე. მოდით ვნახოთ რამდენიმე მაგალითი.

s = "011101"
5

განმარტება: მარტივად დაინახავს, ​​რომ შესაძლებელია მაქსიმალური ქულის მიღწევა, თუ სტრიქონს გავყოფთ პირველი ინდექსის შემდეგ. ამ გზით ჩვენ გვაქვს ოთხი 1 მარჯვენა ნახევარში და ერთი 0 მარცხენა ნახევარში.

მაქსიმალური ქულა სტრიქონის Leetcode ამოხსნის გაყოფის შემდეგ

s = "00111"
5

განმარტება: მარტივად შეიძლება გაერკვნენ, რომ თუ სტრიქონს გავყოფთ ისე, რომ მარცხენა ნახევარი შეიცავს ყველა 0-ს, ხოლო მეორე ნახევარში შეიცავს ყველა 1-ს. ამ გზით მივიღებთ მაქსიმალურ ქულას. ასე რომ, ადვილი გასაგებია, რომ გაყოფის წერტილი უნდა იყოს ინდექსი 2.

მიახლოებითი ქულის მიდგომა სტრიქონის Leetcode ამოხსნის გაყოფის შემდეგ

პრობლემა მაქსიმალური ქულა სტრიქონის გაყოფის შემდეგ Leetcode Solution უკვე აღწერილია ზემოთ პრობლემის აღწერაში. მოკლედ, პრობლემამ გვთხოვა მაქსიმალური ქულის პოვნა, რომლის მიღწევაც შეიძლება, თუ სტრიქონს ორ ნაწილად გავყოფთ. ქულა ფასდება მარცხენა ნახევარში 0-ების და მარჯვენა ნახევარში 1-ების რაოდენობის მიხედვით. ამრიგად, პირველ რიგში, გამოვთვლით მოცემულ სტრიქონში ნულებისა და ერთების მთლიან რაოდენობას. მეორე მარყუჟში, ჩვენ ვაგრძელებთ აქამდე ნაპოვნი 0f 0-ების გამოთვლას.

ჩვენ ვიყენებთ ამ მარყუჟს სიმების გაყოფის პროცესის სიმულაციაზე. ჩვენ ვინახავთ ნულებსა და აქამდე არსებულ ნულებს. მარჯვენა ნახევარში ადვილად გამოითვლება მარცხენა ნახევარში 1-ის რაოდენობის გამოკლებით. ჩვენ განვაგრძობთ პასუხის განახლებას მაქსიმალური მნიშვნელობით, რომლის მიღებაც შესაძლებელია.

კოპირება მაქსიმალური ქულისთვის სიმებიანი Leetcode ამოხსნის გაყოფის შემდეგ

C ++ კოდი

#include <bits/stdc++.h>
using namespace std;

int maxScore(string s) {
    int zero = 0, one = 0;
    for(int i=0;i<s.size();i++)
        (s[i] == '0') ? zero++ : one++;
    int curZero = (s[0] == '0'), curOne = (s[0] == '1');
    int ans = curZero + one - curOne;
    for(int i=1;i<s.size()-1;i++){
        (s[i] == '0') ? curZero++ : curOne++;
        ans = max(ans, curZero + one - curOne);
    }
    return ans;
}

int main(){
    cout<<maxScore("00111");
}
5

ჯავის კოდი

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int maxScore(String s) {
        int one = 0, zero = 0;
        for(int i=0;i<s.length();i++)
            if(s.charAt(i) == '0')
                zero++;
            else
                one++;
        int curZero = (s.charAt(0) == '0' ? 1 : 0), curOne = (s.charAt(0) == '1' ? 1 : 0);
        int ans = curZero + one - curOne;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i) == '0')curZero++;
            else curOne++;
            ans = Math.max(ans, curZero + one-curOne);
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(maxScore("00111"));
  }
}
5

სირთულის ანალიზი

დროის სირთულე

O (N), მიუხედავად იმისა, რომ მიდგომა ორპასიანია, დროის სირთულე კვლავ ხაზოვანია.

სივრცის სირთულე

O (1), რადგან ალგორითმში მუდმივი სივრცეა გამოყენებული.