java - Java名人算法的蛮力解决方案

在N人的聚会中，每个人只有一个人认识。这样的人可能在聚会中，如果是的话，他不认识聚会中的任何人。我们只能问“ A知道B吗？ ”。在最少的问题中找到陌生人（名人）。

我知道可以使用队列或堆栈来解决此问题，但我想先使用蛮力解决它，然后再练习。我的尝试遍历矩阵，看哪一行全为0。现在，我该如何再次检查该行是否包含一个0和其余的1s？这是我的代码：

public static int[][] matrix = {{0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 0, 0},
                                {0, 0, 1, 0}};

public static void main(String[] args) {
    if(knowsCeleb() > 0){
        System.out.println(knowsCeleb() + " is the celebrity.");
    }else{
        System.out.println("There is no celebrity.");
    }
}

public static int knowsCeleb(){
    int count = 0;

    for(int i = 0; i < matrix.length; i++){
        for(int j = 0; j < matrix[i].length; j++){

            if(matrix[i][j] == 0){
                count++;
            }else{
                count = 0;
                break;
            }
        }

        if(count == matrix[i].length){
            return (i+1);
        }
    }
    return 0;
}

在这种情况下，第三行是名人，因为它不认识一个人（该行中为0），但每个人都知道它（该列中为1s）。如何修复我的代码，以便它仔细检查正确的列是否包含1和一个零。例如，此输入：

 public static int[][] matrix = {{0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 0, 0}};

即使没人知道4（在最后一列中没有1），它也会显示4是名人。如何执行第二次检查以确认它实际上是名人？请帮忙！

最佳答案

如果我正确地理解了目标，则看来您已经描述了确认矩阵条目所必须满足的条件：“仔细检查正确的列是否包含1和一个零。”因此，我们可以创建一个可以做到这一点的方法，显式检查列中是否包含一和一个零：

public static boolean confirm(int column){
    int zeros = 0;
    int ones = 0;
    column = column - 1; // java indexes from zero, so we decrement column

    boolean confirmed = false; // set the result initially unconfirmed

    // for each row
    for(int i = 0; i < matrix[column].length; i++){
        // if the value in the specified column is zero
        if (matrix[i][column] == 0)
            // add to zeros
            zeros++;
        // otherwise if the value in the specified column is one
        else if (matrix[i][column] == 1)
            // add to ones
            ones++;
    }

    // the condition we want to double check
    // "correct column contains 1s and one zero"
    if (zeros == 1 && ones == 3){
        confirmed = true;  // confirm
    }
    return confirmed;
}

现在我们有了可用的方法，从main调用它：

System.out.println("Confirm " + knowsCeleb() + ": " + confirm(knowsCeleb()));

给输出类似：

3 is the celebrity.
Confirm 3: true

关于java - Java名人算法的蛮力解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47625932/