`
scholers
  • 浏览: 614810 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

一道JAVA面试题

面试JavaJ#算法 
阅读更多

   题目：一列整型数组，从第一个开始，累加后续两个数字，得到一个新的数组，然后判断新的数组中的最大值，从而得到这个最大值是原始数组中哪三个数字累加的，输出（打印）这三个数字，并且输出（打印）出这个最大值。

   如:2,5,-6,12,7,15,6,-10

  结果应该是输出：12,7,15

   最大值： 34

 

 

 我的思路1：

  1.先统计处累加的数组，数组长度是原始数组长度-2

  2.计算新数组的最大值

  3.根据最大值的位置输出原始数组的三个数字

  4。输出最大值

 

 思路2（如果可以打乱原始数组的次序)：

  1。先冒泡排序一次，从小到大排序

  2。计算最后三个数字的值，得到结果

 

 

 

 

分享到：
| 美剧LOST--《迷失》
评论
35 楼 dreamtalee 2010-10-22   
public class Lianxi1
{
	public static void main(String[]args)
	{
		int[] sample = {2,5,-6,12,7,15,6,-10};
		int[] sample1= {15,8,12,13,5,17};
		result(sample1);
		result(sample);
	}
	public static void result(int[] old)
	{
		int index[]=new int[5];
		int max = 0;
		int j = 0;
		for(int i = 0; i<old.length-2; i++)
		{
			if(old[i]+old[i+1]+old[i+2]>max)
			{
				max = old[i]+old[i+1]+old[i+2];
				index[j] = i;
			}else if(old[i]+old[i+1]+old[i+2]==max)
			{
				j++;
				index[j] = i;
			}
			
		}
		System.out.println("max="+max);
		for(int k = 0;k<=j;k++)
		System.out.println(old[index[k]]+","+old[index[k]+1]+","+old[index[k]+2]);
	}
}

sample1= {15,8,12,13,5,17};
这种情况两组都打印
34 楼 scholers 2010-10-22  
lxs575208196 写道
我怎么看不懂题目的意思啊 、？  什么叫累加啊？  累加后怎么办。。。。


累加后形成一个新的数组，然后找出新数组的最大值，然后得到下标，算出新数组是原始数组中哪三个值计算出来的
33 楼 lxs575208196 2010-10-22  
我怎么看不懂题目的意思啊 、？  什么叫累加啊？  累加后怎么办。。。。
32 楼 scholers 2010-10-22  
marshaldong 写道
public static void main(String[] args)
{
int[] num = new int[] { 2, 5, -6, 12, 7, 15, 6, -10 };
int length = num.length;
ArrayList newArray = new ArrayList();

int i = 0;
for (; i < length - 2; i++)
{
newArray.add(num[i] + num[i + 1] + num[i + 2]);

}
int max = (Integer) Collections.max(newArray);
int index = newArray.indexOf(max);
System.out.println(max + "=" + num[index] + "+" + num[index + 1] + "+" + num[index + 2]);

}



这位兄弟对JAVA的基类很精通啊，这个方法最简单了，估计代码量最少
31 楼 marshaldong 2010-10-21  
public static void main(String[] args)
{
int[] num = new int[] { 2, 5, -6, 12, 7, 15, 6, -10 };
int length = num.length;
ArrayList newArray = new ArrayList();

int i = 0;
for (; i < length - 2; i++)
{
newArray.add(num[i] + num[i + 1] + num[i + 2]);

}
int max = (Integer) Collections.max(newArray);
int index = newArray.indexOf(max);
System.out.println(max + "=" + num[index] + "+" + num[index + 1] + "+" + num[index + 2]);

}
30 楼 luobin23628 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倍的效果...

经测试。效率和楼上一样。
29 楼 luobin23628 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倍的效果...

28 楼 luobin23628 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] + ". ");
	}
}
27 楼 scholers 2010-10-21  
raito_yagami 写道
悲哀啊，题没看懂，还好我没遇到



别悲哀，大家关注的角度不一样，产生的结果就不一样了。
26 楼 raito_yagami 2010-10-20  
悲哀啊，题没看懂，还好我没遇到
25 楼 scx0237 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);
}


错了 不要骂我  只是交流
24 楼 renwolang521 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}这个数组试下 看你的程序对不？
23 楼 dxjaccp 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]);
}
22 楼 dxjaccp 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]);
}
21 楼 jwd001 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那段最大。

20 楼 scholers 2010-10-19  
<div class="quote_title">笑我痴狂 写道</div>
<div class="quote_div">
<div class="quote_title">scholers 写道</div>
<div class="quote_div">
<div class="quote_title">Kisses99 写道</div>
<div class="quote_div">
<div class="quote_title">scholers 写道</div>
<div class="quote_div">
<p>   题目：一列整型数组，从第一个开始，累加后续两个数字，得到一个新的数组，然后判断新的数组中的最大值，从而得到这个最大值是原始数组中哪三个数字累加的，输出（打印）这三个数字，并且输出（打印）出这个最大值。</p>
<p><span style="font-size: 14.4px;">   如:2,5,-6,12,7,15,6,-10</span></p>
<p><span style="font-size: 14.4px;">  结果应该是输出：</span><span style="font-size: 14.4px;">12,7,15</span></p>
<p><span style="font-size: 14.4px;">   最大值： 34</span></p>
<p> </p>
<p> </p>
<p> 我的思路1：</p>
<p>  1.先统计处累加的数组，数组长度是原始数组长度-2</p>
<p>  2.计算新数组的最大值</p>
<p>  3.根据最大值的位置输出原始数组的三个数字</p>
<p>  4。输出最大值</p>
<p> </p>
<p> 思路2（如果可以打乱原始数组的次序)：</p>
<p>  1。先冒泡排序一次，从小到大排序</p>
<p>  2。计算最后三个数字的值，得到结果</p>
<p> </p>
<p> </p>
<p> </p>
<p> </p>
</div>
<p>思路2不符合题意。</p>
</div>
<p> </p>
<p>  后来想了一下，思路2确实不符合题意</p>
</div>
<div class="quote_div">这样的面试题相信大家都做的出来</div>
<p> </p>
<p> </p>
<p> 恩，这里确实高手很多！</p>
</div>
<p> </p>
19 楼 笑我痴狂 2010-10-19  
<div class="quote_title">scholers 写道</div>
<div class="quote_div">
<div class="quote_title">Kisses99 写道</div>
<div class="quote_div">
<div class="quote_title">scholers 写道</div>
<div class="quote_div">
<p>   题目：一列整型数组，从第一个开始，累加后续两个数字，得到一个新的数组，然后判断新的数组中的最大值，从而得到这个最大值是原始数组中哪三个数字累加的，输出（打印）这三个数字，并且输出（打印）出这个最大值。</p>
<p><span style="font-size: 14.4px;">   如:2,5,-6,12,7,15,6,-10</span></p>
<p><span style="font-size: 14.4px;">  结果应该是输出：</span><span style="font-size: 14.4px;">12,7,15</span></p>
<p><span style="font-size: 14.4px;">   最大值： 34</span></p>
<p> </p>
<p> </p>
<p> 我的思路1：</p>
<p>  1.先统计处累加的数组，数组长度是原始数组长度-2</p>
<p>  2.计算新数组的最大值</p>
<p>  3.根据最大值的位置输出原始数组的三个数字</p>
<p>  4。输出最大值</p>
<p> </p>
<p> 思路2（如果可以打乱原始数组的次序)：</p>
<p>  1。先冒泡排序一次，从小到大排序</p>
<p>  2。计算最后三个数字的值，得到结果</p>
<p> </p>
<p> </p>
<p> </p>
<p> </p>
</div>
<p>思路2不符合题意。</p>
</div>
<p> </p>
<p>  后来想了一下，思路2确实不符合题意</p>
</div>
<div class="quote_div">这样的面试题相信大家都做的出来</div>
<p> </p>
18 楼 randi0624 2010-10-19  
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倍的效果...

一看思想就比我考虑得好，，顶了、、、
17 楼 dingherry 2010-10-19  
1.用数组记录的方式，不如用MAP优。
2.若存在最大值是多个的情况，打印所有的数组对还是第一次出现的那组数据？
16 楼 tq02ksu 2010-10-19  
我想到一个更简单一点的方法.

启发就是比较连续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倍的效果...
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics