Լարային կոդերի լուծում տրոհելուց հետո առավելագույն միավոր


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Google
String

Խնդիրը Առավելագույն միավորը պառակտումից հետո ա String Leetcode Solution- ը մեզ տող է տրամադրել: Տրված տողը պարունակում է ընդամենը 0 և 1. Այսպիսով, կարելի է նաև այն համարել որպես երկուական հաջորդականություն: Դրանից հետո խնդիրը մեզ խնդրեց գտնել տողը բաժանելուց հետո առավելագույն միավորը, որը հնարավոր է ձեռք բերել: Լարը բաժանելուց հետո հաշիվը գնահատվում է որպես ձախ մասի 0-ների և աջ կեսի 1-ների քանակ: Այսպիսով, ինչպես միշտ, լուծույթի մեջ սուզվելուց առաջ: Եկեք նայենք մի քանի օրինակների:

s = "011101"
5

Բացատրություն. Կարելի է հեշտությամբ տեսնել, որ հնարավոր առավելագույն միավորը կարելի է ձեռք բերել, եթե տողը բաժանենք առաջին ցուցանիշից հետո: Այդ կերպ մենք ունենք աջ 1-ում չորս 0, իսկ ձախ կեսում ՝ XNUMX:

Լարային կոդերի լուծում տրոհելուց հետո առավելագույն միավոր

s = "00111"
5

Բացատրություն. Կարելի է հեշտությամբ հասկանալ, որ եթե տողը բաժանենք այնպես, որ ձախ կեսը պարունակի բոլոր 0-ները, իսկ մյուս կեսը `բոլոր 1-երը: Այդպիսով մենք կստանանք առավելագույն միավոր: Այսպիսով, հեշտ է տեսնել, որ պառակտման կետը պետք է լինի 2-րդ ինդեքսում:

Լարային կոդերի լուծում տրոհելուց հետո առավելագույն գնահատականի մոտեցում

Տողի Leetcode լուծումը պառակտելուց հետո առավելագույն միավորը խնդիրը վերը նշված է խնդրի նկարագրության մեջ: Կարճ ասած, խնդիրը խնդրեց մեզ գտնել առավելագույն միավորը, որը կարելի է ստանալ, եթե լարը բաժանենք երկու մասի: Հաշիվը գնահատվում է ըստ ձախ կեսի 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

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), չնայած մոտեցումը երկու անցում է, ժամանակի բարդությունը դեռ մնում է գծային:

Տիեզերական բարդություն

O (1), քանի որ ալգորիթմում օգտագործվում է մշտական ​​տարածություն: