String Leetcode шийдлийг шинэчлэх


Хэцүү байдлын түвшин Easy
Байнга асуудаг Microsoft-
String

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд үсэг, тоон тэмдэг өгдөг мөр өөрөөр хэлбэл мөрөнд зөвхөн жижиг үсэг (az) ба цифр (0-9) байна. Энэ мөрөнд дараалсан цагаан толгой, дараалсан цифр ороогүй аливаа сэлгэлтийг буцааж өгөх шаардлагатай. Хэрэв тийм биш бол Сонголт хийх тэнд байгаа бол бид хоосон мөрийг буцааж өгөх ёстой.

Жишээ нь

s = "a0b1c2"
"0a1b2c"

Тайлбар:

"0a1b2c" -д ижил төрлийн хоёр зэргэлдээ тэмдэгт байхгүй.
“A0b1c2”, “0a1b2c”, “0c2a1b” нь мөн зөв сэлгэлтүүд юм.

s = "leetcode"
""

Тайлбар:

“Leetcode” нь зөвхөн тэмдэгттэй тул тэдгээрийг цифрээр нь ялгаж чадахгүй.

арга барил

Эхлээд сэлгэлтийг буцааж өгөх нөхцөлийг ойлгъё.
Хэрэв мөр нь "abcde" байвал хоёр цагаан толгой, тоо дараалалгүй дараалал оруулах боломжгүй болно.
Үүнтэй адил мөр нь "12335" байвал бид юу ч хийж чадахгүй.
Тэгэхээр үсэг, тоон өөр мөрийг хийхийн тулд ижил тооны цифр, цагаан толгойтой байх ёстой юу?
Үгүй, жишээ нь “covid2019” -ийг үзье, бид 5 цагаан толгой, 4 оронтой.
Гэсэн хэдий ч бид "c2o0v1i9d" боломжтой.

String Leetcode шийдлийг шинэчлэх

Одоо ижил мөрөнд нэг цагаан толгой байх юм бол “covids2019” гэж оруулъя, тэгвэл бид боломжит гаргалт хийж чадахгүй.
Тиймээс энд цагаан толгойн тоо ба цифрүүдийн зөрүү 1-ээс хэтрэхгүй байх нөхцлийг бид авсан болно.
өөрөөр хэлбэл abs (count (цифр) -count (цагаан толгой)) <= 1, бусад ухаалаг үр дүн гарахгүй.

Алгоритмыг одоо ойлгъё,

Алгоритм

  1. Альтернатив гаралтыг бий болгохын тулд бид цагаан толгой, цифрийг тусад нь бүлэглэх хэрэгтэй.
  2. Үүний дараа бид хоёр бүлгийн хэмжээг шалгаж болно, хэрэв зөрүү 1-ээс хэтэрвэл бид хоосон мөрийг буцаана. Бусад тохиолдолд бид цаашаа явна.
  3. Одоо бид хоёр бүлгийн хэмжээг шалгаж болно,
    Хэрэв бүлгийн хэмжээ (цагаан толгойн бүлэг) нөгөөгөөс (цифрийн бүлэг) том (нэгээр) том байвал гаралтын мөрөнд эхний ээлжинд том бүлгийн тэмдэгтийг бөглөж эхлэх хэрэгтэй.
    Үгүй бол аль ч бүлгийн дүр эхний байранд орж магадгүй юм.
    Энэ даалгаварт зориулж тугны хувьсагчийг ашиглаж байна. Энэ нь хоёр бүлгийн эргэлтээс өөр зүйл биш юм. Хэрэв туг нь үнэн бол гаралтын мөрөнд цагаан толгойг байрлуулж цааш үргэлжлүүлнэ. Үгүй бол бид цифр тавих болно.
    Дүүргэлт бүрт бид хоёр бүлгийг ээлжлэн солихын тулд тугийг эргүүлнэ.
  4. Тиймээс тэмдэгтүүдийг нэг нэгээр нь гаргалтанд оруулахаас өмнө цагаан толгойн бүлэг том хэмжээтэй байвал туг далбаагаа үнэн байлгах болно.
  5. Одоо энэ нь гаралтын мөр бөгөөд бид үүнийг буцааж өгөх ёстой.

Хэрэгжүүлэх

String Leetcode шийдлийг шинэчлэхэд зориулсан 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

String Leetcode шийдлийн шинэчлэлд зориулсан 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

Reformat-ийн нарийн төвөгтэй байдлын шинжилгээ The String Leetcode Solution

Цаг хугацааны нарийн төвөгтэй байдал

O (n): Учир нь бид оролтын мөр дээр шугаман байдлаар ажиллаж байна. Тиймээс цаг хугацааны нарийн төвөгтэй байдал O (n) байх болно.

Сансрын нарийн төвөгтэй байдал 

O (n): Бид цөөн хэдэн нэмэлт мөр ашиглах ёстой:

  • а. цагаан толгойн бүлэгт
  • б. тоон бүлгийн хувьд
  • в. гаралтын хувьд

Эдгээрийн хэмжээ нь хамгийн ихдээ оролтын мөрийн урт юм
Тиймээс орон зайн нарийн төвөгтэй байдал нь O (n) юм.