juniper的一道面试题.

deer2010

　　题目来源自http://bbs.iyunv.com/topics/390315847 #32楼


　　


　　juniper的一道面试题.

定义一个数字有以下的特征, 它可以被分成几个部分,而前面的部分相加起来的和是后面的部分.举例来说   
　　1235813,          1+2=3; 2+3=5;3+5=8; 5+8=13;

112112224,      112+112=224;

1981100,          19+81=100;

122436,            12+24=36;

1299111210,    12+99=111,99+111=210;

要求写出一个函数,输入一个数字,判断这个数字是不是要求的这个数。


　　当天看的时候也觉得很简单。但是仔细一想，却发现需要考虑的东西太多太多。光是构思就想了很久（一边做项目一边想），如果在面试的场合下，给1个小时，我肯定是完不成了。脑子不太灵光。这个算法的解决方案是睡觉做梦解决的，很神奇。。早上醒了赶紧给记了下来。难道说我的体内有个青霞么。
　　


　　说下思路吧。
　　首先，数字是一串巨大的数字（也可以是纯数字字符串，我们现在只把他看成int类型，int的缺点就是位数不足。你可以重载我的方法，逻辑不变，只是按位拆解的时候进行小小的重载。），当我们拿到这个数字，我们要把它按位拆解，按位存储到一个数组当中，方便我们以后的提取调用。
　　数字可以是从一位数开始计算、或是两位数、或是三位数、或是更多。接下来我们就是要对输入进来的数字进行判断了。当然，每个数字都是从一位数开始遍历的。当找到可以使算法成立的式子的时候，我们就return一个true。找不到，我们就进行两位数遍历，依此类推。这就是遍历的最外层的大循环。
　　内层小循环是遍历每一次的加法。方法我是通过二叉树的思路想出来的，画张小图来进行解释。



　　我们先把数组的前两个数拿出来，放到a1和a2内。此时要对a1和a2进行判断，观察a2是否已经是叶子节点了。如果是，那么就不符合我们算法的条件了。如果不是，那么我们接着往下来。
　　关于a3和a4的区别。a3和a4其实就是位数上差了1位。a1，a2两个数相加，可能会进位，也可能不进位，这就是a3和a4的区别。
　　当我们的a1+a2==a4的时候，那么，剩下的数也就会在a4下面生成树。我们就要走a4这条分支了，a3这条分支已经被放弃掉。同时，我们把a2往上推给a1，a4推给a2，按照题目的要求，进行下一次的循环，如图。



　　如图，这样一来，我们就有了内循环的模型。类似利用二叉树的条件查找，一步一步往下进行，每一次都会有四个关键的数，进行条件判断。以此类推。
　　当我们最后一次运算将整个输入的数字用完了，并且符合我们的算法要求，那么，这个输入的数字即为true。
　　


　　下面，就来看看我们的实际代码。因为我是个java程序员。所以用java的方式进行算法的编辑，不过注释应该还算清楚。
　　/**
* @Project TestJuniper.java
* @Description juniper的一道算法面试题，通过算法进行计算。
* @author 刺猬七年未到
* @Copyright 刺猬七年未到
* @version v2.0
* 微博：http://weibo.com/u/2873751722?c=spr_web_sq_baidub_weibo_t001
* QQ： 409349829
* 文件履历： 2012/12/19,做成日,刺猬七年未到
*   2012/12/29,细节修改，2.0版本更新,刺猬七年未到
*/
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @ClassName TestJuniper
* @Description 算法类，具体算法思路清参考博客文章。
* @author WL
* @date 2012/12/29
*/
public class TestJuniper {
/**
* @Fields 用于标记数字是否符合格式的布尔类型的标记。
*/
private boolean result = false;
/**
* @Fields 用于表示传入数字的长度
*/
private int length = 1;
/**
* @Fields 用于表示数字需要进行几次计算
*/
private int sumCount = 0;
/**
* @Fields 用于存放传入数据的数组
*/
private int[] array = null;
/**
* @Description 构造函数，对数据进行算法判断，将类内容进行初始化。（long类型的重载）
*/
public TestJuniper(long input) {
System.out.println("输入的数的值为:" + input);
// 初始化length
this.length = returnLength(input);
System.out.println("输入的数的长度为:" + this.length);
// 初始化array[]
this.array = new int[this.length];
this.array = resolution(input, this.length);
// 计算计算的次数。思路见博客
this.sumCount = this.length / 3;
this.result = isFormat();
}
/**
* @Description 构造函数，对数据进行算法判断，将类内容进行初始化。（String类型的重载）
*/
public TestJuniper(String input) {
// 对输入字符串进行判断。
if (strInputCheck(input)) {
System.out.println("输入的数的值为:" + input);
// 初始化length
this.length = returnLength(input);
System.out.println("输入的数的长度为:" + this.length);
// 初始化array[]
this.array = new int[this.length];
this.array = resolution(input, this.length);
// 计算计算的次数。思路见博客
this.sumCount = this.length / 3;
this.result = isFormat();
}
// 如果不是纯数字字符串，则输出错误信息。
else {
System.out.println("ERROR:输入的字符不是纯数字");
}
}
/**
* @Description 返回数据长度（long类型的重载）
* @param input
*            ：输入的数据
* @return 返回数据的长度
*/
private int returnLength(long input) {
// 方法返回值
int l_intsOutput = 1;
// 对输入数据进行循环，如果输出初10大于1，把长度加1。
while (input / 10 >= 1) {
l_intsOutput++;
// 输入数据减少1位，进行下一次循环。
input = input / 10;
}
return l_intsOutput;
}
/**
* @Description 返回数据长度（Sting类型的重载）
* @param input
*            ：输入的数据
* @return 返回数据的长度
*/
private int returnLength(String input) {
// 方法返回值
int l_intsOutput = 0;
// 通过String.length()方法，返回字符串的长度。
l_intsOutput = input.length();
return l_intsOutput;
}
/**
* @Description 对输入的数据进行按位分解，放入一个数组当中（long类型的重载）
* @param input
* @param inputLength
* @return 返回传入数据相应对应的按位拆解过后数组
*/
private int[] resolution(long input, int inputLength) {
// 方法返回值，int数组
int[] l_intsOutput = new int[inputLength];
// 通过循环将数字放入数组中
for (int i = 0; i < inputLength; i++) {
// 求出input最高位的数字，并将其放入数组的相应的位置。
l_intsOutput = (int) (input / java.lang.Math.pow(10, inputLength
- i - 1));
int l_intA = i + 1;
System.out.println(&quot;第&quot; + l_intA + &quot;位=&quot; + l_intsOutput);
// 对input进行求余，使其去掉已经放入数组的数。
input = (int) (input % java.lang.Math.pow(10, inputLength - i - 1));
}
return l_intsOutput;
}
/**
* @Description 对输入的数据进行按位分解，放入一个数组当中（String类型的重载）
* @param input
* @param inputLength
* @return
*/
private int[] resolution(String input, int inputLength) {
// 方法返回值
int[] l_intsOutput = new int[inputLength];
// 通过循环将字符串放入数组中
for (int i = 0; i < inputLength; i++) {
// 通过string.substring(start,end)方法，求出每一位的数值，然后通过
// Integer.valueOf(str).intValue()方法将String类型转为int类型
l_intsOutput = Integer.valueOf(input.substring(i, i + 1))
.intValue();
int l_intA = i + 1;
System.out.println(&quot;第&quot; + l_intA + &quot;位=&quot; + l_intsOutput);
}
return l_intsOutput;
}
/**
* @Description 对TestJuniper的实例通过算法进行判断。
* @return 如果符合算法要求，则返回true，不符合则返回false。
*/
private boolean isFormat() {
// 最外侧大循环，stepLength是步长，也就是从几位数开始进行计算判断。
for (int stepLength = 1; stepLength <= sumCount; stepLength++) {
System.out.println(&quot;目前从&quot; + stepLength + &quot;位数开始进行计算&quot;);
// 设置当前每个计算数字的位数。初始化为步长。
int l_intSumDigits = stepLength;
// 设置已用过的位数，初始化为0。
int l_intUsedLength = 0;
// 用于显示进行了几轮while条件判断
int l_intCount = 1;
// 四个关键数字，在博客的算法介绍中有介绍。
// a1：第一个加数
int a1 = 0;
// a2：第二个加数
int a2 = 0;
// a3：不进位的和
int a3 = 0;
// a4：进位的和
int a4 = 0;
// 对a1关键数字进行初始化。
for (int i = 0; i < stepLength; i++) {
a1 += array[l_intUsedLength]
* java.lang.Math.pow(10, stepLength - i - 1);
l_intUsedLength++;
}
// 对a2关键数字进行初始化。
for (int i = 0; i < stepLength; i++) {
a2 += array[l_intUsedLength]
* java.lang.Math.pow(10, stepLength - i - 1);
l_intUsedLength++;
}
// 进入内层循环，是个死循环，通过内层分支break进行跳出。
while (true) {
System.out.println(&quot;进行第&quot; + l_intCount + &quot;轮 while判断&quot;);
l_intCount++;
/*
* 第一条分支 对已经用过的步长进行判断。
* 如果总长度减去已用长度小于计算数字位数。（说明剩下的数字已经不够生成一个a3或者a4来满足a1+a2了）
* 因为没有满足条件，不对result进行改变。 从第一条条件分支中跳出.
*/
if (length - l_intUsedLength < l_intSumDigits) {
System.out.println(&quot;从第1条条件分支中跳出。&quot;);
break;
}
/*
* 第二条分支 对已经用过的步长进行判断。
* 如果总长度减去已用长度等于计算数字位数。（说明剩下的数字已经足够生成一个a3来满足a1+a2了）
* 对a3进行初始化，判断a1+a2与a3的关系。
*/
else if (length - l_intUsedLength == l_intSumDigits) {
a3 = 0;
// 设置一个临时的l_intUsedLength，为了不对l_intUsedLength进行修改。
int tempUL = l_intUsedLength;
// 初始化a3
for (int i = 0; i < l_intSumDigits; i++) {
a3 += array[tempUL]
* java.lang.Math
.pow(10, l_intSumDigits - i - 1);
tempUL++;
}
/*
* 第2.1条分支 a1加a2等于a3，并且数组已经到了最后，即lengh已经等于usedLength。
* 判断成功，修改result的值为true。 从第2.1条条件分支中跳出。
*/
if (a1 + a2 == a3) {
System.out.println(a1 + &quot;+&quot; + a2 + &quot;=&quot; + a3);
result = true;
System.out.println(&quot;从第2.1条条件分支中跳出。&quot;);
break;
}
/*
* 第2.2条分支 a1加a2不等于a3，并且数组已经到了最后，即lengh已经等于usedLength。
* 因为没有满足条件，不对result进行改变。 从第2.2条条件分支中跳出。
*/
else {
System.out.println(&quot;从第2.2条条件分支中跳出。&quot;);
break;
}
}
/*
* 第三条分支 对已经用过的步长进行判断。
* 如果总长度减去已用长度等于计算数字位数+1。（说明剩下的数字已经足够生成一个a4来满足a1+a2了） 进入第三条条件分支
*/
else if (length - l_intUsedLength == l_intSumDigits + 1) {
a3 = 0;
a4 = 0;
int tempULa3 = l_intUsedLength;
int tempULa4 = l_intUsedLength;
// 初始化a3
for (int i = 0; i < l_intSumDigits; i++) {
a3 += array[tempULa3]
* java.lang.Math
.pow(10, l_intSumDigits - i - 1);
tempULa3++;
}
// 初始化a4
for (int i = 0; i < l_intSumDigits + 1; i++) {
a4 += array[tempULa4]
* java.lang.Math.pow(10, l_intSumDigits + 1 - i
- 1);
tempULa4++;
}
/*
* 第3.1条分支 a1加a2等于a3，但此时最后只剩下1位了，所以肯定不会满足条件。 不对result进行改变。
* 从第3.1条条件分支中跳出。
*/
if (a1 + a2 == a3) {
System.out.println(&quot;从第3.1条条件分支中跳出。&quot;);
break;
}
/*
* 第3.2条分支 a1加a2等于a4，并且数组已经到了最后，即lengh已经等于usedLength。
* 判断成功，修改result的值为true。 从第3.2条条件分支中跳出。
*/
else if (a1 + a2 == a4) {
System.out.println(a1 + &quot;+&quot; + a2 + &quot;=&quot; + a4);
result = true;
System.out.println(&quot;从第3.2条条件分支中跳出。&quot;);
break;
}
/*
* 第3.3条分支 a1加a2不等于a4，并且数组已经到了最后，即lengh已经等于usedLength。
* 从第3.3条条件分支中跳出。
*/
else {
System.out.println(&quot;从第3.3条条件分支中跳出。&quot;);
break;
}
}
/*
* 第四条分支 对已经用过的步长进行判断。 如果总长度减去已用长度大于计算数字位数。
* （说明剩下的数字已经足够生成一个a3或者a4来满足a1+a2了，并且剩下的数组还可以进行下轮计算） 进入第四条条件分支
*/
else if (length - l_intUsedLength > l_intSumDigits + 1) {
a3 = 0;
a4 = 0;
int tempULa3 = l_intUsedLength;
int tempULa4 = l_intUsedLength;
// 初始化a3
for (int i = 0; i < l_intSumDigits; i++) {
a3 += array[tempULa3]
* java.lang.Math
.pow(10, l_intSumDigits - i - 1);
tempULa3++;
}
// 初始化a4
for (int i = 0; i < l_intSumDigits + 1; i++) {
a4 += array[tempULa4]
* java.lang.Math.pow(10, l_intSumDigits + 1 - i
- 1);
tempULa4++;
}
/*
* 第4.1条分支 a1加a2等于a3，后面还有数组，所以运算还没完成。
* 经过第4.1跳条件分支，但是不跳出，继续进行while循环。 对a1，a2进行赋值，后面的值顶替前面的值。
*/
if (a1 + a2 == a3) {
// 对已用长度进行增加
l_intUsedLength = l_intUsedLength + l_intSumDigits;
System.out.println(a1 + &quot;+&quot; + a2 + &quot;=&quot; + a3);
a1 = a2;
a2 = a3;
System.out.println(&quot;从第4.1条条件分支中经过。&quot;);
}
/*
* 第4.2条分支 a1加a2等于a4，后面还有数组，所以运算还没完成。
* 经过第4.2跳条件分支，但是不跳出，继续进行while循环。 对a1，a2进行赋值，后面的值顶替前面的值。
*/
else if (a1 + a2 == a4) {
l_intSumDigits = l_intSumDigits + 1;
l_intUsedLength = l_intUsedLength + l_intSumDigits;
int temp = a1;
a1 = a2;
a2 = a4;
System.out.println(temp + &quot;+&quot; + a1 + &quot;=&quot; + a4);
System.out.println(&quot;从第4.2条条件分支中经过。&quot;);
}
/*
* 第4.3条分支 a1加a2既不等于a3也不等于a4 不满足算法条件，从4.3中跳出。
*/
else {
System.out.println(&quot;从第4.3条条件分支中跳出。&quot;);
break;
}
}
}
// 如果符合算法的规则，就跳出循环，结果为true。
if (result == true) {
System.out.println(&quot;已经符合算法要求，即将跳出循环&quot;);
break;
}
System.out.println(stepLength + &quot;位数的运算结束，即将进入下一次循环&quot;);
}
return result;
}
/**
* @Description 判断字符串是否为纯数字
* @param input
* @return 如果字符串全为数字则返回true，否则返回false
*/
public boolean strInputCheck(String input) {
//方法返回值
boolean l_boolOutput = false;
//通过正则表达式进行判断
Pattern pattern = Pattern.compile(&quot;[0-9]{1,}&quot;);
Matcher matcher = pattern.matcher((CharSequence) input);
l_boolOutput = matcher.matches();
return l_boolOutput;
}
/**
* @Description 程序入口
* @param args
*/
public static void main(String[] args) {
long a = 99182745;
// String b = &quot;99182745&quot;;
TestJuniper tj = new TestJuniper(a);
// TestJuniper tj = new TestJuniper(b);
System.out.println(a + &quot; 的计算结果为 ： &quot; + tj.result);
}
}


代码比较长，但是应该看下来不难懂。
　　我是通过条件判断进行的循环。希望有改进方法的同学们给我留言。
　　还希望大家帮我算下时间复杂度。数据结构当时学得不好。。（挂了2次）
　　


　　


　　

版权声明：本文为博主原创文章，未经博主允许不得转载。