01.AcWing算法基础课
a.课程特点
a.系统完整
覆盖所有基础算法和数据结构。
b.由浅入深
从简单到复杂，循序渐进。
c.配套练习
每个知识点都有对应的练习题。
b.课程内容
基础算法、数据结构、搜索与图论、数学知识、动态规划。
02.基础算法模板
a.快速排序模板
---
void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
---
b.归并排序模板
---
void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
int[] temp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (i = l, k = 0; i <= r; i++, k++) {
arr[i] = temp[k];
}
}
---
c.二分查找模板
---
// 查找左边界
int binarySearchLeft(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
// 查找右边界
int binarySearchRight(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid] <= target) l = mid;
else r = mid - 1;
}
return l;
}
---
03.刷题顺序
a.基础算法
先学习排序、二分、双指针、前缀和等基础算法。
b.数据结构
掌握链表、栈队列、并查集、堆、哈希表等数据结构。
c.搜索与图论
学习DFS、BFS、最短路、最小生成树等算法。
d.动态规划
从背包问题开始，逐步掌握各种DP类型。
04.学习资源
a.AcWing官网
提供完整的算法课程和题库。
b.LeetCode
大量的算法题目，适合刷题练习。
c.算法书籍
算法导论、算法第四版、算法竞赛入门经典等。
01.快速排序原理
a.分治思想
选择基准元素，将数组分为小于基准和大于基准两部分，递归排序。
b.时间复杂度
平均O(n log n)，最坏O(n²)。
c.空间复杂度
O(log n)递归栈空间。
02.AcWing快排模板
a.Java实现
---
public void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
---
b.Go实现
---
func quickSort(arr []int, l, r int) {
if l >= r {
return
}
i, j, x := l-1, r+1, arr[(l+r)>>1]
for i < j {
for {
i++
if arr[i] >= x {
break
}
}
for {
j--
if arr[j] <= x {
break
}
}
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
quickSort(arr, l, j)
quickSort(arr, j+1, r)
}
---
03.快排优化
a.三数取中
选择左、中、右三个元素的中位数作为基准，避免最坏情况。
b.小数组优化
当子数组长度小于阈值时，使用插入排序。
c.三路快排
将数组分为小于、等于、大于基准三部分，处理重复元素更高效。
04.AcWing 785快速排序
a.题目
给定n个整数，请用快速排序算法将其从小到大排序。
b.输入格式
第一行包含整数n，第二行包含n个整数。
c.输出格式
输出排序后的数组。
2.3 归并排序
01.归并排序原理
a.分治思想
将数组分成两半，递归排序，然后合并两个有序数组。
b.时间复杂度
O(n log n)，稳定的时间复杂度。
c.空间复杂度
O(n)，需要额外数组存储临时结果。
02.AcWing归并模板
a.Java实现
---
public void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
int[] temp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (i = l, k = 0; i <= r; i++, k++) {
arr[i] = temp[k];
}
}
---
b.Go实现
---
func mergeSort(arr []int, l, r int) {
if l >= r {
return
}
mid := (l + r) >> 1
mergeSort(arr, l, mid)
mergeSort(arr, mid+1, r)
temp := make([]int, r-l+1)
i, j, k := l, mid+1, 0
for i <= mid && j <= r {
if arr[i] <= arr[j] {
temp[k] = arr[i]
i++
} else {
temp[k] = arr[j]
j++
}
k++
}
for i <= mid {
temp[k] = arr[i]
i++
k++
}
for j <= r {
temp[k] = arr[j]
j++
k++
}
for i, k = l, 0; i <= r; i, k = i+1, k+1 {
arr[i] = temp[k]
}
}
---
03.逆序对问题
a.问题描述
AcWing 788逆序对的数量 - 统计数组中逆序对的个数。
b.归并排序解法
---
long count = 0;
public long mergeSort(int[] arr, int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
long res = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r);
int[] temp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
res += mid - i + 1; // 统计逆序对
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (i = l, k = 0; i <= r; i++, k++) {
arr[i] = temp[k];
}
return res;
}
---
2.4 堆排序
01.堆排序原理
a.基本思想
利用堆这种数据结构进行排序，先建立最大堆，然后依次取出堆顶元素。
b.时间复杂度
O(n log n)，稳定的时间复杂度。
c.空间复杂度
O(1)，原地排序。
02.堆的基本操作
a.下沉操作
---
void siftDown(int[] arr, int i, int n) {
while (2 * i + 1 < n) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest == i) break;
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest;
}
}
---
03.堆排序实现
a.Java实现
---
public void heapSort(int[] arr) {
int n = arr.length;
// 建堆：从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
// 排序：依次取出堆顶元素
for (int i = n - 1; i > 0; i--) {
// 交换堆顶和末尾元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 对剩余元素进行下沉
siftDown(arr, 0, i);
}
}
---
b.Go实现
---
func heapSort(arr []int) {
n := len(arr)
// 建堆
for i := n/2 - 1; i >= 0; i-- {
siftDown(arr, i, n)
}
// 排序
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
siftDown(arr, 0, i)
}
}
func siftDown(arr []int, i, n int) {
for 2*i+1 < n {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < n && arr[left] > arr[largest] {
largest = left
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest == i {
break
}
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
}
}
---
04.AcWing 838堆排序
a.题目
给定n个整数，使用堆排序将其从小到大排序。
b.注意事项
建堆的时间复杂度是O(n)，不是O(n log n)。
2.5 二分查找
01.二分查找原理
a.基本思想
在有序数组中，每次比较中间元素，缩小一半搜索范围。
b.时间复杂度
O(log n)，每次减半。
c.应用场景
有序数组查找、二分答案、最优化问题。
02.整数二分模板
a.查找左边界
---
// 查找>=target的最小索引
public int binarySearchLeft(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
---
b.查找右边界
---
// 查找<=target的最大索引
public int binarySearchRight(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (arr[mid] <= target) l = mid;
else r = mid - 1;
}
return l;
}
---
03.浮点数二分
a.模板
---
public double binarySearchFloat(double l, double r) {
double eps = 1e-8;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
---
b.AcWing 790数的三次方根
---
public double cubicRoot(double n) {
double l = -10000, r = 10000;
while (r - l > 1e-8) {
double mid = (l + r) / 2;
if (mid * mid * mid >= n) r = mid;
else l = mid;
}
return l;
}
---
04.二分答案
a.思想
将最优化问题转化为判定问题，二分答案范围。
b.模板
---
public int binaryAnswer() {
int l = 0, r = Integer.MAX_VALUE;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
---
2.6 离散化
01.离散化概述
a.定义
将无限空间中的有限个体映射到有限空间中，保持元素间的大小关系。
b.应用场景
数据范围很大但数据个数较少，如坐标压缩。
c.核心思想
用排名代替原始值。
02.离散化步骤
a.去重排序
将所有需要离散化的值去重并排序。
b.二分查找
对每个原始值，二分查找其在排序后数组中的位置。
03.离散化实现
a.Java实现
---
public int[] discretize(int[] arr) {
// 去重排序
Set<Integer> set = new TreeSet<>();
for (int num : arr) {
set.add(num);
}
List<Integer> sorted = new ArrayList<>(set);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < sorted.size(); i++) {
map.put(sorted.get(i), i + 1);
}
// 映射
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = map.get(arr[i]);
}
return result;
}
---
b.AcWing模板
---
List<Integer> alls = new ArrayList<>(); // 存储所有待离散化的值
// 去重
Collections.sort(alls);
int unique = 1;
for (int i = 1; i < alls.size(); i++) {
if (!alls.get(i).equals(alls.get(i-1))) {
alls.set(unique++, alls.get(i));
}
}
// 二分查找离散化后的值
int find(int x) {
int l = 0, r = unique - 1;
while (l < r) {
int mid = l + r >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1; // 映射到1, 2, 3...
}
---
04.AcWing 802区间和
a.题目
在数轴上进行区间加法和区间求和操作，坐标范围很大。
b.离散化解法
将所有出现的坐标离散化，然后使用前缀和处理。
2.7 经典题目
01.排序相关
a.数组中的第K个最大元素
LeetCode 215 - 使用快速选择算法，时间复杂度O(n)。
---
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private int quickSelect(int[] nums, int l, int r, int k) {
if (l == r) return nums[l];
int i = l - 1, j = r + 1, x = nums[l + r >> 1];
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
if (k <= j) return quickSelect(nums, l, j, k);
else return quickSelect(nums, j + 1, r, k);
}
---
b.合并两个有序数组
LeetCode 88 - 从后往前合并，避免覆盖。
02.二分查找相关
a.搜索旋转排序数组
LeetCode 33 - 先找到旋转点，再二分查找。
b.寻找峰值
LeetCode 162 - 二分查找局部最大值。
c.在排序数组中查找元素的第一个和最后一个位置
LeetCode 34 - 使用两次二分查找左右边界。
03.逆序对问题
a.AcWing 788逆序对的数量
使用归并排序统计逆序对。
b.剑指Offer 51数组中的逆序对
同样使用归并排序解决。
3 双指针与区间
3.1 双指针算法
01.双指针概述
a.基本思想
使用两个指针遍历数组，通过指针移动优化时间复杂度。
b.常见类型
对撞指针、快慢指针、滑动窗口。
c.时间复杂度
通常将O(n²)优化为O(n)。
02.对撞指针
a.两数之和
---
public int[] twoSum(int[] arr, int target) {
Arrays.sort(arr);
int l = 0, r = arr.length - 1;
while (l < r) {
int sum = arr[l] + arr[r];
if (sum == target) return new int[]{l, r};
else if (sum < target) l++;
else r--;
}
return new int[]{-1, -1};
}
---
b.三数之和
LeetCode 15 - 排序后固定一个数，双指针找另外两个数。
03.快慢指针
a.环形链表
---
public boolean hasCycle(ListNode head) {
if (head == null) return false;
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;
}
---
b.链表中点
快指针走两步，慢指针走一步，快指针到末尾时慢指针在中点。
04.AcWing 799最长连续不重复子序列
a.题目
给定整数序列，求最长的连续不重复子序列长度。
b.双指针解法
---
public int longestSubsequence(int[] arr) {
int n = arr.length;
int[] count = new int[100010];
int maxLen = 0;
for (int i = 0, j = 0; i < n; i++) {
count[arr[i]]++;
while (count[arr[i]] > 1) {
count[arr[j]]--;
j++;
}
maxLen = Math.max(maxLen, i - j + 1);
}
return maxLen;
}
---
3.2 滑动窗口
01.滑动窗口概述
a.基本思想
维护一个窗口，通过移动窗口的左右边界来解决问题。
b.适用场景
连续子数组、子串问题。
c.时间复杂度
通常是O(n)。
02.滑动窗口模板
a.固定窗口大小
---
public void fixedWindow(int[] arr, int k) {
for (int i = 0; i <= arr.length - k; i++) {
// 处理窗口[i, i+k-1]
}
}
---
b.可变窗口大小
---
public int variableWindow(int[] arr) {
int left = 0, result = 0;
for (int right = 0; right < arr.length; right++) {
// 扩大窗口
// add arr[right]
while (/* 窗口不满足条件 */) {
// 缩小窗口
// remove arr[left]
left++;
}
// 更新结果
result = Math.max(result, right - left + 1);
}
return result;
}
---
03.经典题目
a.最小覆盖子串
---
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
int start = 0, len = Integer.MAX_VALUE;
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()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
---
b.找到字符串中所有字母异位词
LeetCode 438 - 使用滑动窗口统计字符频率。
3.3 前缀和
01.前缀和概述
a.定义
前缀和数组s[i]表示原数组前i个元素的和。
b.作用
快速计算区间和，将O(n)优化为O(1)。
c.公式
s[i] = s[i-1] + arr[i]，区间[l,r]的和为s[r] - s[l-1]。
02.一维前缀和
a.AcWing 795前缀和
---
public class PrefixSum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n + 1];
int[] s = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
s[i] = s[i - 1] + arr[i];
}
while (m-- > 0) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(s[r] - s[l - 1]);
}
}
}
---
03.二维前缀和
a.定义
s[i][j]表示从(1,1)到(i,j)的子矩阵元素和。
b.公式
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr[i][j]
c.AcWing 796子矩阵的和
---
public int[][] buildPrefixSum(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
int[][] s = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1];
}
}
return s;
}
public int querySum(int[][] s, int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}
---
04.应用场景
a.区间和查询
多次查询数组区间和。
b.子数组和问题
LeetCode 560和为K的子数组 - 使用前缀和+哈希表。
c.二维矩阵问题
子矩阵和、最大子矩阵等问题。
3.4 差分数组
01.差分数组概述
a.定义
差分数组b[i] = a[i] - a[i-1]，是前缀和的逆运算。
b.作用
将区间修改操作的时间复杂度从O(n)优化到O(1)。
c.应用场景
频繁的区间加减操作。
02.一维差分
a.构造差分数组
---
public int[] buildDiff(int[] arr) {
int n = arr.length;
int[] diff = new int[n + 1];
for (int i = 0; i < n; i++) {
diff[i] = arr[i] - (i > 0 ? arr[i-1] : 0);
}
return diff;
}
---
b.区间修改
---
// 给区间[l, r]加上c
public void rangeAdd(int[] diff, int l, int r, int c) {
diff[l] += c;
diff[r + 1] -= c;
}
---
c.还原数组
---
public int[] restore(int[] diff) {
int n = diff.length;
int[] arr = new int[n];
arr[0] = diff[0];
for (int i = 1; i < n; i++) {
arr[i] = arr[i-1] + diff[i];
}
return arr;
}
---
03.二维差分
a.构造差分矩阵
---
public void insert(int[][] diff, int x1, int y1, int x2, int y2, int c) {
diff[x1][y1] += c;
diff[x2+1][y1] -= c;
diff[x1][y2+1] -= c;
diff[x2+1][y2+1] += c;
}
---
b.AcWing 798差分矩阵
给定矩阵，进行多次子矩阵加法操作，最后输出结果矩阵。
04.应用场景
a.航班预订统计
LeetCode 1109 - 使用差分数组处理区间加法。
b.拼车
LeetCode 1094 - 使用差分数组统计每个位置的乘客数。
3.5 区间合并
01.区间合并概述
a.问题描述
给定若干区间，合并所有重叠的区间。
b.基本思路
先按左端点排序，然后依次合并。
c.时间复杂度
O(n log n)，主要是排序的时间。
02.区间合并实现
a.Java实现
---
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
// 按左端点排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= current[1]) {
// 有重叠，合并
current[1] = Math.max(current[1], intervals[i][1]);
} else {
// 无重叠，加入结果
result.add(current);
current = intervals[i];
}
}
result.add(current);
return result.toArray(new int[result.size()][]);
}
---
b.Go实现
---
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
result := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := result[len(result)-1]
if intervals[i][0] <= last[1] {
last[1] = max(last[1], intervals[i][1])
} else {
result = append(result, intervals[i])
}
}
return result
}
---
03.AcWing 803区间合并
a.题目
给定n个区间，合并所有有交集的区间。
b.输入格式
第一行包含整数n，接下来n行每行包含两个整数l和r。
c.输出格式
输出合并后的区间数量。
04.相关题目
a.插入区间
LeetCode 57 - 在已排序的区间列表中插入新区间。
b.无重叠区间
LeetCode 435 - 计算需要移除多少个区间使得剩余区间不重叠。
3.6 位运算技巧
01.基本位运算
a.常用操作
a.与运算
x & 1判断奇偶，x & (x-1)去掉最低位的1。
b.或运算
x | (1 << k)将第k位设为1。
c.异或运算
x ^ x = 0，x ^ 0 = x，可用于交换变量。
d.左移右移
x << k相当于乘以2的k次方，x >> k相当于除以2的k次方。
02.常用技巧
a.判断第k位是否为1
---
boolean isBitSet(int x, int k) {
return (x & (1 << k)) != 0;
}
---
b.统计1的个数
---
int countOnes(int x) {
int count = 0;
while (x != 0) {
x &= (x - 1);
count++;
}
return count;
}
---
c.lowbit操作
---
int lowbit(int x) {
return x & -x; // 返回最低位的1
}
---
03.位运算应用
a.只出现一次的数字
---
// 其他数字都出现两次
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
---
b.2的幂
---
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
---
c.颠倒二进制位
---
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}
---
04.AcWing 801二进制中1的个数
a.题目
给定n个非负整数，统计每个数的二进制表示中1的个数。
b.lowbit解法
---
public int countOnes(int x) {
int count = 0;
while (x != 0) {
x -= x & -x;
count++;
}
return count;
}
---
3.7 经典题目
01.双指针题目
a.盛最多水的容器
LeetCode 11 - 双指针从两端向中间移动。
---
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
maxWater = Math.max(maxWater, h * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
---
b.删除有序数组中的重复项
LeetCode 26 - 快慢指针原地去重。
02.前缀和题目
a.和为K的子数组
LeetCode 560 - 前缀和+哈希表。
---
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
---
b.连续的子数组和
LeetCode 523 - 前缀和取模+哈希表。
03.区间问题
a.会议室II
LeetCode 253 - 计算最少需要多少个会议室。
b.用最少数量的箭引爆气球
LeetCode 452 - 区间贪心问题。
4 基础数据结构
4.1 链表与邻接表
01.单链表应用
a.AcWing 826单链表
使用数组模拟单链表，支持头插、删除、插入操作。
---
int N = 100010;
int[] e = new int[N]; // 节点值
int[] ne = new int[N]; // next指针
int head = -1, idx = 0;
// 头插
void addToHead(int x) {
e[idx] = x;
ne[idx] = head;
head = idx++;
}
// 在第k个插入的数后面插入x
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
// 删除第k个插入的数后面的数
void remove(int k) {
ne[k] = ne[ne[k]];
}
---
02.双链表应用
a.AcWing 827双链表
---
int N = 100010;
int[] e = new int[N];
int[] l = new int[N]; // 左指针
int[] r = new int[N]; // 右指针
int idx = 2;
void init() {
r[0] = 1;
l[1] = 0;
}
// 在第k个数右边插入x
void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx++;
}
// 删除第k个数
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
---
03.邻接表存储图
a.定义
邻接表是一种常用的图存储方式，每个节点维护一个链表存储所有邻接边。
b.实现
使用数组模拟链表，h[i]存储节点i的第一条边的索引。
4.2 栈与队列应用
01.单调栈应用
a.AcWing 830单调栈
给定序列，求每个数左边第一个比它小的数。
---
public int[] findLeftSmaller(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && stack.peek() >= arr[i]) {
stack.pop();
}
result[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(arr[i]);
}
return result;
}
---
02.单调队列应用
a.AcWing 154滑动窗口
给定数组和窗口大小k，求每个窗口的最小值和最大值。
---
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 移除窗口外的元素
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 维护单调递减队列
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
---
03.表达式求值
a.AcWing 3302表达式求值
使用两个栈，一个存数字，一个存运算符。
4.3 并查集
01.并查集概述
a.定义
并查集是一种树形数据结构，用于处理不相交集合的合并和查询问题。
b.核心操作
find查找根节点、union合并两个集合。
c.时间复杂度
路径压缩和按秩合并后，单次操作接近O(1)。
02.AcWing并查集模板
a.Java实现
---
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找根节点（路径压缩）
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个集合
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}
}
// 判断是否在同一集合
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
---
b.Go实现
---
type UnionFind struct {
parent []int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
return &UnionFind{parent}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
px, py := uf.Find(x), uf.Find(y)
if px != py {
uf.parent[px] = py
}
}
---
03.AcWing 836合并集合
a.题目
维护n个集合，支持合并和查询操作。
b.输入格式
第一行包含n和m，接下来m行每行包含一个操作。
c.操作类型
M a b表示合并a和b所在集合，Q a b查询a和b是否在同一集合。
04.应用场景
a.连通性问题
判断图中两点是否连通。
b.最小生成树
Kruskal算法使用并查集判断是否成环。
c.朋友圈问题
LeetCode 547朋友圈 - 统计连通分量个数。
4.4 堆的应用
01.Top K问题
a.第K大元素
使用最小堆维护K个最大元素。
---
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
---
b.前K个高频元素
LeetCode 347 - 使用哈希表统计频率，堆找Top K。
---
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> heap = new PriorityQueue<>(
(a, b) -> count.get(a) - count.get(b)
);
for (int num : count.keySet()) {
heap.offer(num);
if (heap.size() > k) {
heap.poll();
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = heap.poll();
}
return result;
}
---
02.合并K个有序链表
a.问题描述
LeetCode 23 - 合并k个升序链表。
b.堆解法
---
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
for (ListNode list : lists) {
if (list != null) {
heap.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) {
heap.offer(node.next);
}
}
return dummy.next;
}
---
03.数据流中的中位数
a.问题描述
LeetCode 295 - 动态维护数据流的中位数。
b.双堆解法
---
class MedianFinder {
PriorityQueue<Integer> maxHeap; // 存储较小的一半
PriorityQueue<Integer> minHeap; // 存储较大的一半
public MedianFinder() {
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
// 保持平衡
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
}
---
04.AcWing 838堆排序
a.题目
维护一个小根堆，支持插入、输出最小值、删除最小值操作。
b.手写堆实现
使用数组模拟堆，实现上浮下沉操作。
01.邻接矩阵
a.定义
使用二维数组存储图，g[i][j]表示i到j的边权。
b.优点
查询边是否存在O(1)，适合稠密图。
c.缺点
空间复杂度O(n²)，不适合稀疏图。
d.Java实现
---
int[][] g = new int[n][n];
// 添加边
g[u][v] = w;
// 无向图
g[u][v] = g[v][u] = w;
---
02.邻接表
a.定义
使用链表数组存储图，每个节点维护一个链表存储所有邻接边。
b.优点
空间复杂度O(n+m)，适合稀疏图。
c.缺点
查询边是否存在O(度数)。
d.Java实现
---
List<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
// 添加边
g[u].add(v);
// 带权图
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
List<Edge>[] g = new ArrayList[n];
---
03.AcWing链式前向星
a.定义
使用数组模拟链表，适合竞赛中快速建图。
b.Java实现
---
int N = 100010, M = 200010;
int[] h = new int[N]; // 头节点
int[] e = new int[M]; // 边的终点
int[] ne = new int[M]; // 下一条边
int[] w = new int[M]; // 边权
int idx = 0;
// 初始化
Arrays.fill(h, -1);
// 添加边
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
// 遍历节点u的所有邻接边
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
int weight = w[i];
// 处理边(u, v)
}
---
6.2 最短路算法
01.Dijkstra算法
a.适用场景
单源最短路，边权非负。
b.时间复杂度
朴素版O(n²)，堆优化版O(m log n)。
c.AcWing模板
---
int N = 510;
int[][] g = new int[N][N];
int[] dist = new int[N];
boolean[] visited = new boolean[N];
public int dijkstra(int n, int start) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = true;
for (int v = 1; v <= n; v++) {
if (g[u][v] != Integer.MAX_VALUE) {
dist[v] = Math.min(dist[v], dist[u] + g[u][v]);
}
}
}
return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
}
---
02.Bellman-Ford算法
a.适用场景
单源最短路，可以处理负权边，可以检测负环。
b.时间复杂度
O(nm)。
c.模板
---
class Edge {
int from, to, weight;
}
public int bellmanFord(int n, Edge[] edges, int start) {
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// 迭代n-1次
for (int i = 0; i < n - 1; i++) {
for (Edge e : edges) {
if (dist[e.from] != Integer.MAX_VALUE) {
dist[e.to] = Math.min(dist[e.to], dist[e.from] + e.weight);
}
}
}
return dist[n];
}
---
03.Floyd算法
a.适用场景
多源最短路，求任意两点间最短路。
b.时间复杂度
O(n³)。
c.模板
---
public void floyd(int[][] g, int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
---
04.SPFA算法
a.定义
Bellman-Ford的队列优化版本。
b.时间复杂度
平均O(m)，最坏O(nm)。
c.模板
---
public int spfa(int n, int start) {
int[] dist = new int[n + 1];
boolean[] inQueue = new boolean[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
inQueue[start] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (dist[v] > dist[u] + w[i]) {
dist[v] = dist[u] + w[i];
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
}
}
}
}
return dist[n];
}
---
6.3 最小生成树
01.最小生成树概述
a.定义
连接图中所有节点的边的集合，使得总权值最小。
b.性质
有n个节点的最小生成树有n-1条边。
c.算法
Prim算法、Kruskal算法。
02.Prim算法
a.基本思想
从一个节点开始，每次选择权值最小的边加入生成树。
b.Java实现
---
public int prim(int[][] graph, int n) {
boolean[] inMST = new boolean[n];
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
int totalCost = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!inMST[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
inMST[u] = true;
totalCost += dist[u];
for (int v = 0; v < n; v++) {
if (!inMST[v] && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
}
}
}
return totalCost;
}
---
03.Kruskal算法
a.基本思想
将所有边按权值排序，依次加入边，使用并查集判断是否成环。
b.Java实现
---
class Edge {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
}
public int kruskal(int n, Edge[] edges) {
Arrays.sort(edges, (a, b) -> a.weight - b.weight);
UnionFind uf = new UnionFind(n);
int totalCost = 0;
int edgeCount = 0;
for (Edge edge : edges) {
if (uf.find(edge.u) != uf.find(edge.v)) {
uf.union(edge.u, edge.v);
totalCost += edge.weight;
edgeCount++;
if (edgeCount == n - 1) break;
}
}
return totalCost;
}
---
6.4 二分图
01.二分图定义
a.基本概念
图的节点可以分为两个集合，所有边的两个端点分别属于不同集合。
b.判定方法
染色法、BFS染色。
c.性质
二分图不存在奇数环。
02.染色法判定二分图
a.基本思想
使用DFS或BFS给节点染色，相邻节点染不同颜色。
b.Java实现
---
int[] color;
List<Integer>[] graph;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
if (!dfs(i, 0, graph)) {
return false;
}
}
}
return true;
}
private boolean dfs(int u, int c, int[][] graph) {
color[u] = c;
for (int v : graph[u]) {
if (color[v] == -1) {
if (!dfs(v, 1 - c, graph)) {
return false;
}
} else if (color[v] == c) {
return false;
}
}
return true;
}
---
03.BFS染色
a.实现
---
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
color[i] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
queue.offer(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
}
return true;
}
---
6.5 染色法与匈牙利算法
01.二分图最大匹配
a.定义
在二分图中找到最多的边，使得没有两条边共享端点。
b.应用场景
任务分配、婚配问题。
02.匈牙利算法
a.基本思想
使用DFS为每个左侧节点寻找匹配，如果匹配失败则尝试为已匹配节点重新匹配。
b.Java实现
---
int[] match;
boolean[] visited;
List<Integer>[] graph;
public int maxMatching(int n, int m) {
match = new int[m];
Arrays.fill(match, -1);
int count = 0;
for (int i = 0; i < n; i++) {
visited = new boolean[m];
if (dfs(i)) {
count++;
}
}
return count;
}
private boolean dfs(int u) {
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}
---
03.AcWing 861二分图的最大匹配
a.题目
给定二分图，求最大匹配数。
b.匈牙利算法解决
时间复杂度O(nm)。
01.质数判定
a.试除法
---
public boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) return false;
}
return true;
}
---
b.埃氏筛法
---
public List<Integer> sieve(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
for (int j = i + i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return primes;
}
---
02.最大公约数
a.欧几里得算法
---
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
---
b.最小公倍数
---
public int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
---
03.快速幂
a.递归实现
---
public long quickPow(long a, long b, long mod) {
if (b == 0) return 1;
long half = quickPow(a, b / 2, mod);
long res = half * half % mod;
if (b % 2 == 1) res = res * a % mod;
return res;
}
---
b.迭代实现
---
public long quickPow(long a, long b, long mod) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
---
04.组合数
a.递推公式
C(n,m) = C(n-1,m-1) + C(n-1,m)
b.预处理
---
int N = 2010;
long[][] C = new long[N][N];
public void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) C[i][j] = 1;
else C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
}
---
7.2 质数与约数
01.质数判定
a.试除法
---
public boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) return false;
}
return true;
}
---
b.分解质因数
---
public List<int[]> primeFactors(int n) {
List<int[]> factors = new ArrayList<>();
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
int count = 0;
while (n % i == 0) {
n /= i;
count++;
}
factors.add(new int[]{i, count});
}
}
if (n > 1) factors.add(new int[]{n, 1});
return factors;
}
---
02.筛质数
a.埃氏筛
---
public List<Integer> sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
for (long j = (long)i * i; j <= n; j += i) {
isPrime[(int)j] = false;
}
}
}
return primes;
}
---
b.线性筛
---
public List<Integer> linearSieve(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.add(i);
for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
isPrime[i * primes.get(j)] = false;
if (i % primes.get(j) == 0) break;
}
}
return primes;
}
---
03.约数
a.求所有约数
---
public List<Integer> getDivisors(int n) {
List<Integer> divisors = new ArrayList<>();
for (int i = 1; i <= n / i; i++) {
if (n % i == 0) {
divisors.add(i);
if (i != n / i) divisors.add(n / i);
}
}
Collections.sort(divisors);
return divisors;
}
---
b.约数个数
若n = p1^c1 * p2^c2 * ... * pk^ck，则约数个数为(c1+1)*(c2+1)*...*(ck+1)。
7.3 快速幂
01.快速幂原理
a.基本思想
利用二进制表示，将幂运算的时间复杂度从O(n)降到O(log n)。
b.递推公式
a^n = (a^(n/2))^2，如果n是奇数则再乘以a。
02.快速幂实现
a.递归版本
---
public long quickPow(long a, long b, long mod) {
if (b == 0) return 1;
long half = quickPow(a, b / 2, mod);
long res = half * half % mod;
if (b % 2 == 1) res = res * a % mod;
return res;
}
---
b.迭代版本
---
public long quickPow(long a, long b, long mod) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
---
c.Go实现
---
func quickPow(a, b, mod int64) int64 {
res := int64(1)
for b > 0 {
if b&1 == 1 {
res = res * a % mod
}
a = a * a % mod
b >>= 1
}
return res
}
---
03.快速幂应用
a.求幂
LeetCode 50 - 实现pow(x, n)。
b.超级次方
LeetCode 372 - 计算a^b mod 1337，其中b是数组表示的大数。
c.模运算
AcWing 875快速幂求逆元 - 利用费马小定理求逆元。
7.4 组合计数
01.组合数计算
a.递推公式
C(n,m) = C(n-1,m-1) + C(n-1,m)
b.预处理
---
int N = 2010;
long[][] C = new long[N][N];
public void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) C[i][j] = 1;
else C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
}
---
c.公式法
C(n,m) = n! / (m! * (n-m)!)
02.Lucas定理
a.定理
C(n,m) mod p = C(n/p, m/p) * C(n%p, m%p) mod p，其中p是质数。
b.实现
---
public long lucas(long n, long m, long p) {
if (m == 0) return 1;
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
private long C(long n, long m, long p) {
if (m > n) return 0;
long res = 1;
for (long i = 1, j = n; i <= m; i++, j--) {
res = res * j % p;
res = res * quickPow(i, p - 2, p) % p;
}
return res;
}
---
03.卡特兰数
a.定义
Cat(n) = C(2n, n) / (n + 1)
b.递推公式
Cat(n) = Cat(0)*Cat(n-1) + Cat(1)*Cat(n-2) + ... + Cat(n-1)*Cat(0)
c.应用
a.括号匹配
n对括号的合法组合数。
b.出栈序列
n个元素的出栈序列数。
c.二叉树
n个节点的二叉树数量。
7.5 贪心算法
01.贪心算法概述
a.基本思想
每一步都选择当前状态下的最优解，期望得到全局最优解。
b.适用条件
问题具有贪心选择性质和最优子结构性质。
c.证明方法
交换论证法、反证法、数学归纳法。
02.区间问题
a.区间选点
---
// 给定n个区间，选择最少的点使得每个区间至少包含一个点
public int intervalCover(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0, end = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] > end) {
count++;
end = interval[1];
}
}
return count;
}
---
b.最大不相交区间数
---
public int maxDisjointIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0, end = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] >= end) {
count++;
end = interval[1];
}
}
return count;
}
---
03.Huffman树
a.问题描述
给定n个权值，构造Huffman树使得带权路径长度最小。
b.贪心策略
每次选择两个最小的节点合并。
c.Java实现
---
public long huffman(int[] weights) {
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int w : weights) {
pq.offer((long) w);
}
long cost = 0;
while (pq.size() > 1) {
long a = pq.poll();
long b = pq.poll();
long sum = a + b;
cost += sum;
pq.offer(sum);
}
return cost;
}
---
04.排序不等式
a.问题
给定两个序列，如何配对使得乘积和最大或最小。
b.贪心策略
最大：同序配对，最小：逆序配对。
c.证明
交换论证法。
05.经典贪心题目
a.跳跃游戏
LeetCode 55 - 判断能否跳到最后一个位置。
b.分发饼干
LeetCode 455 - 用最少的饼干满足最多的孩子。
c.买卖股票的最佳时机
LeetCode 121 - 一次交易获得最大利润。
7.6 高精度运算
01.高精度加法
a.实现
---
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = n1 + n2 + carry;
sb.append(sum % 10);
carry = sum / 10;
i--;
j--;
}
return sb.reverse().toString();
}
---
02.高精度减法
a.实现
---
public String subtract(String num1, String num2) {
// 确保num1 >= num2
if (compare(num1, num2) < 0) {
return "-" + subtract(num2, num1);
}
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int borrow = 0;
while (i >= 0) {
int n1 = num1.charAt(i) - '0';
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int diff = n1 - n2 - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
sb.append(diff);
i--;
j--;
}
// 去除前导零
while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
sb.deleteCharAt(sb.length() - 1);
}
return sb.reverse().toString();
}
---
03.高精度乘法
a.大数乘小数
---
public String multiply(String num, int x) {
StringBuilder sb = new StringBuilder();
int carry = 0;
for (int i = num.length() - 1; i >= 0; i--) {
int digit = num.charAt(i) - '0';
int prod = digit * x + carry;
sb.append(prod % 10);
carry = prod / 10;
}
while (carry > 0) {
sb.append(carry % 10);
carry /= 10;
}
return sb.reverse().toString();
}
---
b.大数乘大数
LeetCode 43 - 字符串相乘。
04.高精度除法
a.大数除小数
---
public String divide(String num, int x) {
StringBuilder sb = new StringBuilder();
int remainder = 0;
for (int i = 0; i < num.length(); i++) {
int digit = num.charAt(i) - '0';
int current = remainder * 10 + digit;
sb.append(current / x);
remainder = current % x;
}
// 去除前导零
int start = 0;
while (start < sb.length() - 1 && sb.charAt(start) == '0') {
start++;
}
return sb.substring(start);
}
---
7.7 综合实战
01.数学综合题
a.丑数
LeetCode 264 - 只包含质因子2、3、5的数。
---
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int num2 = dp[p2] * 2;
int num3 = dp[p3] * 3;
int num5 = dp[p5] * 5;
dp[i] = Math.min(num2, Math.min(num3, num5));
if (dp[i] == num2) p2++;
if (dp[i] == num3) p3++;
if (dp[i] == num5) p5++;
}
return dp[n-1];
}
---
b.完全平方数
LeetCode 279 - 和为n的完全平方数的最少数量。
02.贪心综合题
a.跳跃游戏II
LeetCode 45 - 跳到最后一个位置的最小跳跃次数。
---
public int jump(int[] nums) {
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
---
b.加油站
LeetCode 134 - 环形路线中找到起始加油站。
03.AcWing综合题
a.AcWing 104货仓选址
在数轴上选择一个点，使得所有点到该点的距离之和最小。
b.AcWing 125耍杂技的牛
贪心排序问题，按w+s排序。
04.总结
a.数学问题
注重公式推导和数学性质的应用。
b.贪心问题
关键是找到贪心策略并证明其正确性。
c.综合运用
实际问题往往需要多种算法技巧的结合。