ຖອດລະຫັດສາຍຈາກຕົວອັກສອນໄປຫາໂຊລູເຊີ້ແບບຄົບວົງຈອນ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Quip Salesforce
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".

ວິທີການ

ພວກເຮົາສາມາດເຫັນໄດ້ວ່າພວກເຮົາພຽງແຕ່ຕ້ອງກັງວົນກ່ຽວກັບ '#'. ໃນເວລາທີ່ພວກເຮົາຂ້າມສາຍທີ່ໃຫ້ຈາກຊ້າຍຫາຂວາໂດຍໃຊ້ counter (ປ່ອຍໃຫ້ i), ຫຼັງຈາກນັ້ນ, ສຳ ລັບແຕ່ລະດັດຊະນີ i (0 <= i <= n-3), ພວກເຮົາພຽງແຕ່ຕ້ອງກວດເບິ່ງວ່າຕົວລະຄອນຢູ່ຂ້າງດັດສະນີຕໍ່ໄປຈາກ i ຕົວຢ່າງເຊັ່ນຕົວເລກທີ່ດັດຊະນີ i + 2 ແມ່ນ '#'.

ສຳ ລັບແຕ່ລະ i (0 ເຖິງ n-3), ຖ້າຕົວລະຄອນຢູ່ທີ່ດັດຊະນີ i + 2 ແມ່ນ '#' ແລ້ວສົມທົບດັດຊະນີນີ້ i ກັບ i + 1 ແລະປະກອບຕົວອັກສອນໂດຍໃຊ້ສອງຕົວເລກນີ້.
ຕົວຢ່າງ“ 12 #”, ຖ້າພວກເຮົາເລື່ອນສາຍຈາກຊ້າຍຫາຂວາ, ພວກເຮົາເຫັນວ່າເມື່ອຂ້ອຍ = 0 ແລ້ວຕົວສະແດງຢູ່ທີ່ດັດຊະນີ i + 2 ແມ່ນ '#'. ສະນັ້ນສົມທົບຕົວເລກທີ່ມີຢູ່ໃນດັດຊະນີ i ແລະ i + 1 ເຊັ່ນ: ສົມທົບຕົວເລກ 1 ແລະ 2, ເຮັດໃຫ້ພວກມັນ“ 12”. ດຽວນີ້ປ່ຽນ 12 ໄປເປັນແຜນທີ່ຕົວລະຄອນຕົວຢ່າງເຊັ່ນ "l" ແລະຕື່ມໃສ່ມັນ stringbuilder sb.
ເພື່ອປ່ຽນສະຕິງ“ 12” ໃຫ້ເປັນຕົວອັກສອນ 'l', ພວກເຮົາໄດ້ສ້າງ ໜ້າ ທີ່ການແປງ, ເຊິ່ງໃຊ້ເວລາ ຈຳ ນວນ ໜຶ່ງ ໃນຮູບແບບສາຍແລະປ່ຽນມັນເປັນຕົວອັກສອນທີ່ກົງກັນ.
ແລະຖ້າຕົວລະຄອນໃນດັດຊະນີ i + 2 ບໍ່ແມ່ນ '#' ແລ້ວພວກເຮົາບໍ່ຄວນສົມທົບຕົວລະຄອນຢູ່ທີ່ດັດຊະນີ i ກັບຕົວລະຄອນທີ່ດັດຊະນີ i + 1.

ຕົວຢ່າງ“ 123”, ຖ້າພວກເຮົາເຫັນຈາກດັດຊະນີ i = 0, ດັດຊະນີ i + 2 ຕົວອັກສອນທີ່ 2 ບໍ່ແມ່ນ '#', ດັ່ງນັ້ນພວກເຮົາພຽງແຕ່ຈະເພີ່ມການປ່ຽນຕົວ ໜັງ ສື "1" ໃນ ຄຳ ຕອບຂອງພວກເຮົາ.

ສຳ ລັບຕົວລະຄອນທີ່ດັດຊະນີ n-2 ແລະ n-1, ພວກເຮົາສາມາດເວົ້າໄດ້ວ່າຖ້າ char ທີ່ n-1 ຈະມີ '#' ແລ້ວ, ແລ້ວພວກເຮົາຈະບໍ່ອອກຈາກ loop ຫຼັງຈາກດັດຊະນີ n-3, ອີກຕົວອັກສອນທັງສອງຢູ່ n-2 ແລະ n-1 ຕ້ອງຖືກສ້າງແຜນທີ່ແຍກຕ່າງຫາກ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບຖອດລະຫັດເຊລຈາກ Alphabet ຫາ Integer Mapping Leetcode Solution

#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

Java Program ສຳ ລັບຖອດລະຫັດຊ່ອຍແນ່ຈາກ Alphabet ຫາ Integer Mapping Leetcode Solution

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຖອດລະຫັດສາຍຈາກຕົວອັກສອນໄປສູ່ການແກ້ໄຂແຜນທີ່ແບບບູເລຄອມພິວເຕີ້

ຄວາມສັບສົນເວລາ

ໂອ (n): ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຜ່ານສາຍການປ້ອນຂໍ້ມູນຂອງພວກເຮົາຕັ້ງແຕ່ຊ້າຍຫາຂວາດັ່ງນັ້ນເວລາ O (n) ຈະຖືກປະຕິບັດ.

ຄວາມສັບສົນໃນອະວະກາດ 

ໂອ (n): ພວກເຮົາໄດ້ໃຊ້ຜູ້ສ້າງສາຍສະລະໃນກໍລະນີຂອງ java ແລະສາຍສະຕິງໃນ cpp. ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດຫຼັງຈາກນັ້ນຄວາມຍາວຈະຄືກັນກັບຄວາມຍາວຂອງການປ້ອນຂໍ້ມູນເຂົ້າ. ດັ່ງນັ້ນ, ຄວາມສັບສົນໃນອະວະກາດກໍ່ຄື O (n).