|
锁定老帖子 主题：一道JAVA面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (2)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-19
笑我痴狂 写道
scholers 写道
Kisses99 写道
scholers 写道
题目：一列整型数组，从第一个开始，累加后续两个数字，得到一个新的数组，然后判断新的数组中的最大值，从而得到这个最大值是原始数组中哪三个数字累加的，输出（打印）这三个数字，并且输出（打印）出这个最大值。 如:2,5,-6,12,7,15,6,-10 结果应该是输出：12,7,15 最大值： 34
我的思路1： 1.先统计处累加的数组，数组长度是原始数组长度-2 2.计算新数组的最大值 3.根据最大值的位置输出原始数组的三个数字 4。输出最大值
思路2（如果可以打乱原始数组的次序)： 1。先冒泡排序一次，从小到大排序 2。计算最后三个数字的值，得到结果
思路2不符合题意。
后来想了一下，思路2确实不符合题意 这样的面试题相信大家都做的出来
恩，这里确实高手很多！
|
| 返回顶楼 | |
|
发表时间：2010-10-19
lyw985 写道 感觉这题变简单了，
以前的题目是一列整型数组，找出最大的连续和值和起始下标 例子：4，-7，6，-10，-3，3，2 答案为：6，下标是2(以0开始) 从下标0开始累积和，找出最大的累积和（变量si）及下标（i），以及最小的累积和（sj）及下标j。如果i>j，那么从j+1到i的那段就是最大连续和（si-sj）；如果i<j, 则比较si与sn(全部和)-sj的大小，如果更大，则从0至i那段最大，否则j～n那段最大。 |
| 返回顶楼 | |
|
发表时间：2010-10-20
public static void main(String[] args){
[b]int[] arr = new int[]{2,5,-6,12,7,15,6,-10}; int max = 0;//记录最大值 int number = 0 ;//记录下标 for(int i = 0;i<arr.length-2;i++){ int result = arr[i]+arr[i+1]+arr[i+2]; if(result>max){ max = result; number = i; } }[/b] System.out.println("最大值为："+max+"三个数字分别为："+arr[number]+","+arr[number+1]+","+arr[number+2]); } |
| 返回顶楼 | |
|
发表时间：2010-10-20
public static void main(String[] args){
int[] arr = new int[]{2,5,-6,12,7,15,6,-10}; int max = 0;//记录最大值 int number = 0 ;//记录下标 for(int i = 0;i<arr.length-2;i++){ int result = arr[i]+arr[i+1]+arr[i+2]; if(result>max){ max = result; number = i; } } System.out.println("最大值为："+max+"三个数字分别为："+arr[number]+","+arr[number+1]+","+arr[number+2]); } |
| 返回顶楼 | |
|
发表时间：2010-10-20
tq02ksu 写道 我想到一个更简单一点的方法.
启发就是比较连续2组数的时候只需要比较有差别的那2个. 比如: 数据下标 0 1 2 和 1 2 3 比较的时候只需要比较 下标0 和下标3 的大小即可. 这样比较的次数是原来的1/3. 具体实现如下:
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 2, 5, -6, 12, 7, 15, 6, -10, 38 };
Test.find(arr);
}
public static void find(int[] data) {
/**
* make sure the length of data more than or equal 5;
*/
if (data.length <= 5)
return;
/**
* difference between current comparing data subscript
* and max subscript of data
*/
int diff = 0;
/**
* index of max subscript of data, can also be
* a array to record max combinations.
*/
int maxIdx = 0;
for (int i = 1; i < data.length - 2; i++) {
int bigger = data[i - 1] - data[i + 2];
if (diff + bigger > 0) {
diff += bigger;
} else {
maxIdx = i;
diff = data[i - 1] - data[i + 2];
}
}
System.out.println("maxIndex : " + maxIdx + ", data : " + data[maxIdx]
+ ", " + data[maxIdx + 1] + ", " + data[maxIdx + 2] + ". ");
}
}
benchmark了一下. 确实要比楼上的那个实现快一点. 100000次. 这个是1515ms, 楼上的实现是2406ms. 不过还没有达到3倍的效果... 你拿{2, 5, -6, 12, 7, 15, 6, -10, 16}这个数组试下 看你的程序对不？ |
| 返回顶楼 | |
|
发表时间：2010-10-20
public static void main(String[] args) { int[] array={2,5,-6,12,7,15,6,-10}; int max=0; Map map=new HashMap(); for (int i = 0; i < (array.length-3)+1; i++) { if(i==0 ){ max=array[i]+array[i+1]+array[i+2]; } if(max<array[i]+array[i+1]+array[i+2]){ max=array[i]+array[i+1]+array[i+2]; map.put("index", i); map.put("value", max); } } /** * 最大的值 和 开始累加的数的下标。 */ System.out.println(map); } 错了 不要骂我 只是交流 |
| 返回顶楼 | |
|
发表时间：2010-10-20
悲哀啊，题没看懂，还好我没遇到
|
| 返回顶楼 | |
|
发表时间：2010-10-21
raito_yagami 写道 悲哀啊，题没看懂，还好我没遇到
别悲哀，大家关注的角度不一样，产生的结果就不一样了。 |
| 返回顶楼 | |
|
发表时间：2010-10-21
tq02ksu 写道 我想到一个更简单一点的方法.
启发就是比较连续2组数的时候只需要比较有差别的那2个. 比如: 数据下标 0 1 2 和 1 2 3 比较的时候只需要比较 下标0 和下标3 的大小即可. 这样比较的次数是原来的1/3. 具体实现如下:
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 2, 5, -6, 12, 7, 15, 6, -10, 38 };
Test.find(arr);
}
public static void find(int[] data) {
/**
* make sure the length of data more than or equal 5;
*/
if (data.length <= 5)
return;
/**
* difference between current comparing data subscript
* and max subscript of data
*/
int diff = 0;
/**
* index of max subscript of data, can also be
* a array to record max combinations.
*/
int maxIdx = 0;
for (int i = 1; i < data.length - 2; i++) {
int bigger = data[i - 1] - data[i + 2];
if (diff + bigger > 0) {
diff += bigger;
} else {
maxIdx = i;
diff = data[i - 1] - data[i + 2];
}
}
System.out.println("maxIndex : " + maxIdx + ", data : " + data[maxIdx]
+ ", " + data[maxIdx + 1] + ", " + data[maxIdx + 2] + ". ");
}
}
benchmark了一下. 确实要比楼上的那个实现快一点. 100000次. 这个是1515ms, 楼上的实现是2406ms. 不过还没有达到3倍的效果... 确实是一个好算法，不过程序有点小问题 更正一下 import java.io.FileNotFoundException;
import java.io.RandomAccessFile;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = {2, 5, -6, 12, 7, 15, 6, -10, 16 };
Test.find(arr);
}
public static void find(int[] data) {
/**
* make sure the length of data more than or equal 5;
*/
if (data.length <= 5)
return;
/**
* difference between current comparing data subscript
* and max subscript of data
*/
int diff = 0;
/**
* index of max subscript of data, can also be
* a array to record max combinations.
*/
int maxIdx = 0;
for (int i = 1; i < data.length - 2; i++) {
int bigger = data[i - 1] - data[i + 2];
if (diff + bigger > 0) {
diff += bigger;
} else {
maxIdx = i;
diff = 0;
}
}
System.out.println("maxIndex : " + maxIdx + ", data : " + data[maxIdx]
+ ", " + data[maxIdx + 1] + ", " + data[maxIdx + 2] + ". ");
}
}
|
| 返回顶楼 | |
|
发表时间：2010-10-21
tq02ksu 写道 我想到一个更简单一点的方法.
启发就是比较连续2组数的时候只需要比较有差别的那2个. 比如: 数据下标 0 1 2 和 1 2 3 比较的时候只需要比较 下标0 和下标3 的大小即可. 这样比较的次数是原来的1/3. 具体实现如下:
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 2, 5, -6, 12, 7, 15, 6, -10, 38 };
Test.find(arr);
}
public static void find(int[] data) {
/**
* make sure the length of data more than or equal 5;
*/
if (data.length <= 5)
return;
/**
* difference between current comparing data subscript
* and max subscript of data
*/
int diff = 0;
/**
* index of max subscript of data, can also be
* a array to record max combinations.
*/
int maxIdx = 0;
for (int i = 1; i < data.length - 2; i++) {
int bigger = data[i - 1] - data[i + 2];
if (diff + bigger > 0) {
diff += bigger;
} else {
maxIdx = i;
diff = data[i - 1] - data[i + 2];
}
}
System.out.println("maxIndex : " + maxIdx + ", data : " + data[maxIdx]
+ ", " + data[maxIdx + 1] + ", " + data[maxIdx + 2] + ". ");
}
}
benchmark了一下. 确实要比楼上的那个实现快一点. 100000次. 这个是1515ms, 楼上的实现是2406ms. 不过还没有达到3倍的效果... |
| 返回顶楼 | |
