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

是有关算法的
如果有一个等差数组,然后对这个数组里面的每个元素做如下操作
1. 如果这个元素是偶数,除以2, 然后得到的数字再分析是否是偶数,如果还是,继续除2,一直除到是奇数,
2. 如果这个元素是奇数,那么就保持原样
这样就得到了另外一个数组,
现在要求根据这个变换后的数组,能否得到变换前的数组,请描述下思路.
比如现在有个数组{1,2,3,4},变换后是{1,1,3,1},那么需要根据{1,1,3,1},得到1,2,3,4.

我当场想了20分钟也没有想出来,回头又想了几天还是没有什么很完整的思路,问了一个清华数学研究生,也没有搞定,因为对这个挺感兴趣的,发出来大家讨论下看看有没有高人能解答的.

谢谢

看了别人答案, 发现自己算法没考虑周全

这样的数组不止一个，不一定能恢复成变换前数组吧。。
如8,12,16,20 偶数除以2之后变成了 1,3,1,5。。
恢复算法最多变成4,6,8,10。。

应该不能直接根据“变换后的数组”变成“变换前数组”；
同求解决方案

只是个想法 mark一下在这里先
for(int i=0;i<a.lenth;i++){
if(a[i+1]<a[i]){
             c=a[i];d=a[i+1];e=i;
break; }else{b[]=a[];  }//目标数组全是奇数的数组
}

if(d<c){ while(d<c){d=d*2} ; f=d-c; g=a[e]-e*f for(int i=0;i<a.length;i++){ b[i]=g+f*i }    }

for(int i=a.length;i>0;i--){
if(a[i]==a[i-1]) {
             c=a[i-1];d=a[i];e=i;
break; }
}
if(d==c){ (如果==1 最后一个等于1的数对应的要还原的数就是Math.pow(2，数组中1的个数) 如果!=1 依靠相邻的数算出对应数及公差  根据公差生成要还原的数组}

算法：
1.默认是递增数列。
2.算法核心是一直找最大的公差。

写程序的时候，算法不是很明确，等程序写完之后，发现算法核心是找到最大的公差。所以程序可以优化。这里是雏形就这样看吧。希望大家有更好的办法来实现。

	static int[] arrays = { 1,1,3,1,5,7};
	static int[] srcArrays = new int[arrays.length];

	public static void main(String[] args) {

		int i = 0;
		int gongcha = 0;
		boolean falg = true;
		
		while (falg) {
			if (i == 0) {
				srcArrays[i] = arrays[i]*2;
				i++;
				continue;
			}
			System.out.println(" 处理第ige:" + i);
			if (i == 1) {
				//如果已经修改
				int back = srcArrays[i];
				if (back != 0) {
					gongcha = srcArrays[1]-srcArrays[0];
					continue;
				}
				srcArrays[i] = arrays[i] * 2;
				gongcha = srcArrays[1]-srcArrays[0];
				i++;
				continue;
			}
			if (i >= 2) {
				if (i == arrays.length) {
					falg = false;
					continue;
				}
				
				//如果当前值太小，一直成2，直到大于前面数为止 并且 和第一数的公差必须为前面一个数公差的和（前面几个数个数倍数）
				boolean ff = true;
				int cru = arrays[i] * 2;
				int k = 0;  // 防止找不到一直循环
				do{
					if (k++ == 200) {
						System.out.println("找不到适合的数程序自动退出"); return ;
					}
					if ((cru > srcArrays[i-1])  && ((cru - srcArrays[0]) % i ==0)) {
						ff = false;
					} else {
						cru = cru * 2;
					}
				}while(ff);
				int tmpGongcha = (cru - srcArrays[0]) / i;
				if (tmpGongcha > gongcha) {
					addDengCha(tmpGongcha, i); //修改前面值，使用新的公差
					gongcha = tmpGongcha;
				} 
				srcArrays[i] = cru;
				i++;
			}
		}
		// print 
		 for (int k = 0; k < srcArrays.length; k++) {
			 System.out.println("jieguo:"+srcArrays[k]);
		 }
	}
	public static void addDengCha(int dengcha, int k) {
		for (int i = 1; i < k; i++) {
			srcArrays[i] = srcArrays[i-1]+dengcha;
			System.out.println("修改值："+srcArrays[i] + "    weizhi :"+i);
		}
	}

这是个人的一点小的解决方法，贴出来交流一下！
public static  void  main(String[] args)
    {
         int arrys[]={1,51,203,19,405};
         int i=0;
         int gc=0; //公差
         int gc1=arrys[1]-arrys[0];
         int gc2=arrys[2]-arrys[1];
         //公差为偶数的情况,那么所有的数字应该为奇数，否则可以化简
         if(gc1==gc2)
         {  
        gc=gc1;
        System.out.println("原等差数列的公差为："+gc);
        System.out.println("原等差数列为：");
        for(i=0;i<=arrys.length;i++)
        {
           System.out.print(arrys[i]+"  ");
        }
         }
         else   //公差为奇数的情况
         {
        if(gc1<gc2)             //原首项为奇数
        {  
        gc=(arrys[2]-arrys[0])/2;
        System.out.println("原等差数列的公差为："+gc);
            System.out.println("原等差数列为：");
            System.out.print(arrys[0]+"  ");
        for(i=1;i<=arrys.length;i++)
        {
        arrys[i]=arrys[i-1]+gc;
        System.out.print(arrys[i]+"  ");
        }
        }
        else
        {
        gc=(arrys[3]-arrys[1])/2;
        System.out.println("原等差数列的公差为："+gc);
            System.out.println("原等差数列为：");
            arrys[0]=arrys[1]-gc;
            System.out.print(arrys[0]+"  ");
            System.out.print(arrys[1]+"  ");
        for(i=2;i<=arrys.length;i++)
        {
        arrys[i]=arrys[i-1]+gc;
        System.out.print(arrys[i]+"  ");
        }
        }
         }
    }

看了Scooler的之后 ，发现还要考虑变换次数 及等差。。。 不是很简单。。。

找到数组最后面的一个 1 (这个为转换次数最多的那个数) ， 通过 2^变换次数 获得这个位置的初始值，然后根据等差值前后推 ....


考虑不周，没有考虑数组里有没有1

 

不太懂，是不是我想得太简单了。123456789 变换后变成113151719，完全就是偶数位=这位偶数位+1位的数值减去公差！！！