时间戳

首页 > 解决方案 > 给定两个表示路径的数组的 Java 小练习

java - 给定两个表示路径的数组的 Java 小练习

问题描述

给定两个代表路径的数组，数组中的每个元素代表司机行驶的时间，编写一个方法来选择他能走的最快路径。驱动程序只能在阵列之间切换一次路径。例如以下数组：

int[] road1 = new int[] { 5, 4, 5, 8, 12, 9, 9, 3 };
int[] road2 = new int[] { 7, 3, 3, 12, 10, 2, 10, 7 };

输出应为 49，因为驱动程序将从 road2 开始并在索引 6 处切换到第二个数组。

编辑：我的问题是如何在切换到另一个数组后停止递归？我试图放置一个计数器标记，但它不起作用，我恢复到原来的输出。我错过了一些关于递归如何工作的东西吗？

我的代码在应该打印 49 的地方打印 53。

我的代码：

public class MyClass {

    public static int shortestRoad(int[] road1, int[] road2) {
        return shortestRoadNumbers(road1, road2, 0);
    }

    private static int shortestRoadNumbers(int[] road1, int[] road2, int index) {
        if (index == road1.length || index == road2.length) {
            return 0;
        }
        if (road1[index] >= road2[index] && road1[index + 2] >= road2[index + 2]) {
            return (road2[index] + shortestRoadNumbers(road1, road2, index + 1));
        } else {
            return (road1[index] + shortestRoadNumbers(road1, road2, index + 1));
        }

    }

    public static void main(String args[]) {
        int[] road1 = new int[] { 5, 4, 5, 8, 12, 9, 9, 3 };
        int[] road2 = new int[] { 7, 3, 3, 12, 10, 2, 10, 7 };
        MyClass.shortestRoad(road1, road2);
        int result = MyClass.shortestRoad(road1, road2);
        System.out.println(result);
    }
}

标签： javaarraysloopsrecursion

解决方案

让下面的模式来说明你的问题
在此处输入图像描述

我们有两条路径，每条路径包含许多节点（值），我们可以从一条路径切换到另一条路径一次。找到使分数最小化的节点（值）的最佳组合。
我们可以区分 4 种情况：
1- 没有切换的第一条路径的值的总和。
2-没有切换的第二条路径的值的总和。
3-从第一条路径到节点 i 的值的总和，然后从节点 i+1 切换到路径第二条路径（从节点+1 到结束的总和）
4-点 3 的倒数。

static int shortestRoad(int road1[], int road2[])
{
    // case 1
    int bestValue = sumValues(road1,0);

    // case 2
    int sumValuesRoad2 = sumValues(road2,0);
    if ( sumValuesRoad2 < bestValue)
        bestValue = sumValuesRoad2;

    // case 3: best values of all combination from road 1 to road 2
    int bestValuesSwitchFromRoad1ToRoad2 = shortestRoad_Switch_RoadFrom_RoadTo(road1, road2);
    if ( bestValuesSwitchFromRoad1ToRoad2 < bestValue)
        bestValue = bestValuesSwitchFromRoad1ToRoad2;

    // case 4: best values of all combination from road 2 to road 1
    int bestValuesSwitchFromRoad2ToRoad1 =  shortestRoad_Switch_RoadFrom_RoadTo(road2, road1);

    if ( bestValuesSwitchFromRoad2ToRoad1 < bestValue)
        bestValue = bestValuesSwitchFromRoad2ToRoad1;

    return bestValue;
}

从 idx 对给定数组的值求和直到结束：

static int sumValues(int array[], int idx_from)
{
    int sum = 0;
    for (int i = idx_from; i<array.length; ++i)
        sum += array[i];

    return sum;
}

案例 3 和 4：

static int shortestRoad_Switch_RoadFrom_RoadTo(int[] road_from, int[] road_to)
{
    int sumValues_RoadFrom_til_idx = 0;
    int sumValues_RoadFrom_idx_switch_RoadTo = 0;
    int bestValue = Integer.MAX_VALUE;

    for (int i = 0; i<road_from.length-1; ++i)
    {
        sumValues_RoadFrom_til_idx += road_from[i];

        sumValues_RoadFrom_idx_switch_RoadTo = sumValues_RoadFrom_til_idx+sumValues(road_to,i+1);

        if(sumValues_RoadFrom_idx_switch_RoadTo < bestValue )
            bestValue = sumValues_RoadFrom_idx_switch_RoadTo;
    }

    return bestValue;
}

驱动代码：

public static void main(String[] args) 
{
    
    int road1[] = { 5, 4, 5, 8, 12, 9, 9, 3 };
    int road2[] = { 7, 3, 3, 12, 10, 2, 10, 7 };

    int road_a[] = { 1, 1, 1, 1, 1, 9, 9, 9,9,9 };
    int road_b[] = { 9, 9, 9, 9, 9, 1, 1, 1,1,1 };

    int road_c[] = { 1, 1, 1, 1, 1, 2 };
    int road_d[] = { 9, 9, 9, 9, 9, 1, 1, 1,1,1 };

    System.out.println("best road1, road2 = "+shortestRoad(road1,road2));
    System.out.println("best road_a, road_b = "+shortestRoad(road_a,road_b));
    System.out.println("best road_c, road_d = "+shortestRoad(road_c,road_d));

    return 0;
}

结果：

best road1, road2 = 49
best road_a, road_b = 10
best road_c, road_d = 7

ps：您示例中的最佳路径是从 road2 开始，然后在 i=5 处切换到道路 1（我从 0 开始）

{    5, 4, 5, 8, 12, 9,  -->9, 3 }  
{ -->7, 3, 3, 12, 10, 2 /, 10, 7 }

推荐阅读