الحد الأقصى من النقاط بعد تقسيم حل Leetcode المتسلسل


مستوى الصعوبة سهل
كثيرا ما يطلب في جوجل
خيط

مشكلة الحد الأقصى من النقاط بعد التقسيم أ خيط زودنا Leetcode Solution بسلسلة. تحتوي السلسلة المحددة على 0 و 1. لذلك يمكن للمرء أيضًا اعتبارها سلسلة ثنائية. ثم طلبت منا المشكلة إيجاد الدرجة القصوى التي يمكن تحقيقها بعد تقسيم السلسلة. بعد تقسيم السلسلة ، يتم تقييم الدرجة على أنها عدد 0s في الجزء الأيسر وعدد 1s في النصف الأيمن. كالمعتاد ، قبل الغوص في الحل. دعونا نلقي نظرة على بعض الأمثلة.

s = "011101"
5

التفسير: يمكن للمرء أن يرى بسهولة أنه يمكن تحقيق أقصى درجة ممكنة إذا قمنا بتقسيم السلسلة بعد الفهرس الأول. بهذه الطريقة يكون لدينا أربعة آحاد في النصف الأيمن وصفر واحد في النصف الأيسر.

الحد الأقصى من النقاط بعد تقسيم حل Leetcode المتسلسل

s = "00111"
5

التفسير: يمكن للمرء أن يكتشف بسهولة أنه إذا قسمنا السلسلة بحيث احتوى النصف الأيسر على جميع الأصفار والنصف الآخر يحتوي على جميع الآحاد. بهذه الطريقة سوف نحصل على الدرجة القصوى. لذلك ، من السهل ملاحظة أن نقطة الانقسام يجب أن تكون عند الفهرس 0.

نهج لأقصى درجة بعد تقسيم حل Leetcode سلسلة

تم بالفعل ذكر مشكلة Maximum Score بعد تقسيم String Leetcode Solution أعلاه في وصف المشكلة. باختصار ، طلبت منا المسألة إيجاد الدرجة القصوى التي يمكن تحقيقها إذا قسمنا الخيط إلى نصفين. يتم تقييم النتيجة وفقًا لعدد 0 ثانية في النصف الأيسر و 1 ثانية في النصف الأيمن. لذلك ، نحسب أولاً العدد الإجمالي للأصفار والآحاد في السلسلة المحددة. في الحلقة الثانية ، نستمر في حساب الرقم 0f 0s الذي تمت مواجهته حتى الآن.

نحن نستخدم هذه الحلقة لمحاكاة عملية تقسيم السلسلة. نقوم بتخزين الأصفار والآحاد التي تمت مواجهتها حتى الآن. يمكن حساب الآحاد الموجودة في النصف الأيمن بسهولة عن طريق طرح عدد الآحاد في النصف الأيسر. نستمر في تحديث الإجابة بأقصى قيمة يمكن تحقيقها.

رمز الحد الأقصى من النقاط بعد تقسيم حل 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) على الرغم من أن هذا النهج عبارة عن تمريرين ، إلا أن التعقيد الزمني لا يزال خطيًا.

تعقيد الفضاء

يا (1) ، لأنه يتم استخدام مساحة ثابتة في الخوارزمية.