የሕብረቁምፊ Leetcode መፍትሔን እንደገና ማሻሻል


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Microsoft
ሕብረቁምፊ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ የቁጥር ቁጥሮች ተሰጠን ክር ማለትም ሕብረቁምፊው አነስተኛ ፊደላት (አዝ) እና አሃዞች (0-9) ብቻ አሉት። በእሱ ውስጥ ምንም ተከታታይ ፊደል የሌለበት ወይም ተከታታይ አሃዞች የሌሉበትን ማንኛውንም የዚህ ገመድ ክርክር መመለስ ይጠበቅብናል። እንደዚህ ካልሆነ መለወጥ አለ ፣ ከዚያ ባዶ ገመድ መመለስ አለብን።

ለምሳሌ

s = "a0b1c2"
"0a1b2c"

ማብራሪያ:

በ "0a1b2c" ውስጥ ሁለት ተጎራባች ቁምፊዎች ተመሳሳይ ዓይነት የላቸውም።
“A0b1c2” ፣ “0a1b2c” ፣ “0c2a1b” እንዲሁ ትክክለኛ ጥፋቶች ናቸው ፡፡

s = "leetcode"
""

ማብራሪያ:

“Leetcode” ቁምፊዎች ብቻ አሉት ስለሆነም በዲጂቶች ልንለያቸው አንችልም ፡፡

ቀረበ

እስትንፋስ መመለስ የምንችልበትን ሁኔታ በመጀመሪያ እንገንዘብ ፡፡
ሕብረቁምፊ “abcde” ከሆነ እንበል ፣ ከዚያ ምንም ሁለት ፊደላት ወይም ቁጥሮች በተከታታይ የማይገኙበት ከዚህ ውስጥ ማንኛውንም ጥሰት ማድረግ አንችልም።
በተመሳሳይ ሕብረቁምፊ “12335” ከሆነ ከዚያ እኛ ምንም ማድረግ አንችልም።
ስለዚህ ፣ አማራጭ የቁጥር ቁጥሮች ሕብረቁምፊ ለማድረግ እኩል ቁጥሮች እና ፊደላት ሊኖሩን ይገባል?
አይ ፣ እስቲ “covid2019” ን እንመልከት 5 ፊደላት እና 4 አሃዞች አሉን ፡፡
አሁንም ቢሆን “c2o0v1i9d” የሚቻል መልስ አለን ፡፡

የሕብረቁምፊ Leetcode መፍትሔን እንደገና ማሻሻል

አሁን በተመሳሳይ ሕብረቁምፊ ውስጥ አንድ ተጨማሪ ፊደል ቢኖር ኖሮ “covids2019” ን እንግዲያውስ እኛ ማንኛውንም ውጤት ማምጣት አልቻልንም።
ስለዚህ እዚህ የቁጥር ፊደላት እና የቁጥር ቁጥሮች ልዩነት ከ 1 መብለጥ የለበትም የሚል ቅድመ ሁኔታ አግኝተናል ፡፡
ማለትም ABS (ቆጠራ (አሃዞች) -ቁጥር (ፊደላት)) <= 1 ፣ ሌላ ብልህ ምንም ውጤት አይኖርም ፡፡

እስቲ አሁን ስልተ ቀመሩን እንረዳ ፣

አልጎሪዝም

  1. አማራጭ ውጤቱን ለመፍጠር በተናጠል ፊደሎችን እና አሃዞችን ማሰባሰብ አለብን ፡፡
  2. ከዚያ በኋላ የሁለቱን ቡድኖች መጠን መመርመር እንችላለን ፣ ልዩነቱ ከ 1 በላይ ከሆነ የምንመልሰው ባዶ ሕብረቁምፊ ነው። ሌላ እኛ ወደ ፊት እንሄዳለን ፡፡
  3. አሁን የሁለቱን ቡድን መጠን ማረጋገጥ እንችላለን ፣
    የቡድን መጠን (የፊደላት ቡድን) ከሌላው (በአንዱ) ከሌላው የበለጠ ከሆነ (በአሃዞች ቡድን) ፣ ከዚያ በመጀመሪያ ደረጃ በትልቁ የውጤት ገመድ ውስጥ ትልቁን ቡድን ባህሪ በመሙላት መጀመር አለብን።
    አለበለዚያ የማንኛውም ቡድን ባህሪ የመጀመሪያ ቦታ ሊወስድ ይችላል ፡፡
    እዚህ እኛ ለዚህ ተግባር ባንዲራ ተለዋዋጭ እንጠቀማለን ፡፡ ለሁለቱም ቡድን ተራ ካልሆነ በስተቀር ሌላ ምንም ነገር የለም ፡፡ ሰንደቅ ዓላማው እውነት ከሆነ ፊደልን አሁን ባለው ቦታ በውጤት ገመድ ውስጥ በማስቀመጥ የበለጠ እንቀጥላለን ፡፡ አለበለዚያ አሃዝ እናስቀምጣለን ፡፡
    በተጨማሪም በእያንዳንዱ ሙሌት ላይ በሁለቱ ቡድኖች መካከል መቀያየርን ለማስቀጠል ባንዲራን እንገልባለን ፡፡
  4. ስለዚህ ገጸ-ባህሪያቱን አንድ በአንድ በውጤታማነት ከመጨመራችን በፊት የፊደላት ቡድን መጠናቸው የበለጠ ከሆነ ባንዲራችን እውነተኛ እንሆናለን ፣ አለበለዚያ ባንዲራ ሐሰተኛ ሆኖ ይቀራል ፡፡
  5. አሁን ይህ የውፅዓት ገመድ ነው እኛም ተመሳሳይ መመለስ አለብን ፡፡

አፈጻጸም

የ C ++ ፕሮግራም ለሪፎርም የሕብረቁምፊ ሌትኮድ መፍትሔ

#include <iostream>
using namespace std;

string reformat(string s) {
        
        string alphas;
        string digs;
        
        for(int i=0;i<s.length();i++){
            char ch=s[i];
            string str=string(1, ch); 
            if(ch>='0' && ch<='9')digs.append(str);
            else alphas.append(str);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=abs(alen-dlen);
        if(diff>1)return "";
        
        string ans;
        
        bool flag=0;
        if(alen-dlen==1)flag=1;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                string str=string(1, alphas[j++]); 
                ans.append(str);
            }else{
                string str=string(1, digs[k++]); 
                ans.append(str);
            }
            flag=!flag;
        }
    
        return ans;
    }


int main() {
  string str="covid2019";
  string ans=reformat(str);
    cout<<ans<<endl;	
  return 0;
}
c2o0v1i9d

የጃቫ ፕሮግራም ለሪፎርም የሕብረቁምፊ ሌትኮድ መፍትሔ

import java.util.*;
class ReformatString{
  public static  String reformat(String s) {
        
        StringBuilder alphas=new StringBuilder();
        StringBuilder digs=new StringBuilder();
        
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch>='0' && ch<='9')digs.append(ch);
            else alphas.append(ch);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=Math.abs(alen-dlen);
        if(diff>1)return "";
        
        StringBuilder ans=new StringBuilder();
        
        boolean flag=false;
        if(alen-dlen==1)flag=true;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                ans.append(alphas.charAt(j++));
            }else{
                ans.append(digs.charAt(k++));
            }
            flag=!flag;
        }
        return ans.toString();
    }
  
    public static void main(String args[]){
        
    String str="covid2019";
    String ans=reformat(str);
    System.out.println(ans);
    }
}
c2o0v1i9d

ለሪፎርማት ውስብስብነት ትንተና የክርክር ሌቲኮድ መፍትሔ

የጊዜ ውስብስብነት

ኦ (n): ምክንያቱም ፣ በግብዓት ገመድ ላይ በመስመር ላይ እየሰራን ነው። ስለሆነም ፣ የጊዜ ውስብስብነቱ O (n) ይሆናል።

የቦታ ውስብስብነት 

ኦ (n): ጥቂት ተጨማሪ ሕብረቁምፊዎችን መጠቀም አለብን

  • ሀ. ለፊደል ቡድን
  • ለ. ለአሃዞች ቡድን
  • ሐ. ለውጤት

የእነዚህ ሁሉ መጠን ቢበዛ የግብዓት ገመድ ርዝመት ነው
ስለሆነም የቦታ ውስብስብነቱ O (n) ነው።