題目描述

假定一種編碼的編碼范圍是a ~ y的25個(gè)字母，從1位到4位的編碼，如果我們把該編碼按字典序排序，形成一個(gè)數(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，以此類推。 編寫一個(gè)函數(shù)，輸入是任意一個(gè)編碼，輸出這個(gè)編碼對(duì)應(yīng)的Index.

輸入描述:

輸入一個(gè)待編碼的字符串,字符串長(zhǎng)度小于等于100.

輸出描述:

輸出這個(gè)編碼的index

示例1

輸入

baca

輸出

16331

首先分析題目，發(fā)現(xiàn)編碼其實(shí)是一個(gè)數(shù)組，數(shù)組大小為25的四次方。但是代碼構(gòu)建一個(gè)數(shù)組會(huì)有空間限制的問(wèn)題，構(gòu)建完成之后再遍歷查詢得到編碼又會(huì)有時(shí)間復(fù)雜度的問(wèn)題。所以這種方式不建議選取。

仔細(xì)觀察這個(gè)數(shù)組，發(fā)現(xiàn)有一定的規(guī)律。a開(kāi)頭的所有編碼占用了連續(xù)的一段數(shù)組空間（其他字母同理），所以聯(lián)想到樹(shù)。

然后先構(gòu)建一個(gè)由25棵樹(shù)組成的森林，根節(jié)點(diǎn)分別為a、b、c…y，每棵樹(shù)都是高度為3的滿25叉樹(shù)，子節(jié)點(diǎn)分別為a、b、c…y。如下圖所示（有些b與y之間忘了打省略號(hào)請(qǐng)忽略）。

從第一棵樹(shù)的根節(jié)點(diǎn)開(kāi)始至各個(gè)節(jié)點(diǎn)的路徑便為編碼順序，以第一棵樹(shù)為例為a、aa、aaa、aaaa、aaab…ayyy，緊接第二棵樹(shù)為b、ba、baa、baaa……byyy，最終達(dá)到y(tǒng)yyy。

下面開(kāi)始聯(lián)系題目。以baca為例，編碼即為根節(jié)點(diǎn)為b的樹(shù)和其子節(jié)點(diǎn)a及下一層子節(jié)點(diǎn)c及再下一層子節(jié)點(diǎn)a所組成路徑的左側(cè)節(jié)點(diǎn)個(gè)數(shù)（包括b、a、c、a四個(gè)節(jié)點(diǎn)）減一（因?yàn)閍的編碼為0）。如下圖所示。

這時(shí)候，問(wèn)題就由求解編碼，變?yōu)榱擞?jì)算這條線左端所有節(jié)點(diǎn)的個(gè)數(shù)和。

我們假設(shè)輸入字符串為S0S1S2S3共計(jì)四個(gè)字符。

那么第一層的個(gè)數(shù)和便為：S0 - 'a' + 1

第二層個(gè)數(shù)和為：（S0 - 'a'）* 25^1 + (S1 - 'a' + 1)

第三層個(gè)數(shù)和為：（S0 - 'a'）* 25^2 + (S1 - 'a') * 25^1 + (S2 - 'a' + 1)

第四層個(gè)數(shù)和為：（S0 - 'a'）* 25^3 + (S1 - 'a') * 25^2 + (S2 - 'a') * 25^1 + (S3 - 'a' +1)

計(jì)算過(guò)程中注意判斷S1、S2、S3是否存在，不存在時(shí)將對(duì)應(yīng)的小的計(jì)算塊置為0。

廢話少說(shuō)，下面上代碼（考慮到擴(kuò)展性，增加了size變量，表示題目中規(guī)定的編碼字符串最大長(zhǎng)度）。

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;
    }
}

最新評(píng)論