Closed. This question needs details or clarity. It is not currently accepting answers. Learn more。
想改进这个问题吗?添加细节并通过editing this post澄清问题。
我必须找到最小索引才能启动两个数组,如下所示:
cities= [2,4,5,2] gallons = [4,3,1,3]
这个问题包括两部分
在第一部分中,我必须找到一个有效的起始城市是否存在。在上面的例子中,我不能从第一个位置开始,因为城市(cities[0])的第一个位置的值小于加仑(gallons[0]=4)的第一个位置的值所以我必须继续寻找正确的索引我可以开始旅行的第一点是在指数1中,因为城市[1]>=加仑[1]。此时路径为:
4-gallons[1] + cities[2] = 4 -3 + 5 = 6
6-gallons[2] + cities[3] = 6 -1 + 2 = 7
7-gallons[3] + cities[0] = 7 -3 + 2 = 6
6-gallons[0] = 6-4 =2
返回将是1,我开始旅程的指数。
下一个是无效路径,因此在这种情况下,我必须返回-1:
cities= [8,4,1,9] gallons= [10,9,3,5]
在上面的例子中,我从索引3开始,因为它是第一个城市大于加仑的位置,所以在这种情况下,操作如下:
注意:列表是循环的,因此本例中的下一个城市是cities[0]=8,在下面的示例中:
9-gallons[3] + cities[2] + cities[0] = 9 -5 + 8 = 12
12-gallons[0] + cities[1] = 12 -10 + 4 = 6
6-gallons[1] + cities[2] = 6 - 9 + 1
在最后的操作中6-9=-3,因为这个原因,我们没有足够的加仑来继续行程,所以响应是-1,我们不需要继续这个过程。
接下来是另一个从指数0开始的情况,因为城市[0]>=加仑[0]:
cities[3,2,5,4] gallons = [2,3,4,2]
cities[0] - gallons [0] + cities[1] = 3-2+2 = 3
3 - gallons [1] + cities[2] = 3-3+5 = 5
5 - gallons [2] + cities[3] = 5-4+4 = 5
5 - gallons [3] = 5-2 = 3
这种情况下的响应是0,因为我们从指数0开始,路线是有效的,我的意思是我们总是有足够的加仑来继续旅行(我们没有在城市累计总行程减去可用加仑数之间出现负结果,与第二种情况的例子相反)。
下一个是到目前为止我的代码,但我失败了几个测试用例,我做了几个个人测试用例,但我真的不知道为什么我的代码会失败,有什么想法吗?这两个数组可能有不同的维数。
public static int bestIndexToStartJorney(List<Integer> cities, List<Integer> gallons) {
int n = 0;
int starts = -1;
int total = 0;
if (cities.size() > 0 && gallons.size() > 0 && (cities.size() == gallons.size())) {
n = cities.size();
} else {
return -1;
}
for (int i = 0; i < n; i++) {
if (cities.get(i) >= gallons.get(i)) {
//Define a start point
starts = i;
break;
}
}
//If we have a valid case.
if (starts >= 0) {
total = cities.get(starts);
for (int i = 0; i < n; i++) {
//Constraints
if ((cities.get(i) < 0 || cities.get(i) > 10000) || (gallons.get(i) < 0 || gallons.get(i) > 10000)) {
starts = -1;
break;
}
//Define the current position to transverse circularly
int position = (i + starts) % n;
total += -gallons.get(position);
//If total < gallonsance the path is invalid.
if (total < 0) {
starts = -1;
break;
}
if (position < n - 1 && position + 1 != starts) {
total += cities.get(position + 1);
} else {
if (starts > 0 && position + 1 != starts)
total += cities.get(0);
}
}
}
return starts;
}
限制条件:
1<=size <= 100000
0<=cities[i] <= 10000
0<=gallons[i] <= 10000
最佳答案
目前,你使用position + 1
来计算下一个位置,但是在循环标引位置本身之前,它没有循环使用,没有以前使用的% n
。
因此,您的for循环结束时的if语句应该能够被使用循环索引的下面所替换。
int nextPosition = (position + 1) % n;
if (nextPosition != starts) {
total += cities.get(nextPosition);
}
这就是我在代码中看到的所有可能会给您带来问题的地方,因此如果没有一些失败的测试用例,我就无法进一步帮助您。