እየቀነሰ የሚሄድ ገመድ Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አኩና ካፒታል
መደርደር ሕብረቁምፊ

ችግሩ እየቀነሰ የሚሄድ ገመድ / Leetcode Solution / እንደተሰጠን ይገልጻል ሀ ክር እንደ ግብዓት. ግቤቱን ማሻሻል ያስፈልገናል ፡፡ ወይም ጥያቄው እንደሚለው እኛ መደርደር ያስፈልገናል ፡፡ እዚህ መደርደር የሚለው ቃል የግድ ቁምፊዎችን መደርደር ማለት አይደለም ፡፡ እየጨመረ የሚሄደውን ቁምፊ እስክንደርስ ድረስ በመጀመሪያ ፊደሎችን በጥብቅ እየጨመረ በቅደም ተከተል በቅደም ተከተል በቅደም ተከተል በቅደም ተከተል በቅደም ተከተል በቅደም ተከተል እንለካቸዋለን ፡፡ እናም ትልቁን ገጸ-ባህሪ ስንደርስ ከሚገኘው ትልቁ ቁምፊ ጀምሮ ደብዳቤዎችን በጥብቅ እየቀነሰ በቅደም ተከተል ማዘጋጀት እንጀምራለን ፡፡ ጠቅላላው የሕብረቁምፊ ቁምፊዎች ጥቅም ላይ እስኪውሉ ድረስ ይህንን ሂደት መድገም ያስፈልገናል። ስለዚህ እንደተለመደው በመጀመሪያ ጥቂት ምሳሌዎችን እንመልከት ፡፡

እየቀነሰ የሚሄድ ገመድ Leetcode መፍትሔ

s = "aaaabbbbcccc"
"abccbaabccba"

ማብራሪያ-ከላይ እንደተጠቀሰው የተደረደረው ገመድ የተወሰነ ንድፍ መከተል አለበት ፡፡ በመጀመሪያ ፣ ገጸ-ባህሪያቱ በጥብቅ እየጨመረ በሚሄድ ንድፍ ውስጥ እና በመቀነስ መቀነስ አለባቸው ፡፡ እዚህ ያለው ውጤት ተመሳሳይ ንድፍ ይከተላል። ሕብረቁምፊው የሚጀምረው በ a እና እስከመጨረሻው በጥብቅ የሚጨምር ንድፍ ይከተላል c. ከዚያ እንደገና በመጀመር c ያበቃል በ a. የግብዓት ገመድ ፊደላት እስኪደክሙ ድረስ ሂደቱ ይደገማል ፡፡

s = "rat"
"art"

ማብራሪያ-የተደረደረው (የውጤት) ሕብረቁምፊ በትንሽ ባህሪው ይጀምራል እና ምንም ቁምፊዎች እስክንተው ድረስ ተመሳሳይ ንድፍ ይከተላል ፡፡

የሕብረቁምፊ Leetcode መፍትሄን ለመቀነስ አቀራረብ

የሕብረቁምፊ ሌቲኮድ መፍትሔን የመጨመር ችግር በተወሰነ መንገድ የተሰጠንን የግብዓት ገመድ እንድናስተካክል ጠየቀን ፡፡ ንድፍ ከላይ በዝርዝር ተገልጻል ፡፡ በአጭሩ የግብአት ቁምፊዎችን መጀመሪያ በጥብቅ በመጨመር ቅደም ተከተል እና ከዚያ ምንም ቁምፊዎች እስከማይቀጥሉ ድረስ በጥብቅ በሚቀንሰው ቅደም ተከተል ያስተካክሉ ፡፡ ስለዚህ ፣ በግብዓት ውስጥ የእያንዳንዱን ቁምፊ ቆጠራ ለማከማቸት ድግግሞሽ ድርድር እንፈጥራለን ፡፡ ከዚያ በውስጡ ያሉት ሁሉም ቁምፊዎች እስኪያልቅ ድረስ እኛ በድግግሞሽ ድርድር ላይ አንድ ዙር እንሠራለን ፡፡

የውጪው ዑደት በድግግሞሽ ድርድር ውስጥ ቁምፊዎች (ከ 1 በላይ ድግግሞሽ) እስከሚኖር ድረስ ይሠራል። ውስጣዊ ሉፕ ገጸ-ባህሪውን በጊዜያዊ ገመድ ውስጥ ያያይዘዋል። ይህ ጊዜያዊ ገመድ በመዞሪያው ላይ በመመርኮዝ መልሱ ላይ ተተክሏል ፡፡ ጊዜያዊው ገመድ ሲታከል የመጀመሪያው ተራ ከሆነ በተመሳሳይ የመጨመሩ ሁኔታ ይታከላል ፡፡ ግን ተራ ተራ ከሆነ ፣ ከዚያ መልስ ከመስጠቱ በፊት ሕብረቁምፊው ይገለበጣል። በድግግሞሽ ድርድር ውስጥ የቁምፊዎች ድካምና በኋላ። አልጎሪዝም አዲስ የመልስ ህብረቁምፊን ለተጠሪው ተግባር ይመልሳል።

ኮድ

የሕብረቁምፊ Leetcode መፍትሄን ለመቀነስ የ 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

የጃቫ ኮድ ሕብረቁምፊ Leetcode መፍትሔን ለመቀነስ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ በአልጎሪዝም ውስጥ ካለው የውጭ ዑደት ጀምሮ ቁምፊዎቹ በድግግሞሽ ድርድር ውስጥ እስከሚቀሩ ድረስ ይሠራል።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም አዲሱ ሕብረቁምፊ በመግቢያው የተወሰደውን ተመሳሳይ ቦታ ይወስዳል።