|
锁定老帖子 主题：谷歌的一道面试题,请大家集思广益
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (2)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-25
marshaldong 写道 要是不记录这个去偶的过程的话，即不依赖另外的数据结构来存储去偶的操作的话，只能从原始数组的奇数中找出规律来，来还原那些偶数的项。
要是给定的数组全是偶数的话，可能根据去偶后的数据来还原，再根据等差值来确定是否已经还原成功。 |
| 返回顶楼 | |
|
发表时间：2011-05-25
{2,4,6,8}
{1,2,3,4} 你告诉我 这俩 数组的到底原来的 是哪个？？ |
| 返回顶楼 | |
|
发表时间：2011-05-25
如果 原 数组 为 我上面说到的那种 那么 根本 就无法 判断 所以这题 有问题
|
| 返回顶楼 | |
|
发表时间：2011-05-25
thihy的回答又让我回到20年前参加奥数的情形。
你的答案我认为是正解。如果求最小，那就是看结果数组中奇数位的情形。 我的只是反证无法唯一确定，少了个条件。 |
| 返回顶楼 | |
|
发表时间：2011-05-25
feelifecn 写道 是有关算法的
如果有一个等差数组,然后对这个数组里面的每个元素做如下操作 1. 如果这个元素是偶数,除以2, 然后得到的数字再分析是否是偶数,如果还是,继续除2,一直除到是奇数, 2. 如果这个元素是奇数,那么就保持原样 这样就得到了另外一个数组, 现在要求根据这个变换后的数组,能否得到变换前的数组,请描述下思路. 比如现在有个数组{1,2,3,4},变换后是{1,1,3,1},那么需要根据{1,1,3,1},得到1,2,3,4. 我当场想了20分钟也没有想出来,回头又想了几天还是没有什么很完整的思路,问了一个清华数学研究生,也没有搞定,因为对这个挺感兴趣的,发出来大家讨论下看看有没有高人能解答的. 谢谢 {1,1,3,4}=>(min){1,2,3,4},但数列可以是2^n{1,2,3,4},只可以说是必要不充分 |
| 返回顶楼 | |
|
发表时间：2011-05-25
我的一个思路：
因为原数组为等差数组，且数组中的奇数不会变动，所以处理后的数组的奇数下标位置的所有数字，或者偶数下标位置的所有数字还是一个等差数组，因此只要将处理后的数组按隔一位的方式拆分为两个数组，然后校验其中哪个数组时等差数组（原数组处理前的所有偶数经过除2处理后，不可能形成等差数组，这个很容易理解），校验通过的数组可以直接拿来生成原数组。
|
| 返回顶楼 | |
|
发表时间：2011-05-25
上面考虑的不全面，最后的答案应该是不能还原吧，因为：假设如果有算法能将一个处理后的数组还原到1、2、3、4，那怎么判断原数组是1、2、3、4还是2、4、6、8？ |
| 返回顶楼 | |
|
发表时间：2011-05-25
2234 下来也是 1131。
所以只根据这些条件是不能反向得到唯一的1234的。 |
| 返回顶楼 | |
|
发表时间：2011-05-25
Cross_Lee 写道 2234 下来也是 1131。
所以只根据这些条件是不能反向得到唯一的1234的。 注意是等差数列，同学 |
| 返回顶楼 | |
|
发表时间：2011-05-25
lzyzizi 写道
Cross_Lee 写道
2234 下来也是 1131。
所以只根据这些条件是不能反向得到唯一的1234的。 注意是等差数列，同学
假设如果有算法能将一个处理后的数组还原到1、2、3、4，那怎么判断原数组是1、2、3、4还是2、4、6、8？ |
| 返回顶楼 | |
