跳到主要内容
Java java 算法
LeetCode Hot 100 算法题解（Java 版） LeetCode Hot 100 高频算法题的 Java 解法，涵盖哈希、双指针、滑动窗口、动态规划、树、图论等核心知识点。包含题目思路分析与完整代码实现，旨在帮助开发者系统复习数据结构与算法，提升编码能力。
雪落无声 发布于 2026/3/27 更新于 2026/6/12 LeetCode Hot 100 算法题解（Java 版）
哈希
两数之和
思路 ：
考虑到的点是一定有一个有效答案，并且是两数之和，返回的是 num 的序号，于是想到采取 hashmap 存放值和序号的映射。
从前向后遍历，先存在当前的 i，判断 target-num[i] 是否存在于数组即可。
解法
class Solution {
public int [] twoSum(int [] nums, int target) {
int [] res = new int [2 ];
Map<Integer, Integer> map = new HashMap <>();
for (int i = 0 ; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
res[0 ] = map.get(target - nums[i]);
res[1 ] = i;
break ;
} else {
map.put(nums[i], i);
}
}
return res;
}
}
字母异位词分组
思路 ：
此题的难点，在于如何判断两个单词是否是同样数量和同样类型的字母组成的，但是题目限制了只有小写字母，于是我们可以考虑采取字符串重新排序，再组成一个新的字符串，如果存在 map 中说明就已经有了。
解法
class Solution {
public List<List<String>> groupAnagrams (String[] strs) {
Map<String, List<String>> res = new HashMap <>();
String s;
for (int i = 0 ; i < strs.length; i++) {
char
if
else
new
ArrayList
return
new
ArrayList
最长连续序列 思路 ：
首先采取 set 去重，遍历 set，我们的思想是只遍历头部元素，其他元素不遍历。
class Solution {
public int longestConsecutive (int [] nums) {
Set<Integer> set = new HashSet <>();
for (int i = 0 ; i < nums.length; i++) {
set.add(nums[i]);
}
int maxs = 0 ;
for (int num : set) {
if (!set.contains(num - 1 )) {
int now = num;
int len = 1 ;
while (set.contains(now + 1 )) {
now++;
len++;
}
maxs = Math.max(len, maxs);
}
}
return maxs;
}
}
双指针
移动零 思路 ：
一个 left，一个 right，每次 right 为 0 时就和 left 交换，left 每次都会指向下一个 0。
class Solution {
public static void swap (int [] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public static void moveZeroes (int [] nums) {
int n = nums.length, left = 0 , right = 0 ;
while (right < n) {
if (nums[right] != 0 ) {
swap(nums, left, right);
left++;
}
right++;
}
}
}
盛最多水的容器 解法 ：
直接计算就好，每次移动较小的一边水槽就行。
class Solution {
public int maxArea (int [] height) {
int max = 0 ;
int left = 0 , right = height.length - 1 , temp = 0 ;
while (left < right) {
temp = Math.min(height[left], height[right]) * (right - left);
if (temp > max) {
max = temp;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
三数之和 class Solution {
public static List<List<Integer>> threeSum (int [] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList <>();
int x, y, z, target;
for (x = 0 ; x < nums.length; x++) {
if (x > 0 && nums[x] == nums[x - 1 ]) {
continue ;
}
target = -nums[x];
z = nums.length - 1 ;
for (y = x + 1 ; y < nums.length; y++) {
if (y > x + 1 && nums[y] == nums[y - 1 ]) {
continue ;
}
while (y < z && nums[y] + nums[z] > target) {
z--;
}
if (y == z) {
break ;
}
if (nums[y] + nums[z] == target) {
List<Integer> tmp = new ArrayList <>();
tmp.add(nums[x]);
tmp.add(nums[y]);
tmp.add(nums[z]);
res.add(tmp);
}
}
}
return res;
}
}
接雨水 class Solution {
public static int trap (int [] height) {
int n = height.length;
if (n == 0 ) {
return 0 ;
}
int [] left = new int [n];
left[0 ] = height[0 ];
for (int i = 1 ; i < n; ++i) {
left[i] = Math.max(left[i - 1 ], height[i]);
}
int [] right = new int [n];
right[n - 1 ] = height[n - 1 ];
for (int i = n - 2 ; i >= 0 ; --i) {
right[i] = Math.max(right[i + 1 ], height[i]);
}
int ans = 0 ;
for (int i = 0 ; i < n; ++i) {
ans += Math.min(left[i], right[i]) - height[i];
}
return ans;
}
}
滑动窗口
无重复字符的最长子串 思路 ：
采取滑动窗口的方法，用 HashMap 记录字符和字符的索引。
如果字符不存在于 HashMap 中，就加入 HashMap 中。
如果字符存在于 HashMap 中，就更新 beg 为重复字符的索引 +1，并删除 HashMap 中重复字符之前的所有字符。
class Solution {
public int lengthOfLongestSubstring (String s) {
if (s.length() == 0 ) {
return 0 ;
}
int max = 1 ;
char [] charArray = s.toCharArray();
Map<Character, Integer> map = new HashMap <>();
int beg = 0 ;
for (int i = 0 ; i < charArray.length; i++) {
if (!map.containsKey(charArray[i])) {
map.put(charArray[i], i);
} else {
if (max < i - beg) {
max = i - beg;
}
for (int j = beg; j < map.get(charArray[i]); j++) {
map.remove(charArray[j]);
}
beg = map.get(charArray[i]) + 1 ;
map.put(charArray[i], i);
}
}
if (max < map.size()) {
max = map.size();
}
return max;
}
}
找到字符串中所有字母异位词 思路 ：
采取 hash 的思想，对比数组是否相等判断是否为子串。
class Solution {
public static List<Integer> findAnagrams (String s, String p) {
List<Integer> res = new ArrayList <>();
if (p.length() > s.length()) {
return res;
}
int [] pl = new int [26 ];
int [] sl = new int [26 ];
for (int i = 0 ; i < p.length(); i++) {
pl[p.charAt(i) - 'a' ]++;
sl[s.charAt(i) - 'a' ]++;
}
if (Arrays.equals(pl, sl)) {
res.add(0 );
}
for (int i = 0 ; i < s.length() - p.length(); i++) {
sl[s.charAt(i) - 'a' ]--;
sl[s.charAt(i + p.length()) - 'a' ]++;
if (Arrays.equals(pl, sl)) {
res.add(i + 1 );
}
}
return res;
}
}
子串
和为 k 的子数组 思路 ：
对于每个前缀和 s[i]，只要统计前面有多少个前缀和 s[j] 等于 s[i]-k，就有多少个以 i 结尾、和为 k 的子数组。
class Solution {
public int subarraySum (int [] nums, int k) {
Map<Integer, Integer> map = new HashMap <>();
map.put(0 , 1 );
int res = 0 ;
int total = 0 ;
for (int i = 0 ; i < nums.length; i++) {
total += nums[i];
if (map.containsKey(total - k)) {
res += map.get(total - k);
}
map.put(total, map.getOrDefault(total, 0 ) + 1 );
}
return res;
}
}
滑动窗口最大值 思路 ：
单调队列，具体思路见，主要就是考虑新进来的元素是窗口中最大，以及最大的元素出窗口。
class Solution {
public int [] maxSlidingWindow(int [] nums, int k) {
int n = nums.length;
Deque<Integer> win = new ArrayDeque <>();
int [] res = new int [n - k + 1 ];
for (int i = 0 ; i < n; i++) {
while (!win.isEmpty() && nums[win.getLast()] <= nums[i]) {
win.removeLast();
}
win.addLast(i);
int beg = i - k + 1 ;
while (win.getFirst() < beg) {
win.removeFirst();
}
if (beg >= 0 ) {
res[beg] = nums[win.getFirst()];
}
}
return res;
}
}
最小覆盖子串 思路 ：
对于此题我们要考虑的点是：1. 如何找到最小的；2. 如何快速判断 left 到 right 中是否包含子串。
这里采取了 tmap 存放了子串的每个字符出现的次数，tmap 的长度就是子串的不同字符个数 total。
smap 用来快速判断 left 和 right 之间是否存在子串，移动 right，如果出现了 t 中的字符并且数量和 t 中对应字符相同，now 加 1。
当 now 和 total 相同时，说明 left 和 right 之间存在子串。
就移动 left 缩短长度，如果减少了 t 中的字符，导致 now 不等于 total 就跳出缩短过程，继续扩大 right。
class Solution {
public static String minWindow (String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "" ;
}
Map<Character, Integer> tmap = new HashMap <>();
Map<Character, Integer> smap = new HashMap <>();
for (int i = 0 ; i < t.length(); i++) {
tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i), 0 ) + 1 );
}
int total = tmap.size();
int now = 0 ;
int left = 0 , right = 0 ;
int [] ans = new int []{-1 , 0 , 0 };
while (left <= right && right < s.length()) {
smap.put(s.charAt(right), smap.getOrDefault(s.charAt(right), 0 ) + 1 );
if (tmap.containsKey(s.charAt(right)) && tmap.get(s.charAt(right)).equals(smap.get(s.charAt(right)))) {
now++;
}
if (now == total) {
while (left <= right && now == total) {
char c = s.charAt(left);
if (tmap.containsKey(c)) {
if (ans[0 ] == -1 || ans[0 ] > right - left + 1 ) {
ans[0 ] = right - left + 1 ;
ans[1 ] = left;
ans[2 ] = right;
}
}
smap.put(s.charAt(left), smap.get(s.charAt(left)) - 1 );
if (tmap.containsKey(s.charAt(left)) && smap.get(s.charAt(left)) < tmap.get(s.charAt(left))) {
now--;
}
left++;
}
}
right++;
}
return ans[0 ] == -1 ? "" : s.substring(ans[1 ], ans[2 ] + 1 );
}
}
普通数组
最大子数组和 class Solution {
public static int maxSubArray (int [] nums) {
int be = nums[0 ];
int max = nums[0 ];
for (int i = 1 ; i < nums.length; i++) {
int x = be + nums[i];
if (x > nums[i]) {
be = x;
} else {
be = nums[i];
}
max = Math.max(max, be);
}
return max;
}
}
合并区间 class Solution {
public int [][] merge(int [][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0 ] - b[0 ]);
List<int []> mergedIntervals = new ArrayList <>();
int beg = intervals[0 ][0 ];
int end = intervals[0 ][1 ];
for (int i = 1 ; i < intervals.length; i++) {
if (intervals[i][0 ] <= end) {
end = Math.max(end, intervals[i][1 ]);
} else {
mergedIntervals.add(new int []{beg, end});
beg = intervals[i][0 ];
end = intervals[i][1 ];
}
}
mergedIntervals.add(new int []{beg, end});
return mergedIntervals.toArray(new int [mergedIntervals.size()][]);
}
}
轮转数组 后 k 个倒序，0-len-k-1 倒序，整体倒序。
class Solution {
public void reverse (int [] nums, int beg, int end) {
int x;
for (int i = beg; i <= (end + beg) / 2 ; i++) {
x = nums[i];
nums[i] = nums[beg + end - i];
nums[beg + end - i] = x;
}
}
public void rotate (int [] nums, int k) {
k = k % nums.length;
reverse(nums, 0 , nums.length - 1 - k);
reverse(nums, nums.length - k, nums.length - 1 );
reverse(nums, 0 , nums.length - 1 );
}
}
除了自身以外数组的乘积 class Solution {
public int [] productExceptSelf(int [] nums) {
int n, i, j, r;
r = 1 ;
n = nums.length;
int [] answer = new int [n];
answer[0 ] = 1 ;
for (i = 1 ; i < n; i++) {
answer[i] = answer[i - 1 ] * nums[i - 1 ];
}
for (j = n - 1 ; j >= 0 ; j--) {
answer[j] = answer[j] * r;
r = r * nums[j];
}
return answer;
}
}
缺失的第一个正数 思路 ：
使用占位的思想，对于一个位置 nums[i]，他按照值来说，正常位次应该在 nums[nums[i]-1] 的位置，我们将所有的值放在该在的位置，然后遍历数组，哪个位置的值不满足要求，就返回这个位置的值就行。如果都满足要求，就返回数组长度 +1 就行。
class Solution {
public int firstMissingPositive (int [] nums) {
for (int i = 0 ; i < nums.length; i++) {
while (nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1 ]) {
int a = nums[nums[i] - 1 ];
nums[nums[i] - 1 ] = nums[i];
nums[i] = a;
}
}
for (int i = 0 ; i < nums.length; ++i) {
if (nums[i] != i + 1 ) {
return i + 1 ;
}
}
return nums.length + 1 ;
}
}
矩阵
矩阵置零 class Solution {
public void setZeroes (int [][] matrix) {
int row = 1 ;
for (int i = 0 ; i < matrix.length; i++) {
for (int j = 0 ; j < matrix[i].length; j++) {
if (matrix[i][j] == 0 ) {
if (i == 0 ) {
row = 0 ;
} else {
matrix[i][0 ] = 0 ;
}
matrix[0 ][j] = 0 ;
}
}
}
for (int i = 1 ; i < matrix.length; i++) {
if (matrix[i][0 ] == 0 ) {
for (int j = 1 ; j < matrix[i].length; j++) {
matrix[i][j] = 0 ;
}
}
}
for (int i = 0 ; i < matrix[0 ].length; i++) {
if (matrix[0 ][i] == 0 ) {
for (int j = 1 ; j < matrix.length; j++) {
matrix[j][i] = 0 ;
}
}
}
if (row == 0 ) {
for (int i = 0 ; i < matrix[0 ].length; i++) {
matrix[0 ][i] = 0 ;
}
}
}
}
螺旋数组 class Solution {
public List<Integer> spiralOrder (int [][] matrix) {
int m, n;
List<Integer> res = new ArrayList <>();
m = matrix.length;
n = matrix[0 ].length;
int i = 0 , j = 0 ;
int x = 0 ;
int minx = 0 , miny = 0 ;
while (n != 0 && m != 0 ) {
if (x == 0 ) {
while (j <= n - 1 ) {
res.add(matrix[i][j]);
j++;
}
j = n - 1 ;
i++;
if (i >= m) {
break ;
}
x = 1 ;
} else if (x == 1 ) {
while (i <= m - 1 ) {
res.add(matrix[i][j]);
i++;
}
i = m - 1 ;
j--;
if (j < minx) {
break ;
}
x = 2 ;
} else if (x == 2 ) {
while (j >= minx) {
res.add(matrix[i][j]);
j--;
}
j = minx;
i--;
x = 3 ;
} else {
while (i > miny) {
res.add(matrix[i][j]);
i--;
}
j++;
x = 0 ;
minx++;
miny++;
i = miny;
m--;
n--;
if (i >= m || j >= n) {
break ;
}
}
}
return res;
}
}
旋转图像 class Solution {
public void rotate (int [][] matrix) {
int x = 0 ;
int n = matrix.length;
for (int i = 0 ; i < n; i++) {
for (int j = i; j < n; j++) {
x = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = x;
}
}
for (int i = 0 ; i < n / 2 ; i++) {
for (int j = 0 ; j < n; j++) {
x = matrix[j][i];
matrix[j][i] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = x;
}
}
}
}
搜索二维矩阵 II 思路 ：
根据样例而言，我们将行和列连起来看，即第一行 + 最后一列，按照右上角的元素来看，比这个元素大的就在列上，小的就在行上，基于这个发现，引申出来的做法：初始化为整个二维数组最右上角的元素。如果 target 等于这个元素，直接返回 true。如果说 target 小于这个元素，说明不可能存在于这一列上，那么就把这一列向前移动。如果说 target 大于这个元素，说明不可能存在于这一行上，那么就把这一行向下移动。
class Solution {
public boolean searchMatrix (int [][] matrix, int target) {
int x = 0 ;
int y = matrix[x].length - 1 ;
while (x < matrix.length && y >= 0 ) {
if (matrix[x][y] == target) {
return true ;
} else if (matrix[x][y] < target) {
x++;
} else {
y--;
}
}
return false ;
}
}
链表
相交链表 class Solution {
public ListNode getIntersectionNode (ListNode headA, ListNode headB) {
int lena = 0 , lenb = 0 ;
ListNode head1 = headA;
while (head1 != null ) {
head1 = head1.next;
lena++;
}
ListNode head2 = headB;
while (head2 != null ) {
head2 = head2.next;
lenb++;
}
head1 = headA;
head2 = headB;
while (lena > lenb) {
head1 = head1.next;
lena--;
}
while (lena < lenb) {
head2 = head2.next;
lenb--;
}
while (head2 != head1 && head1 != null && head2 != null ) {
head1 = head1.next;
head2 = head2.next;
}
if (head1 != null && head2 != null ) {
return head1;
}
return null ;
}
}
反转链表 class Solution {
public ListNode reverseList (ListNode head) {
if (head == null || head.next == null ) {
return head;
}
ListNode before = null ;
ListNode now = head;
while (now != null ) {
ListNode a = now.next;
now.next = before;
before = now;
now = a;
}
return before;
}
}
回文链表 class Solution {
public boolean isPalindrome (ListNode head) {
boolean res = true ;
if (head == null ) {
return false ;
}
if (head.next == null ) {
return true ;
}
ListNode beg = head;
ListNode end = head;
while (end != null ) {
beg = beg.next;
end = end.next;
if (end != null ) {
end = end.next;
}
}
ListNode before = null ;
ListNode now = beg;
while (now != null ) {
ListNode a = now.next;
now.next = before;
before = now;
now = a;
}
ListNode hou = before;
ListNode qian = head;
while (qian != null && hou != null ) {
if (qian.val != hou.val) {
res = false ;
break ;
}
qian = qian.next;
hou = hou.next;
}
return res;
}
}
环形链表 思路 ：快慢指针。如果当块指针遇到慢指针就有环，遇不到能走到末尾就没环。
class Solution {
public boolean hasCycle (ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true ;
}
}
return false ;
}
}
环形链表 II 思路 ：pos 不是参数，只是评测内部的判断是否有环的参数。所以此题的目的是找到环的开始位置。
我们使用快慢指针，慢指针一次走 1，快指针一次走 2。如上图所示，在紫色点相遇。此时快指针走过的距离为：fast=a+b+n*(b+c)。由此可知慢指针走的距离是 fast/2 = a+b。由此整理可知道 2a+2b=a+b+nb+nc，a=c+(n-1)(b+c)。由此我们找相遇点，此时慢指针在紫色点，距离相遇点距离为 c，我们让一个节点从头结点向前走（每次 1 个），他们会在相遇点相遇。
class Solution {
public ListNode detectCycle (ListNode head) {
if (head == null ) {
return null ;
}
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null ) {
slow = slow.next;
fast = fast.next;
if (fast == null ) {
return null ;
} else {
fast = fast.next;
}
if (fast != null && slow != null ) {
if (fast == slow) {
break ;
}
} else {
return null ;
}
}
ListNode beg = head;
while (beg != slow) {
beg = beg.next;
slow = slow.next;
}
return beg;
}
}
合并两个有序链表 class Solution {
public ListNode mergeTwoLists (ListNode list1, ListNode list2) {
ListNode res = new ListNode ();
ListNode x = res;
while (list1 != null && list2 != null ) {
if (list1.val <= list2.val) {
x.next = list1;
list1 = list1.next;
} else {
x.next = list2;
list2 = list2.next;
}
x = x.next;
}
if (list1 == null && list2 != null ) {
x.next = list2;
}
if (list2 == null && list1 != null ) {
x.next = list1;
}
return res.next;
}
}
两数相加 class Solution {
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
ListNode res = new ListNode ();
ListNode head = res;
int num = 0 ;
while (l1 != null && l2 != null ) {
int x = l1.val + l2.val + num;
if (x >= 10 ) {
num = 1 ;
res.next = new ListNode (x % 10 );
res = res.next;
} else {
num = 0 ;
res.next = new ListNode (x);
res = res.next;
}
l1 = l1.next;
l2 = l2.next;
}
if (l1 == null ) {
while (l2 != null ) {
int x = num + l2.val;
if (x >= 10 ) {
num = 1 ;
res.next = new ListNode (x % 10 );
res = res.next;
} else {
num = 0 ;
res.next = new ListNode (x);
res = res.next;
}
l2 = l2.next;
}
} else {
while (l1 != null ) {
int x = num + l1.val;
if (x >= 10 ) {
num = 1 ;
res.next = new ListNode (x % 10 );
res = res.next;
} else {
num = 0 ;
res.next = new ListNode (x);
res = res.next;
}
l1 = l1.next;
}
}
if (num == 1 ) {
res.next = new ListNode (1 );
res = res.next;
}
return head.next;
}
}
删除链表的倒数第 N 个节点 class Solution {
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode fake = new ListNode ();
fake.next = head;
ListNode fakehead = fake;
ListNode x = head;
ListNode y = head;
int i = 1 ;
while (i != n) {
y = y.next;
i++;
}
while (y.next != null ) {
x = x.next;
y = y.next;
fakehead = fakehead.next;
}
fakehead.next = x.next;
return fake.next;
}
}
两两交换链表中的节点 思路 ：采取一个空节点作为头结点（方便操作）。before 保存两两交换的前一个节点，a 为两两交换的第一个节点，be 为两两交换的第二个节点，next 保存下一组的第一个节点。
class Solution {
public ListNode swapPairs (ListNode head) {
if (head == null || head.next == null ) {
return head;
}
ListNode first = new ListNode ();
first.next = head;
ListNode be = first;
ListNode mid = head;
ListNode end = head.next;
ListNode cun = new ListNode ();
while (true ) {
be.next = end;
cun = end.next;
end.next = mid;
mid.next = cun;
be = mid;
mid = cun;
if (mid == null ) {
break ;
}
end = cun.next;
if (end == null ) {
break ;
}
}
return first.next;
}
}
K 个一组翻转链表 class Solution {
public ListNode reverseKGroup (ListNode head, int k) {
if (k == 1 ) {
return head;
}
ListNode fakehead = new ListNode ();
fakehead.next = head;
ListNode pre = fakehead;
ListNode beg = head;
ListNode end = head;
while (beg != null && end != null ) {
for (int i = 0 ; i < k - 1 ; i++) {
end = end.next;
if (end == null ) {
return fakehead.next;
}
}
ListNode m = new ListNode ();
ListNode beg1 = beg;
ListNode nextbeg = end.next;
while (beg1 != end) {
m = beg1.next;
beg1.next = end.next;
end.next = beg1;
beg1 = m;
}
pre.next = end;
pre = beg;
beg = beg.next;
end = beg;
}
return fakehead.next;
}
}
随机链表的复制 class Solution {
public Node copyRandomList (Node head) {
Map<Node, Integer> map = new HashMap <>();
List<Node> list = new ArrayList <>();
int i = 0 ;
Node beg = head;
while (beg != null ) {
map.put(beg, i);
i++;
beg = beg.next;
}
Node res = new Node (0 );
Node x = res;
beg = head;
while (beg != null ) {
Node tes = new Node (beg.val);
x.next = tes;
x = x.next;
beg = beg.next;
list.add(tes);
}
beg = head;
x = res.next;
int num;
while (beg != null ) {
if (beg.random != null ) {
num = map.get(beg.random);
x.random = list.get(num);
} else {
x.random = null ;
}
beg = beg.next;
x = x.next;
}
return res.next;
}
}
排序链表 class Solution {
public ListNode sortList (ListNode head) {
if (head == null || head.next == null ) {
return head;
}
ListNode mid = getMiddle(head);
ListNode rightHead = mid.next;
mid.next = null ;
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
return merge(left, right);
}
private ListNode getMiddle (ListNode head) {
if (head == null ) return null ;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge (ListNode l1, ListNode l2) {
if (l1 == null ) return l2;
if (l2 == null ) return l1;
ListNode dummy = new ListNode (0 );
ListNode tail = dummy;
while (l1 != null && l2 != null ) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
if (l1 != null ) tail.next = l1;
if (l2 != null ) tail.next = l2;
return dummy.next;
}
}
合并 K 个升序链表 思路 ：lists 一分为二（尽量均分），先合并前一半的链表，再合并后一半的链表，然后把这两个链表合并成最终的链表。
class Solution {
public ListNode mergeKLists (ListNode[] lists) {
return merge(lists, 0 , lists.length - 1 );
}
public ListNode merge (ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null ;
}
int mid = (l + r) / 2 ;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1 , r));
}
public ListNode mergeTwoLists (ListNode a, ListNode b) {
if (a == null || b == null ) {
return a != null ? a : b;
}
ListNode head = new ListNode (0 );
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null ) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}
LRU 缓存 思路 ：直接使用 LinkedHashMap，它本身就实现了 LRU。get 之前先把 map 中的 key 删了再插入。put 之前先判断是否存在，存在就删除再插入，返回就行，如果不存在就判断 size，如果 size 不满，插入返回就好。如果 size 满了，就用迭代器取出 key 的第一个（最久未使用的），删除。
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private final int capacity;
private final Node dummy = new Node (0 , 0 );
private final Map<Integer, Node> keyToNode = new HashMap <>();
public LRUCache (int capacity) {
this .capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
private Node getNode (int key) {
if (!keyToNode.containsKey(key)) {
return null ;
}
Node node = keyToNode.get(key);
remove(node);
pushFront(node);
return node;
}
private void remove (Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
private void pushFront (Node x) {
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
public int get (int key) {
if (!keyToNode.containsKey(key)) {
return -1 ;
}
Node x = getNode(key);
return x.value;
}
public void put (int key, int value) {
Node node = getNode(key);
if (node != null ) {
node.value = value;
return ;
}
node = new Node (key, value);
keyToNode.put(key, node);
pushFront(node);
if (keyToNode.size() > capacity) {
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
}
}
}
二叉树
二叉树的中序遍历 class Solution {
public List<Integer> inorderTraversal (TreeNode root) {
List<Integer> res = new ArrayList <>();
find(root, res);
return res;
}
public void find (TreeNode root, List<Integer> res) {
if (root == null ) {
return ;
}
find(root.left, res);
res.add(root.val);
find(root.right, res);
}
}
二叉树的最大深度 class Solution {
public int max = 0 ;
public int maxDepth (TreeNode root) {
findmax(root, 1 );
return max;
}
public void findmax (TreeNode root, int len) {
if (root == null ) {
return ;
}
if (len > max) {
max = len;
}
findmax(root.left, len + 1 );
findmax(root.right, len + 1 );
}
}
翻转二叉树 class Solution {
public TreeNode invertTree (TreeNode root) {
reverse(root);
return root;
}
public void reverse (TreeNode root) {
if (root == null ) {
return ;
}
if (root.left != null || root.right != null ) {
TreeNode s = root.left;
root.left = root.right;
root.right = s;
}
reverse(root.left);
reverse(root.right);
}
}
对称二叉树 class Solution {
boolean res = true ;
public void check (TreeNode r1, TreeNode r2) {
if (res == false || (r1 == null && r2 == null )) {
return ;
}
if ((r1 == null && r2 != null ) || (r1 != null && r2 == null )) {
res = false ;
return ;
}
if (r1.val != r2.val) {
res = false ;
return ;
}
check(r1.left, r2.right);
check(r1.right, r2.left);
}
public boolean isSymmetric (TreeNode root) {
TreeNode left = root.left;
TreeNode right = root.right;
check(left, right);
return res;
}
}
二叉树的直径 class Solution {
int ans;
public int diameterOfBinaryTree (TreeNode root) {
ans = 1 ;
depth(root);
return ans - 1 ;
}
public int depth (TreeNode node) {
if (node == null ) {
return 0 ;
}
int L = depth(node.left);
int R = depth(node.right);
ans = Math.max(ans, L + R + 1 );
return Math.max(L, R) + 1 ;
}
}
二叉树的层序遍历 class Solution {
public List<List<Integer>> levelOrder (TreeNode root) {
List<List<Integer>> res = new ArrayList <>();
levelOrderleft(root, 0 , res);
return res;
}
public void levelOrderleft (TreeNode root, int height, List<List<Integer>> res) {
if (root == null ) {
return ;
}
if (res.size() - 1 < height) {
List<Integer> tes = new ArrayList <>();
res.add(tes);
}
res.get(height).add(root.val);
if (root.left != null ) {
levelOrderleft(root.left, height + 1 , res);
}
if (root.right != null ) {
levelOrderleft(root.right, height + 1 , res);
}
}
}
将有序数组转换为二叉搜索树 class Solution {
public TreeNode sortedArrayToBST (int [] nums) {
return helper(nums, 0 , nums.length - 1 );
}
public TreeNode helper (int [] nums, int left, int right) {
if (left > right) {
return null ;
}
int mid = (left + right) / 2 ;
TreeNode root = new TreeNode (nums[mid]);
root.left = helper(nums, left, mid - 1 );
root.right = helper(nums, mid + 1 , right);
return root;
}
}
验证二叉搜索树 class Solution {
public boolean isValidBST (TreeNode root) {
Deque<TreeNode> stack = new LinkedList <>();
double inorder = -Double.MAX_VALUE;
while (!stack.isEmpty() || root != null ) {
while (root != null ) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.val <= inorder) {
return false ;
}
inorder = root.val;
root = root.right;
}
return true ;
}
}
二叉搜索树中第 K 小的元素 class Solution {
int x = 1 ;
int num;
public void mid (TreeNode root, int k) {
if (root == null || x > k) {
return ;
}
mid(root.left, k);
if (x == k) {
num = root.val;
}
x++;
mid(root.right, k);
}
public int kthSmallest (TreeNode root, int k) {
mid(root, k);
return num;
}
}
二叉树的右视图 class Solution {
public List<Integer> rightSideView (TreeNode root) {
List<Integer> res = new ArrayList <>();
find(root, res, 1 );
return res;
}
public void find (TreeNode root, List<Integer> res, int heigh) {
if (root == null ) {
return ;
}
if (res.size() < heigh) {
res.add(root.val);
}
find(root.right, res, heigh + 1 );
find(root.left, res, heigh + 1 );
}
}
二叉树展开为链表
如果当前节点为空，返回。
递归右子树。
递归左子树。
把 root.left 置为空。
头插法，把 root 插在 head 的前面，也就是 root.right=head。
现在 root 是链表的头节点，把 head 更新为 root。
class Solution {
private TreeNode head;
public void flatten (TreeNode root) {
if (root == null ) {
return ;
}
flatten(root.right);
flatten(root.left);
root.left = null ;
root.right = head;
head = root;
}
}
从前序与中序遍历序列构造二叉树 class Solution {
public Map<Integer, Integer> indexMap;
public TreeNode buildTree (int [] preorder, int [] inorder) {
int n = inorder.length;
indexMap = new HashMap <>();
for (int i = 0 ; i < n; i++) {
indexMap.put(inorder[i], i);
}
return findroot(preorder, inorder, 0 , n - 1 , 0 , n - 1 );
}
public TreeNode findroot (int [] preorder, int [] inorder, int preleft, int preright, int inleft, int inright) {
if (preleft > preright) {
return null ;
}
int root_num = preleft;
int in = indexMap.get(preorder[root_num]);
TreeNode root = new TreeNode (preorder[root_num]);
root.left = findroot(preorder, inorder, preleft + 1 , preleft + in - inleft, inleft, in - 1 );
root.right = findroot(preorder, inorder, preleft + in - inleft + 1 , preright, in + 1 , inright);
return root;
}
}
路径总和 III 思路 ：前缀和。使用 map，key 为到当前节点前的前缀和，value 为个数。dfs（）包含的参数，只介绍下 sum，为到这个节点前的所有前缀和，其他的都知道。到一个节点，先前缀和 + 这个节点值 sum。判断这个 sum-目标值后是否在 map 中存在并且大于 0，满足就将 res+（map 中的值）。然后将这个 sum 放入 map 中。遍历左右。出来后将这个 map（sum）减 1。
class Solution {
public int res = 0 ;
public int pathSum (TreeNode root, int targetSum) {
if (root == null ) {
return 0 ;
}
Map<Long, Integer> map = new HashMap <>();
map.put(0L , 1 );
dfs(root, targetSum, map, 0L );
return res;
}
public void dfs (TreeNode root, int targetSum, Map<Long, Integer> map, Long sum) {
if (root == null ) {
return ;
}
sum += root.val;
if (map.containsKey(sum - targetSum) && map.get(sum - targetSum) > 0 ) {
res += map.get(sum - targetSum);
}
map.put(sum, map.getOrDefault(sum, 0 ) + 1 );
dfs(root.left, targetSum, map, sum);
dfs(root.right, targetSum, map, sum);
map.put(sum, map.get(sum) - 1 );
}
}
二叉树的最近公共祖先 class Solution {
public List<TreeNode> list1 = new ArrayList <>();
public List<TreeNode> list2 = new ArrayList <>();
public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> res = new ArrayList <>();
dfs(root, p, q, res);
TreeNode result = root;
for (int i = list1.size() - 1 ; i >= 0 ; i--) {
TreeNode s = list1.get(i);
if (list2.contains(s)) {
return s;
}
}
return result;
}
public void dfs (TreeNode root, TreeNode p, TreeNode q, List<TreeNode> res) {
if (root == null || (list1.size() != 0 && list2.size() != 0 )) {
return ;
}
res.add(root);
if (root == p) {
list1 = new ArrayList <>(res);
}
if (root == q) {
list2 = new ArrayList <>(res);
}
dfs(root.left, p, q, res);
dfs(root.right, p, q, res);
res.remove(res.size() - 1 );
}
}
二叉树的最大路径和 class Solution {
public int max = Integer.MIN_VALUE;
public int maxPathSum (TreeNode root) {
findmax(root);
return max;
}
public int findmax (TreeNode root) {
if (root == null ) {
return 0 ;
}
int left = Math.max(findmax(root.left), 0 );
int right = Math.max(findmax(root.right), 0 );
int sum = root.val + left + right;
max = Math.max(sum, max);
return root.val + Math.max(left, right);
}
}
图论
岛屿数量 class Solution {
public int sum = 0 ;
public int numIslands (char [][] grid) {
for (int i = 0 ; i < grid.length; i++) {
for (int j = 0 ; j < grid[0 ].length; j++) {
if (grid[i][j] == '1' ) {
find(grid, i, j);
sum++;
}
}
}
return sum;
}
public void find (char [][] grid, int i, int j) {
if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0 ].length - 1 || grid[i][j] != '1' ) {
return ;
}
grid[i][j] = '0' ;
find(grid, i - 1 , j);
find(grid, i + 1 , j);
find(grid, i, j - 1 );
find(grid, i, j + 1 );
}
}
腐烂的橘子 思路 ：1 遍历网格中所有腐烂橘子（值≥2）的位置，对每个腐烂橘子的上下左右四个方向格子执行 DFS，DFS 中先判断边界、空格子（值为 0）、非新鲜且代际≤当前传入代际的情况，满足则直接返回，否则将当前格子标记为当前代际值（代表该时间点腐烂），并递归处理该格子的四个方向（代际 + 1）；2 二次遍历网格，先检查是否存在未腐烂的新鲜橘子（值为 1），若有则返回 -1，同时计算每个腐烂橘子代际值与初始腐烂值（2）的差值，更新最大差值到 max 变量；3 最终返回 max，该值即为所有新鲜橘子被腐烂的最大时间（无新鲜橘子时返回 0）。
class Solution {
public int max = 0 ;
public int orangesRotting (int [][] grid) {
for (int i = 0 ; i < grid.length; i++) {
for (int j = 0 ; j < grid[i].length; j++) {
if (grid[i][j] >= 2 ) {
dfs(grid, i - 1 , j, grid[i][j] + 1 );
dfs(grid, i + 1 , j, grid[i][j] + 1 );
dfs(grid, i, j - 1 , grid[i][j] + 1 );
dfs(grid, i, j + 1 , grid[i][j] + 1 );
}
}
}
for (int i = 0 ; i < grid.length; i++) {
for (int j = 0 ; j < grid[i].length; j++) {
if (grid[i][j] == 1 ) {
return -1 ;
}
max = Math.max(max, grid[i][j] - 2 );
}
}
return max;
}
public void dfs (int [][] grid, int i, int j, int gen) {
if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0 ].length - 1 || grid[i][j] == 0 || (grid[i][j] != 1 && grid[i][j] <= gen)) {
return ;
}
grid[i][j] = gen;
dfs(grid, i - 1 , j, gen + 1 );
dfs(grid, i + 1 , j, gen + 1 );
dfs(grid, i, j - 1 , gen + 1 );
dfs(grid, i, j + 1 , gen + 1 );
}
}
课程表 宽搜思想：将出度信息保存在一个 grid。使用一个队列。每次放入新的起点。
class Solution {
public boolean canFinish (int numCourses, int [][] prerequisites) {
int [] tes = new int [numCourses];
List<List<Integer>> grid = new ArrayList <>();
for (int i = 0 ; i < numCourses; i++) {
grid.add(new ArrayList <Integer>());
}
for (int i = 0 ; i < prerequisites.length; i++) {
grid.get(prerequisites[i][1 ]).add(prerequisites[i][0 ]);
tes[prerequisites[i][0 ]]++;
}
Queue<Integer> queue = new LinkedList <>();
for (int i = 0 ; i < numCourses; i++) {
if (tes[i] == 0 ) {
queue.offer(i);
}
}
int len = 0 ;
while (!queue.isEmpty()) {
len++;
int beg = queue.poll();
for (int i = 0 ; i < grid.get(beg).size(); i++) {
tes[grid.get(beg).get(i)]--;
if (tes[grid.get(beg).get(i)] == 0 ) {
queue.offer(grid.get(beg).get(i));
}
}
}
return len == numCourses;
}
}
实现前缀树 class Trie {
public Trie[] child;
public boolean isend;
public Trie () {
child = new Trie [26 ];
isend = false ;
}
public void insert (String word) {
Trie node = this ;
for (int i = 0 ; i < word.length(); i++) {
char a = word.charAt(i);
if (node.child[a - 'a' ] == null ) {
node.child[a - 'a' ] = new Trie ();
}
node = node.child[a - 'a' ];
}
node.isend = true ;
}
public boolean search (String word) {
Trie node = this ;
for (int i = 0 ; i < word.length(); i++) {
char a = word.charAt(i);
if (node.child[a - 'a' ] == null ) {
return false ;
}
node = node.child[a - 'a' ];
}
if (node.isend == false ) {
return false ;
}
return true ;
}
public boolean startsWith (String prefix) {
Trie node = this ;
for (int i = 0 ; i < prefix.length(); i++) {
char a = prefix.charAt(i);
if (node.child[a - 'a' ] == null ) {
return false ;
}
node = node.child[a - 'a' ];
}
return true ;
}
}
回溯
全排列 class Solution {
public List<List<Integer>> res;
public List<Integer> tes;
public List<List<Integer>> permute (int [] nums) {
res = new ArrayList <>();
tes = new ArrayList <>();
int [] zai = new int [nums.length];
dfs(nums, zai);
return res;
}
public void dfs (int [] nums, int [] zai) {
if (tes.size() == zai.length) {
res.add(new ArrayList <>(tes));
return ;
}
for (int i = 0 ; i < nums.length; i++) {
if (zai[i] == 0 ) {
zai[i] = 1 ;
tes.add(nums[i]);
dfs(nums, zai);
zai[i] = 0 ;
tes.remove(tes.size() - 1 );
}
}
}
}
子集 class Solution {
public List<List<Integer>> res;
public List<List<Integer>> subsets (int [] nums) {
int [] zai = new int [nums.length];
List<Integer> tes = new ArrayList <>();
res = new ArrayList <>();
for (int i = 0 ; i <= nums.length; i++) {
dfs(nums, tes, i, 0 );
}
return res;
}
public void dfs (int [] nums, List<Integer> tes, int len, int beg) {
if (tes.size() == len) {
res.add(new ArrayList <>(tes));
return ;
}
for (int i = beg; i < nums.length; i++) {
tes.add(nums[i]);
dfs(nums, tes, len, i + 1 );
tes.remove(tes.size() - 1 );
}
}
}
电话号码的字母组合 class Solution {
public List<String> letterCombinations (String digits) {
List<String> res = new ArrayList <String>();
if (digits.length() == 0 ) {
return res;
}
Map<Character, String> num = new HashMap <>();
num.put('2' , "abc" );
num.put('3' , "def" );
num.put('4' , "ghi" );
num.put('5' , "jkl" );
num.put('6' , "mno" );
num.put('7' , "pqrs" );
num.put('8' , "tuv" );
num.put('9' , "wxyz" );
find(res, num, digits, 0 , new StringBuffer ());
return res;
}
public void find (List<String> res, Map<Character, String> num, String digits, int beg, StringBuffer tes) {
if (beg == digits.length()) {
res.add(tes.toString());
return ;
}
String a = num.get(digits.charAt(beg));
for (int j = 0 ; j < a.length(); j++) {
tes.append(a.charAt(j));
find(res, num, digits, beg + 1 , tes);
tes.deleteCharAt(beg);
}
}
}
组合总数 class Solution {
public List<List<Integer>> res;
public List<List<Integer>> combinationSum (int [] candidates, int target) {
List<Integer> tes = new ArrayList <>();
res = new ArrayList <>();
find(candidates, target, tes, 0 , 0 );
return res;
}
public void find (int [] candidates, int target, List<Integer> tes, int sum, int beg) {
if (sum == target) {
res.add(new ArrayList <>(tes));
return ;
}
for (int i = beg; i < candidates.length; i++) {
if (sum + candidates[i] <= target) {
tes.add(candidates[i]);
find(candidates, target, tes, sum + candidates[i], i);
tes.remove(tes.size() - 1 );
}
}
}
}
括号生成 class Solution {
public List<String> res;
public List<String> generateParenthesis (int n) {
res = new ArrayList <>();
StringBuffer s = new StringBuffer ();
int [] zai = new int [2 ];
zai[0 ] = n;
zai[1 ] = n;
find(zai, s);
return res;
}
public void find (int [] zai, StringBuffer s) {
if (zai[0 ] == 0 && zai[1 ] == 0 ) {
res.add(s.toString());
return ;
}
for (int i = 0 ; i <= 1 ; i++) {
if (i == 0 && zai[0 ] > 0 ) {
s.append('(' );
zai[0 ]--;
find(zai, s);
zai[0 ]++;
s.deleteCharAt(s.length() - 1 );
}
if (i == 1 && zai[1 ] > 0 && zai[0 ] < zai[1 ]) {
s.append(')' );
zai[1 ]--;
find(zai, s);
zai[1 ]++;
s.deleteCharAt(s.length() - 1 );
}
}
}
}
单词搜索 class Solution {
boolean isexist = false ;
public boolean exist (char [][] board, String word) {
int [][] zai = new int [board.length][board[0 ].length];
for (int i = 0 ; i < board.length; i++) {
for (int j = 0 ; j < board[i].length; j++) {
if (board[i][j] == word.charAt(0 )) {
zai[i][j] = 1 ;
find(board, i, j, word, 1 , zai);
zai[i][j] = 0 ;
}
if (isexist) {
return isexist;
}
}
}
return isexist;
}
public void find (char [][] board, int i, int j, String word, int index, int [][] zai) {
if (index == word.length() || isexist) {
isexist = true ;
return ;
}
if (i - 1 >= 0 && zai[i - 1 ][j] != 1 && board[i - 1 ][j] == word.charAt(index)) {
zai[i - 1 ][j] = 1 ;
find(board, i - 1 , j, word, index + 1 , zai);
zai[i - 1 ][j] = 0 ;
}
if (i + 1 < board.length && zai[i + 1 ][j] != 1 && board[i + 1 ][j] == word.charAt(index)) {
zai[i + 1 ][j] = 1 ;
find(board, i + 1 , j, word, index + 1 , zai);
zai[i + 1 ][j] = 0 ;
}
if (j - 1 >= 0 && zai[i][j - 1 ] != 1 && board[i][j - 1 ] == word.charAt(index)) {
zai[i][j - 1 ] = 1 ;
find(board, i, j - 1 , word, index + 1 , zai);
zai[i][j - 1 ] = 0 ;
}
if (j + 1 < board[i].length && zai[i][j + 1 ] != 1 && board[i][j + 1 ] == word.charAt(index)) {
zai[i][j + 1 ] = 1 ;
find(board, i, j + 1 , word, index + 1 , zai);
zai[i][j + 1 ] = 0 ;
}
}
}
分割回文串 class Solution {
public List<List<String>> partition (String s) {
List<List<String>> res = new ArrayList <>();
int [][] dp = new int [s.length()][s.length()];
dfs(s, 0 , res, dp, new ArrayList <>());
return res;
}
public void dfs (String s, int index, List<List<String>> res, int [][] dp, List<String> tes) {
if (index == s.length()) {
res.add(new ArrayList <>(tes));
return ;
}
for (int i = index; i < s.length(); ++i) {
if (ishui(index, i, s, dp)) {
tes.add(s.substring(index, i + 1 ));
dfs(s, i + 1 , res, dp, tes);
tes.remove(tes.size() - 1 );
}
}
}
public boolean ishui (int left, int right, String s, int [][] dp) {
if (dp[left][right] == 1 ) {
return true ;
}
if (dp[left][right] == -1 ) {
return false ;
}
while (left != right && left < right) {
if (s.charAt(left) != s.charAt(right)) {
dp[left][right] = -1 ;
return false ;
}
left++;
right--;
}
dp[left][right] = 1 ;
return true ;
}
}
N 皇后 class Solution {
public List<List<String>> solveNQueens (int n) {
String[][] dp = new String [n][n];
int [] col = new int [n];
for (int i = 0 ; i < n; i++) {
for (int j = 0 ; j < n; j++) {
dp[i][j] = "." ;
}
}
List<List<String>> res = new ArrayList <>();
find(0 , n, dp, res, col);
return res;
}
public void find (int index, int n, String[][] dp, List<List<String>> res, int [] col) {
if (index == n) {
List<String> tes = new ArrayList <>();
for (int i = 0 ; i < n; i++) {
String s = "" ;
for (int j = 0 ; j < n; j++) {
s += dp[i][j];
}
tes.add(s);
}
res.add(tes);
return ;
}
for (int i = 0 ; i < n; i++) {
if (isok(dp, index, i, n, col) || index == 0 ) {
dp[index][i] = "Q" ;
col[i] = 1 ;
find(index + 1 , n, dp, res, col);
col[i] = 0 ;
dp[index][i] = "." ;
}
}
}
public boolean isok (String[][] dp, int x, int y, int n, int [] col) {
if (col[y] == 1 ) {
return false ;
}
int i = x - 1 ;
int j = y - 1 ;
while (i >= 0 && j >= 0 ) {
if (dp[i][j].equals("Q" )) {
return false ;
}
i--;
j--;
}
i = x - 1 ;
j = y + 1 ;
while (i >= 0 && j < n) {
if (dp[i][j].equals("Q" )) {
return false ;
}
i--;
j++;
}
return true ;
}
}
二分查找
搜索插入位置 class Solution {
public int searchInsert (int [] nums, int target) {
int beg = 0 ;
int end = nums.length - 1 ;
int mid;
while (beg <= end) {
mid = beg + ((end - beg) / 2 );
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
end = mid - 1 ;
} else {
beg = mid + 1 ;
}
}
return end + 1 ;
}
}
搜索二维矩阵 class Solution {
public boolean searchMatrix (int [][] matrix, int target) {
int row = -1 ;
for (int i = 0 ; i < matrix.length; i++) {
if (target <= matrix[i][matrix[i].length - 1 ]) {
row = i;
break ;
}
}
if (row == -1 || target < matrix[row][0 ]) {
return false ;
}
int left = 0 ;
int right = matrix[row].length - 1 ;
int mid = 0 ;
while (left <= right) {
mid = (left + right) / 2 ;
if (matrix[row][mid] == target) {
return true ;
} else if (matrix[row][mid] < target) {
left = mid + 1 ;
} else {
right = mid - 1 ;
}
}
return false ;
}
}
在排序数组中查找元素的第一个和最后一个位置 class Solution {
public int [] searchRange(int [] nums, int target) {
int [] res = new int []{-1 , -1 };
if (nums == null || nums.length == 0 ) {
return res;
}
int left = 0 ;
int right = nums.length - 1 ;
while (left <= right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < target) {
left = mid + 1 ;
} else {
right = mid - 1 ;
}
}
if (left >= nums.length || nums[left] != target) {
return res;
}
res[0 ] = left;
left = 0 ;
right = nums.length - 1 ;
while (left <= right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] <= target) {
left = mid + 1 ;
} else {
right = mid - 1 ;
}
}
if (right < 0 || nums[right] != target) {
return res;
}
res[1 ] = right;
return res;
}
}
搜索旋转排序数组 class Solution {
public int search (int [] nums, int target) {
int beg = 0 ;
int end = nums.length - 1 ;
while (beg <= end) {
int mid = beg + (end - beg) / 2 ;
if (target == nums[mid]) {
return mid;
}
if (nums[beg] <= nums[mid]) {
if (target <= nums[mid] && target >= nums[beg]) {
end = mid - 1 ;
} else {
beg = mid + 1 ;
}
} else {
if (target > nums[mid] && target <= nums[end]) {
beg = mid + 1 ;
} else {
end = mid - 1 ;
}
}
}
return -1 ;
}
}
寻找旋转排序数组中的最小值 class Solution {
public int findMin (int [] nums) {
int beg = 0 ;
int end = nums.length - 1 ;
int min = nums[nums.length - 1 ];
if (nums[nums.length - 1 ] >= nums[0 ]) {
return nums[0 ];
}
while (beg < end) {
int mid = beg + (end - beg) / 2 ;
if (nums[mid] > nums[end]) {
beg = mid + 1 ;
} else {
end = mid;
}
}
return nums[beg];
}
}
寻找两个正序数组的中位数 class Solution {
public double findMedianSortedArrays (int [] nums1, int [] nums2) {
int [] res = nums1;
if (nums1.length > nums2.length) {
int [] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int left = 0 , right = m;
while (left <= right) {
int i = (left + right) / 2 ;
int j = (m + n + 1 ) / 2 - i;
int left1, right1, left2, right2;
if (i == 0 ) {
left1 = Integer.MIN_VALUE;
} else {
left1 = nums1[i - 1 ];
}
if (i == m) {
right1 = Integer.MAX_VALUE;
} else {
right1 = nums1[i];
}
if (j == 0 ) {
left2 = Integer.MIN_VALUE;
} else {
left2 = nums2[j - 1 ];
}
if (j == n) {
right2 = Integer.MAX_VALUE;
} else {
right2 = nums2[j];
}
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 == 0 ) {
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0 ;
} else {
return Math.max(left1, left2) + 0.0 ;
}
} else if (left1 > right2) {
right = i - 1 ;
} else {
left = i + 1 ;
}
}
return 0 ;
}
}
栈
有效的括号 class Solution {
public boolean isValid (String s) {
Stack<Character> left = new Stack <>();
char c;
for (int i = 0 ; i < s.length(); i++) {
c = s.charAt(i);
if (c == '(' || c == '{' || c == '[' ) {
left.push(c);
} else if (c == ')' ) {
if (!left.isEmpty() && left.peek() == '(' ) {
left.pop();
} else {
return false ;
}
} else if (c == '}' ) {
if (!left.isEmpty() && left.peek() == '{' ) {
left.pop();
} else {
return false ;
}
} else {
if (!left.isEmpty() && left.peek() == '[' ) {
left.pop();
} else {
return false ;
}
}
}
if (left.isEmpty()) {
return true ;
} else {
return false ;
}
}
}
最小栈 class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack () {
stack = new Stack <Integer>();
minStack = new Stack <Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push (int val) {
stack.push(val);
if (val < minStack.peek()) {
minStack.push(val);
} else {
minStack.push(minStack.peek());
}
}
public void pop () {
stack.pop();
minStack.pop();
}
public int top () {
return stack.peek();
}
public int getMin () {
return minStack.peek();
}
}
字符串解码 class Solution {
public String decodeString (String s) {
Stack<Integer> num = new Stack <>();
Stack<String> value = new Stack <>();
StringBuilder sb = new StringBuilder ();
int i = 0 ;
while (i < s.length()) {
char a = s.charAt(i);
if (a == '[' ) {
value.push(sb.toString());
sb.setLength(0 );
i++;
} else if (Character.isDigit(a)) {
int x = a - '0' ;
i++;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
x = x * 10 + (s.charAt(i) - '0' );
i++;
}
num.push(x);
} else if (a == ']' ) {
int x = num.isEmpty() ? 1 : num.pop();
String res = sb.toString();
sb.setLength(0 );
for (int j = 0 ; j < x; j++) {
sb.append(res);
}
if (!value.isEmpty()) {
sb.insert(0 , value.pop());
}
i++;
} else {
sb.append(a);
i++;
}
}
return sb.toString();
}
}
每日温度 class Solution {
public int [] dailyTemperatures(int [] temperatures) {
Deque<Integer> xu = new LinkedList <>();
int n = temperatures.length;
int [] res = new int [n];
for (int i = 0 ; i < n; i++) {
while (!xu.isEmpty() && temperatures[i] > temperatures[xu.peek()]) {
int num = xu.pop();
res[num] = i - num;
}
xu.push(i);
}
return res;
}
}
柱状图中的最大的矩形 class Solution {
public int largestRectangleArea (int [] heights) {
int [] left = new int [heights.length];
int [] right = new int [heights.length];
Deque<Integer> stack = new LinkedList <>();
for (int i = 0 ; i < left.length; i++) {
left[i] = -1 ;
right[i] = heights.length;
}
for (int i = 0 ; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
right[stack.peek()] = i;
stack.pop();
}
if (!stack.isEmpty()) {
left[i] = stack.peek();
}
stack.push(i);
}
int max = 0 ;
for (int i = 0 ; i < heights.length; i++) {
max = Math.max(max, (right[i] - left[i] - 1 ) * heights[i]);
}
return max;
}
}
堆
数组中的第 K 个最大元素 class Solution {
public int findKthLargest (int [] _nums, int k) {
int n = _nums.length;
return quickselect(_nums, 0 , n - 1 , n - k);
}
int quickselect (int [] nums, int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1 , j = r + 1 ;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if (k <= j) return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1 , r, k);
}
}
前 K 个高频元素 class Solution {
public int [] topKFrequent(int [] nums, int k) {
Map<Integer, Integer> map = new HashMap <>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0 ) + 1 );
}
PriorityQueue<int []> queue = new PriorityQueue <int []>(new Comparator <int []>() {
public int compare (int [] m, int [] n) {
return m[1 ] - n[1 ];
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1 ] < count) {
queue.poll();
queue.offer(new int []{num, count});
}
} else {
queue.offer(new int []{num, count});
}
}
int [] ret = new int [k];
for (int i = 0 ; i < k; ++i) {
ret[i] = queue.poll()[0 ];
}
return ret;
}
}
数据流的中位数 class MedianFinder {
PriorityQueue<Integer> queMin;
PriorityQueue<Integer> queMax;
public MedianFinder () {
queMin = new PriorityQueue <Integer>((a, b) -> (b - a));
queMax = new PriorityQueue <Integer>((a, b) -> (a - b));
}
public void addNum (int num) {
if (queMin.isEmpty() || num <= queMin.peek()) {
queMin.offer(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.offer(queMin.poll());
}
} else {
queMax.offer(num);
if (queMax.size() > queMin.size()) {
queMin.offer(queMax.poll());
}
}
}
public double findMedian () {
if (queMin.size() > queMax.size()) {
return queMin.peek();
}
return (queMin.peek() + queMax.peek()) / 2.0 ;
}
}
贪心算法
买卖股票的最佳时机 class Solution {
public int maxProfit (int [] prices) {
int max = 0 , min = prices[prices.length - 1 ];
for (int i = prices.length - 2 ; i >= 0 ; i--) {
if (prices[i] > min) {
min = prices[i];
} else {
if (max < min - prices[i]) {
max = min - prices[i];
}
}
}
return max;
}
}
跳跃游戏 class Solution {
public boolean canJump (int [] nums) {
int end = nums.length - 1 ;
for (int i = nums.length - 2 ; i >= 0 ; i--) {
if (i + nums[i] >= end) {
end = i;
}
}
if (end == 0 ) {
return true ;
} else {
return false ;
}
}
}
跳跃游戏 II class Solution {
public int jump (int [] nums) {
int max = 0 , min = 0 , maxs = 0 ;
for (int i = 0 ; i < nums.length - 1 ; i++) {
int x = nums[i] + i;
if (x > max) {
max = x;
}
if (maxs == i) {
maxs = max;
min++;
}
}
return min;
}
}
划分字母区间 class Solution {
public List<Integer> partitionLabels (String s) {
int [] map = new int [26 ];
for (int i = 0 ; i < s.length(); i++) {
map[s.charAt(i) - 'a' ]++;
}
List<Integer> res = new ArrayList <>();
int [] find = new int [26 ];
int sum = 0 ;
int total = 0 ;
StringBuffer sb = new StringBuffer ();
for (int i = 0 ; i < s.length(); i++) {
char a = s.charAt(i);
sb.append(a);
if (find[a - 'a' ] == 0 ) {
sum++;
}
find[a - 'a' ]++;
if (find[a - 'a' ] == map[a - 'a' ]) {
total++;
}
if (total == sum) {
res.add(sb.length());
total = 0 ;
sum = 0 ;
sb.setLength(0 );
}
}
return res;
}
}
动态规划
走楼梯 class Solution {
public int climbStairs (int n) {
int [] dp = new int [1001 ];
return find(dp, n);
}
public int find (int [] dp, int n) {
if (n == 1 ) {
return 1 ;
}
if (n == 0 ) {
return 1 ;
}
if (dp[n] != 0 ) {
return dp[n];
}
dp[n] = find(dp, n - 1 ) + find(dp, n - 2 );
return dp[n];
}
}
杨辉三角 class Solution {
public List<List<Integer>> generate (int numRows) {
List<List<Integer>> res = new ArrayList <>();
for (int i = 0 ; i < numRows; i++) {
List<Integer> tes = new ArrayList <Integer>();
tes.add(1 );
res.add(tes);
}
for (int i = 1 ; i < numRows; i++) {
for (int j = 1 ; j <= i; j++) {
if (j == i) {
res.get(i).add(1 );
} else {
int a = res.get(i - 1 ).get(j - 1 );
int b = res.get(i - 1 ).get(j);
res.get(i).add(a + b);
}
}
}
return res;
}
}
打家劫舍 class Solution {
public int rob (int [] nums) {
if (nums.length == 0 ) {
return 0 ;
}
if (nums.length == 1 ) {
return nums[0 ];
}
if (nums.length == 2 ) {
return Math.max(nums[0 ], nums[1 ]);
}
int [] dp = new int [nums.length];
dp[0 ] = nums[0 ];
dp[1 ] = Math.max(nums[0 ], nums[1 ]);
for (int i = 2 ; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2 ] + nums[i], dp[i - 1 ]);
}
return dp[nums.length - 1 ];
}
}
完全平方数 class Solution {
public int numSquares (int n) {
int [] dp = new int [n + 1 ];
for (int i = 0 ; i <= n; i++) {
dp[i] = i;
for (int j = 0 ; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1 );
}
}
return dp[n];
}
}
零钱兑换 class Solution {
public int coinChange (int [] coins, int amount) {
int [] f = new int [amount + 1 ];
Arrays.fill(f, Integer.MAX_VALUE / 2 );
f[0 ] = 0 ;
for (int i = 0 ; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
f[j] = Math.min(f[j], f[j - coins[i]] + 1 );
}
}
return f[amount] < Integer.MAX_VALUE / 2 ? f[amount] : -1 ;
}
}
单词拆分 class Solution {
public boolean wordBreak (String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet (wordDict);
boolean [] dp = new boolean [s.length() + 1 ];
dp[0 ] = true ;
for (int i = 1 ; i <= s.length(); i++) {
for (int j = 0 ; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true ;
break ;
}
}
}
return dp[s.length()];
}
}
最长递增子序列 class Solution {
public int lengthOfLIS (int [] nums) {
int [] res = new int [nums.length];
res[nums.length - 1 ] = 1 ;
int max = 1 ;
for (int i = nums.length - 2 ; i >= 0 ; i--) {
for (int j = i + 1 ; j < nums.length; j++) {
if (nums[j] > nums[i]) {
if (res[i] < res[j] + 1 ) {
res[i] = res[j] + 1 ;
}
}
}
if (res[i] == 0 ) {
res[i] = 1 ;
}
if (res[i] > max) {
max = res[i];
}
}
return max;
}
}
乘积最大子数组 class Solution {
public int maxProduct (int [] nums) {
if (nums.length == 0 ) {
return 0 ;
}
int [] max = new int [nums.length];
int [] min = new int [nums.length];
for (int i = 0 ; i < nums.length; i++) {
max[i] = nums[i];
min[i] = nums[i];
}
for (int i = 1 ; i < nums.length; i++) {
max[i] = Math.max(max[i - 1 ] * nums[i], Math.max(nums[i], min[i - 1 ] * nums[i]));
min[i] = Math.min(min[i - 1 ] * nums[i], Math.min(nums[i], max[i - 1 ] * nums[i]));
}
int ans = max[0 ];
for (int i = 1 ; i < nums.length; ++i) {
ans = Math.max(ans, max[i]);
}
return ans;
}
}
分割等和子集 class Solution {
public boolean canPartition (int [] nums) {
int sum = 0 ;
int n = nums.length;
for (int num : nums) {
sum = sum + num;
}
if (sum % 2 == 1 ) {
return false ;
}
int target = sum / 2 ;
int [] dp = new int [target + 1 ];
for (int i = 0 ; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target;
}
}
最长有效括号 class Solution {
public int longestValidParentheses (String s) {
int left = 0 , right = 0 , maxlength = 0 ;
for (int i = 0 ; i < s.length(); i++) {
if (s.charAt(i) == '(' ) {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0 ;
}
}
left = right = 0 ;
for (int i = s.length() - 1 ; i >= 0 ; i--) {
if (s.charAt(i) == '(' ) {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0 ;
}
}
return maxlength;
}
}
多维动态规划
不同路径 class Solution {
public int uniquePaths (int m, int n) {
int [] f = new int [n];
for (int i = 0 ; i < n; ++i) {
f[i] = 1 ;
}
for (int i = 1 ; i < m; i++) {
for (int j = 1 ; j < n; j++) {
f[j] += f[j - 1 ];
}
}
return f[n - 1 ];
}
}
最小路径和 class Solution {
public int minPathSum (int [][] grid) {
int m = grid.length;
int n = grid[0 ].length;
if (m == 1 && n == 1 ) {
return grid[0 ][0 ];
}
if (n > 1 ) {
for (int i = 1 ; i < n; i++) {
grid[0 ][i] += grid[0 ][i - 1 ];
}
}
if (m > 1 ) {
for (int i = 1 ; i < m; i++) {
grid[i][0 ] += grid[i - 1 ][0 ];
}
}
for (int i = 1 ; i < m; i++) {
for (int j = 1 ; j < n; j++) {
grid[i][j] = Math.min(grid[i][j] + grid[i - 1 ][j], grid[i][j - 1 ] + grid[i][j]);
}
}
return grid[m - 1 ][n - 1 ];
}
}
最长回文子串 class Solution {
public String longestPalindrome (String s) {
int max = 1 ;
int beg = 0 ;
int left, right;
int n = s.length();
for (int i = 0 ; i < n; i++) {
left = i - 1 ;
right = i + 1 ;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
if (max < right - left + 1 ) {
max = right - left + 1 ;
beg = left;
}
left--;
right++;
}
left = i;
right = i + 1 ;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
if (max < right - left + 1 ) {
max = right - left + 1 ;
beg = left;
}
left--;
right++;
}
}
return s.substring(beg, beg + max);
}
}
最长公共子序列 class Solution {
public int longestCommonSubsequence (String text1, String text2) {
char [] t = text2.toCharArray();
int m = t.length;
int [] f = new int [m + 1 ];
for (char x : text1.toCharArray()) {
int pre = 0 ;
for (int j = 0 ; j < m; j++) {
int tmp = f[j + 1 ];
if (x == t[j]) {
f[j + 1 ] = pre + 1 ;
} else {
f[j + 1 ] = Math.max(f[j + 1 ], f[j]);
}
pre = tmp;
}
}
return f[m];
}
}
编辑距离 class Solution {
public int minDistance (String word1, String word2) {
int n = word1.length();
int m = word2.length();
int [][] dp = new int [n + 1 ][m + 1 ];
for (int i = 0 ; i <= m; i++) {
dp[0 ][i] = i;
}
for (int j = 0 ; j <= n; j++) {
dp[j][0 ] = j;
}
for (int i = 1 ; i < n + 1 ; i++) {
for (int j = 1 ; j < m + 1 ; j++) {
if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) {
dp[i][j] = Math.min(dp[i - 1 ][j] + 1 , dp[i][j - 1 ] + 1 );
if (dp[i - 1 ][j - 1 ] < dp[i][j]) {
dp[i][j] = dp[i - 1 ][j - 1 ];
}
} else {
dp[i][j] = Math.min(dp[i - 1 ][j] + 1 , dp[i][j - 1 ] + 1 );
if (dp[i - 1 ][j - 1 ] + 1 < dp[i][j]) {
dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ;
}
}
}
}
return dp[n][m];
}
}
技巧
只出现一次的数字 解法 ：两两异或，相同的会变成 0，剩下的就是出现一次的。
class Solution {
public int singleNumber (int [] nums) {
int x = nums[0 ];
if (nums.length == 0 ) {
return x;
}
for (int i = 1 ; i < nums.length; i++) {
x = x ^ nums[i];
}
return x;
}
}
多数元素 class Solution {
public int majorityElement (int [] nums) {
int ms = nums[0 ];
int count = 1 ;
for (int i = 1 ; i < nums.length; i++) {
if (nums[i] == ms) {
count++;
} else {
count--;
if (count == 0 ) {
ms = nums[i];
count = 1 ;
}
}
}
return ms;
}
}
颜色分类 class Solution {
public void sortColors (int [] nums) {
int len = nums.length;
if (len < 2 ) {
return ;
}
int beg = 0 ;
int end = len - 1 ;
int i = 0 ;
while (i <= end) {
if (nums[i] == 0 ) {
swap(nums, beg, i);
beg++;
i++;
} else if (nums[i] == 1 ) {
i++;
} else {
swap(nums, i, end);
end--;
}
}
}
public void swap (int [] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
下一个排列 class Solution {
public void nextPermutation (int [] nums) {
int len = nums.length;
for (int i = len - 1 ; i >= 1 ; i--) {
if (nums[i - 1 ] < nums[i]) {
reverse(nums, i, len - 1 );
for (int j = i; j < len; j++) {
if (nums[j] > nums[i - 1 ]) {
swap(nums, j, i - 1 );
break ;
}
}
break ;
}
if (i == 1 ) {
reverse(nums, 0 , len - 1 );
}
}
}
public void swap (int [] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public void reverse (int [] nums, int left, int right) {
while (left < right) {
swap(nums, left++, right--);
}
}
}
寻找重复数 解法 ：快慢指针的做法，根据条件，元素的大小是不超过数组的长度的，那么也就会，出现重复数意味着出现环，那么就是采取回环链表的做法。
class Solution {
public int findDuplicate (int [] nums) {
int slow = 0 ;
int fast = 0 ;
while (true ) {
slow = nums[slow];
fast = nums[nums[fast]];
if (fast == slow) {
break ;
}
}
fast = 0 ;
while (true ) {
slow = nums[slow];
fast = nums[fast];
if (slow == fast) {
return slow;
}
}
}
}
相关免费在线工具 Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
