一道软件面试题

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

 

    5

   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，结果正确吗？

 

结果好像正确，只是看程序好像做了一些无用功
我写了一点代码，没有别的意思，只是我先抛块砖，希望能引出玉来。
        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();

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

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

这段代码好像有问题的吧

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

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

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

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

没有人尝试用递归么？

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