LeetCode Hot 100 Guide#
LeetCode Hot 100 指路：https://leetcode.cn/studyplan/top-100-liked/
This is actually my second time going through it; if I don't practice, I might get rusty. =)
Hashing#
Arrays, HashSet, HashMap.
1. Two Sum#
To return the array indices, we need to keep track of both the numbers and their indices using a HashMap.
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
49. Group Anagrams#
Use a HashMap, where the key is the word sorted in alphabetical order, and the value is a list containing all anagrams of that word.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for(String str:strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
128. Longest Consecutive Sequence#
The key is to find the starting point of the consecutive sequence.
class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
int count = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
for(int num : set) {
if(!set.contains(num-1)) { // start point
count = 0;
while(set.contains(num)) {
num++;
count++;
}
max = max < count ? count : max;
}
}
return max;
}
}
Two Pointers#
There are mainly two types of two pointers: inward pointers and fast-slow pointers.
Reference: Two Pointers Technique to Solve Array Problems
283. Move Zeroes#
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for(;slow<nums.length;slow++) { // fill 0
nums[slow] = 0;
}
}
}
11. Container With Most Water#
Reference: Extended Discussion
Inward pointers approach, moving from both sides towards the center, bringing the shorter side closer to the center while keeping track of the maximum value.
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int v = Math.min(height[left], height[right]) * (right - left);
if (v > max) {
max = v;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
15. 3Sum#
Reference: A Method to Solve nSum Problems
Exhaustive search; first determine the first number, which reduces it to a two-sum problem.
The array must be sorted when using two pointers.
The key to this problem is to avoid duplicates.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Must sort first to ensure accurate traversal
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0)
break;
if (i >= 1 && nums[i - 1] == nums[i])
continue; // Deduplicate the first number nums[i]
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[left]);
ans.add(nums[right]);
result.add(ans);
while (right > left && nums[right] == nums[right - 1])
right--; // Deduplicate nums[right]
while (right > left && nums[left] == nums[left + 1])
left++; // Deduplicate nums[left]
left++;
right--; // To find all possible combinations, cannot break
} else if (sum > 0)
right--;
else if (sum < 0)
left++;
}
}
return result;
}
}
42. Trapping Rain Water#
Reference: How to Efficiently Solve the Trapping Rain Water Problem
The local idea is that the amount of water that can be held at a position is determined by the minimum height of the tallest pillars on the left and right sides. The brute force algorithm is to traverse all positions' left and right pillars, and the optimization point is to calculate and record once, so that we do not have to calculate each position repeatedly.
class Solution {
public int trap(int[] height) {
int[] lmax = new int[height.length]; // The height of the tallest pillar on the left for each position
int[] rmax = new int[height.length]; // The height of the tallest pillar on the right for each position
lmax[0] = height[0];
rmax[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++) {
lmax[i] = Math.max(lmax[i-1], height[i]);
}
for(int i=height.length-2;i>=0;i--) {
rmax[i] = Math.max(rmax[i+1], height[i]);
}
int result = 0;
for(int i=0;i<height.length;i++) {
result = result + Math.min(lmax[i], rmax[i]) - height[i];
}
return result;
}
}
The two-pointer solution does not use a memo, calculating while moving, saving space complexity. lmax is the maximum height from 0 to left, and rmax is the maximum height from right to the far right. If lmax is smaller, count it as the left position, and vice versa.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int lmax = 0, rmax = 0;
int result = 0;
while (left < right) {
lmax = Math.max(height[left], lmax);
rmax = Math.max(height[right], rmax);
if(lmax < rmax) {
result = result + lmax - height[left];
left++;
} else {
result = result + rmax - height[right];
right--;
}
}
return result;
}
}
Sliding Window#
Reference: I Wrote a Poem, Turning the Sliding Window Algorithm into a Dictation Question
The sliding window is essentially a technique for using fast and slow pointers. Pay attention to invariants; it is recommended that the window interval be left-closed and right-open.
3. Longest Substring Without Repeating Characters#
Reference: Four, Longest Substring Without Repeating Characters
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
char[] chars = s.toCharArray();
int left = 0, right = 0; // Left-closed, right-open
int max = 0;
while(right < chars.length) {
char c = chars[right];
while(window.contains(c)) { // Shrink the window
window.remove(chars[left]);
left++;
}
window.add(c); // Expand the window
right++;
max = max >= (right - left) ? max : (right - left);
}
return max;
}
}
438. Find All Anagrams in a String#
Reference: Three, Find All Anagrams
This problem has two key points: one is the condition for shrinking, and the other is how to determine if it is an anagram.
The shrinking condition can be maintained by a fixed-length window, which means when the length equals the length of p, shrink it, like a caterpillar crawling.
Determining an anagram is determined by two factors: the fixed-length window mentioned above and the count of elements with the same number. As long as the count of elements is the same, valid increases by 1. We don't have to worry about how to handle the case where the count of that letter exceeds the required number because the fixed-length window limits that if this letter exceeds, other letters won't meet the requirement of valid + 1, so it won't be an anagram. The decrease of valid is achieved during the window shrink.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>(); // <Character, Count>
HashMap<Character, Integer> window = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
List<Integer> res = new ArrayList<>();
int left = 0, right = 0; // Left-closed, right-open
int valid = 0;
char[] chars = s.toCharArray();
while (right < chars.length) {
char c = chars[right];
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
right++;
while ((right - left) >= p.length()) {
if (valid == need.size()) { // Check if it is an anagram before shrinking
res.add(left);
}
char d = chars[left];
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) { // Check before removing
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return res;
}
}
Note: In Java, when comparing the sizes of two Integer objects, using the == operator may lead to unexpected results because the == operator compares object references, not object values. To compare the values of two Integer objects, you should use the .equals() method or unbox them to the primitive type int.#
Substring#
560. Subarray Sum Equals K#
Prefix sum technique.
Reference: Small and Beautiful Algorithm Technique: Prefix Sum Array day4_prefixSum2
class Solution {
public int subarraySum(int[] nums, int k) {
/**
* By calculating the prefix sum, we transform the problem into finding the case where the difference between two prefix sums equals k.
* Suppose the prefix sum array is prefixSum, where prefixSum[i] represents the sum of elements from [0, i].
* For any two indices i and j (i < j), if prefixSum[j] - prefixSum[i] = k,
* then the sum of elements in the range [i+1, j] equals k.
* By traversing the array, we calculate the prefix sum at each position and use a hash table to store the count of each prefix sum.
* During the traversal, we check if there exists a prefix sum of prefixSum[j] - k (where the current cursor is j).
* If it exists, it indicates that the sum of the continuous subarray from some position to the current position equals k, and we accumulate the corresponding count into the result.
* Thus, by traversing the array once, we can count the number of continuous subarrays that sum to k, with a time complexity of O(n), where n is the length of the array.
*/
int count = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>(); // <Prefix Sum, Count>
map.put(0, 1); // Used to solve the case where the sum from index 0 to index i equals k, for unified processing
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
239. Sliding Window Maximum#
Monotonic queue.
Reference: Using Monotonic Queue Structure to Solve Sliding Window Problems
Maintain a monotonically decreasing queue; the element at the front of the queue is the maximum value in the window. Note that in the actual implementation, the queue should store indices to correctly remove elements that should be removed from the left side when the window shifts.
You can use a deque to simulate a monotonic queue, similar to a stack.
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>(); // Deque simulates a monotonic queue
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
}
res[0] = nums[queue.peekFirst()];
for (int i = k; i < nums.length; i++) {
if (i - k == queue.peekFirst()) {
queue.pollFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
76. Minimum Window Substring#
A typical sliding window problem, the idea is similar to 438. Find All Anagrams in a String.
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
for(char c:t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0)+1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0;
int start = 0, len = s.length()+1; // Used to extract the result
while (right<s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0)+1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid >= need.size()) {
char d = s.charAt(left);
if(right-left < len) { // Save once first
start = left;
len = right - left;
}
if(need.containsKey(d)) {
if(window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d)-1);
}
left++;
}
}
if(len == s.length()+1) {
return "";
}
return s.substring(start, start+len);
}
}
Regular Arrays#
53. Maximum Subarray#
Reference: 4. Maximum Subarray
Greedy idea, directly simulate, sum records whether the local sum is less than 0; if less than 0, discard it, res records the maximum value result.
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res = sum > res ? sum : res; // Take the maximum value of the interval (equivalent to constantly determining the maximum subarray termination position)
if (sum < 0) { // Equivalent to resetting the starting position of the maximum subarray, because encountering a negative number will definitely lower the total
sum = 0;
}
}
return res;
}
}
Another greedy implementation, essentially the same.
class Solution {
public int maxSubArray(int[] nums) {
int preSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++) {
if(preSum<=0) {
maxSum = Math.max(nums[i], maxSum);
preSum = nums[i];
} else {
maxSum = Math.max(nums[i] + preSum, maxSum);
preSum = nums[i]+preSum;
}
}
return maxSum;
}
}
Dynamic programming implementation:
class Solution {
public int maxSubArray(int[] nums) {
// dp[j] is the maximum sum of the continuous subarray ending with nums[j]
// dp[i] = Math.max(dp[i], dp[i-1]+nums[i])
int[] dp = new int[nums.length];
// Initial value dp[i] = nums[i]
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // Either continue or start from scratch
res = Math.max(res, dp[i]);
}
return res;
}
}
The prefix sum idea is also clever:
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int minPreSum = 0;
int preSum = 0;
for (int x : nums) {
preSum += x; // Current prefix sum
ans = Math.max(ans, preSum - minPreSum); // Subtract the minimum prefix sum
minPreSum = Math.min(minPreSum, preSum); // Maintain the minimum prefix sum
}
return ans;
}
}
56. Merge Intervals#
Reference: 20. Merge Intervals
Determine interval overlap, sort first and then process. This can be considered a form of greedy strategy.
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]); // Sort by left boundary
List<int[]> res = new ArrayList<>();
int start = intervals[0][0]; // Left boundary
int rightBound = intervals[0][1]; // Right boundary
for(int i = 1;i<intervals.length;i++) {
if(intervals[i][0]<=rightBound) { // Interval overlap
rightBound = Math.max(intervals[i][1], rightBound);
} else {
res.add(new int[]{start, rightBound}); // Non-overlapping interval
start = intervals[i][0];
rightBound = intervals[i][1];
}
}
res.add(new int[]{start, rightBound});
return res.toArray(new int[res.size()][]);
}
}
189. Rotate Array#
A pure technique question; the simplest way is to use an extra array to place the element at index i of the original array to the new array at index (i + k) mod n.
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
If you find the pattern, you can use three array reversals to achieve it:
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
238. Product of Array Except Self#
First calculate the prefix product array and the suffix product array, then traverse once to calculate the result, which is the prefix product times the suffix product.
Actually, the process of calculating the prefix and suffix arrays can also be seen as a very simple dynamic programming.
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
prefix[0] = 1;
suffix[nums.length - 1] = 1;
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
41. First Missing Positive#
Reference: First Missing Positive
The first thing to note is the pigeonhole principle. For an array of length N, the smallest positive integer that does not appear must be in the range [1, N+1].
If there are no extra time and space complexity requirements, it is easy to think of putting all the numbers into a hash table, and then enumerating positive integers starting from 1 to check if they are in the hash table, with a time complexity of O(N) and space complexity of O(N).
To reduce space complexity, we must use the given array to store some states and transform the given array into a hash table.
Traverse the array, and for each number x, if it is in the range [1, N], mark the position of the x−1 element in the array (note: array indices start from 0). After the traversal, if all positions are marked, the answer is N+1; otherwise, the answer is the smallest unmarked position plus 1.
class Solution {
public int firstMissingPositive(int[] nums) {
// First, exclude non-positive integers
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = Integer.MAX_VALUE;
}
}
// Traverse the array, marking the numbers in the range [1, n]
// Set nums[x-1] to negative
for (int i = 0; i < nums.length; i++) {
int num = Math.abs(nums[i]); // Take the absolute value to avoid skipping untraversed but marked negative numbers
if (num >= 1 && num <= nums.length) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// Last traversal, check the marks
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) { // Not marked
return i + 1;
}
}
return nums.length + 1;
}
}
Besides marking, we can also achieve it through swapping, making the x−1 element equal to x. Each mismatched position represents a missing positive integer.
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // Avoid infinite loop
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
Matrix#
73. Set Matrix Zeroes#
A space complexity of O(m+n) implementation, using two hash tables to store the row and column indices of the zero values, and then traversing to set them to zero.
class Solution {
public void setZeroes(int[][] matrix) {
HashSet<Integer> rows = new HashSet<>();
HashSet<Integer> columns = new HashSet<>();
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[0].length;j++) {
if(matrix[i][j]==0) {
rows.add(i);
columns.add(j);
}
}
}
for(int i : rows) {
for(int j=0;j<matrix[0].length;j++) {
matrix[i][j] = 0;
}
}
for(int j:columns) {
for(int i=0;i<matrix.length;i++) {
matrix[i][j] = 0;
}
}
}
}
54. Spiral Matrix#
Reference: Fancy Traversal Techniques for Two-Dimensional Arrays
The core idea of the solution is to traverse the array in the order of right, down, left, and up, using four variables to define the boundaries of the untraversed elements.
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new ArrayList<>();
while (res.size() < m * n) { // Traversal completed when equal
// Traverse the top from left to right, note that the interval is left-closed and right-closed
if (upper_bound <= lower_bound) { // Only traverse this row if this condition is met
for (int i = left_bound; i <= right_bound; i++) {
res.add(matrix[upper_bound][i]);
}
upper_bound++;
}
// Traverse the right side from top to bottom
if (left_bound <= right_bound) {
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
right_bound--;
}
// Traverse the bottom from right to left
if (upper_bound <= lower_bound) {
for (int i = right_bound; i >= left_bound; i--) {
res.add(matrix[lower_bound][i]);
}
lower_bound--;
}
// Traverse the left side from bottom to top
if (left_bound <= right_bound) {
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
48. Rotate Image#
Pure technique, use flipping instead of rotating; first flip the matrix along the diagonal, then flip each row.
class Solution {
public void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - j - 1];
matrix[i][matrix.length - j - 1] = tmp;
}
}
}
}
240. Search a 2D Matrix II#
Observe the matrix in the example; if you start searching from the top left corner, if the target value is greater than the number in the top left corner, the subsequent search direction has two options: left or down. The same applies when starting from the bottom right corner. However, searching from the other two corners is completely different.
Linear search, the official solution is called Z-shaped search:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
You can also use binary search on each row.
Linked List#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
160. Intersection of Two Linked Lists#
Reference: Whether Two Linked Lists Intersect
The key to solving this problem is to find a way for p1 and p2 to reach the intersection node simultaneously.
You can do this by pre-calculating the lengths of both linked lists to align the tails:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// First, find the lengths of both linked lists
int lenA = 0, lenB = 0;
ListNode node = headA;
while(node!=null) {
lenA++;
node=node.next;
}
node = headB;
while(node!=null) {
lenB++;
node = node.next;
}
// Let ListA be the shorter linked list
if(lenA>lenB) {
node = headA;
headA = headB;
headB = node;
int tmp = lenA;
lenA = lenB;
lenB = tmp;
}
// Fast and slow pointers start, fast pointer moves first
for(int i=0;i<lenB-lenA;i++) {
headB = headB.next;
}
while(headA!=null && headB!=null) {
if(headA==headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
A more clever way is to concatenate the lists, allowing p1 to traverse list A and then list B, and p2 to traverse list B and then list A. This way, both pointers will meet at the intersection point if there is one.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 points to the head node of list A, p2 points to the head node of list B
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 moves one step, if it reaches the end of list A, it goes to list B
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 moves one step, if it reaches the end of list B, it goes to list A
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
206. Reverse Linked List#
Using the two-pointer method:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while (cur!=null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
Head insertion method, higher space complexity:
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null)
return null;
ListNode resultList = new ListNode(head.val, null);
ListNode currentNode = head;
while(currentNode.next != null) {
currentNode = currentNode.next;
ListNode toAdd = new ListNode(currentNode.val, resultList);
resultList = toAdd;
}
return resultList;
}
}
Recursive method, reference: Recursive Magic: Reverse a Singly Linked List
class Solution {
// Definition: Input a singly linked list head node, reverse the linked list, and return the new head node
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) { // Base case for recursion
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
234. Palindrome Linked List#
Reference: How to Determine a Palindrome Linked List Palindrome Linked List
Method 1: Copy values into an array and use the two-pointer method. No technical content.
Method 2: Fast and slow pointers. Reverse the second half of the linked list (modify the linked list structure), then compare the first half and the second half. After comparison, we should restore the linked list.
Method 3: Use recursion to simulate two-pointer implementation of palindrome checking.
class Solution {
ListNode left; // Pointer moving from left to right
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) {
return true;
}
if (traverse(right.next)) {
if (left.val == right.val) {
left = left.next;
return true;
}
}
return false;
}
}
141. Linked List Cycle#
Reference: Determine Whether a Linked List Contains a Cycle
Fast and slow pointer technique, the slow pointer moves one step, the fast pointer moves two steps; if they meet, it indicates that there is a cycle.
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
Actually, I'm not very clear about the condition for judging the fast pointer that moves two steps; when to use (fast != null && fast.next != null) and when to use (fast.next != null && fast.next.next != null)?
142. Linked List Cycle II#
Reference: Determine Whether a Linked List Contains a Cycle 8. Linked List Cycle II
This is also a fast and slow pointer, but this time we need to return the entry point of the cycle. Simply return the slow pointer to the head, and then both slow and fast pointers start at the same pace; the position where they meet is the entrance of the cycle.
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
21. Merge Two Sorted Lists#
Reference: Merge Two Sorted Lists
This problem is simple; iteratively perform tail insertion, and note that using a dummy head node will be more convenient.
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next; // p keeps moving forward
}
if (list1 == null) {
p.next = list2;
}
if (list2 == null) {
p.next = list1;
}
return dummy.next;
}
}
2. Add Two Numbers#
This problem feels similar to merging sorted lists; there’s not much to say, just remember to add an extra node when there’s still a carry.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
p.next = node;
p = p.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry != 0) {
p.next = new ListNode(carry);
}
return dummy.next;
}
}
19. Remove Nth Node From End of List#
Reference: The k-th Node from the End of a Singly Linked List
At a glance, the fast-slow pointer method is consistent with the fast-slow pointer solutions for intersection and palindrome linked lists.
The basic approach is for the fast pointer to move a few steps first, and then the fast and slow pointers move together, so that the distance between the two pointers is fixed, making it easy to find a specific position.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
Note that the use of a dummy head node is to prevent null pointer exceptions.
24. Swap Nodes in Pairs#
Reference: 5. Swap Nodes in Pairs
The idea of this problem is very similar to reversing a linked list, using a double pointer. Also, be sure to get used to using a dummy head node.
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1, head);
ListNode cur = dummyHead;
// Only swap if there are two nodes
while (cur.next != null && cur.next.next != null) {
ListNode tmp = cur.next;
cur.next = cur.next.next;
ListNode tmp1 = cur.next.next;
cur.next.next = tmp;
tmp.next = tmp1;
cur = cur.next.next;
}
return dummyHead.next;
}
}
You can also use recursion to implement it, which is easy to understand:
class Solution {
public ListNode swapPairs(ListNode head) {
// Base case: insufficient two nodes
if (head == null || head.next == null) {
return head;
}
ListNode next1 = head.next;
ListNode next2 = swapPairs(head.next.next); // Recursion
head.next = next2;
next1.next = head;
return next1;
}
}
25. Reverse Nodes in k-Group#
Reference: How to Reverse a Linked List in k Groups
This problem should be linked to 206. Reverse Linked List, using iterative implementation to reverse part of the linked list and then concatenate the lists. Using a recursive idea to solve this problem is much more elegant than iterative (which is just a while loop).
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return head; // Base case: total nodes < k
}
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k); // a is the tail node after the interval [a, b] is reversed
return newHead;
}
// Reverse the elements in the interval [a, b), note that it is left-closed and right-open
ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
138. Copy List with Random Pointer#
Reference: Copy a Linked List with Random Pointers
The first solution is backtracking + hash table, using a hash table to record the creation status of each node. During the traversal of the linked list, check the creation status of the "successor node of the current node" and the "node pointed to by the random pointer of the current node." If either of these two nodes has not been created, we immediately create it recursively. When the copy is complete and we backtrack to the current layer, we can complete the pointer assignment for the current node. Note that a node may be pointed to by multiple other nodes, so it may recursively attempt to copy a certain node multiple times. To prevent duplicate copying, we need to check whether the current node has been copied first; if it has been copied, we can directly retrieve the pointer to the copied node from the hash table and return it.
class Solution {
HashMap<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.containsKey(head)) {
return map.get(head);
}
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
return newHead;
}
}
Actually, the above lengthy explanation is overly complicated; you can directly traverse the linked list once, put the nodes and their corresponding new nodes into the hash table, and then traverse the linked list again to assign the next and random pointers of each new node, which can be directly retrieved from the hash table.
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur=head;
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}
Another solution is iterative + node splitting, which I call the interleaved insertion method. It requires three traversals: the first traversal creates new nodes and inserts them into the original nodes; the second traversal copies the random pointers; the third traversal separates the new linked list from the original linked list.
148. Sort List#
Insertion sort (147. Insertion Sort List):
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1, head); // Convenient for inserting nodes before head
ListNode last = head; // Maintain the last node of the sorted part
ListNode cur = head.next; // Node to be inserted
while (cur != null) {
if (cur.val >= last.val) {
last = cur;
} else {
ListNode ptr = dummy;
while (ptr != last) {
if (cur.val <= ptr.next.val) {
last.next = cur.next;
cur.next = ptr.next;
ptr.next = cur;
break;
} else {
ptr = ptr.next;
}
}
}
cur = last.next;
}
return dummy.next;
}
}
Top-down merge sort:
The first step is to find the midpoint to split the linked list using the fast-slow pointer technique; the second step is to sort the two sub-linked lists recursively; the third step is to merge the sorted linked lists using the method of 21. Merge Two Sorted Lists.
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) { // Base case
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null; // Find the midpoint and split the linked list
ListNode left = sortList(head);
ListNode right = sortList(rightHead); // Recursively sort
return merge(left, right);
}
ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
if (a == null) {
cur.next = b;
} else {
cur.next = a;
}
return dummy.next;
}
}
The space complexity of top-down merge sort is O(logn), while using the bottom-up merge sort method can achieve O(1) space complexity. But actually, there is no need for that.
23. Merge K Sorted Lists#
Reference: Merge k Sorted Lists
Similar to 21. Merge Two Sorted Lists, the key is how to quickly find the smallest value among K nodes, which can be optimized using a priority queue.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) { // Add the head nodes of k linked lists to the min heap
if (head != null) {
pq.add(head);
}
}
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
p.next = node;
p = node;
if (node.next != null) {
pq.add(node.next);
}
}
return dummy.next;
}
}
146. LRU Cache#
Reference: Algorithms are Like Building Lego: Hand-Crafting the LRU Algorithm
Hash table mapping + doubly linked list = Hash linked list LinkedHashMap
class LRUCache {
HashMap<Integer, Node> map = new HashMap<>();
DoubleLinkedList linkedlist = new DoubleLinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
linkedlist.remove(node); // Move the accessed node to the end of the list
linkedlist.addLast(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
linkedlist.remove(node); // Move the updated node to the end of the list
node.value = value; // Update value
linkedlist.addLast(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
linkedlist.addLast(node);
if (linkedlist.size() > capacity) {
Node removed = linkedlist.removeFirst();
map.remove(removed.key);
}
}
}
}
class Node {
int key, value;
Node next, prev;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoubleLinkedList {
Node head, tail; // Dummy head and tail nodes
int size;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
this.size = 0;
}
public Node addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
return node;
}
public Node removeFirst() {
if (size == 0) {
return null;
}
Node node = head.next;
remove(node);
return node;
}
public void remove(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
size--;
}
public int size() {
return this.size;
}
}
You can also use Java's built-in type LinkedHashMap to implement the LRU algorithm.
Binary Tree#
Reference: Dong Ge Takes You to Brush Binary Trees (Outline) 1. Binary Tree Theoretical Basics
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
94. Binary Tree Inorder Traversal#
Recursive inorder traversal:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traverse(root, res);
return res;
}
void traverse(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
traverse(root.left, res);
res.add(root.val);
traverse(root.right, res);
}
}
104. Maximum Depth of Binary Tree#
The recursive idea is to decompose the problem; the maximum depth of a binary tree is the maximum depth of its left and right subtrees plus one.
The maximum depth is usually defined as the longest path from a node to a leaf node, while depth usually refers to the path length from the root node to a specific node (sometimes the number of nodes rather than path length).
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
226. Invert Binary Tree#
Post-order traversal, recursively invert the left and right subtrees.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.right = left;
root.left = right;
return root;
}
}
101. Symmetric Tree#
Two trees are mirrors of each other if the following conditions are met: 1. The values of the root nodes are equal; 2. The left subtree of each tree is a mirror of the right subtree of the other tree.
The previous approach recursively compares the "left subtree's left subtree" with the "right subtree's right subtree," and the "left subtree's right subtree" with the "right subtree's left subtree."
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return false;
return compare(root.left,root.right);
}
boolean compare(TreeNode left, TreeNode right) {
if(left==null && right!=null) return false;
else if(left!=null && right==null) return false;
else if(left==null && right ==null) return true;
else if(left!=null && right!=null && left.val!=right.val) return false;
else {
if(compare(left.left,right.right)&&compare(left.right,right.left))
return true;
else return false;
}
}
}
A more elegant approach is to move two pointers simultaneously to traverse, which is essentially the same.
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) { // Only one is null
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
543. Diameter of Binary Tree#
For each node of the tree, the maximum diameter is the sum of the "height of the left subtree" and the "height of the right subtree," using post-order recursive traversal.
The height usually refers to the longest path from a node to a leaf node, while depth usually refers to the path length from the root node to a specific node.
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxHeight(root);
return maxDiameter;
}
int maxHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
// Update the maximum diameter
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// Return the maximum height of the current node
return Math.max(leftHeight, rightHeight) + 1;
}
}
102. Binary Tree Level Order Traversal#
Level order traversal is essentially a breadth-first traversal in graph theory, requiring the use of an auxiliary data structure (queue) to implement.
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
// While loop, traversing each level of the tree from top to bottom
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
// For loop, traversing each node in this level from left to right
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
list.add(node.val);
}
res.add(list);
}
return res;
}
}
108. Convert Sorted Array to Binary Search Tree#
Reference: 32. Convert Sorted Array to Binary Search Tree
Constructing a binary tree from an array essentially involves finding the partition point, which serves as the current node, and then recursively handling the left and right intervals. The midpoint of the sorted array serves as the node of the binary search tree.
Constructing the binary tree uses pre-order traversal.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return traverse(nums, 0, nums.length);
}
// [begin, end) left-closed and right-open
TreeNode traverse(int[] nums, int begin, int end) {
if (begin >= end) {
return null;
}
int mid = begin + (end - begin) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = traverse(nums, begin, mid);
root.right = traverse(nums, mid + 1, end);
return root;
}
}
98. Validate Binary Search Tree#
Reference: 23. Validate Binary Search Tree
A more intuitive method is to perform an in-order traversal and place the values into an array to check if the array is sorted. You can also directly check if it is sorted during the in-order traversal.
This problem is easy to make mistakes; the common mistake is to simply compare the left node being less than the middle node and the right node being greater than the middle node, but you must compare all nodes in the left subtree being less than the middle node and all nodes in the right subtree being greater than the middle node. This requires using a global variable to store the current maximum value to compare whether the traversed node is sorted.
class Solution {
TreeNode max;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (max != null && max.val >= root.val) {
return false;
}
max = root;
return isValidBST(root.right);
}
}
230. Kth Smallest Element in a BST#
In-order traversal, counting:
class Solution {
int count = 0;
int result = -1;
public int kthSmallest(TreeNode root, int k) {
inorderTravel(root, k);
return result;
}
void inorderTravel(TreeNode root, int k) {
if (root == null)
return;
inorderTravel(root.left, k);
count++;
if (count == k) {
result = root.val;
return;
}
inorderTravel(root.right, k);
}
}
If you need to frequently find the k-th smallest value, you can record the number of nodes in each subtree:
class Solution {
// Store the number of nodes in the subtree rooted at each node
HashMap<TreeNode, Integer> map = new HashMap<>();
public int kthSmallest(TreeNode root, int k) {
count(root);
while (root != null) {
int left = map.getOrDefault(root.left, 0);
if (left > k - 1) {
root = root.left;
} else if (left < k - 1) {
root = root.right;
k = k - (left + 1);
} else {
break;
}
}
return root.val;
}
// Post-order recursive traversal to count the number of nodes in the subtree rooted at root
int count(TreeNode root) {
if (root == null) {
return 0;
}
int left = count(root.left);
int right = count(root.right);
map.put(root, left + right + 1);
return left + right + 1;
}
}
199. Binary Tree Right Side View#
Level order traversal, only taking the rightmost element of each level:
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) {
res.add(node.val);
}
}
}
return res;
}
}
114. Flatten Binary Tree to Linked List#
Reference: Detailed and Simple Idea Analysis, Multiple Solutions
This is a modified post-order traversal (first visit the right subtree), using a global variable pre to record the last traversed node, connecting from the end of the linked list. The use of pre is similar to that in 98. Validate Binary Search Tree.
class Solution {
TreeNode pre = null; // The pointer to the last traversed node
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
return;
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal#
Reference: 18. Construct Binary Tree from Inorder and Postorder Traversal
The first element of the pre-order traversal sequence is the root node, which is the partition point. Based on this element's position in the in-order traversal sequence, we can split it into the left and right in-order traversal sequences, and then split the pre-order traversal sequence into the left and right sub-sequences based on the sizes of the left and right in-order sub-sequences. This way, we can recursively construct the binary tree.
Constructing the binary tree uses pre-order traversal.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return construct(preorder, 0, preorder.length,
inorder, 0, inorder.length);
}
// [begin, end) left-closed and right-open
TreeNode construct(int[] preorder, int begin_pre, int end_pre,
int[] inorder, int begin_in, int end_in) {
if (begin_pre >= end_pre || begin_in >= end_in) {
return null;
}
int root_val = preorder[begin_pre];
int splitIndex = begin_in;
for (; splitIndex < end_in; splitIndex++) {
if (inorder[splitIndex] == root_val) {
break;
}
}
TreeNode root = new TreeNode(root_val);
root.left = construct(preorder, begin_pre + 1, begin_pre + 1 + splitIndex - begin_in,
inorder, begin_in, splitIndex);
root.right = construct(preorder, begin_pre + 1 + splitIndex - begin_in, end_pre,
inorder, splitIndex + 1, end_in);
return root;
}
}
437. Path Sum III#
Reference: 17. Path Sum Path Sum III
Depth-first search, recursively traverse all possible paths:
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = rootSum(root, targetSum);
count += pathSum(root.left, targetSum);
count += pathSum(root.right, targetSum);
return count;
}
// The number of paths starting from the root node
int rootSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = 0;
if (root.val == targetSum) {
count++;
}
count += rootSum(root.left, targetSum - root.val);
count += rootSum(root.right, targetSum - root.val);
return count;
}
}
The depth-first search solution