अधिकतम स्कोर स्ट्रि Le लेटकोड समाधान विभाजन पछि


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
घागो

समस्या अधिकतम स्कोर विभाजित पछि घागो लेटकोड समाधानले हामीलाई स्ट्रि with प्रदान गरेको छ। दिइएको स्ट्रिले ० र १ मात्र समावेश गर्दछ। त्यसैले कसैले पनि यसलाई बाइनरी अनुक्रमका रूपमा विचार गर्न सक्दछ। समस्याले हामीलाई स्ट्रि after विभाजन गरेपछि प्राप्त गर्न सक्ने अधिकतम स्कोर पत्ता लगाउन भन्यो। स्ट्रि split विभाजित गरेपछि स्कोर दायाँ आधामा ० से ० को संख्या र दायाँ आधा १ को संख्याको रूपमा मूल्या is्कन गरिन्छ। सामान्यको रूपमा, समाधानमा डाइभिंग गर्नु अघि। आउनुहोस् हामी केही उदाहरणहरू हेरौं।

s = "011101"
5

स्पष्टीकरण: एकले सजिलैसँग हेर्न सक्दछ कि अधिकतम स्कोर प्राप्त गर्न सकिन्छ यदि हामीले पहिलो सूचकांक पछि स्ट्रिंग विभाजित गर्‍यौं भने। यो तरिकाले हामीसँग दाँया आधा चार चार छ र बायाँ आधामा एकल ० छ।

अधिकतम स्कोर स्ट्रि Le लेटकोड समाधान विभाजन पछि

s = "00111"
5

स्पष्टीकरण: एक सजिलै पत्ता लगाउन सक्दछ कि यदि हामीले स्ट्रिंगलाई विभाजित गर्‍यौं भने बायाँ आधाले सबै ० हरू समावेश गर्दछ र अन्य आधाले सबै १s समावेश गर्दछ। यस तरिका हामी अधिकतम स्कोर प्राप्त गर्नेछौं। त्यसोभए, यो सजीलो छ कि विभाजन को विन्दु २ मा हुनु पर्छ।

स्ट्रिंग लेटकोड समाधान विभाजन गरेपछि अधिकतम स्कोरको लागि दृष्टिकोण

स्ट्रिंग लेटकोड समाधान विभाजन गरेपछि समस्या अधिकतम स्कोर समस्या माथि वर्णन गरिसकिएको छ। संक्षिप्तमा, समस्याले हामीलाई अधिकतम स्कोर पत्ता लगाउन भन्यो यदि हामीले स्ट्रिंगलाई दुई भागमा विभाजित गर्यौं भने प्राप्त गर्न सकिन्छ। बायाँ आधा मा ० से ० र दायाँ आधा १ को संख्या अनुसार स्कोर मूल्या The्कन गरिन्छ। त्यसो भए, पहिले हामी दिइएका स्ट्रि inमा शून्य र व्यक्तिको कुल संख्या गणना गर्दछौं। दोस्रो लूपमा हामी अहिले सम्म ०ff ० सेकेन्डको गणना गर्न जारी राख्छौं।

हामी यो लूप प्रयोग गर्दै छौं स्ट्रिंग विभाजनको प्रक्रिया अनुकरण गर्न। हामीले शून्यहरू र स्टोरहरू गरेका छौं जुन अहिले सम्म आयो। बायाँ आधामा १s को संख्या घटाएर सजिलै गणना गर्न सकिन्छ। हामी प्राप्त गर्न सकिने अधिकतम मूल्यको साथ उत्तर अपडेट गर्न जारी राख्छौं।

अधिकतम स्कोर को लागी स्ट्रिंग 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), जे होस् दृष्टिकोण दुई पास छ, समय जटिलता अझै लाईनियर हुन।

ठाउँ जटिलता

O (१), किनभने स्थिर स्थान एल्गोरिथ्ममा प्रयोग भएको छ।