Tag: 矩阵

解法一：

class Solution {
    public boolean isValidSudoku(char[][] board) {
        ArrayList<HashSet<Character>> list = new ArrayList<>();
        ArrayList<HashSet<Character>> list2 = new ArrayList<>();
        ArrayList<HashSet<Character>> list3 = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            list.add(new HashSet<Character>());
            list2.add(new HashSet<Character>());
            list3.add(new HashSet<Character>());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if(list.get(i / 3 * 3 + j / 3).contains(board[i][j])) return false;
                if(list2.get(j).contains(board[i][j])) return false;
                if(list3.get(i).contains(board[i][j])) return false;
                list.get(i / 3 * 3 + j / 3).add(board[i][j]);
                list2.get(j).add(board[i][j]);
                list3.get(i).add(board[i][j]);
            }
        }
        return true;
    }
}

T4mako4/17/26About 1 min

048_旋转图像

解法一：

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for(int i = 0;i < len / 2;i++){
            int a3 = matrix[len - i - 1][i];
            int a4 = matrix[len - i - 1][len - i - 1];
            int count = 0;
            int[] temp = new int[len];
            int[] temp2 = new int[len];
            int[] temp3 = new int[len];
            for (int j = i; j < len - i; j++) {
                temp3[j - i] = matrix[i][j];
            }
            for(;count < 4;count++){
                if(count == 0){
                    for(int j = i;j < len - i;j++){
                        temp[j - i] = matrix[j][len - i -1];
                        matrix[j][len - i -1] = temp3[j - i];
                    }
                    count++;
                }
                if(count == 1){
                    for(int j = i;j < len - i;j++){
                        temp2[j - i] = matrix[len - i -1][j];
                        matrix[len - i -1][j] = temp[len - i - 1 - j];
                    }
                    temp2[len - i - 1 - i] = a4;
                    count++;
                }
                if(count == 2){
                    for (int j = i; j < len - i; j++) {
                        temp[j - i] = matrix[j][i];
                        matrix[j][i] = temp2[j - i];
                    }
                    temp[len - i - 1 - i] = a3;
                    count++;
                }
                if(count == 3){
                    for (int j = i; j < len - i; j++) {
                        matrix[i][j] = temp[len - i - 1 - j];
                    }
                    count++;
                }
            }
        }
    }
}

T4mako4/17/26About 1 min

063. 不同路径 II

题目描述

将障碍物填充 0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[m - 1];
    }
}

T4mako4/17/26Less than 1 minute

064. 最小路径和

题目描述

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i - 1 >= 0 && j - 1 >= 0) grid[i][j] += Math.min(grid[i - 1][j],grid[i][j - 1]);
                else if (i - 1 >= 0) grid[i][j] += grid[i - 1][j];
                else if (j - 1 >= 0) grid[i][j] += grid[i][j - 1];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

T4mako4/17/26Less than 1 minute

79. 单词搜索

题目描述

解法：回溯

class Solution {
    public boolean exist(char[][] board, String word) {
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board[0].length; col++) {
            if (dfs(row, col, 0, board, word, new boolean[board.length][board[0].length], new StringBuilder())) {
                return true;
            }
        }
    }
    return false;
}

public boolean dfs(int row, int col, int i, char[][] board, String word, boolean[][] flag, StringBuilder check) {
    if (i >= word.length()) {
        return false;
    }
    
    if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || flag[row][col] || word.charAt(i) != board[row][col]) {
        return false;
    }

    check.append(board[row][col]);
    if (i + 1 == word.length() && word.equals(check.toString())) {
        return true;
    }
    
    flag[row][col] = true;
    if (dfs(row - 1, col, i + 1, board, word, flag, check) ||
        dfs(row + 1, col, i + 1, board, word, flag, check) ||
        dfs(row, col - 1, i + 1, board, word, flag, check) ||
        dfs(row, col + 1, i + 1, board, word, flag, check)) {
        return true;
    }
    
    flag[row][col] = false;
    check.deleteCharAt(check.length() - 1);
    return false;
}


}

T4mako3/25/24Less than 1 minute

130. 被围绕的区域

题目描述

解法：深度优先搜索 + 递归
第一次遍历，从边缘的 O 开始搜索，记录所有可达的 O，并将访问过的设置为 #
再次遍历，将 O 置 X，# 置为 O

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘o开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            // board[i][j] == '#' 说明已经搜索过了. 
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
}

T4mako3/21/24Less than 1 minute

200. 岛屿数量

题目描述

解法：使用深度优先的思想，不断找相邻为 1 的坐标

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int row = 0;row < grid.length;row++) {
        	for(int col = 0;col < grid[0].length;col++) {
        		if(grid[row][col] == '1') {
        			res++;
        			find(grid,row,col);
        		}else {
        			continue;
        		}
        	}
        }
        return res;
    }

	public void find(char[][] grid, int row, int col) {
		if(row >= 0 && col >= 0 && row < grid.length && col < grid[0].length && grid[row][col] == '1') {
			grid[row][col] = '2';
			// 上下左右
			find(grid,row - 1,col);
			find(grid,row + 1,col);
			find(grid,row,col - 1);
			find(grid,row,col + 1);
		}
		return;
	}
}

T4mako3/19/24Less than 1 minute

289. 生命游戏

题目描述

解法思路：对每一个位置计算其周围的 0 和 1 的值

class Solution {
    public void gameOfLife(int[][] board) {
		int rows = board.length;
		int cols = board[0].length;
		int[][] copy = new int[rows][cols];
		for (int i = 0; i < board.length; i++) {
            System.arraycopy(board[i], 0, copy[i], 0, board[i].length);
        }
		
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				modify(row, col, copy, board);
			}
		}
	}

	public void modify(int row, int col, int[][] board, int[][] res) {
		int val = board[row][col];
		int count1 = 0, count0 = 0;
		// 左上
		int temp = row - 1 < 0 || col - 1 < 0 || board[row - 1][col - 1] == 0 ? count0++ : count1++;
		// 上
		temp = row - 1 < 0 || board[row - 1][col] == 0 ? count0++ : count1++;
		// 右上
		temp = row - 1 < 0 || col + 1 >= board[0].length || board[row - 1][col + 1] == 0 ? count0++ : count1++;
		// 左
		temp = col - 1 < 0 || board[row][col - 1] == 0 ? count0++ : count1++;
		// 右
		temp = col + 1 >= board[0].length || board[row][col + 1] == 0 ? count0++ : count1++;
		// 左下
		temp = col - 1 < 0 || row + 1 >= board.length || board[row + 1][col - 1] == 0 ? count0++ : count1++;
		// 下
        temp = row + 1 >= board.length || board[row + 1][col] == 0 ? count0++ : count1++;
        // 右下
		temp = col + 1 >= board[0].length || row + 1 >= board.length || board[row + 1][col + 1] == 0 ? count0++ : count1++;
		if (val == 0) {
			res[row][col] = count1 == 3 ? 1 : 0;
		} else {
			res[row][col] = count1 < 2 || count1 > 3 ? 0 : 1;
		}

	}
}

T4mako3/18/24Less than 1 minute

054. 螺旋矩阵

题目描述

解题思路： index 代表动作，flag 数组代表该位置是否已访问过

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
		int maxRow = matrix.length;
		int maxCol = matrix[0].length;
		boolean[][] flag = new boolean[maxRow][maxCol];
		int index = 0;
		List<Integer> res = new ArrayList<>();
		int row = 0, col = 0;
		while (true) {
			if(row < 0 || col < 0 || row >= maxRow || col >= maxCol || flag[row][col]) return res;
			flag[row][col] = true;
			res.add(matrix[row][col]);
			if (index == 0) {
				// 右
				if (col + 1 < maxCol && !flag[row][col + 1]) {
					col++;
				} else {
					index = 1;
					row++;
				}
				continue;
			}
			// 下
			if (index == 1) {
				if (row + 1 < maxRow && !flag[row + 1][col]) {
					row++;
				} else {
					index = 2;
					col--;
				}
				continue;
			}
			// 左
			if (index == 2) {
				if (col - 1 >= 0 && !flag[row][col - 1]) {
					col--;
				} else {
					index = 3;
					row--;
				}
				continue;
			}
			// 上
			if (index == 3) {
				if (row - 1 >= 0 && !flag[row - 1][col]) {
					row--;
					
				} else {
					index = 0;
                    col++;
				}
				continue;
			}
		}
	}
}

T4mako3/17/24Less than 1 minute

73. 矩阵置零

题目描述

解法思路：首先通过遍历记录哪些行和列需要置 0，再遍历一次将 0 填充

class Solution {
    public void setZeroes(int[][] matrix) {
		HashSet<Integer> rows = new HashSet<>();
		HashSet<Integer> cols = new HashSet<>();
		for (int r = 0; r < matrix.length; r++) {
			for (int c = 0; c < matrix[0].length; c++) {
				if (matrix[r][c] == 0) {
					rows.add(r);
					cols.add(c);
				}
			}
		}
		for (int r = 0; r < matrix.length; r++) {
			for (int c = 0; c < matrix[0].length; c++) {
				if (rows.contains(r)) {
					matrix[r][c] = 0;
				}
				if (cols.contains(c)) {
					matrix[r][c] = 0;
				}
			}
		}

	}
}

T4mako3/16/24Less than 1 minute