स्ट्रिंग लीटकोड सोल्यूशन विभाजित केल्यानंतर कमाल स्कोर


अडचण पातळी सोपे
वारंवार विचारले Google
अक्षरमाळा

समस्या विभाजनानंतर कमाल स्कोर अक्षरमाळा लीटकोड सोल्यूशनने आम्हाला एक स्ट्रिंग प्रदान केली. दिलेल्या स्ट्रिंगमध्ये केवळ 0 आणि 1 असते. म्हणून कोणीही बायनरी अनुक्रम म्हणून विचार करू शकतो. त्यानंतर समस्येने स्ट्रिंग विभाजित केल्यावर आम्हाला जास्तीत जास्त स्कोअर प्राप्त करण्यास सांगितले. स्ट्रिंगचे विभाजन केल्यावर डाव्या भागामध्ये 0 से संख्या आणि उजव्या अर्ध्या भागामध्ये 1 चे संख्या म्हणून गुणांचे मूल्यांकन केले जाते. सोल्यूशनमध्ये जाण्यापूर्वी नेहमीप्रमाणे. चला काही उदाहरणे पाहू या.

s = "011101"
5

स्पष्टीकरणः एखादी व्यक्ती सहजतेने पाहू शकते की जर आम्ही पहिल्या निर्देशांका नंतर स्ट्रिंग विभाजित केले तर जास्तीत जास्त स्कोअर मिळवता येईल. अशा प्रकारे आपल्याकडे उजवीकडे अर्ध्यामध्ये चार 1s आणि डाव्या अर्ध्या भागामध्ये एकच 0 आहे.

स्ट्रिंग लीटकोड सोल्यूशन विभाजित केल्यानंतर कमाल स्कोर

s = "00111"
5

स्पष्टीकरणः एखादी व्यक्ती सहजपणे शोधू शकते की जर आपण अशा स्ट्रिंगचे विभाजन केले तर डाव्या अर्ध्यामध्ये सर्व 0s आणि दुसर्‍या अर्ध्यामध्ये सर्व 1s समाविष्ट आहेत. अशा प्रकारे आम्ही जास्तीत जास्त स्कोअर प्राप्त करू. तर हे पाहणे सोपे आहे की विभाजनाचा बिंदू निर्देशांक 2 वर असावा.

स्ट्रिंग लीटकोड सोल्यूशन विभाजनानंतर जास्तीत जास्त स्कोअरसाठी दृष्टीकोन

स्ट्रिंग लीटकोड सोल्यूशन विभाजित केल्या नंतर समस्या जास्तीत जास्त स्कोअर आधीच समस्येच्या वर्णनात वर नमूद केले गेले आहे. थोडक्यात, समस्येने आम्हाला स्ट्रिंग दोन भागात विभाजित केल्यास प्राप्त करता येणारे जास्तीत जास्त स्कोअर शोधण्यास सांगितले. डाव्या अर्ध्या भागामध्ये 0 च्या संख्येनुसार आणि उजव्या अर्ध्यामध्ये 1 से नुसार गुणांचे मूल्यांकन केले जाते. तर, प्रथम आम्ही दिलेल्या स्ट्रिंगमध्ये शून्य आणि त्यांची एकूण संख्या काढू. दुसर्‍या लूपमध्ये आम्ही आतापर्यंत 0 0 XNUMX XNUMX चे संख्या मोजत आहोत.

स्ट्रिंग विभाजित करण्याच्या प्रक्रियेचे नक्कल करण्यासाठी आम्ही हे लूप वापरतो. आम्ही आतापर्यंत आलेल्या शून्य आणि एक संचयित करतो. डाव्या अर्ध्या भागातील 1s ची संख्या वजा करुन सहज अर्ध्या भागाची गणना केली जाऊ शकते. आम्ही उत्तर मिळवू शकतो त्या जास्तीत जास्त मूल्यासह अद्यतनित करीत आहोत.

स्ट्रिंग लीटकोड सोल्यूशन विभाजित केल्यावर जास्तीत जास्त स्कोअरसाठी कोड

सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), दृष्टिकोन दोन-पास असूनही, वेळ गुंतागुंत अद्याप रेखीय असणे बाकी आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण अल्गोरिदममध्ये निरंतर जागा वापरली जातात.