Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place?
难度：medium
Solution: Level by Level Movement
从最外层开始，把每个元素直接swap到对应的位置。
public class Solution {
public void rotate(int[][] matrix) {
int up = 0, down = matrix.length - 1, left = 0, right = matrix.length - 1;
int n = matrix.length - 1;
while(up < down) {
for(int i = left; i < right; ++i) {
int temp = matrix[down][i];
matrix[down][i] = matrix[n - i][right];
matrix[n - i][right] = matrix[up][n - i];
matrix[up][n - i] = matrix[i][left];
matrix[i][left] = temp;
}
++up;
--down;
++left;
--right;
}
}
}
Solution: Flipping
clockwise rotate first reverse up to down, then swap the symmetry 1 2 3 => 7 8 9 => 7 4 1 4 5 6 => 4 5 6 => 8 5 2 7 8 9 => 1 2 3 => 9 6 3
public class Solution {
public void rotate(int[][] matrix) {
int up = 0, down = matrix.length - 1;
while(up < down) {
for(int j = 0; j < matrix.length; ++j) {
int temp = matrix[up][j];
matrix[up][j] = matrix[down][j];
matrix[down][j] = temp;
}
++up;
--down;
}
for (int i = 0; i < matrix.length; ++i) {
for (int j = i + 1; j < matrix[i].length; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
anticlockwise rotate first reverse left to right, then swap the symmetry 1 2 3 => 3 2 1 => 3 6 9 4 5 6 => 6 5 4 => 2 5 8 7 8 9 => 9 8 7 => 1 4 7
public class Solution {
public void rotate(int[][] matrix) {
int left = 0, right = matrix.length - 1;
while(left < right) {
for(int i = 0; i < matrix.length; ++i) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
}
++left;
--right;
}
for (int i = 0; i < matrix.length; ++i) {
for (int j = i + 1; j < matrix[i].length; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
难度：medium
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if(matrix.length == 0) {
return res;
}
int up = 0, down = matrix.length - 1, left = 0, right = matrix[0].length - 1;
while(up <= down && left <= right) {
// up
for(int j = left; j <= right; ++j) { // while condition has checked the boundary
res.add(matrix[up][j]);
}
++up;
// right
for(int i = up; i <= down; ++i) { // while condition has checked the boundary
res.add(matrix[i][right]);
}
--right;
// down
if(up > down) { // check the boundary
break;
}
for(int j = right; j >= left; --j) {
res.add(matrix[down][j]);
}
--down;
// left
if(left > right) { // check the boundary
break;
}
for(int i = down; i >= up; --i) {
res.add(matrix[i][left]);
}
++left;
}
return res;
}
}
Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
难度：medium
public class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int up = 0, down = n - 1, left = 0, right = n - 1;
int num = 1;
while(up <= down) {
// up
for(int i = left; i <= right; ++i) {
res[up][i] = num++;
}
++up;
// right
for(int j = up; j <= down; ++j) {
res[j][right] = num++;
}
--right;
if(down < up) {
break;
}
for(int i = right; i >= left; --i) {
res[down][i] = num++;
}
--down;
if(left > right) {
break;
}
for(int j = down; j >= up; --j) {
res[j][left] = num++;
}
++left;
}
return res;
}
}
Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
难度：medium
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstColumnZero = false;
boolean firstRowZero = false;
for(int i = 0; i < m; ++i) {
if(matrix[i][0] == 0) {
firstColumnZero = true;
break;
}
}
for(int j = 0; j < n; ++j) {
if(matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
if(matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i = 1; i < m; ++i) {
if(matrix[i][0] == 0) {
for(int j = 1; j < n; ++j) {
matrix[i][j] = 0;
}
}
}
for(int j = 1; j < n; ++j) {
if(matrix[0][j] == 0) {
for(int i = 1; i < m; ++i) {
matrix[i][j] = 0;
}
}
}
if(firstColumnZero) {
for(int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
if(firstRowZero) {
for(int j = 0; j < n; ++j) {
matrix[0][j] = 0;
}
}
}
}
Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
难度：medium
Solution: Binary Search
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int begin = 0, end = m * n - 1, mid, i, j;
while(begin <= end) {
mid = begin + ((end - begin) >> 1);
i = mid / n;
j = mid % n;
if(matrix[i][j] == target) {
return true;
} else if(matrix[i][j] > target) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
return false;
}
}
Kth Smallest Element in a Sorted Matrix
Medium
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Note: You may assume k is always valid, 1 ≤ k ≤ n2.
Solution: Heap
Note: this problem is very similar to the problem - merge k sorted linked list.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
PriorityQueue<int[]> heap = new PriorityQueue<>((n1, n2) -> n1[0] - n2[0]);
int bound = Math.min(k, matrix.length);
for(int i = 0; i < bound; ++i) {
heap.offer(new int[]{matrix[i][0], i, 0});
}
for(int i = 0; i < k - 1; ++i) {
int[] cur = heap.poll();
if(cur[2] + 1 < matrix.length) {
heap.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
}
}
return heap.poll()[0];
}
}
Solution: Binary Search
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int start = matrix[0][0], end = matrix[matrix.length - 1][matrix.length - 1];
while(start < end) {
int mid = start + ((end - start) >> 1);
int count = 0;
for(int i = 0; i < matrix.length; ++i) {
for(int j = 0; j < matrix.length; ++j) {
if(matrix[i][j] > mid) {
break;
}
++count;
}
}
if(count < k) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}
Valid Sudoku
Determine if a Sudoku is valid. A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
难度：medium
Solution: Hashtable
public class Solution {
public boolean isValidSudoku(char[][] board) {
Map<Character, Integer> digits = new HashMap<>();
int m = board.length;
int n = board[0].length;
// row
for(int i = 0; i < m; ++i) {
digits.clear();
for(int j = 0; j < n; ++j) {
if(board[i][j] == '.') {
continue;
}
if(digits.containsKey(board[i][j])) {
return false;
} else {
digits.put(board[i][j], 1);
}
}
}
// each cell
for(int cell = 0; cell < 9; ++cell) {
digits.clear();
for(int index = 0; index < 9; ++index) {
int i = index / 3;
int j = index % 3;
i += (cell / 3) * 3;
j += (cell % 3) * 3;
if(board[i][j] == '.') {
continue;
}
if(digits.containsKey(board[i][j])) {
return false;
} else {
digits.put(board[i][j], 1);
}
}
}
// column
for(int j = 0; j < n; ++j) {
digits.clear();
for(int i = 0; i < m; ++i) {
if(board[i][j] == '.') {
continue;
}
if(digits.containsKey(board[i][j])) {
return false;
} else {
digits.put(board[i][j], 1);
}
}
}
return true;
}
}
Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.
难度：hard
Solution: Backtracking
public class Solution {
private char[] digits = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
public void solveSudoku(char[][] board) {
solveSudokuHelper(board, 0);
}
private boolean solveSudokuHelper(char[][] board, int start) {
if(start == 81) {
return true;
}
int i = start / 9, j = start % 9;
if(board[i][j] != '.') {
return solveSudokuHelper(board, start + 1);
}
for(char digit : digits) {
if(isValid(board, i, j, digit)) {
board[i][j] = digit;
if(solveSudokuHelper(board, start + 1)) {
return true;
}
}
board[i][j] = '.';
}
return false;
}
private boolean isValid(char[][] board, int i, int j, char digit) {
for(int k = 0; k < 9; ++k) {
if(board[k][j] == digit || board[i][k] == digit || board[k / 3 + (i / 3) * 3][k % 3 + (j / 3) * 3] == digit) {
return false;
}
}
return true;
}
}
N-Queens
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.
难度：hard
Solution: Backtracking
public class Solution {
private void solveNQueensHelper(int n, int start, List<List<String>> res, List<String> tempRes, boolean[] column, boolean[] angle, boolean[] backAngle) {
if(start == n) {
res.add(new ArrayList<String>(tempRes));
return;
}
for(int i = 0; i < n; ++i) {
if(column[i] || backAngle[i + start] || angle[n - 1 + start - i]) {
continue;
}
column[i] = angle[n - 1 + start - i] = backAngle[i + start] = true;
StringBuilder place = new StringBuilder();
for(int j = 0; j < n; ++j) {
if(j == i) {
place.append('Q');
} else {
place.append('.');
}
}
tempRes.add(place.toString());
solveNQueensHelper(n, start + 1, res, tempRes, column, angle, backAngle);
tempRes.remove(tempRes.size() - 1);
column[i] = angle[n - 1 + start - i] = backAngle[i + start] = false;
}
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
boolean[] column = new boolean[n];
boolean[] angle = new boolean[2 * n - 1];
boolean[] backAngle = new boolean[2 * n - 1];
solveNQueensHelper(n, 0, res, new ArrayList<String>(), column, angle, backAngle);
return res;
}
}
N-Queens II
Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions.
难度：hard
Solution: Backtracking
public class Solution {
private int solutions = 0;
public int totalNQueens(int n) {
boolean[] column = new boolean[n];
boolean[] diagonal = new boolean[2*n - 1];
boolean[] antiDiagonal = new boolean[2*n - 1];
totalNQueensHelper(n, 0, column, diagonal, antiDiagonal);
return solutions;
}
private void totalNQueensHelper(int n, int start, boolean[] column, boolean[] diagonal, boolean[] antiDiagonal) {
if(start == n) {
solutions += 1;
return;
}
for(int j = 0; j < n; ++j) {
if(!column[j] && !diagonal[n - 1 + j - start] && !antiDiagonal[j + start]) {
column[j] = diagonal[n - 1 + j - start] = antiDiagonal[j + start] = true;
totalNQueensHelper(n, start + 1, column, diagonal, antiDiagonal);
column[j] = diagonal[n - 1 + j - start] = antiDiagonal[j + start] = false;
}
}
}
}
Surrounded Regions
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.
难度：medium 这个问题实际上是一个Connected Components问题。
Solution: DFS
public class Solution {
private void dfs(char[][] board, int i, int j) {
if(i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == 'O') {
board[i][j] = 'I';
if(i > 1) {
dfs(board, i - 1, j);
}
if(i < board.length - 2) {
dfs(board, i + 1, j);
}
if(j > 1) {
dfs(board, i, j - 1);
}
if(j < board[0].length - 2) {
dfs(board, i, j + 1);
}
}
}
public void solve(char[][] board) {
if(board.length == 0 || board[0].length == 0) {
return;
}
int m = board.length, n = board[0].length;
for(int i = 0; i < m; ++i) {
if(board[i][0] == 'O') {
board[i][0] = 'I';
dfs(board, i, 1);
}
if(board[i][n - 1] == 'O') {
board[i][n - 1] = 'I';
dfs(board,i, n - 2);
}
}
for(int j = 0; j < n; ++j) {
if(board[0][j] == 'O') {
board[0][j] = 'I';
dfs(board, 1, j);
}
if(board[m - 1][j] == 'O') {
board[m - 1][j] = 'I';
dfs(board, m - 2, j);
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == 'I') {
board[i][j] = 'O';
}
}
}
}
}
Solution: BFS
public class Solution {
public void solve(char[][] board) {
if(board.length == 0) {
return;
}
int m = board.length, n = board[0].length;
Queue<Integer> elements = new LinkedList<>();
for(int i = 0; i < m; ++i) {
if(board[i][0] == 'O') {
elements.add(i * n + 0);
}
if(board[i][n - 1] == 'O') {
elements.add(i * n + n - 1);
}
}
for(int j = 1; j < n - 1; ++j) {
if(board[0][j] == 'O') {
elements.add(0 * n + j);
}
if(board[m - 1][j] == 'O') {
elements.add((m - 1) * n + j);
}
}
while(!elements.isEmpty()) {
int index = elements.remove();
int i = index / n, j = index % n;
board[i][j] = 'I';
if(i - 1 >= 0 && board[i - 1][j] == 'O') {
elements.add((i - 1) * n + j);
}
if(i + 1 != m && board[i + 1][j] == 'O') {
elements.add((i + 1) * n + j);
}
if(j - 1 >= 0 && board[i][j - 1] == 'O') {
elements.add(i * n + j - 1);
}
if(j + 1 != n && board[i][j + 1] == 'O') {
elements.add(i * n + j + 1);
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == 'I') {
board[i][j] = 'O';
}
}
}
}
}
Perfect Rectangle
Hard
Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).
Solution: Hash Table
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
Set<String> set = new HashSet<>();
int down = Integer.MAX_VALUE, left = Integer.MAX_VALUE, top = Integer.MIN_VALUE, right = Integer.MIN_VALUE;
int area = 0;
for(int[] rec : rectangles) {
down = Math.min(rec[0], down);
left = Math.min(rec[1], left);
top = Math.max(rec[2], top);
right = Math.max(rec[3], right);
area += (rec[2] - rec[0]) * (rec[3] - rec[1]);
String s1 = rec[0] + " " + rec[1];
String s2 = rec[0] + " " + rec[3];
String s3 = rec[2] + " " + rec[3];
String s4 = rec[2] + " " + rec[1];
if (!set.add(s1)) set.remove(s1);
if (!set.add(s2)) set.remove(s2);
if (!set.add(s3)) set.remove(s3);
if (!set.add(s4)) set.remove(s4);
}
if (!set.contains(down + " " + left) ||
!set.contains(down + " " + right) ||
!set.contains(top + " " + left) ||
!set.contains(top + " " + right) ||
set.size() != 4) {
return false;
}
return area == (top - down) * (right - left);
}
}