如何在 Java 中处理分支计算？

Question

我试图根据变量有多少个连接来找到最长的可能路径，而不需要重复连接。我想到的方法是创建一个列表，其中包含已经经过的所有点，但是当路径结束并且我需要检查新路径时，所有这些旧连接都保留在列表中。如何从初始点重新开始我的列表？

将其放入递归函数本身每次都会清除列表。有比使用列表更好的选择吗？

相关代码：

package testapp;

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.io.IOException;

import java.util.List;

class TestApp {   

    // Store list of objects we have already matched with

    static List<NumberObject> holdingList = new ArrayList<NumberObject>();

    

    //Test objects

    static int[] array1 = {2,2};

    static int[] array2 = {3,1};

    static int[] array3 = {2,1};

    static int[] array4 = {1,1};

    

    static NumberObject eight = new NumberObject(array1, 8);

    static NumberObject two = new NumberObject(array2, 2);

    static NumberObject three = new NumberObject(array3, 3);

    static NumberObject four = new NumberObject(array4, 4);

    // Test objects ^^

    

    public static int longestSequence(int[][] grid) {

        // TODO: implement this function

        // Code exists here not relevant to the problem

        //Setting up a new numberList array for testing

        NumberObject[] newNumberList = {eight, two, three, four};

        NumberObject[] connections1 = {two, four};

        NumberObject[] connections2 = {two, three};

        //Adding connections

        eight.connections = connections1;

        four.connections = connections2;

        

        for (NumberObject s: newNumberList){

          recursive(s);

        }

        return 0;

    }

理想情况下，图像显示我想要发生的事情。相反，所有旧的分支连接仍保持在 上holdingList。应该注意的是，路径可以分支到两个以上的其他对象。

Answer 1

您可以将列表副本的实例作为参数传递给函数，而不是将列表存储在字段中。所以你的函数的签名recursive将如下所示：public static void recursive(NumberObject object, List<NumberObject> visited)为了隐藏此实现细节，我建议编写两个函数，其中第二个函数仅将空列表传递给另一个函数。但是，我会选择不同的方法，因为您的新列表会获取与树中的条目一样多的新列表。在以下实现中，每个“树端”只有一个列表。此外，就像前面的建议一样，这使您的班级保持无状态。static List<NumberObject> findLongestPath(NumberObject currentNode) {&nbsp; &nbsp; &nbsp; &nbsp; if (currentNode.getConnectedNodes().isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; List<NumberObject> result = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.add(currentNode);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; List<NumberObject> longestPath = currentNode.getConnectedNodes().stream()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map(PathFinder::findLongestPath)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .max(Comparator.comparing(List::size))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .get();&nbsp; &nbsp; &nbsp; &nbsp; longestPath.add(currentNode);&nbsp; &nbsp; &nbsp; &nbsp; return longestPath;&nbsp; &nbsp; }