腾讯面试算法题之编码问题案例分析

题目描述

假定一种编码的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。 编写一个函数，输入是任意一个编码，输出这个编码对应的Index.

输入描述:

输入一个待编码的字符串,字符串长度小于等于100.

输出描述:

输出这个编码的index

示例1

输入

baca

输出

16331

首先分析题目，发现编码其实是一个数组，数组大小为25的四次方。但是代码构建一个数组会有空间限制的问题，构建完成之后再遍历查询得到编码又会有时间复杂度的问题。所以这种方式不建议选取。

仔细观察这个数组，发现有一定的规律。a开头的所有编码占用了连续的一段数组空间（其他字母同理），所以联想到树。

然后先构建一个由25棵树组成的森林，根节点分别为a、b、c…y，每棵树都是高度为3的满25叉树，子节点分别为a、b、c…y。如下图所示（有些b与y之间忘了打省略号请忽略）。

从第一棵树的根节点开始至各个节点的路径便为编码顺序，以第一棵树为例为a、aa、aaa、aaaa、aaab…ayyy，紧接第二棵树为b、ba、baa、baaa……byyy，最终达到yyyy。

下面开始联系题目。以baca为例，编码即为根节点为b的树和其子节点a及下一层子节点c及再下一层子节点a所组成路径的左侧节点个数（包括b、a、c、a四个节点）减一（因为a的编码为0）。如下图所示。

这时候，问题就由求解编码，变为了计算这条线左端所有节点的个数和。

我们假设输入字符串为S0S1S2S3共计四个字符。

那么第一层的个数和便为：S0 - 'a' + 1

第二层个数和为：（S0 - 'a'）* 25^1 + (S1 - 'a' + 1)

第三层个数和为：（S0 - 'a'）* 25^2 + (S1 - 'a') * 25^1 + (S2 - 'a' + 1)

第四层个数和为：（S0 - 'a'）* 25^3 + (S1 - 'a') * 25^2 + (S2 - 'a') * 25^1 + (S3 - 'a' +1)

计算过程中注意判断S1、S2、S3是否存在，不存在时将对应的小的计算块置为0。

废话少说，下面上代码（考虑到扩展性，增加了size变量，表示题目中规定的编码字符串最大长度）。

 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("输入数据格式有误"); }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  'y'){ return index; } } index = 0; for(int i = 0; i