გაყოფილი გაწონასწორებული სტრიქონების სიმები Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Bloomberg Walmart Labs
ხარბ სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ გვეძლევა ა სიმებიანი სიმბოლოების, რომლებიც შეიცავს მხოლოდ "R" და "L". სიმებს დაბალანსებულს ვუწოდებთ, თუ მას აქვს იგივე რაოდენობის 'R' და 'L'. მოცემული სტრიქონი შეგვიძლია დავყოთ ცალკეულ ქვესადგურებად. მიზანი არის დაბალანსებული გაყოფილი სტრიქონების მაქსიმალური რაოდენობის პოვნა.

შენიშვნა:

  • მოცემული სტრიქონი დაბალანსებულია.
  • სიმების სიგრძე მდებარეობს დიაპაზონში: [1, 1000]
  • მხოლოდ 'L' და 'R' მოცემულია შესავალში

მაგალითი

s = "RLRRLLRLRL"
4
s = "RLLLLRRRLR"
3

განმარტება:

გაყოფილი გაწონასწორებული სტრიქონების სიმები Leetcode Solution

 

მიდგომა (ხარბი)

ამიტომ, მინიმუმ 1 შესაძლო დაბალანსებული გაყოფილი გვექნება. ახლა, ჩვენ უნდა გავაუმჯობესოთ დანაწევრებების რაოდენობა, რომ მიიღოთ დანაყოფების მაქსიმალური რაოდენობა. ინტუიციურად, ჩვენ შეგვიძლია მისი მოგვარება ხარბად. ჩვენ გადავკვეთთ სტრიქონს და ნებისმიერ წერტილში, სადაც მივიღეთ თანაბარი რიცხვი 'L's და' R ', ჩვენ გაზრდის შესაძლო მონაკვეთების რაოდენობას. ამ გზით, ჩვენ გავითვალისწინებთ ყველა გამოსავალს დაბალანსებული გაყოფილი სტრიქონისთვის.

განხეთქილების სტრიქონის განხორციელება დაბალანსებულ სტრიქონებში Leetcode ამოხსნაში

C ++ პროგრამა

#include <bits/stdc++.h>

using namespace std;

int balancedStringSplit(string s) {
    int balance = 0 , splits = 0;
    for(char &c : s) {
        balance += (c == 'L' ? -1 : 1);
        if(balance == 0)
            splits++;
    }
    return splits;
}

int main() {
    string s = "RLRRLLRLRL";
    cout << balancedStringSplit(s) << endl;
    return 0;
}

ჯავა პროგრამა

import java.util.*;
import java.io.*;

class balanced_splits {
    public static int balancedStringSplit(String s) {
        int balance = 0 , splits = 0;
        for(int i = 0 ; i < s.length() ; i++) {
            char c = s.charAt(i);
            balance += (c == 'L' ? -1 : 1);
            if(balance == 0)
                splits++;
        }
        return splits;
    }

    public static void main(String args[]) {
        String s = "RLRRLLRLRL";
        System.out.println(balancedStringSplit(s));
    }
}
4

დაბალანსებული სიმების Leetcode ამოხსნის სტრიქონის გაყოფის სირთულის ანალიზი

დროის სირთულე

O (N), N = სტრიქონის სიგრძე. დროის სირთულე წრფივია, რადგან მთელ სტრიქონს ერთხელ გადავკვეთთ.

სივრცის სირთულე 

O (1), რადგან ჩვენ ვიყენებთ მხოლოდ მუდმივ მეხსიერების ადგილს.