欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

腾讯面试算法题——编码

程序员文章站 2022-04-26 22:31:43
...
题目描述
假定一种编码的编码范围是a ~ y的25个字母,从1位到4位的编码,如果我们把该编码按字典序排序,形成一个数组如下: a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, ab, 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 < 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;
    }
}


相关标签: 腾讯 面试