二维数组遍历以获得不同的 7 位数字组合

Question

我运行遇到了面试准备书中的一个棘手问题，该问题...... 您有一个包含 1 到 9 整数的 3 x 3 矩阵，如下所示

 1 2 3
 4 5 6
 7 8 9

如何获得第一个数字都以 4 开头的唯一 7 位数字组合（矩阵 [1][0]）。遍历就像棋盘上的车一样。水平或垂直的一种方式......（顺便说一句，4125874 是有效的 7 位数字组合）。

我尝试编写一些代码并在此处使用布尔访问标志进行常规 2D 矩阵遍历以获得答案并将每个组合存储在 hashSet 中以确保唯一性但我被卡住了。任何能让我的代码正常工作的评论、提示和代码修改都将不胜感激。

class Ideone
{

    void dfs(int[][] matrix, boolean visited) //considered dfs with a boolean visited flag but I am stuck. I want to make my solution recursive
    {
        boolean visited =  false;

    }

    public static HashSet<String> get7DigitCombo(int[][] matrix)
    {
        String result = "";
        int[][] cache =  matrix.clone();
        Set<String> comboSet =  new HashSet<String>();
        boolean visited =  false;

        int resultStart = matrix[1][0];

        for(int row = 1; row < matrix.length; row++)
        {
            for(int col = 0; col < matrix[0].length; col++)
            {
                if (visited == false & result.length < 7)
                {
                    result += "" + (matrix[row + 1][col] || matrix[row -1][col] || matrix[row][col+1] || matrix[row][col-1]);
                }

            }
        }

        comboSet.add(result);
        return comboSet;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        int[][] matrix =  {{1, 2, 3},
                          {4, 5, 6}, 
                          {7, 8, 9},
                          };

        HashSet<String> comboSet =  get7DigitCombo(matrix);

        System.out.print(comboSet);
    }
}

Answer 1

这是一道吃豆子问题。您必须寻找或定义每个矩阵值的邻居。然后交叉矩阵 fallowing 每个矩阵值的邻居。它通常用递归函数解决。我认为您的代码必须使用不同的方法从头开始更改。

Answer 2

下面的mcve演示了递归获取邻居然后累加到独特的组合。
代码记录在注释中：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Ideone
{
    private static final int SIZE = 7;     //size of combo 

    private static int[][] directions = {  //represents moving directions 
            {-1, 0},  //up
            { 0,-1},  //left
            { 0, 1},  //right
            { 1, 0}   //down
    };

    public static void main (String[] args) throws java.lang.Exception
    {
        int[][] matrix =  {{1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
        };
        Set<String> comboSet =  get7DigitCombo(matrix);
        System.out.print(comboSet.size());
    }

    public static Set<String> get7DigitCombo(int[][] matrix)
    {
        Set<String> comboSet =  new HashSet<>();

        get7DigitCombo(1, 0, matrix, String.valueOf(matrix[1][0]), comboSet);
        return comboSet;
    }

     //recursively get all neighbors. generate combos by appending each neighbor 
    //combo represents a single combination. combos accumulates combination 
    static void get7DigitCombo(int row, int col, int[][] matrix, String combo, Set<String> combos){

        if(combo !=null && combo.length() == SIZE) { //when combo reached the right size, add it  
            //System.out.println(combo);
            combos.add(combo);
            return;
        }

        //get and iterate over all adjacent neighbors 
        for(int[] neighbor : getNeighbors(row, col, matrix)){
            get7DigitCombo(neighbor[0], neighbor[1], matrix, combo+neighbor[2], combos);
        }
    }

    //return list of adjacent neighbors. each neighbor is represented by
    //int[3]: row, column, value
    private static List<int[]> getNeighbors(int row, int col, int[][] matrix) {

        List<int[]> neighbors = new ArrayList<>();
        for(int[] dir : directions){
            int newRow = row + dir[0] ; int newCol = col + dir[1];
            if(isValidAddress(newRow, newCol, matrix)) {
                neighbors.add( new int[]{newRow,newCol, matrix[newRow][newCol]});
            }
        }
        return neighbors;
    }

    private static boolean isValidAddress(int row, int col, int[][] matrix) {

        if(row < 0 || col < 0) return false;
        if(row >= matrix.length || col >= matrix[row].length) return false;
        return true;
    }
}

二维数组遍历以获得不同的 7 位数字组合

2D array traversal to get distinct 7 digit number combos

hashset

multidimensional-array

depth-first-search