ការបង្កើនដំណោះស្រាយឡេឡេកូដកូដកាន់តែថយចុះ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ អាហ្គូណារាជធានី
តម្រៀប ខ្សែអក្សរ

បញ្ហាការកើនឡើងនៃដំណោះស្រាយការថយចុះខ្សែឡេឡេហ្សកូដបង្ហាញថាយើងត្រូវបានផ្តល់ឱ្យ ខ្សែអក្សរ ជាការបញ្ចូល។ យើងត្រូវកែប្រែធាតុបញ្ចូល។ ឬដូចសំណួរបានលើកឡើងយើងត្រូវតម្រៀបវា។ ការតម្រៀបពាក្យនៅទីនេះមិនមានន័យថាគ្រាន់តែតម្រៀបតួអក្សរនោះទេ។ យើងនឹងតម្រៀបខ្សែអក្សរតាមលំដាប់លំដោយជាក់លាក់មួយនៃការរៀបចំអក្សរដំបូងតាមលំដាប់លំដោយយ៉ាងតឹងរ៉ឹងរហូតដល់យើងឈានដល់ចរិតកើនឡើង។ ហើយនៅពេលយើងឈានដល់តួអក្សរធំបំផុតយើងចាប់ផ្តើមរៀបចំអក្សរតាមលំដាប់ដែលមានការថយចុះយ៉ាងតឹងរ៉ឹងចាប់ផ្តើមដោយតួអក្សរធំបំផុតដែលមាន។ យើងត្រូវធ្វើបែបបទនេះម្តងទៀតរហូតដល់តួអក្សរខ្សែអក្សរទាំងមូលត្រូវបានប្រើ។ ដូច្នេះជាធម្មតាដំបូងយើងសូមពិនិត្យមើលឧទាហរណ៍មួយចំនួន។

ការបង្កើនដំណោះស្រាយឡេឡេកូដកូដកាន់តែថយចុះ

s = "aaaabbbbcccc"
"abccbaabccba"

ការពន្យល់ៈដូចដែលបានបញ្ជាក់ខាងលើខ្សែអក្សរដែលបានតម្រៀបត្រូវធ្វើតាមគំរូជាក់លាក់។ ទីមួយតួអង្គត្រូវតែស្ថិតនៅក្នុងលំនាំដែលមានការកើនឡើងជាលំដាប់ហើយបន្ទាប់មកមានការថយចុះ។ លទ្ធផលនៅទីនេះធ្វើតាមលំនាំដូចគ្នា។ ខ្សែអក្សរចាប់ផ្តើមជាមួយ a និងធ្វើតាមលំនាំកើនឡើងយ៉ាងតឹងរឹងរហូតដល់ c។ បន្ទាប់មកចាប់ផ្តើមម្តងទៀត c បញ្ចប់ដោយ a. ដំណើរការត្រូវបានធ្វើម្តងទៀតរហូតដល់អក្សរនៃខ្សែបញ្ចូលត្រូវបានអស់។

s = "rat"
"art"

ការពន្យល់៖ ខ្សែអក្សរដែលបានតម្រៀប (លទ្ធផល) ចាប់ផ្តើមដោយតួអក្សរតូចបំផុតហើយធ្វើតាមលំនាំដដែលរហូតដល់យើងទុកចោលដោយគ្មានតួអក្សរ។

វិធីសាស្រ្តសម្រាប់ការបង្កើនដំណោះស្រាយឡេឡេកូដកូដកាន់តែថយចុះ

បញ្ហាការបង្កើនដំណោះស្រាយខ្សែអក្សរឡេតូលេខកូដបានស្នើឱ្យយើងតម្រៀបខ្សែបញ្ចូលដែលបានផ្តល់ឱ្យតាមរបៀបជាក់លាក់មួយ។ លំនាំត្រូវបានពិពណ៌នាលម្អិតខាងលើ។ និយាយឱ្យខ្លីត្រូវរៀបចំតួអក្សរបញ្ចូលជាមុនតាមលំដាប់លំដោយដែលមានការកើនឡើងជាលំដាប់ហើយបន្ទាប់មកមានការថយចុះយ៉ាងតឹងរ៉ឹងរហូតដល់មិនមានតួអក្សរ។ ដូច្នេះយើងបង្កើតអារេហ្វ្រេកង់ដើម្បីរក្សាទុកចំនួនតួអក្សរនីមួយៗនៅក្នុងធាតុបញ្ចូល។ បន្ទាប់មកយើងដំណើរការរង្វិលជុំនៅលើប្រេកង់ប្រេកង់រហូតដល់តួអក្សរទាំងអស់នៅក្នុងវាអស់កម្លាំង។

រង្វិលជុំខាងក្រៅដំណើរការរហូតដល់មានតួអក្សរ (ប្រេកង់ធំជាង 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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ចាប់តាំងពីរង្វិលជុំខាងក្រៅនៅក្នុងក្បួនដោះស្រាយដំណើរការរហូតដល់តួអក្សរនៅសល់ក្នុងអារេប្រេកង់។

ភាពស្មុគស្មាញនៃលំហ

O (N), ពីព្រោះខ្សែអក្សរថ្មីយកទំហំផ្ទុកដូចគ្នានឹងការបញ្ចូល។