最新Amazon Online test机经(14年四月)

analog123 发表于 2014-8-26 23:01
第一题排序应该是固定的。。如果给输入排个序使得 A < B < C < D，那么要使差值和最大的排序就一定是
B ...

少年 我感觉 第一题 给的题目 并不是按照你给的那个顺序嘞  咱再仔细看看 0.0

jackjiang2 发表于 2014-8-27 10:39
少年 我感觉 第一题 给的题目 并不是按照你给的那个顺序嘞  咱再仔细看看 0.0

我的意思是可以给输入排个序，然后按照我之前给的顺序计算最后的值输出就行了。因为输入是固定4个数，排序都是常数级的。

偶 我演算了一下 贪心是不对的 但是能说下那个两个顺序 bdac cadb 是咋算出来滴么
0.0

analog123 发表于 2014-8-27 11:31
我的意思是可以给输入排个序，然后按照我之前给的顺序计算最后的值输出就行了。因为输入是固定4个数，排 ...

偶 我演算了一下 贪心是不对的 但是能说下那个两个顺序 bdac cadb 是咋算出来滴么
0.0

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

analog123 发表于 2014-8-27 15:13
我的大概思路是先考虑四个数中最大值和最小值的位置：

假设A < B < C < D，

了解。灰常感谢。请问第二题有啥解法。

第一题没看懂～第二题想了一个方法～两个for循环～但是好像不能保证O（N）啊～
第三题也好难啊～是不是需要一些bst的性质啊～

jackjiang2 发表于 2014-8-27 15:36
了解。灰常感谢。请问第二题有啥解法。

直接上代码吧，两个index维持一个window就行了，很常规的解法

1.         public static int numOfArithmeticSlices(int[] arr) {
   
2.                 int count = 0, start = 0, end = 1, d = 0;
   
3.                 while (start < arr.length-2) {
   
4.                         if (start+1 == end) {
   
5.                                 d = arr[end] - arr[start];
   
6.                                 end++;
   
7.                                
   
8.                         } else {
   
9.                                 if (end == arr.length || arr[end] - arr[end-1] != d) {
   
10.                                         if (end - start >= 3) {
    
11.                                                 count += (end - start - 2);
    
12.                                         }
    
13.                                         start++;
    
14.                                 } else
    
15.                                         end++;
    
16.                         }
    
17.                 }
    
18.                 return count;
    
19.         }

复制代码

analog123 发表于 2014-8-27 17:02
直接上代码吧，两个index维持一个window就行了，很常规的解法

nice leetcode也有一道维持窗口的 题

看不到图啊。。。