一道软件面试题

eddysheng

浏览: 111718 次
性别:
来自: 北京

最近访客更多访客>>

存储炒菜错

binbin_xiang

鸡蛋灌饼

wlyp4

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

软件思想

面试软件测试 J#算法 F#

从第一行的第一个数字开始，计算下一行临近的两个数字中较大的一个，统计所有临近较大数字的总和，看下例：

9 6

4 6 8

0 7 1 5

计算总和为：5+9+6+7=27

用程序计算附件中的总和值。

simplest Demo：

package algorith;

import java.io.InputStream;
import java.util.List;

import org.apache.commons.io.IOUtils;

public class TestTriangle {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		InputStream ins = TestTriangle.class.getResourceAsStream("file2.txt");
		List<String> lines = IOUtils.readLines(ins);
		for(String line:lines){
			//System.out.println(line);
		}
		int[][] arrays = new int[lines.size()][];
		int i = 0;
		for(String line:lines){
			String[] temp = line.split(" ");			
			arrays[i] = getIntArray(temp);			
			i++;
		}
		int max = getMax(arrays);
		System.out.println("Max=="+max);
	}
	
	public static int[] getIntArray(String[] strs){
		int[] temp = new int[strs.length];
		int i = 0;
		//StringBuffer sb = new StringBuffer("");
		for(String s:strs){
			temp[i] = Integer.parseInt(s);
			//sb.append(temp[i]).append("-");
			i++;
		}
		//System.out.println("=length="+temp.length);
		return temp;
	}
	
	public static int getMax(int[][] arrays){
		int max = arrays[0][0];
		//System.out.println("=number="+arrays[0][0]);
		int px=0,py=0;
		for(int i=1;i<arrays.length;i++){
			px = i;
			int pyl = py;
			int pyr = py+1;
			if(arrays[px][pyl]>=arrays[px][pyr]){
				py = pyl;
			}else{
				py = pyr;
			}
			//System.out.println("=number="+arrays[px][py]);
			max += arrays[px][py];
		}
		return max;
	}

}

运算结果为655321，结果正确吗？

file2.rar (11.8 KB)
下载次数: 161

分享到：

关于数据库sharding带来的聚合问题 | How other's become mine?

2010-07-12 15:22
浏览 1368
评论(18)
论坛回复 / 浏览 (18 / 11091)
分类:编程语言
查看更多

18 楼徐风子 2010-07-14

原题来自：http://projecteuler.net/index.php?section=problems&id=18
 
java解法：
<pre name="code" class="java">public static int maxSum(int[][] graph, int x, int y, int sum) {
if (x == 14)
 return sum+graph[x][y];
int max = max = Math.max(maxSum(graph, x+1, y, sum), maxSum(graph, x+1, y+1, sum));
sum += graph[x][y];
return sum+max;
}</pre>
 很简单嘛。
 
随便贴一段里面最牛逼的解题代码：
<pre name="code" class="Haskell">triangle =
 [[75],
 [95, 64],
 ... Snip ...
 [04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23]]

main = print (foldr1 reduce triangle)
 where reduce a b = zipWith (+) a (zipWith max b (tail b))</pre>

17 楼 eddysheng 2010-07-14

昨晚想了一下，其实用动态规划算法并不适合这道题，也许上面的要求换成求自上而下相邻的数字的和的最大值，用动态规划才合适。毕竟题目的要求是下一行相邻数字中较大的一个累加，这也就决定了如果下一行相邻数字不相同的话，自上而下只有一条路可以走。

另外说一下，上面的测试程序没有考虑如果下行相邻两数字相同的情况，相同的情况就可能出现几个最终值，需要最后进行比对得出最大值。

16 楼 hz86655032 2010-07-13

xdsnet 写道

这个分解开其实就是每行的冒泡比较出最大数然后累加吧，应该是比较简单的，复杂度应该是固定值。

哥哥，题目看清楚。

15 楼 eddysheng 2010-07-13

这个看来用动态规划算法比较合适，刚才网上搜索了一下，发现已经很多解法，其中一个是来自http://www.java3z.com/cwbwebhome/article/article5/51198.html
内容：

public class Test{
  public static void main(String args[]){
     int n=5;
    int a[][]={{0,0,0,0,0,7,0,0,0,0,0},
               {0,0,0,0,3,0,8,0,0,0,0},
               {0,0,0,8,0,1,0,0,0,0,0},
               {0,0,2,0,7,0,4,0,4,0,0},
               {0,4,0,5,0,2,0,6,0,5,0}};
    int s[][]=new int[5][11];  
    s[0][5]=a[0][5]; 
    for(int i=1;i< n;i++){
     for(int j=1;j< 10;j++){
       s[i][j]=Math.max(s[i-1][j-1],s[i-1][j+1])+a[i][j];
     }
    }
    System.out.println("原始数据");
    for(int i=0;i< n;i++){
     for(int j=0;j< 11;j++){
       System.out.printf("%-4d",a[i][j]);
    }
    System.out.println();
   }
    
   System.out.println();
   System.out.println("对应的最大路径");
   for(int i=0;i< n;i++){
     for(int j=0;j< 11;j++){
       System.out.printf("%-4d",s[i][j]);
    }
    System.out.println();
   }
   System.out.println();
   System.out.println("最长路径的值为：");
    System.out.println(max(s[n-1]));
 
}
  public static int max(int b[]){
    int max=b[0];
   for(int i=1;i< b.length;i++){
     if(b[i]>max) max=b[i];
   }
   return max;
 }
     
}

14 楼 imtrash 2010-07-13

不知道是不是写的罗嗦，请指正。

package MianShi;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;



public class exam1 {

	public static void main(String args[]){
		try {
			InputStream is = new FileInputStream("src/MianShi/asd.txt");
			InputStreamReader in = new InputStreamReader(is);
			BufferedReader bufReader = new BufferedReader(in);
			
			String lineContent;//每行的内容
			
			boolean firstLine = true;//是否是第一行
			
			int upperIndex = 0;//焦点index
			int preIndex;//当前行与焦点临近的前一个数的index
			int nextIndex;//当前行与焦点临近的后一个数的index
			
			int upperValue = 0;//焦点值
			int preValue;//当前行焦点前一个值
			int nextValue;//当前行焦点后一个值
			
			int total = 0;//总值
			
			while((lineContent = bufReader.readLine())!=null){
				if(firstLine){
					upperIndex = lineContent.length()-1;
					preIndex = 0;
					nextIndex = 0;
					
					upperValue = Integer.parseInt(""+lineContent.charAt(upperIndex));
					preValue = 0;
					nextValue = 0;
					
					total += upperValue;
					firstLine = false;
				}else{
					
					preIndex = upperIndex - 1;
					nextIndex = upperIndex + 1;
					
					preValue = indexGetValue(preIndex,lineContent);
					nextValue = indexGetValue(nextIndex,lineContent);
					upperValue = focused(preValue, nextValue);
					
					upperIndex = (upperValue==preValue?preIndex:nextIndex);
					
					total += upperValue;
				}
			}
			System.out.println(total);
			
			bufReader.close();
			in.close();
			is.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}
	
	private static int indexGetValue(int index, String lineContent) {
		return Integer.parseInt(""+lineContent.charAt(index));
	}

	private static int focused(int pre, int next){
		return pre>next?pre:next;
	}

}

asd.txt文件内容格式如附件中图片。

13 楼 tangshuang 2010-07-13

我不知道你的文件格式是什么样的，不过可以模拟一下，你参考一下吧：

public class Test2 {
	public static void main(String[] args) {
		StringBuffer sb = new StringBuffer();
		sb.append("5\r");
		sb.append("9 6\r");
		sb.append("4 6 8\r");
		sb.append("0 7 1 5\r");

		System.out.println(sb.toString());

		System.out.println("------------------");

		int sum = 0;
		int rowMaxIndex = 0;
		String[] rows = sb.toString().split("\r");
		for (int i = 0; i < rows.length; i++) {
			String row = rows[i];
			String[] cells = row.split(" ");
			int cellMax = Integer.parseInt(cells[0]);
			int min = rowMaxIndex <= 0 ? 0 : rowMaxIndex;
			int max = rowMaxIndex >= cells.length - 1 ? cells.length - 1
					: rowMaxIndex + 1;
			for (int j = min; j <= max; j++) {
				int temp = Integer.parseInt(cells[j]);
				if (temp > cellMax) {
					cellMax = temp;
					rowMaxIndex = j;
				}
			}
			System.out.println(cellMax);
			sum += cellMax;

		}
		System.out.println(sum);

	}
}

12 楼 angi_sky 2010-07-13

<div class="quote_title">angi_sky 写道</div>
<div class="quote_div">
 
我做了一些修改
public static int getMax(int[][] arrays){ int max = arrays[0][0]; for(int i=1;i<arrays.length;i++){ int temp =arrays[i][0]; for(int j=0;j<arrays[i].length-1;j++){ if(temp<arrays[i][j+1]){ temp=arrays[i][j+1]; } } max+=temp; } return max; } 
 
希望大家指点。
我理解题目出错。
</div>

11 楼 angi_sky 2010-07-13

楼主的getMax方法好像不正确
我做了一些修改
public static int getMax(int[][] arrays){ int max = arrays[0][0]; for(int i=1;i<arrays.length;i++){ int temp =arrays[i][0]; for(int j=0;j<arrays[i].length-1;j++){ if(temp<arrays[i][j+1]){ temp=arrays[i][j+1]; } } max+=temp; } return max; } 
 
希望大家指点。

10 楼 seele 2010-07-13

shbgreenery 写道

结果好像正确，只是看程序好像做了一些无用功
我写了一点代码，没有别的意思，只是我先抛块砖，希望能引出玉来。
        String strFile = "file2.txt";
        File f = new File(strFile);
        int row = 0;
        int col = 0;
        int sum = 0;
        BufferedReader reader = new BufferedReader(new FileReader(f));
        for (String line = null; (line = reader.readLine()) != null;) {
            String[] str = line.split("\\s+");
            if (row == 0) {
                sum += Integer.parseInt(str[0]);
            } else {
                int a = Integer.parseInt(str[col]);
                int b = Integer.parseInt(str[col + 1]);
                if (a > b) {
                    sum += a;
                } else {
                    sum += b;
                    col += 1;
                }
            }
            row += 1;
        }
        System.out.println(sum);
        reader.close();

这样是最快的..

9 楼 braint8 2010-07-13

几乎没接触用算法，是不是很失败，咋整

8 楼 seele 2010-07-13

没有人尝试用递归么？

7 楼 xdsnet 2010-07-13

这个分解开其实就是每行的冒泡比较出最大数然后累加吧，应该是比较简单的，复杂度应该是固定值。

6 楼 shbgreenery 2010-07-13

淡夏的斌写道

shbgreenery 写道

这段代码好像有问题的吧

有什么问题呢？难道是说没有类名和主函数名？

5 楼 kingjiang09 2010-07-13

读每行的前两位存入一个2维整形数组,不足两位用0补

int total=0;
for(int [] num:array){
if(num[0]>num[1]){
total+=num[0];
}else{
total+=num[1];
}
}

4 楼淡夏的斌 2010-07-12

shbgreenery 写道

这段代码好像有问题的吧

3 楼 fivestarwy 2010-07-12

这个要用动规的，你用贪心显然错了，比如
5
9 6
4 6 84
0 7 1 5
应得到100

2 楼 samwalt 2010-07-12

只看了题目，没有看代码。
用动态规划算法吧。

1 楼 shbgreenery 2010-07-12

发表评论

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

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论