افزایش محلول کد کد رشته ای


سطح دشواری ساده
اغلب در پایتخت آکونا
مرتب سازی رشته

مسئله افزایش کاهش رشته راه حل کد بیان می کند که به ما یک a داده می شود رشته به عنوان ورودی ما باید ورودی را اصلاح کنیم. یا همانطور که سوال بیان می شود ، باید آن را مرتب کنیم. اصطلاح مرتب سازی در اینجا لزوماً به معنی مرتب سازی ساده کاراکترها نیست. ما رشته را به ترتیب خاصی مرتب خواهیم کرد که ابتدا حروف را به ترتیب کاملاً در حال افزایش مرتب کنیم تا زمانی که به شخصیت در حال افزایش برسیم. و هنگامی که به بزرگترین نویسه می رسیم ، شروع به ترتیب دادن حروف به ترتیب کاملاً کاهنده می کنیم که از بزرگترین نویسه موجود شروع می شود. ما باید این روند را تکرار کنیم تا زمانی که از کل کاراکترهای رشته استفاده شود. بنابراین طبق معمول ، ابتدا چند نمونه را بررسی می کنیم.

افزایش محلول کد کد رشته ای

s = "aaaabbbbcccc"
"abccbaabccba"

توضیح: همانطور که در بالا گفته شد ، رشته مرتب شده باید از الگوی خاصی پیروی کند. ابتدا شخصیت ها باید الگوی کاملاً در حال افزایش و سپس الگوی کاهشی باشند. خروجی در اینجا از همان الگوی پیروی می کند. رشته با شروع می شود a و الگویی کاملاً فزاینده را دنبال می کند تا اینکه c. سپس دوباره با شروع c به پایان می رسد با a. این روند تکرار می شود تا حروف رشته ورودی تمام شود.

s = "rat"
"art"

توضیحات: رشته مرتب شده (نتیجه) با کوچکترین کاراکتر شروع می شود و از همان الگو پیروی می کند تا اینکه بدون هیچ کاراکتر باقی بمانیم.

رویکرد برای افزایش محلول کد کد رشته ای

مسئله افزایش کاهش رشته راه حل Leetcode از ما خواست که رشته ورودی داده شده را به روشی خاص مرتب کنیم. این الگو در بالا با جزئیات شرح داده شده است. به طور خلاصه ، نویسه های ورودی را ابتدا به ترتیب کاملاً افزایش یافته و سپس با ترتیب کاملاً کاهشی مرتب کنید تا جایی که هیچ کاراکتری باقی نماند. بنابراین ، ما یک آرایه فرکانس برای ذخیره تعداد هر کاراکتر در ورودی ایجاد می کنیم. سپس به سادگی یک حلقه روی آرایه فرکانس اجرا می کنیم تا تمام شخصیت های موجود در آن خسته شوند.

حلقه خارجی اجرا می شود تا زمانی که در آرایه فرکانس نویسه (فرکانس بیشتر از 1) وجود داشته باشد. حلقه داخلی کاراکتر را در یک رشته موقت اضافه می کند. این رشته موقت بسته به پیچ به جواب اضافه می شود. اگر هنگام اضافه شدن رشته موقتی ، اولین چرخش باشد ، به همان ترتیب افزایش یافته اضافه می شود. اما اگر یک چرخش یکنواخت باشد ، پس از آن رشته قبل از افزودن برای پاسخگویی معکوس می شود. پس از فرسودگی شخصیت ها در آرایه فرکانس. الگوریتم رشته پاسخ جدیدی را به عملکرد فراخواننده برمی گرداند.

رمز

کد ++ C برای افزایش محلول کاهش کد رشته

#include <bits/stdc++.h>
using namespace std;

string sortString(string s) {
    vector<int> frq(26, 0);
    for(auto x: s)
        frq[x-'a']++;
    int par = false;
    string ans = "";
    bool can = false;
    do{
        can = false;
        string ss = "";
        for(int i=0;i<26;i++)
            if(frq[i]){
                ss += (char)(i+'a');
                frq[i]--;
                can |= (frq[i] > 0);
            }
        if(par == true)
            reverse(ss.begin(), ss.end());
        par ^= 1;
        ans += ss;
    } while(can);
    return ans;
}

int main()
{
    cout<<sortString("aaaabbbbcccc");
}
abccbaabccba

کد جاوا برای افزایش راه حل کد کد رشته ای

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

class Main
{
  public static String sortString(String s) {
        ArrayList<Integer> frq = new ArrayList<Integer>();
        for(int i=0;i<26;i++)
            frq.add(0);
        for(int i=0;i<s.length();i++)
            frq.set(s.charAt(i)-'a', frq.get(s.charAt(i)-'a')+1);
        int par = 0;
        StringBuilder ans = new StringBuilder();
        boolean can = false;
        do{
            can = false;
            StringBuilder ss = new StringBuilder();
            for(int i=0;i<26;i++)
                if(frq.get(i)>0){
                    ss.append((char)(i+'a'));
                    frq.set(i, frq.get(i)-1);
                    can |= (frq.get(i) > 0);
                }
            if(par == 1)
                ss.reverse();
            par ^= 1;
            ans.append(ss);
        } while(can == true);
        return ans.toString();
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(sortString("aaaabbbbcccc"));
  }
}
abccbaabccba

تحلیل پیچیدگی

پیچیدگی زمان

بر)، از آنجا که حلقه بیرونی در الگوریتم اجرا می شود ، تا زمانی که کاراکترها در آرایه فرکانس باقی بمانند.

پیچیدگی فضا

بر)، زیرا رشته جدید به همان اندازه فضای ورودی اشغال می کند.