Максимальний бал після розбиття рядкового рішення з використанням Леткоду


Рівень складності Легко
Часто запитують у Google
рядок

Проблема Максимальний бал після розділення a рядок Рішення Leetcode надало нам рядок. Наведений рядок містить лише 0 і 1. Отже, його також можна розглядати як двійкову послідовність. Потім проблема попросила нас знайти максимальну оцінку, досяжну після розбиття рядка. Після розбиття рядка оцінка оцінюється як кількість 0 в лівій частині та кількість 1 в правій половині. Як зазвичай, перед зануренням у розчин. Давайте розглянемо кілька прикладів.

s = "011101"
5

Пояснення: Можна легко побачити, що максимально можливий бал може бути досягнутий, якщо розділити рядок після першого індексу. Таким чином ми маємо чотири одиниці в правій половині та одиницю 1 у лівій половині.

Максимальний бал після розбиття рядкового рішення з використанням Леткоду

s = "00111"
5

Пояснення: Можна легко зрозуміти, що якщо розділити рядок таким чином, щоб ліва половина містила всі 0, а інша половина - всі 1. Таким чином ми отримаємо максимальний бал. Отже, неважко помітити, що точка розщеплення повинна бути на позначці 2.

Підхід до отримання максимального балу після розбиття струнного рішення з використанням Леткоду

Максимальна оцінка проблеми після розбиття рядка Рішення штрих-коду вже було зазначено вище в описі проблеми. Коротше кажучи, проблема попросила нас знайти максимальну оцінку, яку можна досягти, якщо розділити рядок на дві половини. Оцінка оцінюється за кількістю 0 в лівій половині та 1 секунді в правій половині. Отже, спочатку ми обчислюємо загальну кількість нулів та одиниць у даному рядку. У другому циклі ми продовжуємо обчислювати число 0f 0s, що зустрічалося до цього часу.

Ми використовуємо цей цикл для імітації процесу розбиття рядка. Ми зберігаємо нулі та одиниці, які зустрічались до цього часу. Ті, що знаходяться в правій половині, можна легко обчислити, віднявши кількість 1s у лівій половині. Ми продовжуємо оновлювати відповідь з максимальним значенням, яке може бути досягнуте.

Код для максимального балу після розбиття рядкового рішення Leetcode

Код С ++

#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), оскільки в алгоритмі використовується постійний простір.