Сызык Leetcode Чечимин бөлгөндөн кийинки максималдуу упай


Кыйынчылык деңгээли жеңил
Көп суралган Гугл
аркан

Бөлүнгөндөн кийинки максималдуу упай а аркан Leetcode Solution бизге сап менен камсыз кылды. Берилген сапта 0 жана 1 гана камтылган. Ошентип, аны экилик катар катары кароого болот. Көйгөй сапты бөлгөндөн кийин максималдуу упай табууну суранды. Жипти бөлгөндөн кийин, упай сол бөлүктөгү 0 жана оң жарымдагы 1 сан катары бааланат. Ошентип, адаттагыдай эле, эритмеге сүңгүү алдында. Келгиле, бир нече мисалдарды карап көрөлү.

s = "011101"
5

Түшүндүрмө: Биринчи индекстен кийин сапты бөлүп салсак, максималдуу упайга жетүүгө боло тургандыгын оңой эле байкаса болот. Ошентип, оң жарымда төрт 1, сол жакта жалгыз 0 болот.

Сызык Leetcode Чечимин бөлгөндөн кийинки максималдуу упай

s = "00111"
5

Түшүндүрмө: Эгерде жипти бөлүп алсак, сол жарымында бардык 0лер, калган жарымында бардык 1лер камтылаарын оңой эле түшүнсө болот. Ошентип, биз максималдуу упайга ээ болобуз. Демек, бөлүнүү чекити 2 индексинде болушу керектигин байкоо кыйын эмес.

Сызык Leetcode Чечимин бөлгөндөн кийин максималдуу упай алуу ыкмасы

Сызыкты бөлүштүрүүдөн кийинки максималдуу упай көйгөйү Leetcode Solution жогоруда көйгөйдү баяндоодо айтылган. Кыскача айтканда, көйгөй бизди жипти эки бөлүккө бөлүп алсак, эң жогорку баллды табууну суранды. Упай сол жактагы 0 жана оң жарымдагы 1 санына жараша бааланат. Ошентип, адегенде, берилген саптагы нөлдөрдүн жана бирдиктердин жалпы санын эсептейбиз. Экинчи циклде, ушул кезге чейин болгон 0f 0s санын эсептей беребиз.

Бул циклди колдонуп, сапты бөлүү процессин окшоштуруп жатабыз. Буга чейин кездешкен нөлдөрдү жана ошолорду сактайбыз. Оң жарымындагыларды сол жарымындагы 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

Java коду

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), анткени алгоритмде туруктуу мейкиндик колдонулат.