Javajava算法
LeetCode Hot 100 算法题解（Java 版）
LeetCode Hot 100 高频算法题的 Java 解法，涵盖哈希、双指针、滑动窗口、动态规划、树、图论等核心知识点。包含题目思路分析与完整代码实现，旨在帮助开发者系统复习数据结构与算法，提升编码能力。
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[] str1 = strs[i].toCharArray();
Arrays.sort(str1);
s = String.valueOf(str1);
if (res.containsKey(s)) {
List<String> tes = res.get(s);
tes.add(strs[i]);
res.put(s, tes);
} else {
List<String> tes = new ArrayList<>();
tes.add(strs[i]);
res.put(s, tes);
}
}
return new ArrayList<>(res.values());
}
}
思路： 首先采取 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;
}
}
思路： 对于每个前缀和 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;
}
}
}
}
思路： 根据样例而言，我们将行和列连起来看，即第一行 + 最后一列，按照右上角的元素来看，比这个元素大的就在列上，小的就在行上，基于这个发现，引申出来的做法：初始化为整个二维数组最右上角的元素。如果 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;
}
}
思路：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;
}
}
解法
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;
}
}
思路：类似于上题的思路。
解法
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;
}
}
思路：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;
}
}
思路：直接使用 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;
}
}
解法
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);
}
}
思路：
解法
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;
}
}
思路：前缀和。使用 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;
}
}
解法
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;
}
}
解法
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);
}
}
解法
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;
}
}
}
解法
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;
}
}
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online