1. 数组中找两数和小于等于M的数对数量 100
2. 字符串的第k个字符 100
3. 小朋友分纸张 70
4. 二维数组求最短路径 66.67
第三题部分代码，过了70%，请问有路过的大佬解释一下吗？
int tmp = list.get(0); // 第一个小朋友年龄
int num = 1; // 记录纸的总数
int per = 1; // 当前小朋友该发的纸数
for (int i = 1; i < list.size(); i++) { // 遍历其他小朋友
int age = list.get(i);
if (age > tmp) { // 后面小朋友年纪大，多发一张：per+1
per++;
} else if (age < tmp) { // 小 --->有一句话：【旁边】小朋友年龄大的话纸张数要多
per--;
} else // 同岁
per = 1; // // 同岁的小朋友可以少于等于
tmp = list.get(i);
num += per;
} 第四题用的是矩阵动态规划的思想，想不明白为什么没有AC public static int minSailCost(int[][] input) {
int m = input.length, n = input[0].length;
int[][] res = new int[m][n];
res[0][0] = 0;
// 初始化第一列
for (int i = 1; i < m; i++) {
if (input[i][0] == 0)
res[i][0] += (res[i - 1][0] + 2);
if (input[i][0] == 1)
res[i][0] += (res[i - 1][0] + 1);
if (input[i][0] == 2)
res[i][0] = Integer.MAX_VALUE;
}
// 初始化第一行
for (int j = 1; j < n; j++) {
if (input[0][j] == 0)
res[0][j] += (res[0][j - 1] + 2);
if (input[0][j] == 1)
res[0][j] += (res[0][j - 1] + 1);
if (input[0][j] == 2)
res[0][j] = 999999;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (res[i - 1][j] == 9999999 && res[i][j - 1] == 9999999) {
return -1;
}
if (input[i][j] == 0)
res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + 2;
if (input[i][j] == 1)
res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + 1;
if (input[i][j] == 2)
res[i][j] = 9999999;
}
}
print(res);
return res[m - 1][n - 1];
} 
全部评论
(6) 回帖