2020-3-30

279.完全平方数

✒解题思路：

1. DP和332.硬币相似

   $$dp[i] = min(dp[i-j*j]+1,dp[i])$$

2. BFS

//DP
class Solution {
	public int numSquares(int n) {
		if (n == 0) {
			return 0;
		}
		int[] dp = new int[n + 1];
		for (int i = 1; i <= n; i++) {
            dp[i] = i;
			for (int j = 1; j * j <= i; j++) {
				dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
			}
		}
		return dp[n];
	}
}
//广度优先算法
class Solution {
    public int numSquares(int n) {
		if (n == 0) {
			return 0;
		}
		Queue<Integer> queue = new LinkedList<>();
		Set<Integer> set = new HashSet<>();
		queue.add(0);
		set.add(0);
		int result = 0;
		while (!queue.isEmpty()) {
			result++;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int num = queue.poll();
				for (int j = 1; j * j + num <= n; j++) {
					if (j * j + num == n) {
						return result;
					}
					if (!set.contains(j * j + num)) {
						queue.add(j * j + num);
						set.add(j * j + num);
					}
				}
			}
		}
		return result;
	}
}

面试题13.机器人的运动范围

✒解题思路：

1. 广度优先遍历+标记数组

class Solution {
	public int movingCount(int m, int n, int k) {
		int result = 0;
		boolean[][] marked = new boolean[m][n];
		Queue<int[]> queue = new LinkedList<>();
		marked[0][0] = true;
		queue.add(new int[]{0, 0});
		while (!queue.isEmpty()) {
			int size = queue.size();
			result += size;
			for (int i = 0; i < size; i++) {
				int[] point = queue.poll();
				int x = point[0];
				int y = point[1];
				if (x + 1 < m && getSum(x + 1) + getSum(y) <= k && !marked[x + 1][y]) {
					marked[x + 1][y] = true;
					queue.add(new int[]{x + 1, y});
				}
				if (y + 1 < n && getSum(x) + getSum(y + 1) <= k && !marked[x][y + 1]) {
					marked[x][y + 1] = true;
					queue.add(new int[]{x, y + 1});
				}
			}
		}
		return result;
	}

	private int getSum(int i) {
		int sum = 0;
		while (i > 0) {
			sum += (i % 10);
			i /= 10;
		}
		return sum;
	}
}

79.单词搜索

1. 深度优先搜索+回溯

class Solution {
	public boolean exist(char[][] board, String word) {
		int m = board.length;
		int n = board[0].length;
		boolean[][] marked = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (dfs(i, j, marked, word, board, 0)) {
					return true;
				}
			}
		}
		return false;
	}

	private boolean dfs(int i, int j, boolean[][] marked, String word, char[][] board, int start) {
		if (start == word.length() - 1) {
			return board[i][j] == word.charAt(start);
		}
		int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		if (board[i][j] == word.charAt(start)) {
			marked[i][j] = true;
			for (int k = 0; k < 4; k++) {
				int newX = i + directions[k][0];
				int newY = j + directions[k][1];
				if (newX >= 0 && newY >= 0 && newX < board.length && newY < board[0].length && marked[newX][newY] == false) {
					if (dfs(newX, newY, marked, word, board, start + 1)) {
						return true;
					}
				}
			}
			marked[i][j] = false;
		}
		return false;
	}
}

994.腐烂的橘子

✒解题思路：

1. 广度优先遍历+记录搜索层数

class Solution {
	public int orangesRotting(int[][] grid) {
		int m = grid.length;
		if (m < 1) {
			return 0;
		}
		int n = grid[0].length;
		if (n < 1) {
			return 0;
		}
		int count = 0;
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1) {
					count++;
				}
				if (grid[i][j] == 2) {
					queue.add(new int[]{i, j});
				}
			}
		}
		int result = 0;
		while (count > 0 && !queue.isEmpty()) {
			result++;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int[] point = queue.poll();
				int row = point[0];
				int col = point[1];
				if (row - 1 >= 0 && grid[row - 1][col] == 1) {
					grid[row - 1][col] = 2;
					count--;
					queue.add(new int[]{row - 1, col});
				}
				if (row + 1 < m && grid[row + 1][col] == 1) {
					grid[row + 1][col] = 2;
					count--;
					queue.add(new int[]{row + 1, col});
				}
				if (col - 1 >= 0 && grid[row][col - 1] == 1) {
					grid[row][col - 1] = 2;
					count--;
					queue.add(new int[]{row, col - 1});
				}
				if (col + 1 < n && grid[row][col + 1] == 1) {
					grid[row][col + 1] = 2;
					count--;
					queue.add(new int[]{row, col + 1});
				}
			}
		}
		return count == 0 ? result : -1;
	}
}

1162.地图分析

✒解题思路：

1. 广度优先搜索

class Solution {
	public int maxDistance(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		Queue<int[]> queue = new LinkedList<>();
		int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		int count = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 1) {
					queue.add(new int[]{i, j});
					count++;
				}
			}
		}
		int step = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			step++;
			for (int i = 0; i < size; i++) {
				int[] point = queue.poll();
				int x = point[0];
				int y = point[1];
				for (int j = 0; j < 4; j++) {
					int newX = x + directions[j][0];
					int newY = y + directions[j][1];
					if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 0) {
						queue.add(new int[]{newX, newY});
						grid[newX][newY] = 1;
					}
				}
			}
		}
		if (count == 0 || count == m * n) {
			return -1;
		}
		return step - 1;
	}
}

11.盛水最多的容器

✒解题思路：

1. 双指针，移动高度较小的指针

class Solution {
	public int maxArea(int[] height) {
		int len = height.length;
		if (len < 2) {
			return 0;
		}
		int maxArea = 0, left = 0, right = len - 1;
		while (left < right) {
			maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
			if (height[left] > height[right]) {
				right--;
			} else {
				left++;
			}
		}
		return maxArea;
	}
}

面试题62.圆圈中最后剩下的数字

✒解题思路：

1. 使用ArrayList模拟链表

class Solution {
	public int lastRemaining(int n, int m) {
		ArrayList<Integer> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(i);
		}
		int index = 0;
		while (n > 1) {
			index = (index + m - 1) % n;
			list.remove(index);
			n--;
		}
		return list.get(0);
	}
}

面试题32-II.从上到下打印二叉树II

✒解题思路：

1. 简单层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			result.add(list);
		}
		return result;
	}
}

993.二叉树的堂兄弟节点

✒解题思路：

1. 层次遍历，使用Map存储每个节点的深度和父节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean isCousins(TreeNode root, int x, int y) {
		Map<Integer, Integer> depth = new HashMap<>();
		Map<Integer, Integer> parent = new HashMap<>();

		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		parent.put(root.val, -1);
		int step = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				depth.put(node.val, step);
				if (node.left != null) {
					queue.add(node.left);
					parent.put(node.left.val, node.val);
				}
				if (node.right != null) {
					queue.add(node.right);
					parent.put(node.right.val, node.val);
				}
			}
            step++;
		}
		return depth.get(x).equals(depth.get(y)) && !parent.get(x).equals(parent.get(y));
	}
}

面试题16.19.水域大小

✒解题思路：

1. 广度优先算法

class Solution {
	public int[] pondSizes(int[][] land) {
		int m = land.length;
		int n = land[0].length;
		ArrayList<Integer> result = new ArrayList<>();
		int[][] directions = new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int total = 0;
				if (land[i][j] == 0) {
					total++;
					land[i][j] = 1;
					Queue<int[]> queue = new LinkedList<>();
					queue.add(new int[]{i, j});
					while (!queue.isEmpty()) {
						int[] point = queue.poll();
						int x = point[0];
						int y = point[1];
						for (int l = 0; l < 8; l++) {
							int newX = x + directions[l][0];
							int newY = y + directions[l][1];
							if (newX >= 0 && newY >= 0 && newX < m && newY < n && land[newX][newY] == 0) {
								queue.add(new int[]{newX, newY});
								land[newX][newY] = 1;
								total++;
							}
						}
					}
					result.add(total);
				}
			}
		}
		Collections.sort(result);
		int[] ans = new int[result.size()];
		for (int i = 0; i < result.size(); i++) {
			ans[i] = result.get(i);
		}
		return ans;
	}
}