leetcode热题 HOT 100
题目分类
207. 课程表
【方法1】拓扑排序、深度搜索【方法2】拓扑排序、广度搜索 221. 最大正方形
【方法1】动态规划 226. 翻转二叉树
【方法1】使用队列按层遍历二叉树【方法2】递归遍历二叉树 236. 二叉树最近的公共祖先
【方法1】递归【方法二】存储前序遍历节点的路径 238. 除自身以外数组的乘积
【方法1】利用前缀乘积和后缀乘积数组【方法2】优化，去掉数组prefix和suffix 239. 滑动窗口最大值
【方法1】优先队列实现最大堆 240. 搜索二维矩阵II
【方法1】暴力解法，遍历搜索O(mn)不推荐【方法2】按行二分查找O(mlogn)【方法3】Z字型查找 279. 完全平方数
【方法1】动态规划 283.移动零
【方法1】双指针 300. 最长递增子序列
【方法1】动态规划
高频知识点
)
| 分类 | 题号 |
|---|---|
| 深度搜索 | 207 |
| 广度搜索 | 207 |
| 拓扑排序 | 210 |
| 二叉树 | 226、236 |
| 动态规划 | 221、279、300 |
| 前缀和 | 238 |
| 滑动窗口 | 239 |
| 最大最小堆 | 239 |
| 搜索 | 240 |
| 二分查找 | 240 |
| 双指针 | 283 |
class Solution {
private List> edges;
// 0-未搜索，1-搜索中，2-已完成
private int[] visited;
// 图中是否存在环，即此题是否有解
private boolean valid = true;
private List> buildGraph(int nodes, int[][] relationship) {
List> edges = new ArrayList<>();
for (int i = 0; i < nodes; i++) {
edges.add(new ArrayList<>());
}
for (int[] a : relationship) {
edges.get(a[1]).add(a[0]);
}
return edges;
}
private void dfs(int u) {
// 搜索u时现将u标记为搜索中
visited[u] = 1;
// 遍历所有与u相连的节点
for (int v : edges.get(u)) {
if (visited[v] == 0) {
// v节点未搜索时，则深度搜索v
dfs(v);
// 如果无效则直接返回
if (!valid) {
return;
}
} else if (visited[v] == 1) {
// v节点搜索中时，图中存在环，无效
valid = false;
return;
}
}
// 对节点u完成搜索，标记为已完成
visited[u] = 2;
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = buildGraph(numCourses, prerequisites);
visited = new int[numCourses];
// 遍历节点，如果无效直接退出
for (int i = 0; i < numCourses & valid; i++) {
if (visited[i] == 0) {
// 节点未搜索，则深度搜索此节点
dfs(i);
}
}
return valid;
}
}
【方法2】拓扑排序、广度搜索
class Solution {
private List> edges;
private int[] inDeg;
private List> buildGraph(int nodes, int[][] relationship) {
List> edges = new ArrayList<>();
for (int i = 0; i < nodes; i++) {
edges.add(new ArrayList<>());
}
for (int[] a : relationship) {
edges.get(a[1]).add(a[0]);
++inDeg[a[0]];
}
return edges;
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
inDeg = new int[numCourses];
edges = buildGraph(numCourses, prerequisites);
Queue queue = new linkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDeg[i] == 0) {
queue.offer(i);
}
}
List stack = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
stack.add(u);
for (int v : edges.get(u)) {
--inDeg[v];
if (inDeg[v] == 0) {
queue.offer(v);
}
}
}
return stack.size() == numCourses;
}
}
221. 最大正方形
【方法1】动态规划
状态转移方程:
定义dp[i][j]为以(i, j) 为有下角的正方形的最大边长，有：
d
p
[
i
]
[
j
]
=
{
m
a
t
r
i
x
[
i
]
[
j
]
i
=
0
或
j
=
0
0
m
a
t
r
i
x
[
i
]
[
j
]
=
0
min
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
,
d
p
[
i
−
1
]
[
j
−
1
]
)
+
1
其
他
dp[i][j] = begin{cases} matrix[i][j] & i = 0 或 j = 0 \ 0 & matrix[i][j] = 0 \ min(dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]) +1 & 其他 end{cases}
dp[i][j]=⎩⎪⎨⎪⎧matrix[i][j]0min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1i=0或j=0matrix[i][j]=0其他
class Solution {
public int maximalSquare(char[][] matrix) {
int[][] side = new int[matrix.length][matrix[0].length];
int maxSide = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (i == 0 || j == 0) {
side[i][j] = matrix[i][j] - '0';
} else {
if (matrix[i][j] == '0') {
side[i][j] = 0;
} else {
side[i][j] = Math.min(Math.min(side[i - 1][j], side[i][j - 1]), side[i - 1][j - 1]) + 1;
}
}
maxSide = Math.max(maxSide, side[i][j]);
}
}
return maxSide * maxSide;
}
}
226. 翻转二叉树
【方法1】使用队列按层遍历二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue queue = new linkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.peek();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
queue.poll();
}
return root;
}
}
【方法2】递归遍历二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
236. 二叉树最近的公共祖先
【方法1】递归
递归条件：定义
f
x
f_x
fx表示
x
x
x节点的子树中是否包含 p 节点或 q节点，则公共祖先一定满足
(
f
l
s
o
n
&
&
f
r
s
o
n
)
∣
∣
(
(
x
=
=
p
∣
∣
x
=
=
q
)
&
&
(
f
l
s
o
n
∣
∣
f
r
s
o
n
)
)
(f_{lson} && f_{rson})||((x==p||x==q)&&(f_{lson}||f_{rson}))
(flson&&frson)∣∣((x==p∣∣x==q)&&(flson∣∣frson))
公共祖先左子树和右子树同时包含p节点或者q节点，则一个子树包含一个节点，另外一个节点必在另一子树；节点本身是p或q的一个节点，且其子树包含另一个节点只要从叶子节点开始搜索，则可以保证深度最大的公共祖先
class Solution {
private TreeNode ans;
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}
【方法二】存储前序遍历节点的路径
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
linkedList pPath = new linkedList<>();
linkedList qPath = new linkedList<>();
findPath(root, p, pPath);
findPath(root, p, qPath);
int len = Math.min(pPath.size(), qPath.size());
int i = 0;
for (; i < len; i++) {
if (pPath.get(i) != qPath.get(i)) {
break;
}
}
return pPath.get(i - 1);
}
private boolean findPath(TreeNode root, TreeNode p, linkedList path) {
if (root == null) {
return false;
}
path.add(root);
if (root == p) {
return true;
}
if (findPath(root.left, p , path) || findPath(root.right, p, path)) {
return true;
}
path.removeLast();
return false;
}
}
238. 除自身以外数组的乘积
【方法1】利用前缀乘积和后缀乘积数组
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
prefix[0] = 1;
suffix[nums.length - 1] = 1;
} else {
prefix[i] = prefix[i - 1] * nums[i - 1];
suffix[nums.length - 1 - i] = suffix[nums.length - i] * nums[nums.length - i];
}
}
int[] answer = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
【方法2】优化，去掉数组prefix和suffix
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// R 为右侧所有元素的乘积
// 刚开始右边没有元素，所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--) {
// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];
}
return answer;
}
}
239. 滑动窗口最大值
【方法1】优先队列实现最大堆
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (k == 1) {
return nums;
}
List result = new linkedList<>();
Queue queue = new PriorityQueue<>((o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0]);
for (int i = 0; i < k; i++) {
queue.add(new int[]{nums[i], i});
}
result.add(queue.peek()[0]);
for (int i = k; i < nums.length; i++) {
while (queue.peek()[1] <= i - k) {
queue.poll();
}
queue.offer(new int[] {nums[i], i});
result.add(queue.peek()[0]);
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
240. 搜索二维矩阵II
【方法1】暴力解法，遍历搜索O(mn)不推荐
【方法2】按行二分查找O(mlogn)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
int start = 0;
int end = matrix[0].length;
while (start < end) {
int middle = (end - start) / 2 + start;
if (matrix[i][middle] > target) {
end = middle;
} else if (matrix[i][middle] == target) {
return true;
} else {
start = middle + 1;
}
}
}
return false;
}
}
【方法3】Z字型查找
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
}
}
279. 完全平方数
【方法1】动态规划
定义dp(n)为完全平方数的和为n的个数，则
n
=
i
2
+
n
−
i
2
,
其
中
i
=
[
1
,
n
]
,
且
为
整
数
n = i^2 + n - i^2, 其中i = [1,sqrt{n}], 且为整数
n=i2+n−i2,其中i=[1,n
],且为整数
则
KaTeX parse error: Got function 'sqrt' with no arguments as superscript at position 14: dp(n) = min^̲s̲q̲r̲t̲{n}_idp(n-i*i) …
class Solution {
public int numSquares(int n) {
int[] f = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
min = Math.min(min, f[i - j * j]);
}
f[i] = min + 1;
}
return f[n];
}
}
283.移动零
【方法1】双指针
class Solution {
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int end = nums.length;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == 0) {
end--;
int j = i;
while (j < end) {
nums[j] = nums[j + 1];
j++;
}
nums[end] = 0;
}
}
}
}
300. 最长递增子序列
【方法1】动态规划
定义dp(i)为下标为i结尾的子数组的最长递增数组长度，则
d
p
(
i
)
=
m
a
x
(
d
p
(
j
)
)
+
1
,
其
中
0
=
<
j
<
i
且
n
u
m
s
[
j
]
<
n
u
m
s
[
i
]
dp(i) = max(dp(j)) + 1, 其中 0=class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for (int i = 0; i < nums.length; i++) {
// 只包括当前数本身，即前面都是递减数列时
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
高频知识点
分类 题号 二叉树 226、236 动态规划 221、1277
