例题
简单数组
1. TopK问题
描述 
思路
方法一：快速排序
- 正常划分，当pivot的索引刚好为数组长度n - k 时，即为所求
方法二：优先级队列
- 维护一个K大小的小根堆，不断插入堆中元素，插入原则为，当前元素大于堆顶元素，最后的堆顶元素即为第K大的数。
代码
Java快速排序：
class Solution {
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
public int randomPartition(int[] a, int l, int r) {
int i = random.nextInt(r - l + 1) + l;
swap(a, i, r);
return partition(a, l, r);
}
public int partition(int[] a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a, ++i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Python快速排序：
import random
class Solution:
def findKthLargest(self, nums, k):
def quickSelect(a, left, right, target):
pivotIndex = partition(a, left, right)
if pivotIndex == target:
return a[pivotIndex]
elif pivotIndex > target:
return quickSelect(a, left, pivotIndex - 1, target)
else:
return quickSelect(a, pivotIndex + 1, right, target)
def partition(a, left, right):
randomIdx = random.randint(left, right)
a[randomIdx], a[right] = a[right], a[randomIdx]
index = left
pivot = a[right]
for i in range(left, right):
if a[i] < pivot:
a[i], a[index] = a[index], a[i]
index += 1
a[index], a[right] = a[right], a[index]
return index
return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)
Java优先级队列：
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
q.offer(nums[i]);
}
for (int i = k; i < nums.length; i++) {
if (nums[i] > q.peek()) {
q.offer(nums[i]);
q.poll();
}
}
return q.peek();
}
}
Python优先级队列:
import random
class Solution:
def findKthLargest(self, nums, k):
q = []
heapq.heapify(q)
for i in range(k):
heapq.heappush(q, nums[i])
for i in range(k, len(nums)):
if nums[i] > q[0]:
heapq.heappush(q, nums[i])
heapq.heappop(q)
return q[0]
2. 逆序对
描述 
思路
- 暴力法
- 归并排序
- 树状数组
代码
Python归并排序1：
class Solution:
def __init__(self):
self.cnt = 0
def reversePairs(self, nums):
def merge(nums, start, mid, end, temp):
i = start
j = mid + 1
while i <= mid and j <= end:
if nums[i] <= nums[j]:
temp.append(nums[i])
i += 1
else:
self.cnt += mid - i + 1
temp.append(nums[j])
j += 1
while i <= mid:
temp.append(nums[i])
i += 1
while j <= end:
temp.append(nums[j])
j += 1
for i in range(len(temp)):
nums[start + i] = temp[i]
temp.clear()
def merge_sort(nums, start, end, temp):
if start >= end:
return
mid = start + (end - start) // 2
merge_sort(nums, start, mid, temp)
merge_sort(nums, mid+1, end, temp)
merge(nums, start, mid, end,temp)
merge_sort(nums, 0, len(nums) - 1, [])
return self.cnt
Python归并排序2：
class Solution:
def reversePairs(self, nums: List[int]) -> int:
res = 0
def MergeSort(lists):
nonlocal res
if len(lists) <= 1:
return lists
mid = int( len(lists)/2 )
left = MergeSort(lists[:mid])
right = MergeSort(lists[mid:])
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
res += len(left)-l
result += right[r:]
result += left[l:]
return result
MergeSort(nums)
return res
Java归并排序：
class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
public int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
public int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for(int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
}
Java归并排序2：
class Solution {
// 用于统计逆序对的数量
int res;
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
res = 0;
mergeSort(nums, 0, nums.length - 1);
return res;
}
// 归并排序整体逻辑
public void mergeSort(int[] nums, int left, int right) {
// 如果两个指针相遇，则说明已经排好序
if (left == right) {
return;
}
int middle = left + ((right - left) >> 1);
// 对数组的左半部分进行归并
mergeSort(nums, left, middle);
// 对数组的右半部分进行归并
mergeSort(nums, middle + 1, right);
merge(nums, left, middle, right);
}
// 归并排序合并的过程
public void merge(int[] nums, int left, int middle, int right) {
int[] help = new int[right - left + 1];
int i = 0;
// pos1 指向左半部分数组中第一个元素
int pos1 = left;
// pos2 指向右半部分数组中第一个元素
int pos2 = middle + 1;
while (pos1 <= middle && pos2 <= right) {
// 运算符 <= 是为了去除元素相等的情况
// 例如在 [1, 3, 2, 3, 1] 中，排除 [1, 1] 和 [3, 3] 的情况
if (nums[pos1] <= nums[pos2]) {
// 将元素较小的放进 help 数组中
help[i++] = nums[pos1++];
} else if (nums[pos1] > nums[pos2]) {
help[i++] = nums[pos2++];
// 本题核心：由于 nums[pos1] > nums[pos2]，
// 则从 nums[pos1] 到 nums[middle] 必定都是大于 nums[pos2] 的，
// 因为两部分的子数组已经是各自有序的
res += (middle - pos1 + 1);
}
}
// 下面这两个 while 是当其中一个子数组中的指针如果已经遍历完了，
// 那么另一个子数组肯定会有剩余元素，所以将剩余部分直接放到 help 中
while (pos1 <= middle) {
help[i++] = nums[pos1++];
}
while (pos2 <= right) {
help[i++] = nums[pos2++];
}
// 将 help 中的元素拷贝到原数组
for (int j = 0; j < help.length; j++) {
nums[left + j] = help[j];
}
}
}
前缀和
1. 和为 K 的子数组
描述 
思路
- 前缀和
代码
Python代码：
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
pre = 0
dic = collections.defaultdict(int)
dic[0] = 1
res = 0
for i in range(len(nums)):
pre += nums[i]
if pre - k in dic:
res += dic[pre - k]
dic[pre] = dic.get(pre, 0) + 1
return res
Java代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int preSum = 0;
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
int gap = preSum - k;
if (map.containsKey(gap)) {
res += map.get(gap);
}
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return res;
}
}
2. 和可被K整除的子数组
描述 
思路
- 同余定理
- 前缀和
- 注意python取余和java c++的区别
代码
public class Solution3 {
// 哈希表
public int subarraysDivByK(int[] A, int K) {
int len = A.length;
// 前缀和出现的次数
// key: i 之前的前缀和，value：出现的次数
int[] preSumCount = new int[K];
preSumCount[0] = 1;
int preSum = 0;
int res = 0;
for (int value : A) {
preSum += value;
// (preSum % K + K) % K 这句话要解释清楚
int remainder = (preSum % K + K) % K;
int count = preSumCount[remainder];
res += count;
preSumCount[remainder]++;
}
return res;
}
Python代码：
class Solution:
def subarraysDivByK(self, A: List[int], K: int) -> int:
pre_sum_count = [0] * K
pre_sum_count[0] += 1
pre_sum = 0
res = 0
for num in A:
pre_sum += num
remainder = pre_sum % K
res += pre_sum_count[remainder]
pre_sum_count[remainder] += 1
return res
3.矩形区域不超过K的最大数值和
参考
https://leetcode-cn.com/problems/max-submatrix-lcci/solution/python-zui-da-zi-xu-he-leetcode-363tao-lu-by-wulin/
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/bao-li-onyou-hua-er-fen-er-fen-jian-zhi-by-lzh_yve/
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/javacong-bao-li-kai-shi-you-hua-pei-tu-pei-zhu-shi/
描述 
思路
- 前缀和转求最大子数组和
代码
Python代码：
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
m = len(matrix)
n = len(matrix[0])
ans = float("-inf")
for i in range(n):
rowSum = [0] * (m)
for j in range(i, n):
for x in range(m):
rowSum[x] += matrix[x][j]
ans = max(ans, self.dpMax(rowSum, k))
return ans
def dpMax(self, rowSum, k):
preSum = 0
ans = float("-inf")
for i in range(len(rowSum)):
if preSum > 0:
preSum += rowSum[i]
else:
preSum = rowSum[i]
if preSum > ans:
ans = preSum
if ans <= k:
return ans
ans = float("-inf")
for i in range(len(rowSum)):
s = 0
for j in range(i, len(rowSum)):
s += rowSum[j]
if s == k:
return s
if s <= k and s > ans:
ans = s
return ans
Java代码：
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int ans = Integer.MIN_VALUE;
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < n; i++) {
int[] rowSum = new int[m];
for (int j = i; j < n; j++) {
for (int x = 0; x < m; x++) {
rowSum[x] += matrix[x][j];
}
ans = Math.max(ans, dpMax(rowSum, k));
}
}
return ans;
}
public int dpMax(int[] rowSum, int k) {
int preSum = rowSum[0];
int ans = preSum;
for (int i = 1; i < rowSum.length; i++) {
if (preSum > 0) {
preSum += rowSum[i];
} else {
preSum = rowSum[i];
}
ans = Math.max(ans, preSum);
}
if (ans <= k) return ans;
ans = Integer.MIN_VALUE;
for (int i = 0; i < rowSum.length; i++) {
preSum = 0;
for (int j = i; j < rowSum.length; j++) {
preSum += rowSum[j];
if (preSum == k) return preSum;
if (preSum <= k && preSum > ans) {
ans = preSum;
}
}
}
return ans;
}
}
差分
1. 增减序列
描述
给定一个长度为 nn 的数列 a1,a2,…,ana1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行，每行输入一个整数，第i+1行的整数代表aiai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0
输入样例：
4
1
1
2
2
输出样例：
1
2
思路
- 先求差分
- 统计正数和负数的最大绝对值，因为最开始选两个数，一个加1，另一个减1，或者一个减1，另一个加1
- 目标使差分数组变为0
代码
C++代码：
Java代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n+1];
for (int i = 1; i <= n; i++) {
a[i] = in.nextInt();
}
for (int i = n; i > 1; i--) {
a[i] -= a[i-1];
}
long pos = 0l;
long neg = 0l;
for (int i = 2; i <= n; i++) {
if (a[i] > 0) {
pos += a[i];
} else {
neg -= a[i];
}
}
System.out.println(Math.min(pos, neg) + Math.abs(pos - neg));
System.out.println(Math.abs(pos - neg) + 1);
}
}
2. 最佳牛围栏
农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 NN 和 FF ，数据间用空格隔开。
接下来 NN 行，每行输入一个整数，第i+1i+1行输入的整数代表第ii片区域内包含的牛的数目。
输出格式
输出一个整数，表示平均值的最大值乘以1000再 向下取整 之后得到的结果。
数据范围
1≤N≤1000001≤N≤100000
1≤F≤N1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500
原地哈希
「力扣」第 41 题：缺失的第一个正数（困难）
描述
思路
- 原地哈希
- 二次遍历
代码
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
while (0 < nums[i] && nums[i] <= len && nums[nums[i]- 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
return i+1;
}
}
return len + 1;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Python代码：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in range(n):
if nums[i] != i+1:
return i+1
return n+1
「力扣」第 448 题：找到所有数组中消失的数字
描述 
思路
- 原地哈希
- 二次遍历
代码
Python代码：
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n):
while nums[nums[i]-1] != nums[i]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
res = []
for i in range(n):
if nums[i] != i+1:
res.append(i+1)
return res
Java代码：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
res.add(i + 1);
}
}
return res;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
若有收获，就点个赞吧
0 人点赞
