Matrix

ProblemGiven a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.Example:Input: 3Output:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]Solutionclass Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; if (n == 0) return res; int num = 1, rStart = 0, rEnd = n-1, cStart = 0, cEnd = n-1; while (rStart <= rEnd && cStart <= cEnd) { for (int j = cStart; j <= cEnd; j++) res[rStart][j] = num++; rStart++; for (int i = rStart; i <= rEnd; i++) res[i][cEnd] = num++; cEnd–; for (int j = cEnd; j >= cStart; j–) { if (rStart > rEnd) break; res[rEnd][j] = num++; } rEnd–; for (int i = rEnd; i >= rStart; i–) { if (cStart > cEnd) break; res[i][cStart] = num++; } cStart++; } return res; }} ...

ProblemGiven a matrix A, return the transpose of A.The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.Example 1:Input: [[1,2,3],[4,5,6],[7,8,9]]Output: [[1,4,7],[2,5,8],[3,6,9]]Example 2:Input: [[1,2,3],[4,5,6]]Output: [[1,4],[2,5],[3,6]]Note:1 <= A.length <= 10001 <= A[0].length <= 1000Solutionclass Solution { public int[][] transpose(int[][] A) { int m = A.length, n = A[0].length; int[][] B = new int[n][m]; for (int j = 0; j < n; j++) { for (int i = 0; i < m; i++) { B[j][i] = A[i][j]; } } return B; }} ...

ProblemThe n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.Example:Input: 4Output: [ [".Q..", // Solution 1 “…Q”, “Q…”, “..Q.”], ["..Q.", // Solution 2 “Q…”, “…Q”, “.Q..”]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.Solutionclass Solution { public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], ‘.’); } List<List<String>> res = new ArrayList<>(); dfs(board, 0, res); return res; } private void dfs(char[][] board, int col, List<List<String>> res) { if (col == board.length) { res.add(construct(board)); return; } for (int row = 0; row < board.length; row++) { if (validate(board, row, col)) { board[row][col] = ‘Q’; dfs(board, col+1, res); board[row][col] = ‘.’; } } } private boolean validate(char[][] board, int row, int col) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == ‘Q’ && ( i+j == row+col || row+j == col+i || row == i )) return false; } } return true; } private List<String> construct(char[][] board) { List<String> res = new ArrayList<>(); for (int i = 0; i < board.length; i++) { String str = new String(board[i]); res.add(str); } return res; }} ...