問題給定一個二維數組（矩陣），其高度和寬度可能不相等，僅包含 0 和 1。每個 0 代表土地，每個 1 代表河流的一部分。一條河流由任意數量的水平或垂直相鄰（但不是對角線相鄰）的 1 組成。形成河流的相鄰 1 的數量決定了它的大小。編寫一個函數，返回一個數組，該數組包含輸入矩陣中表示的所有河流的大小。請注意，這些尺寸不需要按任何特定順序排列。Input [[1,0,0,1,0],[1,0,1,0,0],[0,0,1,0,1],[1,0,1,0,1],[1,0,1,1,0],]Output [1,2,2,2,5]我的方法在評估了這個問題之后，我覺得這應該使用像算法這樣的圖形遍歷來完成，也許是深度優先搜索。這正是我所做的。我從左上角遍歷矩陣，看看是否訪問了該值，如果未訪問，如果值為 1，則我遍歷它的所有節點并保留一個計數器以保持河流的大小。最后，我用總河流大小更新了一個數組列表。出于某種原因，我的結果不正確，我不確定我做錯了什么。我也手動跟蹤了我的代碼，但無法找出問題所在。我的代碼import java.util.ArrayList;class Program { public static ArrayList<Integer> riverSizes(int[][] matrix) { ArrayList<Integer> result = new ArrayList<Integer>(); boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length]; for(int row = 0; row<matrix.length; row++){ for(int col = 0; col<matrix.length; col++){ int count = 0; count = traverseMatrix(row,col,matrix,visitStatus,count); result.add(count); } } return result; } public static int traverseMatrix(int row, int col, int [][] matrix, boolean [][] visitStatus, int count){ if(visitStatus[row][col] == true){ return count; }else if(matrix[row][col] == 0){ visitStatus[row][col] = true; return count; }else{ count++; visitStatus[row][col] = true; if(isValid(row,col-1,matrix)){ return traverseMatrix(row,col-1,matrix,visitStatus,count); } if(isValid(row,col+1,matrix)){ return traverseMatrix(row,col+1,matrix,visitStatus,count); } if(isValid(row-1,col,matrix)){ return traverseMatrix(row-1,col,matrix,visitStatus,count); } if(isValid(row+1,col,matrix)){ return traverseMatrix(row+1,col,matrix,visitStatus,count); } } return count; }
3 回答
繁花不似錦
TA貢獻1851條經驗 獲得超4個贊
給定一個高度和寬度可能不相等的二維數組（矩陣）
但是您正在對高度和寬度始終相同的矩陣進行操作
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix.length; col++){ .. }}你應該像下面這樣使用尺寸，我想剩下的就足夠了..
for(int row = 0; row<matrix.length; row++){
for(int col = 0; col<matrix[row].length; col++){ .. }}并且更改也需要應用到函數“isValid”中
public static boolean isValid(int row, int col,int[][] matrix){
return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[row].length);
}
皈依舞
TA貢獻1851條經驗 獲得超3個贊
轉換count為局部變量并累加：
static int traverseMatrix(int row, int col, int[][] matrix, boolean[][] visitStatus) {
if (visitStatus[row][col] || matrix[row][col] == 0) {
return 0;
}
visitStatus[row][col] = true;
int count = 1;
if (isValid(row, col - 1, matrix)) {
count += traverseMatrix(row, col - 1, matrix, visitStatus);
}
...
return count;
}
慕蓋茨4494581
TA貢獻1850條經驗 獲得超11個贊
我的解決方案是用 C# 編寫的，但它與 Java 類似：
您可以將 List 替換為 ArrayList
代碼：
public static List<int> RiverSizes(int[,] matrix)
{
var sizes = new List<int>();
bool[,] visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];
for (int row = 0; row < matrix.GetLength(0); row++)
for (int col = 0; col < matrix.GetLength(1); col++)
if (visited[row, col])
continue;
else
Traverse(matrix, row, col, visited, sizes);
return sizes;
}
public static void Traverse(int[,] matrix, int row, int col, bool[,] visited, List<int> sizes)
{
int currentSize = 0;
var toExplore = new List<int[]>
{
new int[] { row, col }
};
while (toExplore.Count > 0)
{
var current = toExplore[^1];
toExplore.RemoveAt(toExplore.Count - 1);
row = current[0];
col = current[1];
if (visited[row, col])
continue;
visited[row, col] = true;
if (matrix[row, col] == 0)
continue;
currentSize++;
foreach (int[] item in GetNeighbours(matrix, row, col, visited))
toExplore.Add(item);
}
if (currentSize > 0)
sizes.Add(currentSize);
}
public static List<int[]> GetNeighbours(int[,] matrix, int row, int col, bool[,] visited)
{
List<int[]> neighbours = new List<int[]>();
if (row > 0 && !visited[row - 1, col])
neighbours.Add(new int[] { row - 1, col });
if (row < matrix.GetLength(0) - 1 && !visited[row + 1, col])
neighbours.Add(new int[] { row + 1, col });
if (col > 0 && !visited[row, col - 1])
neighbours.Add(new int[] { row, col - 1 });
if (col < matrix.GetLength(1) - 1 && !visited[row, col + 1])
neighbours.Add(new int[] { row, col + 1 });
return neighbours;
}
希望對您有幫助^-^
添加回答
舉報
0/150
提交
取消