Цагаан толгойноос мөрийг шифрлэх, бүхэл зураглал хийх Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Quip Борлуулалтын хүч
String

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

Энэ асуудалд бидэнд (0-9) ба '#' цифрүүдийг агуулсан мөр өгөгдсөн болно. Бид дараахь зураглалыг ашиглан энэ мөрийг англи хэлний жижиг үсгүүд болгон хөрвүүлэх ёстой.

Цагаан толгойноос мөрийг шифрлэх, бүхэл зураглал хийх Leetcode шийдэл

Жишээ нь

s = "10#11#12"
"jkab"

Тайлбар:

“10 #” -> “j”, “11 #” -> “k”, “1” -> “a”, “2” -> “b”.

s = "1326#"
"acz"

Тайлбар:

“1” -> “a”, “3” -> “c”, “26 #” -> “z”.

арга барил

Бид зөвхөн "#" -т санаа зовох ёстойг харж болно. Өгөгдсөн мөрийг тоолуураар (зүүн тийш) зүүнээс баруун тийш гүйлгэхэд i индекс бүрийн хувьд (0 <= i <= n-3) зөвхөн i-ээс дараагийн индексийн хажууд байгаа тэмдэгт байгаа эсэхийг шалгах хэрэгтэй. i + 2 индекс дээрх тэмдэгт '#' байна.

I (0-ээс n-3) бүрийн хувьд i + 2 индексийн тэмдэгт "#" байвал энэ i индексийг i + 1-тэй нэгтгэж эдгээр хоёр цифрийг ашиглан тэмдэгт үүсгээрэй.
жишээ нь “12 #”, хэрэв бид мөрийг зүүнээс баруун тийш гүйлгэх юм бол i = 0 бол i + 2 индекс дээрх тэмдэгт нь '#' болно. Тиймээс i ба i + 1 индекс дээр байгаа цифрүүдийг нэгтгэж, өөрөөр хэлбэл 1 ба 2 цифрүүдийг нэгтгэж, тэдгээрийг "12" болго. Одоо 12-ыг тэмдэгтийн зураглал болгон хөрвүүлээд "l" болгож хавсаргана уу уяачин sb.
“12” мөрийг 'l' тэмдэгт рүү хөрвүүлэхийн тулд хөрвүүлэх функцийг бүтээсэн бөгөөд энэ нь мөрийн форматаар тоо авч, түүнийг тохирох тэмдэгт болгон хөрвүүлдэг.
Хэрэв i + 2 индекс дээрх тэмдэгт "#" биш бол бид i индекс дээрх тэмдэгтийг i + 1 индекс дээрх тэмдэгттэй хослуулах ёсгүй.

жишээ нь "123", хэрэв бид i = 0 индексээс i + 2 индексийг харвал 2 дахь тэмдэгт нь "#" биш тул бид "1" -ийн тэмдэгт хөрвүүлэлтийг зүгээр л хавсаргана.

N-2 ба n-1 индексийн тэмдэгтүүдийн хувьд n-1 дээрх char нь аль хэдийн '#' байх байсан бол n-3 индексийн дараа циклээс гарахгүй, өөрөөр n-2 гэсэн хоёр тэмдэгт байх болно гэж хэлж болно. ба n-1-ийг тусад нь зураглах ёстой.

Хэрэгжүүлэх

C ++ програмыг цагаан толгойноос бүхэлд нь зураглах Leetcode шийдэлд шилжүүлэх мөрийг тайлах програм

#include <bits/stdc++.h>
using namespace std;

char convert(string str){
    stringstream ss(str);
    int num;
    ss>>num;
    return num+96;
}

string freqAlphabets(string s) {
        stringstream ss;
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s[i+2]=='#'){
                ch=(char)convert(s.substr(i, 2) );
                i+=2;
            }else{
                ch=(char)convert(s.substr(i,1));
            }
            i++;
            ss<<ch;
        }
        while(i<s.length()){
            char ch=(char)convert(s.substr(i,1));
            ss<<ch;
            i++;
        }
        
        return ss.str();
    }

int main()
{
    cout << freqAlphabets("1326#") ;
}
acz

Цагаан толгойноос бүхэл зураглал хийх Leetcode шийдэл хүртэлх мөрийг шифрлэх Java програм

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static String freqAlphabets(String s) {
        StringBuilder sb=new StringBuilder();
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s.charAt(i+2)=='#'){
                ch=(char)convert(s.substring(i,i+2));
                i+=2;
            }else{
                ch=(char)convert(s.substring(i,i+1));
            }
            i++;
            sb.append(ch);
        }
        while(i<s.length()){
            char ch=(char)convert(s.substring(i,i+1));
            sb.append(ch);
            i++;
        }
        
        return sb.toString();
    }
    
    
    public static int convert(String str){
        int num=Integer.parseInt(str);
        return num+96;
    }

    public static void main(String args[])
    {
        System.out.println(freqAlphabets("10#11#12"));
    }
}
jkab

Цагаан толгойноос бүхэл зураглал хийх Leetcode шийдэл хүртэлх шифрийг тайлах мөрийн нарийн төвөгтэй байдлын шинжилгээ

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

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

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

O (n): Бид java болон string урсгалд cpp тохиолдолд string builder ашигласан. Хамгийн муу тохиолдолд урт нь оролтын мөрийн урттай ижил байх болно. Тиймээс орон зайн нарийн төвөгтэй байдал нь O (n) юм.