|
锁定老帖子 主题：一道软件面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：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(); 这样是最快的.. |
| 返回顶楼 | |
|
发表时间：2010-07-13
楼主的getMax方法好像不正确 我做了一些修改 public static int getMax(int[][] arrays){
希望大家指点。 |
| 返回顶楼 | |
|
发表时间：2010-07-13
angi_sky 写道
我做了一些修改 public static int getMax(int[][] arrays){
希望大家指点。 我理解题目出错。
|
| 返回顶楼 | |
|
发表时间：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);
}
}
|
| 返回顶楼 | |
|
发表时间：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文件内容格式如附件中图片。 |
| 返回顶楼 | |
|
发表时间：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;
}
}
|
| 返回顶楼 | |
|
发表时间：2010-07-13
xdsnet 写道 这个分解开其实就是每行的冒泡比较出最大数然后累加吧，应该是比较简单的，复杂度应该是固定值。
哥哥，题目看清楚。 |
| 返回顶楼 | |
|
发表时间：2010-07-14
昨晚想了一下，其实用动态规划算法并不适合这道题，也许上面的要求换成求自上而下相邻的数字的和的最大值，用动态规划才合适。毕竟题目的要求是下一行相邻数字中较大的一个累加，这也就决定了如果下一行相邻数字不相同的话，自上而下只有一条路可以走。
另外说一下，上面的测试程序没有考虑如果下行相邻两数字相同的情况，相同的情况就可能出现几个最终值，需要最后进行比对得出最大值。 |
| 返回顶楼 | |
|
发表时间：2010-07-14
最后修改：2010-07-14
原题来自：http://projecteuler.net/index.php?section=problems&id=18
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;
}
很简单嘛。
随便贴一段里面最牛逼的解题代码： 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))
|
| 返回顶楼 | |
