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


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

بیان مسأله  

در این مشکل ، به ما داده می شود رشته از کاراکترها ، حاوی تنها "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 = طول رشته. پیچیدگی زمان خطی است زیرا ما یک رشته کل رشته را رد می کنیم.

همچنین مشاهده کنید
تقاطع محلول Leetcode دو آرایه II

پیچیدگی فضا 

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

1