LeetCode_Hot100_Java_Solution

本文将Leetcode hot 100题目按照类型分类。部分题目可能属于多个类型。

刷leetcode hot 100以前需要了解一些基础知识：

  • 常见排序：冒泡排序，插入排序，选择排序，归并排序，快速排序，堆排序。 时间复杂度为O(nlogn)：归并排序和堆排序。快速排序时间复杂度最好的情况下是O(nlogn)，最坏的情况下是O(n^2)。
  • 字符串的常用方法：length()，substring()，spilt()。 StringBuffer()的常用方法：deleteCharAt()，reverse()，toString()，append()，insert。
  • 常用数据结构及其常用方法：List，HashMap，HashSet，PriorityQueue，stack，queue。
  • Arrays.sort()自定义排序，PriorityQueue()自定义排序。
数据结构 常用方法
List add()，remove(), get()
HashMap put()，size()，remove()，containsKey()
HashSet add()，remove()，size()，contains()
PriorityQueue poll()，offer()，isEmpty()，size()，peek()
stack push()，size()，pop()，isEmpty()，peek()
queue poll()，offer()，isEmpty()，size()，peek()

dp

  • dp数组和下标的含义，递推公式，初始化，遍历顺序。

  • 01背包和完全背包。

题号 题目 题目说明 文字版题解 题解
198 打家劫舍 给定一个数组：
求不相邻的价值总和最大值		 1. dp$dp[i] = max(dp[i-1],dp[i-2]+num[i])$
2. dfs：DFS 枚举每个房子的选择：偷或不偷，记忆化避免重复子问题。本质上和动态规划思路相同，只是递归实现而非迭代		 Java
238 除自身数组以外的乘积 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。 用三个数组分别存储前缀、后缀乘积和 Java
221 最大正方形 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 dp[i][j] 表示：以 (i,j) 这个位置作为右下角时，能形成的最大正方形的边长。
形成递推公式：
dp[i][j] = Math.min(dp[i-1][j], dp[i][j - 1], dp[i - 1][j - 1])+1
因为一个正方形能不能变大，取决于它左、上、左上的最小正方形。		 Java
152 乘积最大子数组 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组,
例如输入: nums = [2,3,-2,4] 输出:6		 1. 用两个变量，记录以某个索引为末尾的子数组的最大乘积和最小乘积.全局最大值即max(max*curnum,min*curnum,curnum)
2. 也可以采用数组存储的形式		 Java
139 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 遍历i->n,dp[i] 表示前 i 个字符是否可被字典拼接；枚举字典单词 word，若 dp[i-len(word)] 为真且当前子串等于 word，则 dp[i]=true。 Java
647 回文子串 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 使用二维动态规划解决回文子串问题。定义 dp[i][j] 表示字符串 s[i..j] 是否为回文串。随着len的依次递增，来表示出状态转移：dp[i][j] = dp[i+1][j-1] Java
322 零钱兑换 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。		 完全背包：

1.dp[i] 表示最少硬币数
2.初始化为“无穷大”

3.状态转移：
$dp[j] = min(dp[j], dp[j - coin] + 1)$		 Java
494 目标和 给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。		 1. 回溯，但是回溯的时间复杂度过大$O(n^2)$;
2**. 背包问**题：
设：正数集合和 = P负数集合和 = N

即$P - N = target$,$P + N = sum$

两式相加：

$2P = target + sum$
$=> P = (target + sum) / 2$

问题变成：

> 从 nums 中选一些数，使它们的和 = (target + sum) / 2，有多少种选法？

解法：0/1背包+计数

java<br>for (int i = 0; i < nums.length; i++) {<br> for (int j = (target + sum) / 2; j >= nums[i]; j--) {<br> pos[j] += pos[j - nums[i]];<br> }<br>}<br>		 Java
416 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 和上一道一样：0/1背包+计数 Java
337 打家劫舍 III 给定二叉树的 root 。返回 在不触动警报的情况下 （需要父节点和子节点都拿），小偷能够盗取的最高金额 。 1. 对于每一个节点，都有选或者不选两种决定，选了该节点，则它的左子节点和右子节点不能选
2. 设定一个数组，下标0代表选了该节点的最大偷盗金额，下标1代表未选择该节点的最小偷盗金额
3. 使用dfs + dp		 Java
312 戳气球 Java
309 买卖股票的最佳时期含冷冻期 Java
300 最长递增子序列 Java
279 完全平方数 Java
42 接雨水 Java
32 最长有效括号 Java
10 正则表达式匹配 Java
5 最长回文子串 Java
96 不同的二叉搜索树 Java
85 最大矩形 Java
72 编辑距离 Java
70 爬楼梯 Java
62 不同路径 Java
53 最大子数组和 Java

链表

  • 链表的题目往往使用虚拟头结点的方法，以避免对头结点为空的情况进行特判。
  • 做链表的题目是，我们需要记住的是链表的增删节点都是使用的双指针。
题号 题目 题目说明 文字版题解 题解
160 相交链表 返回两个单链表相交的起始节点。 1. 哈希表（很容易想到，但是空间复杂度太大了）
2. 双指针：当两个链表长度不同的时候，直接遍历可能不同步，通过跳转到另一条链表头，可以让两个指针在第二轮遍历时“对齐”		 Java
234 回文链表 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 将值复制到数组中后用双指针法 Java
206 反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 1. 使用虚拟头结点的方法 ListNode dummy 让虚拟头结点指向head，避免对head特判
2. 链表的题删除链表、翻转节点、添加节点都要用双指针		 Java
148 排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 使用归并排序 Java
146 LRU 缓存 Java
142 环形链表 II Java
141 环形链表 Java
23 合并 K 个升序链表 Java
21 合并两个有序链表 Java
114 二叉树展开为链表 Java
19 删除链表的倒数第 N 个结点 Java
2 两数相加 Java

单调栈

  • 单调栈按照从栈底到栈顶的大小变化可以分为单调递增栈和单调递减栈。
  • 单调栈中存储的是元素的索引。
题号 题目 题目说明 文字版题解 题解
739 每日温度 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。 维护一个单调递减的栈（存下下标），遇到更大的数，则进行出栈 Java
84 柱状图中最大的矩形 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。		 从i=0开始，寻找heights[i] 作为矩形的 最低高度，那么它能扩展的宽度是（维护一个单调栈）：
1. 向左找到第一个比它小的柱子
2. 向右找到第一个比它小的柱子		 Java

构建数据结构

  • 构建特殊数据结构。
题号 题目 题目说明 文字版题解 题解
207 课程表 给定课程数和前置条件如numCourses = 2, prerequisites = [[1,0]]，判断是都可以完成所有课程的学习 拓扑排序：判断是否存在循环依赖。当前课程——>前置课程画图。使用dfs进行求解。 Java
399 除法求值 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]		 本题可以抽象为 带权有向图问题。注意：
1. 有的节点是没有的，直接返回-1
2. dfs的时候末尾没有边的不能再继续探索		 Java
208 实现 Trie (前缀树) Java

二进制

  • ^异或：任何数^自身 = 0，^0不变。
  • &1：判断末尾数是否为1。
  • «：向左位移1位，»：向右位移1位。
题号 题目 题目说明 文字版题解 题解
461 汉明距离 两个数字对应二进制位不同的位置的数目。 异或^解决，再利用按位与&判断尾数是否为1, »=进行自身的右移即可 Java
338 比特位计数 Java

贪心

  • 通过局部最优，得到全局最优，需要会自定义排序，建议使用lamda表达式。
题号 题目 题目说明 文字版题解 题解
406 根据身高重建队列 打乱顺序的一群人重新排成队列，如输入输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]输出[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]分别表示身高和前面大于等于他的人数 1. 先安排高个子的位置
2. 通过插队的方式安排矮个子的位置		 Java
253 会议室II Java
621 任务调度器 Java

优先队列

  • PriorityQueue是底层是堆排序。
题目 题号 题目说明 文字版题解 题解
239 滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧，求出滑动窗口中的最大值的数组，长度应该为**nums.length-k+1**。 1. 优先队列存储当前元素值和索引，用大顶堆进行排序
2. 使用单调队列维护一个递减的队列		 Java
23 合并 K 个升序链表 Java

回溯

  • 回溯三要素：1.传递的参数和返回类型；2.终止条件；3.回溯的逻辑。
题号 题目 题目说明 文字版题解 题解
22 括号生成 数字 n 代表生成括号的对数，返回所有可能的并且 有效的 括号组合。**输入：**n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]		 回溯，全排列，有效的括号组合，对于任意括号左边的左括号的数量大于等于右括号的数量 Java
46 全排列 Java
17 电话号码的字母组合 Java
78 子集 Java
39 组合总和 Java

数组

  • 需要会二分法的使用和双指针、滑动窗口。
题号 题目 题目说明 文字版题解 题解
48 旋转图像 给定一个矩阵，求出其顺时针旋转后的矩阵 原地旋转（两次折叠）：先[i,j] -> [j,i]，再进行[i,j] -> [i,n-j+1]的交换 Java
33 搜索旋转排序数组 Java
34 在排序数组中查找元素的第一个和最后一个位置 Java
31 下一个排列 Java
15 三数之和 Java
11 盛最多水的容器 Java
4 寻找两个正序数组的中位数 Java
1 两数之和 Java
75 颜色分类 Java
56 合并区间 Java
55 跳跃游戏 Java
215 数组中的第K个最大元素 Java
287 寻找重复数 Java
283 移动零 Java
240 搜索二维矩阵 II Java

二叉树

  • 需要会前中后序遍历的递归、迭代实现和层序遍历。
题号 题目 题目说明 文字版题解 题解
236 二叉树的最近公共祖先 给定一颗树root，和两个节点，求两个节点最近的公共祖先 递归 -> 递归当前节点的左右子树中是否包含p || q，
1. 如果都不为null，则说明左右两个子树各包含一个p || q，即当前root是最近公共祖先
2. 若有一个为null,另一个不为null,即root节点返回该不为null的节点
3. 若都为null,如果root不包含任意一个，即返回null		 Java
226 翻转二叉树 Java
124 二叉树中的最大路径和 Java
297 二叉树的序列化与反序列化 Java
543 二叉树的直径 Java
538 把二叉搜索树转换为累加树 Java
114 二叉树展开为链表 Java
617 合并二叉树 Java
105 从前序与中序遍历序列构造二叉树 Java
104 二叉树的最大深度 Java
102 二叉树的层序遍历 Java
101 对称二叉树 Java
98 验证二叉搜索树 Java
96 不同的二叉搜索树 Java
437 路径总和 III Java
94 二叉树的中序遍历 Java

Stack、Queue、HashMap()、HashSet()

  • Stack、Queue、HashMap和HashSet的常见方法需要会使用。
题号 题目 题目说明 文字版题解 题解
169 多数元素 给出一个数组，返回元素个数大于1/2的元素，没有返回-1 维护一个hashMap<Integer,Integer>,一个是元素，另一个是关于元素的个数，一直判断即可 Java
128 最长连续序列 Java
438 找到字符串中所有字母异位词 Java
394 字符串解码 Java
560 和为 K 的子数组 Java
20 有效的括号 Java
3 无重复字符的最长子串 Java

深度优先搜索和广度优先搜索

  • 深度优先搜索：按照既定的搜索顺序，在一个方向搜索到头之后，回溯搜索下一个方向。

  • 广度优先搜索：从起始位置开始，逐层遍历（按照距离）所有可能到达的位置。

题号 题目 题目说明 文字版题解 题解
79 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 回溯；八皇后的写法 Java
200 岛屿数量 Java