رشته ای را در حلقه های کد متعادل رشته ها تقسیم کنید


سطح دشواری ساده
اغلب در بلومبرگ آزمایشگاه های والمارت
حریص رشته

بیان مسأله

در این مشکل ، به ما داده می شود رشته از کاراکترها ، حاوی تنها "R" و "L" است. اگر یک رشته به همان تعداد R و L باشد ، ما متعادل می نامیم. می توانیم رشته داده شده را به زیر رشته های جدا از هم تقسیم کنیم. هدف یافتن حداکثر تعداد رشته های تقسیم متعادل است.

توجه داشته باشید:

  • رشته داده شده متعادل است.
  • طول رشته در محدوده قرار دارد: [1 ، 1000]
  • فقط "L" و "R" در ورودی وجود دارد

مثال

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

شرح:

رشته ای را در حلقه های کد متعادل رشته ها تقسیم کنید

 

رویکرد (حریص)

بنابراین ، حداقل 1 تقسیم متعادل ممکن خواهیم داشت. اکنون ، برای بدست آوردن حداکثر تعداد پارتیشن ، باید این تعداد تقسیم را به حداکثر برسانیم. بصری ، ما می توانیم آن را حل کنیم با حرص. ما رشته را رد می کنیم و در هر نقطه ای که تعداد برابر L و R دریافت کرده ایم ، تعداد مقاطع ممکن را افزایش می دهیم. به این ترتیب ، ما هر راه حل برای یک رشته تقسیم متعادل را در نظر خواهیم گرفت.

پیاده سازی تقسیم یک رشته در رشته های متعادل راه حل کد

برنامه 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

تجزیه و تحلیل پیچیدگی تقسیم یک رشته در رشته های متعادل راه حل کد

پیچیدگی زمان

O (N) ، N = طول رشته. پیچیدگی زمان خطی است زیرا ما یک رشته کل رشته را رد می کنیم.

پیچیدگی فضا 

O (1)، زیرا ما فقط از فضای حافظه ثابت استفاده می کنیم.