Bir simli Leetcode həllini böldükdən sonra maksimum bal

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions SimBaxılıb 73

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bölünmədən Sonra problem Maksimum Hesab a Sim Leetcode Solution bizə bir simli təqdim etdi. Verilən sətir yalnız 0 və 1-dən ibarətdir. Beləliklə, onu ikili ardıcıllıq kimi qəbul etmək olar. Problem sonra ipi böldükdən sonra əldə edilə bilən maksimum hesabı tapmağımızı istədi. Sətri böldükdən sonra hesab sol hissədəki 0s və sağ hissədəki 1s sayı kimi qiymətləndirilir. Beləliklə, həmişəki kimi, həll yoluna dalmadan əvvəl. Bir neçə nümunəyə nəzər salaq.

s = "011101"
5

İzahat: Birinci indeksdən sonra simli bölsək, mümkün olan maksimum balın əldə olunacağını asanlıqla görmək olar. Bu şəkildə sağ hissədə dörd 1, sol hissədə tək 0 var.

Bir simli Leetcode həllini böldükdən sonra maksimum balPin

s = "00111"
5

İzahat: Biri asanlıqla başa düşə bilər ki, simi sola yarı bütün 0ları, digər yarı bütün 1ləri əhatə edəcək şəkildə bölsək. Bu şəkildə maksimum bal toplayacağıq. Beləliklə, parçalanma nöqtəsinin indeks 2-də olması lazım olduğunu görmək asandır.

Bir simli Leetcode həllini böldükdən sonra maksimum skor üçün yanaşma

Bir Simli Leetcode Çözümünü Böldükdən Sonra Problem Maksimum Skor, yuxarıda problem təsvirində qeyd edilmişdir. Qısaca, problem bizdən ipi iki yarıya böldükdə əldə edilə bilən maksimum hesabı tapmağımızı istədi. Hesab sol yarıda 0s, sağ yarıda 1s sayına görə qiymətləndirilir. Beləliklə, əvvəlcə verilmiş sətirdə sıfır və olanların ümumi sayını hesablayırıq. İkinci dövrədə indiyə qədər qarşılaşdığımız 0f 0s sayını hesablamağa davam edirik.

Bu döngədən ipin parçalanması prosesini simulyasiya etmək üçün istifadə edirik. İndiyə qədər qarşılaşdıqları sıfırları və bunları saxlayırıq. Sağ yarıda olanlar sol hissədəki 1 sayını çıxarıb asanlıqla hesablana bilər. Cavabı əldə edilə bilən maksimum dəyərlə yeniləməyə davam edirik.

Bir Simli Leetcode Çözümünü Böldükdən Sonra Maksimum Qiymət Kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), yanaşma iki keçidli olsa da, zaman mürəkkəbliyi hələ də xətti olaraq qalır.

Kosmik Mürəkkəblik

O (1), çünki alqoritmdə daimi yer istifadə olunur.

Crack Sistemi Dizayn Müsahibələri
Translate »
1