Reformat The Solution Leetcode Solution


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Microsoft
сатр

Изҳороти мушкилот

Дар ин мушкилот, ба мо алифбо-рақамӣ медиҳанд данд яъне сатр танҳо алифбои хурд (аз) ва рақамҳо (0-9) дорад. Мо бояд ҳама гуна ҷойивазкунии ин сатрро, ки дар он алифбои пайдарпай ё рақамҳои пай дар пай вуҷуд надорад, баргардонем. Агар чунин нест ҷойивазкунӣ вуҷуд дорад, пас мо бояд сатри холиро баргардонем.

мисол

s = "a0b1c2"
"0a1b2c"

Шарҳ:

Ягон аломати ҳамшафат дар навъи "0a1b2c" яксон нест.
"A0b1c2", "0a1b2c", "0c2a1b" инчунин ҷойивазкунии дуруст мебошанд.

s = "leetcode"
""

Шарҳ:

"Leetcode" танҳо аломатҳо дорад, бинобар ин мо онҳоро бо рақамҳо ҷудо карда наметавонем.

усул

Биёед аввал ҳолатеро фаҳмем, ки дар он мо метавонем як ҷойивазкуниро баргардонем.
Фарз мекунем, ки агар сатр "abcde" бошад, мо наметавонем аз он ягон ҷойивазкунии имконпазирро созем, ки дар он ҳеҷ ду алифбо ё рақам пай дар пай набошад.
Ба ҳамин монанд, агар сатр "12335" бошад, пас мо низ ҳеҷ кор карда наметавонем.
Пас, барои сохтани сатри алтернативии алтернативӣ, оё мо бояд шумораи рақамҳо ва алифбоҳои баробар дошта бошем?
Не, биёед мисоли «covid2019» -ро бинем, ки мо 5 алифбо ва 4 рақам дорем.
Ҳоло ҳам мо имкон дорем, масалан “c2o0v1i9d”.

Reformat The Solution Leetcode Solution

Ҳоло агар дар ҳамон сатр боз як алифбои дигар мебуд, бигзор "covids2019", пас мо низ ягон натиҷаи имконпазирро ташкил карда наметавонистем.
Ҳамин тариқ, мо шарте ба даст овардем, ки фарқи шумораи алифбоҳо ва шумораи рақамҳо набояд аз 1 зиёд бошад.
яъне abs (count (рақамҳо) -count (алифбоҳо)) <= 1, дигар оқибате вуҷуд надорад.

Биёед алгоритмро ҳоло фаҳмем,

Алгоритм

  1. Барои эҷоди натиҷаи алтернативӣ, мо бояд гурӯҳбандии алифбо ва рақамҳоро алоҳида иҷро кунем.
  2. Пас аз он, мо метавонем андозаи ҳарду гурӯҳро тафтиш кунем, агар фарқ аз 1 зиёд бошад, мо сатри баргардондем. Дар акси ҳол, мо минбаъд меравем.
  3. Ҳоло мо метавонем андозаи ҳарду гурӯҳро тафтиш кунем,
    агар андозаи гурӯҳ (гурӯҳи алифбоҳо) нисбат ба гурӯҳи дигар (гурӯҳи рақамҳо) калонтар (як) бошад, пас мо бояд аз пур кардани аломати гурӯҳи калон дар ҷои аввал дар сатри баромади худ оғоз кунем.
    Дар акси ҳол, хислати ягон гурӯҳ метавонад ҷои аввалро ишғол кунад.
    Дар ин ҷо мо барои ин вазифа тағирёбандаи парчамро истифода мебарем. Ин чизе ҷуз гардиш барои ҳарду гурӯҳ нест. Агар парчам рост бошад, пас мо бо гузоштани алифбо дар ҷои ҳозира дар сатри баромади худ минбаъд ҳаракат хоҳем кард. Дар акси ҳол, мо як рақам мегузорем.
    Инчунин дар ҳар як пуркунӣ, мо парчамро мегардонем, то ивазшавии байни ду гурӯҳро давом диҳем.
  4. Ҳамин тавр, пеш аз он ки мо аломатҳоро як ба як илова намоем, парчамамонро дуруст нигоҳ медорем, агар гурӯҳи алифбо андозаи калонтар дошта бошад, вагарна парчам нодуруст хоҳад монд.
  5. Ҳоло ин сатри баромади аст ва мо бояд ҳамон чизро баргардонем.

татбиќи

Барномаи C ++ барои ислоҳот Solution Leetcode Solution

#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

Барномаи Java барои ислоҳот Solution Leetcode Solution

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

Таҳлили мураккабӣ барои ислоҳот Solution Leetcode Solution

Мураккабии вақт

O (n): Зеро, мо дар сатри вуруд ба таври хаттӣ кор карда истодаем. Аз ин рӯ, мураккабии вақт O (n) хоҳад буд.

Мураккабии фазо 

O (n): Мо бояд якчанд сатри иловагиро истифода барем:

  • а. барои гурӯҳи алифбо
  • б. барои гурӯҳи рақамӣ
  • в. барои баромади

Андозаи ҳамаи инҳо ҳадди аксар дарозии сатри вуруд мебошанд
Аз ин рӯ, мураккабии фазо низ O (n) аст.