Ձևափոխել լարի կոդերի լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Microsoft
String

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է այբբենական թվանշան լարային այսինքն լարն ունի միայն փոքրատառ այբուբեններ (az) և թվանշաններ (0-9): Մեզանից պահանջվում է վերադարձնել այս տողի ցանկացած փոխարկում, որում դրա մեջ չկա հաջորդական այբուբեն կամ հաջորդական թվանշաններ: Եթե ​​այդպիսին չկա տեղադրումը կա, ապա մենք պետք է վերադարձնենք դատարկ տողը:

Օրինակ

s = "a0b1c2"
"0a1b2c"

Բացատրությունը.

«0a1b2c» - ում ոչ մի հարակից նիշ չունի նույն տիպը:
«A0b1c2», «0a1b2c», «0c2a1b» նույնպես վավեր փոխարկումներ են:

s = "leetcode"
""

Բացատրությունը.

«Leetcode» - ն ունի միայն նիշ, այնպես որ մենք չենք կարող դրանք առանձնացնել թվանշաններով:

Մոտեցում

Եկեք նախ հասկանանք, թե ինչ վիճակում կարող ենք վերադարձնել փոխարկում:
Ենթադրենք, եթե տողը «abcde» է, ապա մենք չենք կարող դրանից որեւէ հնարավոր փոխարկում կատարել, որում երկու այբուբեն կամ թիվ իրար հաջորդող չեն:
Նմանապես, եթե տողը «12335» է, ապա նաև մենք ոչինչ չենք կարող անել:
Այսպիսով, այլընտրանքային ալֆան թվային տող պատրաստելու համար մենք պետք է ունենա՞ն հավասար թվանշաններ և այբուբեններ:
Ոչ, Եկեք տեսնենք «covid2019» օրինակը, մենք ունենք 5 այբուբեն և 4 նիշ:
Դեռ մենք ունենք հնարավոր պատասխաններ, օրինակ ՝ «c2o0v1i9d»:

Ձևափոխել լարի կոդերի լուծումը

Հիմա, եթե նույն տողի մեջ մեկ այլ այբուբեն լիներ, ապա թող «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

Լարի կոդերի լուծման բարեփոխման Java ծրագիր

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

Լարային կոդերի լուծման բարեփոխման բարդության վերլուծություն

Timeամանակի բարդություն

Վրա) : Քանի որ, մենք գծային ենք աշխատում մուտքային տողի վրա: Հետևաբար, ժամանակի բարդությունը կլինի O (n):

Տիեզերական բարդություն 

Վրա) : Մենք պետք է օգտագործենք մի քանի լրացուցիչ տողեր.

  • ա այբուբենի խմբի համար
  • բ թվանշանների խմբի համար
  • գ արտադրանքի համար

Այս բոլորի չափը առավելագույնը մուտքային տողի երկարությունն է
Հետևաբար, տիեզերական բարդությունը նույնպես O է (n):