騰訊面試算法題之編碼問題案例分析
我要評論題目描述
假定一種編碼的編碼范圍是a ~ y的25個字母，從1位到4位的編碼，如果我們把該編碼按字典序排序，形成一個數(shù)組如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index為0，aa的Index為1，aaa的Index為2，以此類推。 編寫一個函數(shù)，輸入是任意一個編碼，輸出這個編碼對應(yīng)的Index.
輸入描述:
輸入一個待編碼的字符串,字符串長度小于等于100.
輸出描述:
輸出這個編碼的index
示例1
輸入
baca
輸出
16331
首先分析題目，發(fā)現(xiàn)編碼其實是一個數(shù)組，數(shù)組大小為25的四次方。但是代碼構(gòu)建一個數(shù)組會有空間限制的問題，構(gòu)建完成之后再遍歷查詢得到編碼又會有時間復(fù)雜度的問題。所以這種方式不建議選取。
仔細(xì)觀察這個數(shù)組，發(fā)現(xiàn)有一定的規(guī)律。a開頭的所有編碼占用了連續(xù)的一段數(shù)組空間（其他字母同理），所以聯(lián)想到樹。
然后先構(gòu)建一個由25棵樹組成的森林，根節(jié)點分別為a、b、c…y，每棵樹都是高度為3的滿25叉樹，子節(jié)點分別為a、b、c…y。如下圖所示（有些b與y之間忘了打省略號請忽略）。
從第一棵樹的根節(jié)點開始至各個節(jié)點的路徑便為編碼順序，以第一棵樹為例為a、aa、aaa、aaaa、aaab…ayyy，緊接第二棵樹為b、ba、baa、baaa……byyy，最終達(dá)到y(tǒng)yyy。
下面開始聯(lián)系題目。以baca為例，編碼即為根節(jié)點為b的樹和其子節(jié)點a及下一層子節(jié)點c及再下一層子節(jié)點a所組成路徑的左側(cè)節(jié)點個數(shù)（包括b、a、c、a四個節(jié)點）減一（因為a的編碼為0）。如下圖所示。
這時候，問題就由求解編碼，變?yōu)榱擞嬎氵@條線左端所有節(jié)點的個數(shù)和。
我們假設(shè)輸入字符串為S0S1S2S3共計四個字符。
那么第一層的個數(shù)和便為：S0 - 'a' + 1
第二層個數(shù)和為：（S0 - 'a'）* 25^1 + (S1 - 'a' + 1)
第三層個數(shù)和為：（S0 - 'a'）* 25^2 + (S1 - 'a') * 25^1 + (S2 - 'a' + 1)
第四層個數(shù)和為：（S0 - 'a'）* 25^3 + (S1 - 'a') * 25^2 + (S2 - 'a') * 25^1 + (S3 - 'a' +1)
計算過程中注意判斷S1、S2、S3是否存在，不存在時將對應(yīng)的小的計算塊置為0。
廢話少說，下面上代碼（考慮到擴展性，增加了size變量，表示題目中規(guī)定的編碼字符串最大長度）。
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
Main object = new Main();
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String s = sc.nextLine();
int index = object.encode(s, 4);
if(index < 0){
System.out.println("輸入數(shù)據(jù)格式有誤");
}else{
System.out.println(index);
}
}
sc.close();
}
public int encode(String s, int size){
int index = -1;
int length = s.length();
if(length == 0 || length > size){
return index;
}
for(int i = 0; i < length; i++){
if(s.charAt(i) < 'a' || s.charAt(i) > 'y'){
return index;
}
}
index = 0;
for(int i = 0; i < size; i++){
for(int j = 0; j <= i; j++){
if(j < length){
if(i == j){
index += s.charAt(j) - 'a' + 1;
}else{
index += (s.charAt(j) - 'a') * Math.round(Math.pow((double)25, (double)(i - j)));
}
}
}
}
return index - 1;
}
}
相關(guān)文章
這篇文章主要介紹了字節(jié)跳動的三道編碼面試題的實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-04-08
