1.無重復(fù)字符的最長子串
??? #滑動(dòng)窗口 #雙指針
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> occ = new HashSet<>();
int maxLength = 0, rk = -1;
int n = s.length();
for (int i = 0; i < n; i++) {
if (i != 0) {
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
occ.add(s.charAt(rk + 1));
++rk;
}
maxLength = Math.max(maxLength, rk - i + 1);
}
return maxLength;
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Set<Character> container = new HashSet<Character>();
int n = s.length();
int maxLength = 0;
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && !container.contains(s.charAt(j))) {
container.add(s.charAt(j));
j++;
}
maxLength = Math.max(maxLength, j - i);
container.remove(s.charAt(i));
}
return maxLength;
}
}
2.LRU 緩存
??? #Java類庫
解法 1：復(fù)用 LinkedHashMap
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
解法 2：手寫雙端鏈表
class LRUCache {
private int size;
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode occNode = cache.get(key);
if (occNode == null) {
return -1;
}
moveToHead(occNode);
return occNode.value;
}
public void put(int key, int value) {
DLinkedNode occNode = cache.get(key);
if (occNode == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
++size;
if (size > capacity) {
DLinkedNode tail = removeTail();
cache.remove(tail.key);
--size;
}
} else {
occNode.value = value;
moveToHead(occNode);
}
}
class DLinkedNode {
private int key;
private int value;
private DLinkedNode pre;
private DLinkedNode next;
public DLinkedNode() {
}
public DLinkedNode(int _key, int _value) {
this.key = _key;
this.value = _value;
}
}
private void addToHead(DLinkedNode node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.pre;
removeNode(res);
return res;
}
}
3.反轉(zhuǎn)鏈表
??? #雙指針迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
}
4.反轉(zhuǎn)鏈表 II
??? #雙指針迭代
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode preLeft = dummy;
// 定位到 left 的前一個(gè)節(jié)點(diǎn)
for (int i = 1; i < left; i++) {
preLeft = preLeft.next;
}
ListNode curr = preLeft.next;
ListNode prev = null;
ListNode next = null;
ListNode tail = curr; // 記錄反轉(zhuǎn)后的尾節(jié)點(diǎn)
// 反轉(zhuǎn) left 到 right 的節(jié)點(diǎn)
for (int i = left; i <= right; i++) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 連接反轉(zhuǎn)后的子鏈表
preLeft.next = prev;
tail.next = curr;
return dummy.next;
}
}
5.數(shù)組中的第K個(gè)最大元素
解法 1：用 Java 類庫，Arrays.sort()
??? #Java類庫
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
解法 2：基于快速排序的選擇方法
??? #快速選擇排序
class Solution {
private int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) {
return nums[k];
}
int pivot = nums[left], i = left - 1, j = right + 1;
while (i < j) {
do
i++;
while (nums[i] < pivot);
do
j--;
while (nums[j] > pivot);
if (i < j) {
swap(nums, i, j);
}
}
if (k <= j)
return quickSelect(nums, left, j, k);
else
return quickSelect(nums, j + 1, right, k);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSelect(nums, 0, n - 1, n - k);
}
}
6.三數(shù)之和
??? #雙指針
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return Collections.emptyList();
}
// 先排序
Arrays.sort(nums);
List<List<Integer>> resultList = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
// 沒有符合條件的
if (nums[i] > 0) {
break;
}
// 排重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
resultList.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left = left + 1;
}
while (left < right && nums[right] == nums[right - 1]) {
right = right - 1;
}
left = left + 1;
right = right - 1;
} else if (sum > 0) {
right = right - 1;
} else {
left = left + 1;
}
}
}
return resultList;
}
}
7.最大子數(shù)組和
??? #動(dòng)態(tài)規(guī)劃
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int currentMax = nums[0];
for (int i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
max = Math.max(currentMax, max);
}
return max;
}
}
8.合并兩個(gè)有序鏈表
??? #雙指針
/**
* 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; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode preHead = new ListNode(-1);
ListNode pre = preHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = l1 == null ? l2 : l1;
return preHead.next;
}
}
9.最長回文子串
??? #中心擴(kuò)展算法
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 以i為中心的最長回文子串
int len1 = expandAroundCenter(s, i, i);
// 以i和i+1為中心的最長回文子串
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// 返回以left+1和right-1為中心的回文串的長度
return right - left - 1;
}
10.二叉樹的層序遍歷
??? #廣度優(yōu)先遍歷
/**
* 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;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList();
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
List<List<Integer>> result = new ArrayList();
while (!queue.isEmpty()) {
List<Integer> currentLevel = new ArrayList();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(currentLevel);
}
return result;
}
}
11.兩數(shù)之和
方案 1：暴力求解
??? #雙指針
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
int[] result = new int[2];
for (int i = 0; i < n; i++) {
int j = i + 1;
while (j < n) {
if (nums[j] == target - nums[i]) {
result[0] = i;
result[1] = j;
break;
} else {
j++;
}
}
}
return result;
}
}
方案 2：Map 緩存
??? #哈希表優(yōu)化法（空間換時(shí)間）
class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[] {};
}
Map<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hashMap.containsKey(target - nums[i])) {
return new int[] { hashMap.get(target - nums[i]), i };
}
hashMap.put(nums[i], i);
}
return new int[] {};
}
}
12.搜索旋轉(zhuǎn)排序數(shù)組
??? #二分查找
class Solution {
public int search(int[] nums, int target) {
if(nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int middle = left + (right - left) / 2;
if(target == nums[middle]) {
return middle;
}
if(nums[left] <= nums[middle]) {
if(target >= nums[left] && target < nums[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
} else {
if(target > nums[middle] && target <= nums[right]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
}
}
13.島嶼數(shù)量
??? #深度優(yōu)先遍歷
public class NumIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;
// 邊界檢查或者當(dāng)前位置已經(jīng)是水
if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] == '0') {
return;
}
// 將當(dāng)前陸地標(biāo)記為已訪問（變成水）
grid[i][j] = '0';
// 遞歸訪問上下左右四個(gè)方向
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
14.全排列
??? #回溯
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
boolean[] used = new boolean[nums.length];
backtrack(result, new ArrayList<>(), nums, used);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtrack(result, path, nums, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
15.買賣股票的最佳時(shí)機(jī)
??? #動(dòng)態(tài)規(guī)劃
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) {
return 0;
}
int minPrice = prices[0];
int maxProfit = 0;
for(int i = 1; i < prices.length; i++) {
if(prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
}
return maxProfit;
}
16.有效的括號
??? #棧 #線性遍歷
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
stack.push(s.charAt(i));
} else {
if (stack.isEmpty()) {
return false;
}
Character top = stack.pop();
if (s.charAt(i) == ')' && top != '(') {
return false;
}
if (s.charAt(i) == '}' && top != '{') {
return false;
}
if (s.charAt(i) == ']' && top != '[') {
return false;
}
}
}
return stack.isEmpty();
}
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {
{
put(')', '(');
put(']', '[');
put('}', '{');
}
};
Stack<Character> stack = new Stack();
for (int i = 0; i < n; i++) {
Character ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || pairs.get(ch) != stack.peek()) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
17.二叉樹的最近公共祖先
??? #遞歸分治 #后序遍歷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null) {
return right;
}
if(right == null) {
return left;
}
return root;
}
}
18.環(huán)形鏈表
??? #快慢指針 #雙指針
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null && slow != fast) {
slow = slow.next;
fast = fast.next.next;
}
return fast == slow;
}
}
19.合并 K 個(gè)升序鏈表
??? #分治法 #歸并排序
/**
* 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; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int middle = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, middle), merge(lists, middle + 1, r));
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
/**
* 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; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return mergeKLists(lists, 0, lists.length - 1);
}
private ListNode mergeKLists(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
int middle = l + (r - l) / 2;
ListNode left = mergeKLists(lists, l, middle);
ListNode right = mergeKLists(lists, middle + 1, r);
return mergeTwoList(left, right);
}
private ListNode mergeTwoList(ListNode left, ListNode right) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
pre.next = left;
left = left.next;
} else {
pre.next = right;
right = right.next;
}
pre = pre.next;
}
pre.next = left != null ? left : right;
return dummy.next;
}
}
20.最長遞增子序列
??? #動(dòng)態(tài)規(guī)劃
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxLength = 1;
for(int i=1; i<nums.length; i++) {
dp[i] = 1;
for(int j=0; j<i; j++) {
if(nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
maxLength = Math.max(dp[i], maxLength);
}
return maxLength;
}
}
21.相交鏈表
??? #雙指針 #數(shù)學(xué)路徑
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2) {
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
}
22.合并區(qū)間
??? #預(yù)排序 #貪心算法 #線性遍歷
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals;
}
// 按照區(qū)間起點(diǎn)進(jìn)行排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
int[] current = intervals[0];
merged.add(current);
for (int i = 1; i < intervals.length; i++) {
int[] interval = intervals[i];
// 當(dāng)前區(qū)間的起點(diǎn)小于等于上一個(gè)區(qū)間的終點(diǎn),說明重疊
if (interval[0] <= current[1]) {
// 更新當(dāng)前區(qū)間的終點(diǎn)
current[1] = Math.max(current[1], interval[1]);
} else {
// 不重疊,添加新區(qū)間
current = interval;
merged.add(current);
}
}
return merged.toArray(new int[merged.size()][]);
}
/**
* 向已排序的區(qū)間數(shù)組中插入新區(qū)間，并合并重疊的區(qū)間
*
* @param intervals 已排序的區(qū)間數(shù)組，每個(gè)區(qū)間包含起始和結(jié)束位置
* @param newInterval 需要插入的新區(qū)間
* @return 插入并合并后的區(qū)間數(shù)組
*/
public int[][] insert(int[][] intervals, int[] newInterval) {
// 用于存儲(chǔ)最終結(jié)果
List<int[]> result = new ArrayList<>();
int i = 0;
int n = intervals.length;
// 添加所有在新區(qū)間之前的區(qū)間（不重疊的部分）
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// 處理重疊區(qū)間：合并所有與新區(qū)間重疊的區(qū)間
while (i < n && intervals[i][0] <= newInterval[1]) {
// 更新新區(qū)間的起始位置為所有重疊區(qū)間中的最小起始位置
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
// 更新新區(qū)間的結(jié)束位置為所有重疊區(qū)間中的最大結(jié)束位置
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
// 添加合并后的新區(qū)間
result.add(newInterval);
// 添加所有在新區(qū)間之后的區(qū)間（不重疊的部分）
while (i < n) {
result.add(intervals[i]);
i++;
}
// 將List轉(zhuǎn)換為二維數(shù)組并返回
return result.toArray(new int[result.size()][]);
}
23.接雨水
??? #動(dòng)態(tài)規(guī)劃 #木桶效應(yīng)建模 #分步線性遍歷
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
// 計(jì)算每個(gè)位置左邊的最大高度
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// 計(jì)算每個(gè)位置右邊的最大高度
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// 計(jì)算每個(gè)位置能接的雨水量
int ans = 0;
for (int i = 0; i < n; i++) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
24.環(huán)形鏈表 II
??? #快慢指針 #路徑對齊定位入口
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
ListNode ptr = head;
while(ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
25.編輯距離
??? #動(dòng)態(tài)規(guī)劃
/**
* 計(jì)算兩個(gè)字符串之間的編輯距離(最少操作次數(shù))
* 可以對字符串進(jìn)行的操作包括:插入、刪除、替換
* 使用動(dòng)態(tài)規(guī)劃求解,dp[i][j]表示word1的前i個(gè)字符轉(zhuǎn)換到word2的前j個(gè)字符需要的最少操作數(shù)
*
* @param word1 源字符串
* @param word2 目標(biāo)字符串
* @return 最少操作次數(shù)
*/
public int minDistance(String word1, String word2) {
// 獲取兩個(gè)字符串的長度
int m = word1.length();
int n = word2.length();
// 創(chuàng)建dp數(shù)組,dp[i][j]表示word1前i個(gè)字符轉(zhuǎn)換到word2前j個(gè)字符需要的最少操作數(shù)
int[][] dp = new int[m + 1][n + 1];
// 初始化邊界條件:空串轉(zhuǎn)換到另一個(gè)字符串的操作數(shù)
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// 動(dòng)態(tài)規(guī)劃計(jì)算最少操作數(shù)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 當(dāng)前字符相同時(shí),不需要額外操作
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 當(dāng)前字符不同時(shí),取替換、刪除、插入三種操作的最小值
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[m][n];
}
26.二叉樹中的最大路徑和
??? #遞歸分治
/**
* 計(jì)算二叉樹中的最大路徑和
* 路徑被定義為從樹中的任意節(jié)點(diǎn)出發(fā)，沿著樹的邊走到任意節(jié)點(diǎn)的序列
* 路徑中至少包含一個(gè)節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)
*
* @param root 二叉樹的根節(jié)點(diǎn)
* @return 最大路徑和
*/
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
int[] maxSum = {Integer.MIN_VALUE};
maxGain(root, maxSum);
return maxSum[0];
}
/**
* 遞歸計(jì)算每個(gè)節(jié)點(diǎn)的最大貢獻(xiàn)值
* 節(jié)點(diǎn)的最大貢獻(xiàn)值定義為:以該節(jié)點(diǎn)為起點(diǎn)的一條路徑,所能提供的最大路徑和
*
* @param node 當(dāng)前節(jié)點(diǎn)
* @param maxSum 保存全局最大路徑和的數(shù)組
* @return 以當(dāng)前節(jié)點(diǎn)為起點(diǎn)的最大貢獻(xiàn)值
*/
private int maxGain(TreeNode node, int[] maxSum) {
if (node == null) {
return 0;
}
// 遞歸計(jì)算左右子節(jié)點(diǎn)的最大貢獻(xiàn)值,如果貢獻(xiàn)值為負(fù)則取0
int leftGain = Math.max(maxGain(node.left, maxSum), 0);
int rightGain = Math.max(maxGain(node.right, maxSum), 0);
// 當(dāng)前節(jié)點(diǎn)的最大路徑和 = 當(dāng)前節(jié)點(diǎn)值 + 左子樹貢獻(xiàn) + 右子樹貢獻(xiàn)
int priceNewPath = node.val + leftGain + rightGain;
maxSum[0] = Math.max(maxSum[0], priceNewPath);
// 返回節(jié)點(diǎn)的最大貢獻(xiàn)值,只能選擇左右子樹中的一條路徑
return node.val + Math.max(leftGain, rightGain);
}
27.刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
??? #快慢指針 #虛擬頭節(jié)點(diǎn)
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0, head);
ListNode fast = head;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
/**
* 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; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
ListNode node = reverse(head);
pre.next = node;
int index = 0;
while (pre != null) {
index++;
if (index == n) {
pre.next = pre.next.next;
break;
} else {
pre = pre.next;
}
}
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
}
28.尋找兩個(gè)正序數(shù)組的中位數(shù)
??? #雙指針
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
// 遍歷到中位數(shù)位置
for (int i = 0; i <= len/2; i++) {
left = right;
if (aStart < m && (bStart >= n || nums1[aStart] <= nums2[bStart])) {
right = nums1[aStart++];
} else {
right = nums2[bStart++];
}
}
// 如果總長度為奇數(shù)，返回right；如果為偶數(shù)，返回(left + right)/2
return len % 2 == 0 ? (left + right) / 2.0 : right;
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] nums = new int[m + n];
int i = 0;
int j = 0;
int index = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
nums[index++] = nums1[i++];
} else {
nums[index++] = nums2[j++];
}
}
while (i < m) {
nums[index++] = nums1[i++];
}
while (j < n) {
nums[index++] = nums2[j++];
}
if ((m + n) % 2 == 1) {
return nums[(m + n) / 2];
} else {
return (nums[(m + n) / 2] + nums[(m + n) / 2 - 1]) / 2.0;
}
}
}
29.二叉樹的中序遍歷
??? #中序遍歷 #遞歸 #深度優(yōu)先搜索
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
inorder(root, result);
return result;
}
private void inorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
inorder(root.left, result);
result.add(root.val);
inorder(root.right, result);
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
if (root.left != null) {
result.addAll(inorderTraversal(root.left));
}
result.add(root.val);
if (root.right != null) {
result.addAll(inorderTraversal(root.right));
}
return result;
}
}
30.排序鏈表
??? #快慢指針 #分治 #歸并 #虛擬頭節(jié)點(diǎn)
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 使用快慢指針找到中點(diǎn)
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 分割鏈表
ListNode mid = slow.next;
slow.next = null;
// 遞歸排序左右兩部分
ListNode left = sortList(head);
ListNode right = sortList(mid);
// 合并兩個(gè)有序鏈表
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
curr.next = left != null ? left : right;
return dummy.next;
}
31.下一個(gè)排列
??? #雙指針 #貪心算法
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 1) {
return;
}
int n = nums.length;
// 從右到左，找到第一個(gè)升序位置i
int i = n - 2;
while (i >= 0) {
if (nums[i] < nums[i + 1]) {
break;
}
i--;
}
// 從右到左，找到第一個(gè)比 nums[i]大的數(shù)字的位置 j；交換兩者的位置
if (i >= 0) {
int j = n - 1;
while (j > i) {
if (nums[j] > nums[i]) {
swap(nums, i, j);
break;
}
j--;
}
}
// 反轉(zhuǎn)i之后的數(shù)字
reverse(nums, i + 1);
}
private void reverse(int[] nums, int i) {
int left = i;
int right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
32.括號生成
??? #遞歸窮舉 #回溯
/**
* 生成所有可能的有效括號組合
* @param n 括號對數(shù)
* @return 所有有效的括號組合列表
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
/**
* 回溯法生成括號組合
* @param result 存儲(chǔ)所有有效括號組合的列表
* @param current 當(dāng)前生成的括號字符串
* @param open 已使用的左括號數(shù)量
* @param close 已使用的右括號數(shù)量
* @param max 括號對數(shù)的最大值
*/
private void backtrack(List<String> result, String current, int open, int close, int max) {
// 當(dāng)前字符串長度等于最大長度時(shí),將其添加到結(jié)果集
if (current.length() == max * 2) {
result.add(current);
return;
}
// 如果左括號數(shù)量小于最大值,可以添加左括號
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
// 如果右括號數(shù)量小于左括號數(shù)量,可以添加右括號
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}
33.兩數(shù)相加
??? #虛擬頭節(jié)點(diǎn) #進(jìn)位狀態(tài)管理 #迭代法
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
// 創(chuàng)建虛擬頭節(jié)點(diǎn)
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
// 用于存儲(chǔ)進(jìn)位
int carry = 0;
// 當(dāng)兩個(gè)鏈表都未遍歷完或還有進(jìn)位時(shí)繼續(xù)循環(huán)
while (head1 != null || head2 != null || carry != 0) {
// 初始化本位和為進(jìn)位值
int sum = carry;
// 如果第一個(gè)鏈表未遍歷完，加上其值并移動(dòng)指針
if (head1 != null) {
sum += head1.val;
head1 = head1.next;
}
// 如果第二個(gè)鏈表未遍歷完，加上其值并移動(dòng)指針
if (head2 != null) {
sum += head2.val;
head2 = head2.next;
}
// 計(jì)算進(jìn)位和本位數(shù)
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
}
return dummy.next;
}
public int[] maxSlidingWindow(int[] nums, int k) {
// 特判
if (nums == null || nums.length == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
// 雙端隊(duì)列存儲(chǔ)下標(biāo)
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 1. 移除超出窗口的元素
if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 2. 移除所有小于當(dāng)前元素的值
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// 3. 添加當(dāng)前元素
deque.offerLast(i);
// 4. 窗口形成后記錄結(jié)果
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
35.爬樓梯
??? #動(dòng)態(tài)規(guī)劃
public int climbStairs(int n) {
if (n < 1 || n > 45) {
throw new IllegalArgumentException("入?yún)⒉徽_");
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n - 1];
}
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
36.最長有效括號
??? #動(dòng)態(tài)規(guī)劃
public int longestValidParentheses(String s) {
int maxLen = 0;
// left統(tǒng)計(jì)左括號數(shù)量，right統(tǒng)計(jì)右括號數(shù)量
int left = 0, right = 0;
// 從左向右掃描
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
// 當(dāng)左右括號數(shù)量相等時(shí)，更新最大長度
if (left == right) {
maxLen = Math.max(maxLen, 2 * right);
}
// 當(dāng)右括號數(shù)量大于左括號時(shí)，重置計(jì)數(shù)器
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) {
maxLen = Math.max(maxLen, 2 * left);
}
// 當(dāng)左括號數(shù)量大于右括號時(shí)，重置計(jì)數(shù)器
if (left > right) {
left = right = 0;
}
}
return maxLen;
}
37.零錢兌換
??? #動(dòng)態(tài)規(guī)劃
/**
* 計(jì)算湊成目標(biāo)金額所需的最少硬幣數(shù)量
* 使用動(dòng)態(tài)規(guī)劃解決找零錢問題
*
* @param coins 可用的硬幣面值數(shù)組
* @param amount 目標(biāo)金額
* @return 所需的最少硬幣數(shù)量，如果無法湊出則返回-1
*/
public int coinChange(int[] coins, int amount) {
// 如果目標(biāo)金額為0，不需要硬幣
if (amount == 0) {
return 0;
}
// dp[i]表示湊成金額i所需的最少硬幣數(shù)
int[] dp = new int[amount + 1];
// 初始化dp數(shù)組，設(shè)置一個(gè)不可能達(dá)到的最大值
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
}
// 金額為0時(shí)不需要硬幣
dp[0] = 0;
// 計(jì)算每個(gè)金額所需的最少硬幣數(shù)
for (int i = 1; i <= amount; i++) {
// 嘗試每個(gè)硬幣面值
for (int coin : coins) {
// 當(dāng)前硬幣面值小于等于當(dāng)前計(jì)算的金額時(shí)
if (coin <= i) {
// 更新dp[i]，取當(dāng)前值和使用當(dāng)前硬幣后所需硬幣數(shù)+1的最小值
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果dp[amount]大于amount，說明無法湊出目標(biāo)金額
return dp[amount] > amount ? -1 : dp[amount];
}
38.從前序與中序遍歷序列構(gòu)造二叉樹
??? #分治 #遞歸 #全局索引
// 前序遍歷的索引
private int preorderIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
// 如果沒有節(jié)點(diǎn)要處理
if (left > right) {
return null;
}
// 創(chuàng)建當(dāng)前根節(jié)點(diǎn)
int rootValue = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootValue);
// 在中序遍歷中找到根節(jié)點(diǎn)的位置
int rootPosition = findIndex(inorder, rootValue, left, right);
// 先構(gòu)建左子樹，再構(gòu)建右子樹
root.left = buildTreeHelper(preorder, inorder, left, rootPosition - 1);
root.right = buildTreeHelper(preorder, inorder, rootPosition + 1, right);
return root;
}
private int findIndex(int[] inorder, int target, int left, int right) {
for (int i = left; i <= right; i++) {
if (inorder[i] == target) {
return i;
}
}
return -1;
}
39.最小棧
??? #鏈表模擬棧 #預(yù)存最小值 #動(dòng)態(tài)狀態(tài)傳遞
class MinStack {
Node head;
void push(int val) {
if (head == null) {
head = new Node(val, val);
} else {
Node newNode = new Node(val, Math.min(val, head.min));
newNode.next = head;
head = newNode;
}
}
void pop() {
if (head == null) {
return;
}
head = head.next;
}
int top() {
if (head == null) {
return -1;
}
return head.val;
}
int getMin() {
if (head == null) {
return -1;
}
return head.min;
}
class Node {
int val;
int min;
Node next;
public Node(int val, int min) {
this.val = val;
this.min = min;
this.next = null;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
40.子集
??? #迭代法
/**
* 生成給定數(shù)組的所有可能子集
* 使用迭代方法，對于數(shù)組中的每個(gè)數(shù)字，將其添加到已有的子集中形成新的子集
*
* @param nums 輸入的整數(shù)數(shù)組
* @return 返回包含所有可能子集的列表
*/
public List<List<Integer>> subsets(int[] nums) {
// 創(chuàng)建結(jié)果列表，用于存儲(chǔ)所有子集
List<List<Integer>> result = new ArrayList<>();
// 添加空集作為初始子集
result.add(new ArrayList<>());
// 遍歷輸入數(shù)組中的每個(gè)數(shù)字
for (int num : nums) {
// 獲取當(dāng)前結(jié)果集的大小
int size = result.size();
// 遍歷現(xiàn)有的所有子集
for (int i = 0; i < size; i++) {
// 復(fù)制現(xiàn)有子集并添加當(dāng)前數(shù)字，形成新的子集
List<Integer> subset = new ArrayList<>(result.get(i));
subset.add(num);
// 將新子集添加到結(jié)果集中
result.add(subset);
}
}
return result;
}
41.最小覆蓋子串
??? #滑動(dòng)窗口 #雙指針 #貪心策略 #右擴(kuò)窗口、左縮優(yōu)化、計(jì)數(shù)器同步
暫時(shí)未看懂
/**
* 在字符串s中尋找包含字符串t中所有字符的最小子串
* 使用滑動(dòng)窗口算法實(shí)現(xiàn)
*
* @param s 源字符串
* @param t 目標(biāo)字符串
* @return 包含t中所有字符的最小子串，如果不存在則返回空字符串
*/
public String minWindow(String s, String t) {
if (s == null || t == null || s.isEmpty() || t.isEmpty()) {
return "";
}
// 記錄所需字符的頻率
int[] freq = new int[128];
for (char c : t.toCharArray()) {
freq[c]++;
}
int start = 0, minLen = Integer.MAX_VALUE;
int left = 0, count = t.length();
// 滑動(dòng)窗口
for (int right = 0; right < s.length(); right++) {
// 更新窗口
if (freq[s.charAt(right)]-- > 0) {
count--;
}
// 找到可行解時(shí)收縮窗口
while (count == 0) {
// 更新最小子串
if (right - left + 1 < minLen) {
start = left;
minLen = right - left + 1;
}
// 收縮左邊界
if (++freq[s.charAt(left++)] > 0) {
count++;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
42.對稱二叉樹
??? #遞歸 #深度優(yōu)先遍歷 #雙指針
/**
* 判斷一棵二叉樹是否是對稱的
* 對稱二叉樹定義: 二叉樹的左右子樹鏡像對稱
*
* @param root 二叉樹的根節(jié)點(diǎn)
* @return 如果二叉樹是對稱的返回true，否則返回false
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
/**
* 遞歸檢查兩個(gè)子樹是否鏡像對稱
*
* @param left 左子樹節(jié)點(diǎn)
* @param right 右子樹節(jié)點(diǎn)
* @return 如果兩個(gè)子樹鏡像對稱返回true，否則返回false
*/
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
}
43.二叉樹的最大深度
??? #遞歸 #后序遍歷
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;
}
44.組合總和
??? #回溯選擇與撤銷 #剪枝減少無效計(jì)算 #順序約束去重
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 使用回溯算法解決組合總和問題
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
backtrack(candidates, target, 0, current, result);
return result;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
// 如果目標(biāo)值為0，說明當(dāng)前組合的和等于target，將其添加到結(jié)果中
if (target == 0) {
result.add(new ArrayList<>(current));
return;
}
// 如果目標(biāo)值小于0，說明當(dāng)前組合的和超過了target，直接返回
if (target < 0) {
return;
}
// 從start開始遍歷candidates數(shù)組，避免重復(fù)組合
for (int i = start; i < candidates.length; i++) {
// 將當(dāng)前數(shù)字添加到組合中
current.add(candidates[i]);
// 遞歸調(diào)用，注意這里的start仍然是i，因?yàn)榭梢灾貜?fù)使用同一個(gè)數(shù)字
backtrack(candidates, target - candidates[i], i, current, result);
// 回溯，移除最后添加的數(shù)字
current.remove(current.size() - 1);
}
}
45.最大正方形
??? #動(dòng)態(tài)規(guī)劃 #空間換時(shí)間優(yōu)化 #迭代法
/**
* 計(jì)算二維矩陣中最大正方形的面積
* 使用動(dòng)態(tài)規(guī)劃的方法，dp[i][j]表示以matrix[i-1][j-1]為右下角的最大正方形邊長
*
* @param matrix 輸入的二維字符矩陣,包含'0'和'1'
* @return 矩陣中由1組成的最大正方形面積
*/
public int maximalSquare(char[][] matrix) {
// 處理邊界情況
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
// 獲取矩陣的行數(shù)和列數(shù)
int rows = matrix.length;
int cols = matrix[0].length;
// dp數(shù)組用于存儲(chǔ)以當(dāng)前位置為右下角的最大正方形邊長
int[][] dp = new int[rows + 1][cols + 1];
// 記錄最大正方形邊長
int maxSide = 0;
// 遍歷矩陣中的每個(gè)元素
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
// 當(dāng)前位置為1時(shí)，計(jì)算最大正方形邊長
if (matrix[i - 1][j - 1] == '1') {
// 取左邊、上邊、左上角三個(gè)位置的最小值加1
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
// 更新最大邊長
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
// 返回最大正方形的面積
return maxSide * maxSide;
}
46.旋轉(zhuǎn)圖像
??? #數(shù)學(xué)幾何變換 #原地交換
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻轉(zhuǎn)
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主對角線翻轉(zhuǎn)
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
