谷歌的一道面试题,请大家集思广益

嗯     +1

public class Test {

	public static void main(String[] args) {
		// 64,127,190,253
		int []arr={7,27,101,37};
		int dengchaA=0;
		for(int i=1,len=arr.length;i<len;i++){
			while(arr[i]<=arr[i-1]){
				arr[i]=arr[i]<<1;
			}
			dengchaA+=arr[i]-arr[i-1];
		}
		dengchaA=dengchaA/(arr.length-1);
		for(int i=1,len=arr.length;i<len;i++){
			while(arr[i]-arr[i-1]>dengchaA){
				arr[i-1]=arr[i-1]<<1;
			}
		}
		for(int a:arr){
			System.out.print(a+",");
		}
	}
	
}

public class AnotherClass2 {
	
	public static void main(String[] args){
		int[] old = {1,3,3,1};
		restoreArray(old);
		print(old);
	}
	
	public static void restoreArray(int[] old){//假定old数组一定是由等差数组变换得到的
		if(old[1] != 1){//说明第二个数原来为奇数
			int gradeValue = old[1]-old[0];   //差额
			for(int i=1;i<old.length;i++){
				old[i] = old[0]+i*gradeValue;
			}
		}else if(old[1] ==1 && old[2]==1){           					//第二个和第三个都是1,说明这两个数原来都是偶数，并且偶数之差为偶数，说明等差数组的差也为偶数，
			throw new IllegalArgumentException("无法推算出原数组");      //说明整个数组都为偶数，且old数组中值均为1，此时无法恢复原数组			
		}else if(old[1] ==1 && old[2] != 1){    //说明第二个数原来是偶数，同时第三个数原来是奇数，两者之差为奇数，说明等差数组的差也为奇数，所以第一个数为奇数
			int gradeValue = (old[2]-old[0])/2;
			for(int i=1;i<old.length;i++){
				old[i] = old[0]+i*gradeValue;
			}
		}
	}
	
	public static void print(int[] a){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+" ");
		}
	}
}

思路如下：

1. while  b=0,1,2,3,前提4的值

2. 计算 x1的真实值=  x1<<b,保存到y[1]

3  while  a=0,1,2,3,4,前提3的值

4     计算x2的真实值 = x2 << a，保存到y[2]

5     计算step = x2的真实值-x1的真实值

6     while  i=3 ,4,5,6,7,n+1

7          xi的真实值=xi-1的真实值+step

8          xi’=除2到奇数(xi)

9          检查xi’是否与x’[i]相等，如相等，则保存到y[i], 跳转step 6;不相等则跳转step3

10    end

11  end

12 end

13 输出y序列即为原始序列。

上述算法最多只能计算2*32-1。

欢迎大家探讨。

这个算法，是从数学分析的角度来解决问题，有点像动态规划，分析的有道理。