数据结构与算法005
1. 力扣双指针
下面的题目都会涉及双指针，除此外，还有
- Leetcode3 最长不重复子串，在 hash 表部分讲过了
- 快排中
- 二分中
- ...
1.1 移动零-Leetcode 283
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:
输入: nums = [0] 输出: [0]
自写代码：
public class E283 {
// 10ms 击败 13.25%使用 Java 的用户
public void moveZeroes(int[] nums) {
int tail = nums.length - 1;
while (tail > 0 && nums[tail] == 0) {
tail--;
}
int head = 0;
while (head < tail) { // 等于时，相遇说明已处理到结尾
if (nums[head] == 0) {
// System.out.println(" " + (head+1) + " " + head + " " + (tail-head));
System.arraycopy(nums, head+1, nums, head, tail - head);
nums[tail--] = 0;
} else {
head++; // 连续两个0的话，移动后 head 位置就是0，没问题才能移动
}
}
}
public static void main(String[] args) {
// int[] arr = new int[]{0,1};
int[] arr = new int[]{0,0,1};
new E283().moveZeroes(arr);
System.out.println(Arrays.toString(arr));
}
}
方法一：双指针
思路及解法
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
注意到以下性质：
- 左指针左边均为非零数；
- 右指针左边直到左指针处均为零。
因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
代码：
/* 以下面为例
l r
0, 1, 0, 3, 12
交换后：
l r
1, 0, 0, 3, 12
交换后 l r 自增
l r
1, 0, 0, 3, 12
nums[r] = 0, r 自增 到 非0
l r
1, 0, 0, 3, 12 交换后 指针及数组
l r
1, 3, 0, 0, 12 再交换后 指针及数组
l r
1, 3, 12, 0, 0 r = n 结束。
*/
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
1.2 两数之和 II-Leetcode 167
给你一个下标从 1 开始的整数数组
numbers，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]，则1 <= index1 < index2 <= numbers.length。以长度为 2 的整数数组
[index1, index2]的形式返回这两个整数的下标index1和index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
- 仅存在一个有效答案
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
自写代码1：
// 541ms 击败 7.28%使用 Java 的用户
class Solution {
public int[] twoSum(int[] numbers, int target) {
// int n1 = 0;
// int n2 = 1;
int length = numbers.length;
for(int n1 = 0; n1 < length; n1++) {
for(int n2 = n1 + 1; n2 <length; n2++) {
if (numbers[n1] + numbers[n2] == target) {
return new int[]{n1+1, n2+1};
}
}
}
return null;
}
}
自写代码2：
// 502ms 击败 8.15%使用 Java 的用户
public int[] twoSum(int[] numbers, int target) {
int n1 = 0;
int n2 = n1 + 1;
int length = numbers.length;
while (n1 <= numbers.length - 2) {
if (numbers[n1] + numbers[n2] == target) {
return new int[]{n1+1, n2+1};
} else if (numbers[n1] + numbers[n2] > target) {
n1++;
n2 = n1 + 1;
} else {
n2++;
if(n2 == length) {
n1++;
n2 = n1 + 1;
}
}
}
return null;
}
参考代码：
/**
* <h3>2数之和</h3>
*/
public class SumLeetcode167 {
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9)));
}
/*
思路
- 两个指针 i 和 j 分别指向最左侧和最右侧的数字
- 它俩指向的数字和与 target 相比
- 小于 target i++ 向右找
- 大于 target j-- 向左找 // i 要是左移值更大，此时和j加还是大，此时这个j不用再考虑
- 等于 target 找到
*/
static public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
break;
}
}
return new int[]{i + 1, j + 1};
}
}
与 Leetcode 1 的两数之和区别在于，本题的数组是升序排好的，必须只使用常量级的额外空间
1.3 三数之和-Leetcode 15
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
先固定一个数，那后转变为求两数之和 == （0 - 被固定的数）。左右指针找到解后依然继续 i++, j-- 。因为解可能不唯一。为避免重复解，固定的数不能再被固定，如数组有两个 -1，固定了前面的，后面的就不固定。
/**
* <h3>3数之和</h3>
*/
public class SumLeetcode15 {
static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 排序方便去重
List<List<Integer>> result = new LinkedList<>();
dfs(3, 0, nums.length - 1, 0, nums,
new LinkedList<>(), result);
return result;
}
// n ： 求的是 几数之和
static void dfs(int n, int i, int j, int target, int[] nums,
LinkedList<Integer> stack,
List<List<Integer>> result) {
if (n == 2) {
// 套用两数之和求解
twoSum(i, j, nums, target, stack, result);
return;
}
// for (int k = i; k < j; k++) {
for(int k = i; k < j - (n - 2); k++) { // 预留 两位 数字 做 两数之和
// 检查重复
if (k > i && nums[k] == nums[k - 1]) {
continue;
}
// 固定一个数字，再尝试 n-1 数字之和
stack.push(nums[k]);
// 固定后 i 向后移
dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
// 回溯
stack.pop();
}
}
static int count;
static public void twoSum(int i, int j, int[] numbers, int target,
LinkedList<Integer> stack,
List<List<Integer>> result) {
count++; // 记录调用次数
while (i < j) {
int sum = numbers[i] + numbers[j]; // int sum 记得放在 while循环 2023.11.11
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else { // 找到解
ArrayList<Integer> list = new ArrayList<>(stack);
list.add(numbers[i]);
list.add(numbers[j]);
result.add(list);
// 继续查找其它的解
i++;
j--;
while (i < j && numbers[i] == numbers[i - 1]) {
i++;
}
while (i < j && numbers[j] == numbers[j + 1]) {
j--;
}
}
}
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] candidates = {-4, -1, -1, 0, 0, 1, 1, 2};
// int[] candidates = {-9, -5, -4, -3, -2, -1, 0, 2, 3, 7, 8, 11, 13, 16, 17, 21, 22, 23, 24, 25};
// int[] candidates = new int[]{-19921, -19644, -19607, -19475, -19410, -19391, -19370, -19357, -19335, -19246, -19177, -19165, -19145, -19082, -18980, -18942, -18874, -18838, -18791, -18747, -18563, -18547, -18461, -18422, -18348, -18331, -18242, -18221, -18211, -18159, -18126, -18080, -17902, -17790, -17561, -17452, -17365, -17363, -17341, -17223, -17025, -17008, -16929, -16922, -16866, -16832, -16760, -16580, -16523, -16511, -16464, -16350, -16324, -16267, -16151, -16109, -16085, -16065, -16000, -15982, -15917, -15816, -15802, -15741, -15659, -15653, -15619, -15524, -15501, -15477, -15462, -15331, -15317, -15293, -15239, -15206, -15121, -15114, -15086, -15052, -15016, -14915, -14866, -14859, -14782, -14778, -14606, -14600, -14531, -14530, -14452, -14388, -14270, -14263, -14258, -14104, -14087, -14003, -13897, -13840, -13782, -13726, -13706, -13658, -13631, -13594, -13547, -13505, -13500, -13439, -13417, -13304, -13174, -13155, -13016, -12957, -12879, -12761, -12716, -12641, -12609, -12470, -12458, -12393, -12388, -12374, -12235, -12228, -12179, -12113, -12041, -11931, -11829, -11753, -11670, -11662, -11555, -11433, -11318, -11293, -11270, -11261, -11242, -11219, -11113, -10960, -10957, -10859, -10696, -10660, -10640, -10400, -10301, -10238, -10218, -10184, -10130, -10101, -9741, -9732, -9642, -9474, -9461, -9310, -9274, -9243, -9241, -9096, -9037, -9022, -8966, -8938, -8853, -8849, -8838, -8832, -8824, -8801, -8798, -8763, -8682, -8527, -8420, -8385, -8270, -8217, -7908, -7877, -7845, -7810, -7679, -7642, -7628, -7617, -7611, -7535, -7532, -7528, -7418, -7341, -7269, -7240, -7180, -7049, -7041, -6954, -6939, -6864, -6601, -6511, -6493, -6468, -6417, -6242, -6218, -6167, -6088, -5933, -5860, -5589, -5532, -5475, -5475, -5453, -5431, -5306, -5021, -4942, -4913, -4899, -4866, -4423, -4322, -4259, -4257, -4185, -4159, -4105, -4088, -4026, -3990, -3765, -3728, -3642, -3596, -3555, -3490, -3487, -3406, -3333, -3303, -3271, -3251, -3221, -3218, -3046, -2989, -2954, -2951, -2919, -2863, -2707, -2586, -2460, -2445, -2437, -2388, -2314, -2288, -2243, -2156, -2151, -2141, -2072, -1958, -1900, -1859, -1806, -1760, -1741, -1636, -1560, -1523, -1483, -1415, -1408, -1343, -1331, -1187, -1186, -1119, -759, -602, -585, -562, -542, -447, -394, -104, -90, 20, 21, 46, 250, 252, 324, 727, 792, 860, 874, 910, 910, 925, 929, 1202, 1209, 1454, 1558, 1591, 1637, 1897, 1909, 1919, 1988, 2099, 2246, 2344, 2391, 2590, 2689, 2705, 2759, 2803, 2826, 2890, 2909, 3015, 3023, 3063, 3114, 3213, 3295, 3302, 3325, 3340, 3342, 3638, 3649, 3649, 3695, 3848, 3900, 3939, 4031, 4071, 4103, 4247, 4280, 4320, 4394, 4460, 4508, 4656, 4675, 4713, 4856, 5017, 5262, 5355, 5356, 5453, 5465, 5467, 5475, 5680, 5852, 5897, 5992, 6001, 6019, 6059, 6086, 6184, 6214, 6364, 6421, 6428, 6739, 6822, 6912, 7170, 7225, 7228, 7252, 7332, 7344, 7352, 7461, 7712, 8284, 8315, 8434, 8623, 8731, 8838, 8845, 8860, 8940, 8942, 8959, 8990, 9104, 9147, 9174, 9255, 9337, 9344, 9344, 9541, 9612, 9623, 9883, 9947, 9948, 10029, 10052, 10079, 10093, 10142, 10151, 10153, 10159, 10236, 10390, 10406, 10481, 10673, 10709, 10710, 11092, 11219, 11276, 11422, 11474, 11515, 11576, 11721, 11839, 11855, 12052, 12200, 12241, 12326, 12333, 12582, 12642, 12687, 12718, 12741, 12783, 12808, 12820, 12900, 13033, 13041, 13042, 13048, 13091, 13141, 13170, 13200, 13211, 13213, 13343, 13483, 13501, 13606, 13615, 13616, 13621, 13686, 13700, 13777, 13805, 13848, 13859, 13947, 13974, 14014, 14079, 14162, 14184, 14198, 14333, 14349, 14367, 14525, 14627, 14740, 14848, 14861, 14906, 14961, 14996, 15016, 15086, 15129, 15396, 15473, 15498, 15686, 15690, 15750, 15779, 15922, 15929, 15966, 15970, 16059, 16244, 16296, 16538, 16590, 16634, 16659, 16814, 16822, 17016, 17056, 17165, 17307, 17318, 17452, 17642, 17708, 17718, 17764, 17910, 17921, 17984, 17994, 18008, 18041, 18096, 18123, 18179, 18242, 18403, 18470, 18516, 18593, 18669, 18683, 18749, 18766, 18913, 19121, 19343, 19355, 19355, 19369, 19450, 19486, 19491, 19546, 19553, 19664, 19672, 19700, 19746, 19758, 19878, 19927, 19956, 19997};
System.out.println("数据量:" + candidates.length);
System.out.println(threeSum(candidates));
System.out.println("耗费时间:" + (System.currentTimeMillis() - start));
System.out.println("递归次数:" + count);
}
}
力扣官方题解：
前言
本题与 1. 两数之和 类似，是非常经典的面试题，但是做法不尽相同。
方法一：排序 + 双指针
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
如果按照力扣40的做法，只选择长度为3的结果，效率较低。
if (stack.size() == 3) {
if (target == 0) {
result.add(new ArrayList<>(stack));
}
return;
}
- 本题与之前的两数之和（Leetcode 1 和 Leetcode 167）相比，区别在于
- 两数之和里明确说了，只有一个答案，而本题要找出所有答案
- 本题要考虑去重
- 本题类似于 组合总和 II（Leetcode 40） 区别在于
- 40 题要求列出任意数之和等于 target 的所有组合，而本题要求三数之和等于 target 的所有组合
- 40 题使用回溯的办法时间复杂度是
O(2^n * n)，而本题的三数限制了递归次数仅有一次，并且每次递归终点是求两数之和时间复杂度为O(n)，因此总时间复杂度为O(n^2)
- 小优化：固定数字时，应该预留三个数字做三数之和，预留两个数字做两数之和，因此有 k < j - (n - 2)
1.4 四数之和-Leetcode 18
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
/**
* <h3>4数之和</h3>
*/
public class SumLeetcode18_t {
static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new LinkedList<>();
dfs(4, 0, nums.length - 1, target, nums,
new LinkedList<>(), result);
return result;
}
// 转 long 型 解决测试用例
static void dfs(int n, int i, int j, long target, int[] nums,
LinkedList<Integer> stack,
List<List<Integer>> result) {
if (n == 2) {
// 套用两数之和求解
twoSum(i, j, nums, target, stack, result);
return;
}
for (int k = i; k < j - (n - 2); k++) { // 四数之和 i <j-2 三数之和 i <j-1
// 检查重复
if (k > i && nums[k] == nums[k - 1]) {
continue;
}
// 固定一个数字，再尝试 n-1 数字之和
stack.push(nums[k]);
dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
stack.pop();
}
}
static int count;
static public void twoSum(int i, int j, int[] numbers, long target,
LinkedList<Integer> stack,
List<List<Integer>> result) {
count++;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else { // 找到解
ArrayList<Integer> list = new ArrayList<>(stack);
list.add(numbers[i]);
list.add(numbers[j]);
result.add(list);
// 继续查找其它的解
i++;
j--;
while (i < j && numbers[i] == numbers[i - 1]) {
i++;
}
while (i < j && numbers[j] == numbers[j + 1]) {
j--;
}
}
}
}
public static void main(String[] args) {
// System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
// System.out.println(fourSum(new int[]{2, 2, 2, 2, 2}, 8));
System.out.println(fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296));
System.out.println((long)1000000000+1000000000+1000000000+1000000000);
System.out.println((long) -294967296 - 1000000000 - 1000000000);
}
}
力扣官方题解：
方法一：排序 + 双指针
思路与算法
为了避免枚举到重复四元组，则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素。
为了实现上述要求，可以对数组进行排序，并且在循环过程中遵循以下两点：
- 每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
- 同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。
使用上述方法，可以避免枚举到重复四元组，但是由于仍使用四重循环，时间复杂度仍是 O(n^4)。注意到数组已经被排序，因此可以使用双指针的方法去掉一重循环。
使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标 i 和 j，其中 i<j。初始时，左右指针分别指向下标 j+1 和下标 n−1。每次计算四个数的和，并进行如下操作：
- 如果和等于
target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数； - 如果和小于
target，则将左指针右移一位； - 如果和大于
target，则将右指针左移一位。
使用双指针枚举剩下的两个数的时间复杂度是 O(n)，因此总时间复杂度是 O(n^3)，低于 O(n^4)。
具体实现时，还可以进行一些剪枝操作：
- 在确定第一个数之后，如果
nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target，说明此时剩下的三个数无论取什么值，四数之和一定大于target，因此退出第一重循环； - 在确定第一个数之后，如果
nums[i] + nums[n−3] + nums[n−2] + nums[n−1] < target，说明此时剩下的三个数无论取什么值，四数之和一定小于target，因此第一重循环直接进入下一轮，枚举nums[i+1]； - 在确定前两个数之后，如果
nums[i] + nums[j] + nums[j+1] + nums[j+2] > target，说明此时剩下的两个数无论取什么值，四数之和一定大于target，因此退出第二重循环； - 在确定前两个数之后，如果
nums[i] + nums[j] + nums[n−2] + nums[n−1] < target，说明此时剩下的两个数无论取什么值，四数之和一定小于target，因此第二重循环直接进入下一轮，枚举nums[j+1]。
代码：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4) {
return quadruplets;
}
Arrays.sort(nums); // 排序
int length = nums.length;
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) { // 不固定重复值
continue;
}
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break; // 跳出循环
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue; // 下一轮
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue; // 不固定重复值
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break; // 跳出循环
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue; // 下一轮
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
}
1.5 盛最多水的容器-Leetcode 11
给定一个长度为
n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与
x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1] 输出：1
改变（移动）更短的短板才有可能使得面积增加。
/**
* <h3>盛最多水的容器</h3>
*/
public class MostWaterLeetcode11 {
static int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int max = 0;
while (i < j) {
if (height[i] < height[j]) {
int area = (j - i) * height[i]; // 先获得当前面积
max = Math.max(max, area);
i++;
} else {
int area = (j - i) * height[j];
max = Math.max(max, area);
j--;
}
}
return max;
}
public static void main(String[] args) {
System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49
// System.out.println(maxArea(new int[]{2,1})); // 1
}
}
1.6 反转字符串-Leetcode 344
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
// or
public void reverseString(char[] s) {
int i = 0;
int j = s.length - 1;
while (i < j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
2. Leetcode 单调队列和栈
2.1 单调递减队列
/**
* <h3>单调递减队列</h3>
*/
public class MonotonicQueue {
private LinkedList<Integer> deque = new LinkedList<>();
public Integer peek() {
return deque.peekFirst();
}
public void poll() {
deque.pollFirst();
}
// 6 5 4 2 1 <= 3
public void offer(Integer t) {
while (!deque.isEmpty() && deque.peekLast() < t) {
deque.pollLast();
}
deque.offerLast(t);
}
@Override
public String toString() {
return deque.toString();
}
public static void main(String[] args) {
MonotonicQueue q = new MonotonicQueue();
for (int i : new int[]{1, 3, -1, -3, 5, 3, 6, 7}) {
q.offer(i);
System.out.println(q);
}
}
}
2.2 最大滑动窗口-Leetcode 239
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1 输出：[1]
// 35ms
// 击败 42.61%使用 Java 的用户
/**
* <h3>滑动窗口最大值 - 单调队列</h3>
*/
public class SlidingWindowMaximumLeetcode239 {
// 每次向单调递减队列加入元素，队头元素即为滑动窗口最大值
static int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue queue = new MonotonicQueue();
List<Integer> list = new ArrayList<>(); // 收集结果
for (int i = 0; i < nums.length; i++) {
// 检查队列头部元素，超过滑动窗口范围要移除
if (i >= k && queue.peek() == nums[i - k]) { // 最大值 已被 滑走
queue.poll();
}
int num = nums[i];
queue.offer(num);
// 索引大于窗口 才开始收集
if (i >= (k - 1)) {
// System.out.println(queue.peek());
list.add(queue.peek());
}
}
return list.stream().mapToInt(Integer::intValue)
.toArray();
}
public static void main(String[] args) {
System.out.println(Arrays.toString(
maxSlidingWindow(new int[]{1, 3, -1, -3, -4, 5, 3, 6, 7}, 3))
); //[3, 3, 5, 5, 6, 7]
// System.out.println(Arrays.toString(maxSlidingWindow(new int[]{7, 2, 4}, 2))); // [7, 4]
// System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, 1, 2, 0, 5}, 3))); // [3, 3, 2, 5]
// System.out.println(Arrays.toString(maxSlidingWindow(new int[]{-7, -8, 7, 5, 7, 1, 6, 0}, 4))); // [7, 7, 7, 7, 7]
}
}
力扣官方题解：
方法一：优先队列
思路与算法
对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。
// 87ms
// 击败 15.63%使用 Java 的用户
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1]);
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
// 数值降序 索引降序
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
// 初始窗口
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
复杂度分析
- 时间复杂度：
O(nlogn)- 空间复杂度：
O(n)
方法二：单调队列
思路与算法
我们可以顺着方法一的思路继续进行优化。（思路与第一种单调递减队列一样）
由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i<j），并且 i 对应的元素不大于 j 对应的元素（nums[i] ≤ nums[j]），那么会发生什么呢？
当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。
因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 i，后者为 j，就对应了上面所说的情况，即 nums[i] 会被移除，这就产生了矛盾。
当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。但与方法一中相同的是，此时的最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。因此我们还需要不断从队首弹出元素，直到队首元素在窗口中为止。
为了可以同时弹出队首和队尾的元素，我们需要使用双端队列。满足这种单调性的双端队列一般称作「单调队列」。
// 26ms
// 击败 93.21%使用 Java 的用户
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
// 初始化 前 k
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
// 处理（删除）尾部比插入值还 小的 值（索引）
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
// 加入后，如果最大值 还是 上一轮的值 则删除
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
复杂度分析
时间复杂度：
O(n)空间复杂度：
O(k)
2.3 单调递减栈
/**
* <h3>单调栈 从栈底到栈顶递减</h3>
*/
public class MonotonicStack {
private final LinkedList<Integer> stack = new LinkedList<>();
public void push(int value) {
while (!stack.isEmpty() && stack.peek() < value) {
stack.pop();
}
stack.push(value);
}
@Override
public String toString() {
ArrayList<Integer> reverse = new ArrayList<>(stack);
Collections.reverse(reverse);
return reverse.toString();
}
public static void main(String[] args) {
MonotonicStack stack = new MonotonicStack();
stack.push(3);
stack.push(2);
stack.push(1);
stack.push(2);
System.out.println(stack); // [3, 2, 2]
}
}
2.4 接雨水-Leetcode 42
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
方法零：封装 + 单调栈
// 2ms 击败 37.61%使用 Java 的用户
/**
* <h3>接雨水 - 单调栈</h3>
* 1. 维护一个单调栈
* 2. 当加入一个新元素时，如果发现需要弹出元素
* 表示遇到了一个凹陷的位置
* 此时应该计算雨水的容量
*/
public class TrappingRainWaterLeetcode42 {
public static void main(String[] args) {
System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5})); // 9
}
static int trap(int[] heights) {
LinkedList<Data> stack = new LinkedList<>();
int sum = 0;
for (int i = 0; i < heights.length; i++) {
Data right = new Data(heights[i], i);
// 单调递减栈
while (!stack.isEmpty()
&& stack.peek().height < right.height) {
Data pop = stack.pop();
Data left = stack.peek(); // 栈顶 为 被弹出元素 的 左边界， 是“凹”的左。如果是梯形蓄水，则从底部一行一行计算
if (left != null) { // 计算水的容量 // 没有左侧柱子，说明左边已被计算过，或者第一次加入
int width = right.i - left.i - 1; //
int height = Math.min(left.height, right.height) - pop.height;
sum += width * height;
}
}
stack.push(right);
// System.out.println(stack);
}
return sum;
}
// 储存 索引 及 数值
static class Data{
int height;
int i; // 索引
public Data(int height, int i) {
this.height = height;
this.i = i;
}
@Override
public String toString() {
return String.valueOf(height);
}
}
}
- 维护一个单调栈
- 当加入新柱子（right）时，如果发现要弹出之前的柱子，表示遇到了凹陷的地方
- 此时栈里没有更左边的柱子，表示拦不住雨水
- 栈里有左边柱子（left）就可以计算雨水容量：
(right.i - left.i-1)*Min(right.height,left.height)-pop.height
力扣官方题解：
方法一：动态规划
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n^2)。
上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。
创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0 ≤ i < n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。
显然，leftMax[0] = height[0]，rightMax[n−1] = height[n−1]。两个数组的其余元素的计算如下：
- 当
1 ≤ i ≤ n−1时，leftMax[i] = max(leftMax[i−1], height[i])； - 当
0 ≤ i ≤ n−2时，rightMax[i] = max(rightMax[i+1], height[i])。
因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。
在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0 ≤ i < n ，下标 i 处能接的雨水量等于 min(leftMax[i], rightMax[i]) − height[i]。遍历每个下标位置即可得到能接的雨水总量。
// 1ms 击败 76.86%使用 Java 的用户
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
方法二：单调栈
除了计算并存储每个位置两边的最大高度以外，也可以用单调栈计算能接的雨水总量。
维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left] ≥ height[top] 。如果 height[i] > height[top] ，则得到一个可以接雨水的区域，该区域的宽度是 i − left − 1，高度是 min(height[left], height[i]) − height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。
为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]。
在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。
// 2ms 击败 37.61%使用 Java 的用户
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}
方法三：双指针
动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)？
注意到下标 iii 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0, right=n−1, leftMax=0, rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。
当两个指针没有相遇时，进行如下操作：
- 使用
height[left]和height[right]的值更新leftMax和rightMax的值； - 如果
height[left] < height[right]，则必有leftMax < rightMax，下标left处能接的雨水量等于leftMax − height[left]，将下标left处能接的雨水量加到能接的雨水总量，然后将left加1（即向右移动一位）； - 如果
height[left] ≥ height[right]，则必有leftMax ≥ rightMax，下标right处能接的雨水量等于rightMax − height[right]，将下标right处能接的雨水量加到能接的雨水总量，然后将right减1（即向左移动一位）。
当两个指针相遇时，即可得到能接的雨水总量。
例子，第四步：
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}
3. Leetcode 字符串
3.1 indexOf - Leetcode 28 (KMP算法)
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
暴力匹配：用两根指针逐一比较两个字符串
（i指针外层记录位置，j指针移动比较）
/**
* <h3>字符串匹配</h3>
*/
public class StrStrLeetcode28 {
static int strStr(String str1, String str2) {
char[] origin = str1.toCharArray(); // 原始
char[] pattern = str2.toCharArray(); // 模式
int i = 0; // i 指针对应原始字符串
int j = 0; // j 指针对应模式字符串
while (i <= origin.length - pattern.length) {
for (j = 0; j < pattern.length; j++) { // j = 0; 回退到 模式字符串 的 开头位置
if (pattern[j] != origin[i+j]) {
break;
}
}
if (j == pattern.length) {
return i;
}
i++;
}
return -1;
}
public static void main(String[] args) {
System.out.println(strStr("aaacaaab", "aaab"));
}
}
最长前后缀数组：
/**
* <h3>字符串匹配 - Knuth Morris Pratt 算法</h3>
*/
public class StrStrLeetcode28KMP {
static int strStr(String str1, String str2) {
char[] origin = str1.toCharArray(); // 原始
char[] pattern = str2.toCharArray(); // 模式
int[] lps = lps(pattern); // 最长前后缀数组
/*
1. 匹配成功，i++ j++，直到 j==模式字符串长度
2. 匹配失败
j != 0 跳过最长前后缀字符，继续匹配
j == 0 则 i++
*/
int i = 0;
int j = 0;
while (pattern.length - j <= origin.length - i) {
if (origin[i] == pattern[j]) {
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = lps[j - 1];
}
if (j == pattern.length) {
// 找到解
return i - j;
}
}
return -1;
}
/*
最长前后缀数组：只跟模式字符串相关
1. 索引：使用了模式字符串前 j 个字符串 - 1
2. 值：最长前后缀的长度（恰好是j要跳转的位置）
*/
static int[] lps(char[] pattern) {
// return new int[]{0, 0, 1, 2, 3, 0, 1};
int[] lps = new int[pattern.length];
int i = 1;
int j = 0;
while (i < pattern.length) {
if (pattern[i] == pattern[j]) {
lps[i] = j + 1;
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = lps[j - 1];
}
}
return lps;
}
public static void main(String[] args) {
// System.out.println(strStr("ababababcabacacababaca", "ababaca"));
// System.out.println("ababababcabacacababaca".indexOf("ababaca"));
System.out.println(Arrays.toString(lps("ababaca".toCharArray())));
}
}
- 很多文章里，把
lps数组的向后平移一位，lps用 -1 填充，这个平移后的数组称为 next- 这样可以用 -1 代替 j == 0 的判断
- 并可以在 j > 0 向前移动时，做少量优化（不用 next 数组也能做同样优化）
- 其它字符串匹配算法有：BM 算法、sunday 算法、Horspool 算法等
朴素解法
直观的解法的是：枚举原串ss中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：匹配成功：返回本次匹配的原串「发起点」。
匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。
class Solution {
public int strStr(String ss, String pp) {
int n = ss.length(), m = pp.length();
char[] s = ss.toCharArray(), p = pp.toCharArray();
// 枚举原串的「发起点」
for (int i = 0; i <= n - m; i++) {
// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
int a = i, b = 0;
while (b < m && s[a] == p[b]) {
a++;
b++;
}
// 如果能够完全匹配，返回原串的「发起点」下标
if (b == m) return i;
}
return -1;
}
}
KMP 解法
KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。
上述的朴素解法，不考虑剪枝的话复杂度是
O(m∗n)的，而 KMP 算法的复杂度为O(m+n)。KMP 之所以能够在
O(m+n)复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。你可能不太理解，没关系，我们可以通过举 🌰 来理解 KMP。
1.匹配过程
在模拟 KMP 匹配过程之前，我们先建立两个概念：
- 前缀：对于字符串
abcxxxxefg，我们称abc属于abcxxxxefg的某个前缀。 - 后缀：对于字符串
abcxxxxefg，我们称efg属于abcxxxxefg的某个后缀。
然后我们假设原串为 abeababeabf，匹配串为 abeabf：
我们可以先看看如果不使用 KMP，会如何进行匹配（不使用 substring 函数的情况下）。
首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。
首次匹配的「发起点」是第一个字符 a。显然，后面的 abeab 都是匹配的，两个指针会同时往右移动（黑标）。
在都能匹配上 abeab 的部分，「朴素匹配」和「KMP」并无不同。
直到出现第一个不同的位置（红标）：
接下来，正是「朴素匹配」和「KMP」出现不同的地方：
先看下「朴素匹配」逻辑：
- 将原串的指针移动至本次「发起点」的下一个位置（b 字符处）；匹配串的指针移动至起始位置。
- 尝试匹配，发现对不上，原串的指针会一直往后移动，直到能够与匹配串对上位置。
也就是说，对于「朴素匹配」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配。
这也就不难理解为什么「朴素匹配」的复杂度是 O(m∗n) 了。
- 然后我们再看看「KMP 匹配」过程：
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：
跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：
到这里，你应该清楚 KMP 为什么相比于朴素解法更快：
- 因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。
- 因为 KMP 的原串指针不会进行回溯（没有朴素匹配中回到下一个「发起点」的过程）。
第一点很直观，也很好理解。
我们可以把重点放在第二点上，原串不回溯至「发起点」意味着什么？
其实是意味着：随着匹配过程的进行，原串指针的不断右移，我们本质上是在不断地在否决一些「不可能」的方案。
当我们的原串指针从 i 位置后移到 j 位置，不仅仅代表着「原串」下标范围为 [i,j) 的字符与「匹配串」匹配或者不匹配，更是在否决那些以「原串」下标范围为 [i,j) 为「匹配发起点」的子集。
2.分析实现
我们可以先分析一下复杂度。如果严格按照上述解法的话，最坏情况下我们需要扫描整个原串，复杂度为 O(n)。同时在每一次匹配失败时，去检查已匹配部分的相同「前缀」和「后缀」，跳转到相应的位置，如果不匹配则再检查前面部分是否有相同「前缀」和「后缀」，再跳转到相应的位置 ... 这部分的复杂度是 O(m^2)，因此整体的复杂度是 O(n * m^2) ，而我们的朴素解法是 O(m * n) 的。
说明还有一些性质我们没有利用到。
显然，扫描完整原串操作这一操作是不可避免的，我们可以优化的只能是「检查已匹配部分的相同前缀和后缀」这一过程。
再进一步，我们检查「前缀」和「后缀」的目的其实是「为了确定匹配串中的下一段开始匹配的位置」。
同时我们发现，对于匹配串的任意一个位置而言，由该位置发起的下一个匹配点位置其实与原串无关。
举个 🌰，对于匹配串 abcabd 的字符 d 而言，由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c。
可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的，我们将这一过程称为找 next 点。
显然我们可以预处理出 next 数组，数组中每个位置的值就是该下标应该跳转的目标位置（ next 点）。
当我们进行了这一步优化之后，复杂度是多少呢？
预处理 next 数组的复杂度未知，匹配过程最多扫描完整个原串，复杂度为 O(n)。
因此如果我们希望整个 KMP 过程是 O(m+n) 的话，那么我们需要在 O(m) 的复杂度内预处理出 next 数组。
所以我们的重点在于如何在 O(m)O(m)*O*(*m*) 复杂度内处理处 next 数组。
3.next 数组的构建
接下来，我们看看 next 数组是如何在 O(m) 的复杂度内被预处理出来的。
假设有匹配串 aaabbab，我们来看看对应的 next 是如何被构建出来的。
这就是整个 next 数组的构建过程，时空复杂度均为 O(m)。
至此整个 KMP 匹配过程复杂度是 O(m+n) 的。
4.代码实现
在实际编码时，通常我会往原串和匹配串头部追加一个空格（哨兵）。
目的是让 j 下标从 0 开始，省去 j 从 -1 开始的麻烦。
代码：
class Solution {
// KMP 算法
// ss: 原串(string) pp: 匹配串(pattern)
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格，使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
int[] next = new int[m + 1];
// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话，j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++
if (p[i] == p[j + 1]) j++;
// 更新 next[i]，结束本次循环，i++
next[i] = j;
}
// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++，结束本次循环后 i++
if (s[i] == p[j + 1]) j++;
// 整一段匹配成功，直接返回下标
if (j == m) return i - m;
}
return -1;
}
}
3.2 最长公共前缀-Leetcode 14
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。示例 3：
输入：strs = ["a"] 输出："a"
方法一：横向扫描
用 LCP(S_1…S_n) 表示字符串 S_1…S_n 的最长公共前缀。
可以得到以下结论：
基于该结论，可以得到一种查找字符串数组中的最长公共前缀的简单方法。依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
int count = strs.length;
for (int i = 1; i < count; i++) {
prefix = longestCommonPrefix(prefix, strs[i]);
if (prefix.length() == 0) {
break;
}
}
return prefix;
}
public String longestCommonPrefix(String str1, String str2) {
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++;
}
return str1.substring(0, index);
}
}
方法二：纵向扫描
/**
* <h3>最长公共前缀</h3>
*/
public class LCPLeetcode14 {
static String longestCommonPrefix(String[] strings) {
/*
情况1：比较某一列时，遇到不同字符，i 之前的字符就是解
情况2：比较某一列时，遇到字符串长度不够，i 之前的字符就是解
情况3：i 循环自然结束，此时第一个字符串就是解
*/
char[] first = strings[0].toCharArray(); // 第一个字符串
for (int i = 0; i < first.length; i++) {
char ch = first[i];
for (int j = 1; j < strings.length; j++) {
/*if (strings[j].length() == i) { // 情况 2
return new String(first, 0, i);
}
if(ch != strings[j].charAt(i)) { // 情况 1
return new String(first, 0, i);
} */
if (strings[j].length() == i || ch != strings[j].charAt(i)) {
return new String(first, 0, i);
}
}
}
return strings[0];
}
public static void main(String[] args) {
System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // fl
System.out.println(longestCommonPrefix(new String[]{"dog", "racecar", "car"})); // 空串
System.out.println(longestCommonPrefix(new String[]{"ab", "a"})); // a
System.out.println(longestCommonPrefix(new String[]{"dog", "dogaa", "dogbb"})); // dog
System.out.println(longestCommonPrefix(new String[]{"a"})); // a
}
}
3.3 最长回文子串-Leetcode 5
给你一个字符串
s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
1 <= s.length <= 1000s仅由数字和英文字母组成
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd" 输出："bb"
中心扩展算法，每个字母都被当做回文的中间点，像左右扩展比较。偶数个情况则每两个字母滑动对比。
// 5ms 击败 98.66%使用 Java 的用户
/**
* <h3>最长回文子串</h3>
*/
public class LongestPalindromeLeetcode5 {
public static void main(String[] args) {
System.out.println(longestPalindrome("babad"));
System.out.println(longestPalindrome("cbbd"));
System.out.println(longestPalindrome("a"));
System.out.println(longestPalindrome("bccbcbabcbafa"));
}
static String longestPalindrome(String s) {
left = 0;
right = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length - 1; i++) {
extend(chars, i, i); // 一个字符作为中心点
extend(chars, i, i + 1); // 两个字符作为中心点
}
return new String(chars, left, right - left + 1);
}
// 记录最大的子串的 左右边界
static int left; // i
static int right; // j
static void extend(char[] chars, int i, int j) {
while (i >= 0 && j < chars.length
&& chars[i] == chars[j]) { // 如果是回文，扩大回文范围
i--; // -1
j++; // 4
}
// 退出循环时，i和j指向的不是回文，需要还原
i++;
j--;
if (j - i > right - left) {
left = i;
right = j;
}
}
}
- 还有一个复杂度为
O(n)的Manacher算法。然而本算法十分复杂，一般不作为面试内容。官方题解
3.4 最小覆盖子串-Leetcode 76
给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。- 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
public class MinWindowLeetcode76_2 {
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
// System.out.println(minWindow("aaabbbbbcdd", "abcdd")); // abbbbbcdd
}
static class Result {
int i;
int j;
public Result(int i, int j) {
this.i = i;
this.j = j;
}
}
/*
1. 统计目标串需要各种字符个数， 统计原始串 i~j 范围各种字符个数
2. 如果原始串 i~j 范围内不满足条件，j++ 扩大范围，直到满足条件 j 停下来
3. 一旦满足条件 i++ 缩小范围，直到再次不满足条件 ...
4. 重复 2. 3. 两步直至 j 到达原始串末尾
*/
static String minWindow(String s, String t) {
char[] target = t.toCharArray();
int[] targetCount = new int[128]; // 目标串字符各出现几次
for (char ch : target) {
targetCount[ch]++;
}
// print(targetCount);
int passTotal = 0; // 条件总数
for (int count : targetCount) {
if (count > 0) { // 排除数组默认值 0
passTotal++;
}
}
// System.out.println("条件总数:" + passTotal);
int passed = 0; // 已通过的条件数
char[] source = s.toCharArray();
int[] sourceCount = new int[128]; // 原始串i~j范围内字符各出现几次
int i = 0;
int j = 0;
Result res = null;
while (j < source.length) {
// 扩大 j 范围，更新范围内字符计数 和 通过条件数
char right = source[j];
sourceCount[right]++;
if (sourceCount[right] == targetCount[right]) {
passed++;
}
// System.out.println("处理的字符:" + right + " 通过数:" + passed);
// print(sourceCount);
// System.out.println("----------------------------------------");
// 若已满足所有条件，缩小 i 范围，更新范围内字符计数 和 通过条件数
while (passed == passTotal && i <= j) {
if (res == null) {
res = new Result(i, j);
} else {
if (j - i < res.j - res.i) {
res = new Result(i, j);
}
}
char left = source[i];
sourceCount[left]--;
if (sourceCount[left] < targetCount[left]) {
passed--; // passed -- 后不符合要求，退出循环
}
i++;
}
j++;
}
// System.out.println(res.i + " " + res.j);
return res == null ? "" : new String(source, res.i, res.j - res.i + 1);
}
static void print(int[] count) {
System.out.println(IntStream.range(0, count.length)
.filter(i -> count[i] != 0)
.boxed()
.collect(toMap(i -> (char) i.intValue(), i -> count[i])));
}
}
4. Leetcode 设计
4.1 LRU 缓存-Leetcode 146
请你设计并实现一个满足 LRU Least Recently Used (最近最少使用) 缓存 约束的数据结构。
实现
LRUCache类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。函数
get和put必须以O(1)的平均时间复杂度运行。提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
// 42ms 击败 79.28%使用 Java 的用户
// 117.59MB 击败 17.00%使用 Java 的用户
/**
* <h3>设计 LRU 缓存</h3>
*/
public class LRUCacheLeetcode146 {
static class LRUCache {
static class Node {
Node prev;
Node next;
int key;
int value;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
// LinkedHashMap
static class DoublyLinkedList {
Node head;
Node tail;
public DoublyLinkedList() {
head = tail = new Node();
head.next = tail;
tail.prev = head;
}
// 头部添加 head<->tail
public void addFirst(Node newFirst) { // O(1)
Node oldFirst = head.next;
newFirst.prev = head;
newFirst.next = oldFirst;
head.next = newFirst;
oldFirst.prev = newFirst;
}
// 已知节点删除
public void remove(Node node) { // O(1)
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
// 尾部删除
public Node removeLast() { // O(1)
// 由hashmap判断是否能被删除
Node last = tail.prev;
remove(last);
return last;
}
}
// <key, Node<key, value>>
private final HashMap<Integer, Node> map = new HashMap<>();
private final DoublyLinkedList list = new DoublyLinkedList();
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) { // O(1)
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
// 跳到头部
list.remove(node);
list.addFirst(node);
return node.value;
}
public void put(int key, int value) { // O(1)
if(map.containsKey(key)) { // 更新
Node node = map.get(key);
node.value = value;
list.remove(node);
list.addFirst(node);
} else { // 新增
Node node = new Node(key, value);
map.put(key, node);
list.addFirst(node);
if (map.size() > capacity) {
Node removed = list.removeLast();
map.remove(removed.key);
}
}
}
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 1
cache.put(3, 3);
System.out.println(cache.get(2)); // -1
cache.put(4, 4);
System.out.println(cache.get(1)); // -1
System.out.println(cache.get(3)); // 3
}
}
力扣官方题解：
前言
实现本题的两种操作，需要用到一个哈希表和一个双向链表。在面试中，面试官一般会期望读者能够自己实现一个简单的双向链表，而不是使用语言自带的、封装好的数据结构。在 Java 语言中，同样有类似的数据结构 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);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
注意：
- 这里很重要的一点是，map 中存储 node，可以省去在双向链表中查找 node 的时间，这样让使用最近访问的节点移动到链表头时达到
O(1)的需求 - 同时我们应当意识到，node 的引用不能修改了（不方便修改，真要改得同时改链表）
- 例如，不能在更新时用新的 node 对象替换，而应该在原有的 node 上修改 value
4.2 LFU 缓存-Leetcode 460
请你为 最不经常使用 Least Frequently Used（LFU）缓存算法设计并实现数据结构。
实现
LFUCache类：
LFUCache(int capacity)- 用数据结构的容量capacity初始化对象int get(int key)- 如果键key存在于缓存中，则获取键的值，否则返回-1。void put(int key, int value)- 如果键key已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为
1(由于 put 操作)。对缓存中的键执行get或put操作，使用计数器的值将会递增。函数
get和put必须以O(1)的平均时间复杂度运行。
示例：
输入： ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] 输出： [null, null, null, 1, null, -1, 3, null, -1, 3, 4] 解释： // cnt(x) = 键 x 的使用计数 // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的） LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // 返回 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小 // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用 // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // 返回 4 // cache=[3,4], cnt(4)=2, cnt(3)=3
/**
* <h3>设计 LFU 缓存</h3>
*/
public class LFUCacheLeetcode460 {
static class LFUCache {
static class Node {
Node prev;
Node next;
int key;
int value;
int freq = 1; // 频度
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
static class DoublyLinkedList {
Node head;
Node tail;
int size; // 个数
public DoublyLinkedList() {
head = tail = new Node();
head.next = tail;
tail.prev = head;
}
// 头部添加 head<->tail
public void addFirst(Node newFirst) { // O(1)
Node oldFirst = head.next;
newFirst.prev = head;
newFirst.next = oldFirst;
head.next = newFirst;
oldFirst.prev = newFirst;
size++;
}
// 已知节点删除
public void remove(Node node) { // O(1)
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
size--;
}
// 尾部删除
public Node removeLast() { // O(1)
Node last = tail.prev;
remove(last);
return last;
}
public boolean isEmpty() {
return size == 0;
}
}
// 存储全部 node 的 map
private HashMap<Integer, Node> kvMap = new HashMap<>();
// 存储频率 的 map，每个map链接节点类DoublyLinkedList
private HashMap<Integer, DoublyLinkedList> freqMap = new HashMap<>();
private int capacity;
private int minFreq = 1; // 最小频度
public LFUCache(int capacity) {
this.capacity = capacity;
}
/*
key 不存在
返回 -1
key 存在
返回 value 值
增加节点的使用频度，将其转移到频度+1的链表当中
*/
public int get(int key) {
if (!kvMap.containsKey(key)) {
return -1;
}
Node node = kvMap.get(key);
DoublyLinkedList list = freqMap.get(node.freq);
list.remove(node);
if (list.isEmpty() && node.freq == minFreq) {
minFreq++;
}
node.freq++;
freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
.addFirst(node);
return node.value;
}
/*
更新
将节点的 value 更新，增加节点的使用频度，将其转移到频度+1的链表当中
新增
检查是否超过容量，若超过，淘汰 minFreq 链表的最后节点
创建新节点，放入 kvMap，并加入频度为 1 的双向链表
*/
public void put(int key, int value) {
if(kvMap.containsKey(key)) { // 更新
Node node = kvMap.get(key);
DoublyLinkedList list = freqMap.get(node.freq);
list.remove(node);
if (list.isEmpty() && node.freq == minFreq) {
minFreq++;
}
node.freq++;
freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
.addFirst(node);
node.value = value;
} else { // 新增
if (kvMap.size() == capacity) {
Node node = freqMap.get(minFreq).removeLast();
kvMap.remove(node.key);
}
Node node = new Node(key, value);
kvMap.put(key, node);
freqMap.computeIfAbsent(1, k->new DoublyLinkedList())
.addFirst(node);
minFreq = 1;
}
}
}
public static void main(String[] args) {
LFUCache cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 1 freq=2
cache.put(3, 3);
System.out.println(cache.get(2)); // -1
System.out.println(cache.get(3)); // 3 freq=2
cache.put(4, 4);
System.out.println(cache.get(1)); // -1
System.out.println(cache.get(3)); // 3 freq=3
System.out.println(cache.get(4)); // 4 freq=2
}
}
4.3 随机数
线性同余发生器
线性同余发生器（Linear Congruential Generator，简称LCG）是一种伪随机数生成器，通过一个线性同余方程来产生一系列看似随机的数值序列。其基本形式为：
X_{n+1} = (a \cdot X_n + c) \mod m其中：
X_n是当前的随机数；a是一个称为乘法因子（multiplier）的常数；c是一个称为增量（increment）的常数；m是一个称为模数（modulus）的常数；\mod表示取模运算。LCG 的特性主要由
a、c和m决定，不同的参数可以生成不同的随机数序列。然而，需要注意的是，虽然 LCG 算法是一种常见的伪随机数生成方法，但它并不适用于所有应用，因为它可能会展现出一些不够理想的统计性质，尤其是在低维空间中。为了避免一些常见的问题，选择适当的
a、c和m是至关重要的，且通常需要经过仔细的调整和测试。此外，LCG 的周期性也是一个重要的性质，周期过短可能导致在序列中出现明显的模式。尽管 LCG 在一些应用中被认为不够随机，但在一些特定的情况下，它仍然是一个简单而有效的伪随机数生成器。在实际应用中，一些改进的算法，如Mersenne Twister等，已经取代了LCG，提供了更好的统计性质和更长的周期。
/**
* <h3>随机数</h3>
*/
public class MyRandom {
// 线性同余法
private final int a;
private final int c;
private final int m;
private int seed;
public MyRandom(int a, int c, int m, int seed) {
this.a = a;
this.c = c;
this.m = m;
this.seed = seed;
}
public int nextInt() {
seed = (seed * a + c) % m;
return seed;
}
public static void main(String[] args) {
/*MyRandom r = new MyRandom(7, 0, Integer.MAX_VALUE, 1);
for (int i = 0; i < 20; i++) {
System.out.println(r.nextInt());
}*/
MyRandom r1 = new MyRandom(7, 0, 11, 1);
System.out.println(Arrays.toString(IntStream.generate(r1::nextInt).limit(30).toArray()));
// [7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5, 2, 3, 10, 4, 6, 9, 8, 1]
MyRandom r2 = new MyRandom(7, 0, Integer.MAX_VALUE, 1);
System.out.println(Arrays.toString(IntStream.generate(r2::nextInt).limit(30).toArray()));
// [7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743, 956385313, -1895237401,
// -381759919, 1622647863, -1526366847, -2094633337, -1777531471, 442181591, -1199696159, 192061479, 1344430353,
// 821077879, 1452577857, 1578110407, -1838129039, 17998615, 125990305, 881932135, 1878557649]
}
}
- 32 位随机数生成器
- 乘法会超过 int 范围导致随机性被破坏
java 版
public class MyRandom2 {
private static final long a = 0x5DEECE66DL; // 7,097,364,492,799,003,750,039,552
private static final long c = 0xBL;
private static final long m = 1L << 48;
private long seed;
public MyRandom2(long seed) {
this.seed = (seed ^ a) & (m - 1);
}
public int nextInt() {
seed = (a * seed + c) & (m - 1);
System.out.println(seed);
return ((int) (seed >>> 16));
}
public static void main(String[] args) {
Random r1 = new Random(-1);
MyRandom2 r2 = new MyRandom2(1);
System.out.println(Arrays.toString(IntStream.generate(r1::nextInt).limit(10).toArray()));
System.out.println(Arrays.toString(IntStream.generate(r2::nextInt).limit(100).toArray()));
System.out.println(Arrays.toString(DoubleStream.generate(r1::nextDouble).limit(10).toArray()));
}
}
- 0x5DEECE66DL * 0x5DEECE66DL 不会超过 long 的范围
- m 决定只取 48 位随机数
- 对于 nextInt，只取 48 位随机数的高 32 位
4.4 跳表-Leetcode 1206
不使用任何库函数，设计一个 跳表 。
跳表 是在
O(log(n))时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。例如，一个跳表包含
[30, 40, 50, 60, 70, 90]，然后增加80、45到跳表中，以下图的方式操作：
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过
O(n)。跳表的每一个操作的平均时间复杂度是O(log(n))，空间复杂度是O(n)。了解更多 : https://en.wikipedia.org/wiki/Skip_list
在本题中，你的设计应该要包含这些函数：
bool search(int target): 返回target是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值，如果num不存在，直接返回false. 如果存在多个num，删除其中任意一个即可。注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:
输入 ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] 输出 [null, null, null, null, false, null, true, false, true, false] 解释 Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4); skiplist.search(1); // 返回 true skiplist.erase(0); // 返回 false，0 不在跳表中 skiplist.erase(1); // 返回 true skiplist.search(1); // 返回 false，1 已被擦除
/**
* <h3>跳表</h3>
*/
public class SkipListLeetcode1206 {
public static void main(String[] args) {
Skiplist list = new Skiplist();
Skiplist.Node head = list.head;
Skiplist.Node n3 = new Skiplist.Node(3);
Skiplist.Node n7 = new Skiplist.Node(7);
Skiplist.Node n11 = new Skiplist.Node(11);
Skiplist.Node n12 = new Skiplist.Node(12);
Skiplist.Node n16 = new Skiplist.Node(16);
Skiplist.Node n19 = new Skiplist.Node(19);
Skiplist.Node n22 = new Skiplist.Node(22);
Skiplist.Node n23 = new Skiplist.Node(23);
Skiplist.Node n26 = new Skiplist.Node(26);
Skiplist.Node n30 = new Skiplist.Node(30);
Skiplist.Node n37 = new Skiplist.Node(37);
head.next[0] = head.next[1] = head.next[2] = n3; // 底部三层 指向 3
head.next[3] = head.next[4] = head.next[5] = head.next[6] = head.next[7] = n19;
n3.next[0] = n3.next[1] = n3.next[2] = n7;
n7.next[0] = n11;
n7.next[1] = n12;
n7.next[2] = n16;
n11.next[0] = n12;
n12.next[0] = n12.next[1] = n16;
n16.next[0] = n16.next[1] = n16.next[2] = n19;
n19.next[0] = n19.next[1] = n19.next[2] = n22;
n19.next[3] = n26;
n22.next[0] = n23;
n22.next[1] = n22.next[2] = n26;
n23.next[0] = n26;
n26.next[0] = n30;
n26.next[1] = n37;
n30.next[0] = n37;
System.out.println(Arrays.toString(list.find(30)));
// [Node(26), Node(26), Node(26), Node(26), Node(19), Node(19), Node(19), Node(19), Node(-1), Node(-1)]
System.out.println(Arrays.toString(list.find(26)));
// [Node(23), Node(22), Node(22), Node(19), Node(19), Node(19), Node(19), Node(19), Node(-1), Node(-1)]
}
private static void testRandomLevel() {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
int level = randomLevel(5);
map.compute(level, (k, v) -> v == null ? 1 : v + 1);
}
System.out.println(map.entrySet().stream().collect(
Collectors.toMap(
Map.Entry::getKey,
e -> String.format("%d%%", e.getValue() * 100 / 1000)
)
));
}
/*
设计一个方法，方法会随机返回 1~max 的数字
从 1 开始，数字的几率逐级减半，例如 max = 4，让大概
- 50% 的几率返回 1
- 25% 的几率返回 2
- 12.5% 的几率返回 3
- 12.5% 的几率返回 4
*/
/*
第一轮有 500 个(level 1) >= 0.5 退出循环，剩下 500 个(level 2)
第二轮有 250 个(level 2) >= 0.5 退出循环，剩下 125 个(level 3)
第三轮有 63 个(level 3) >= 0.5 退出循环，剩下 62 个(level 4) 由于第二个条件退出循环
*/
static Random r = new Random();
static int randomLevel(int max) {
// 50% 25% 12.5%
// return r.nextBoolean() ? 1 : r.nextBoolean() ? 2 : r.nextBoolean() ? 3 : 4;
int x = 1;
while (x < max) {
if (r.nextBoolean()) { // true of false 50%
return x;
}
x++;
}
return x;
}
static class Skiplist {
private static final int MAX = 10; // next 指针个数（一列有几个）； redis 32 java 62
private final Node head = new Node(-1);
static class Node {
int val; // 值
Node[] next = new Node[MAX]; // next 数组，右边的node数组（列）
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node(" + val + ")";
}
}
public Node[] find(int val) {
Node[] path = new Node[MAX]; // 记录路径
Node curr = head;
for (int level = MAX - 1; level >= 0; level--) { // 从上向下找
while (curr.next[level] != null && curr.next[level].val < val) { // 向右找
curr = curr.next[level];
}
path[level] = curr;
}
// System.out.println(curr);
return path;
}
public boolean search(int val) {
Node[] path = find(val);
Node node = path[0].next[0]; // 因为数据中都是比目标值小的，需要调next
return node != null && node.val == val;
}
public void add(int val) {
// 1. 确定添加位置（把 val 当作目标查询，经历的路径就可以确定添加位置）
Node[] path = find(val);
// 2. 创建新节点随机高度
Node node = new Node(val);
int level = randomLevel(MAX);
// 3. 修改路径节点 next 指针，以及新节点 next 指针
for (int i = 0; i < level; i++) {
node.next[i] = path[i].next[i];
path[i].next[i] = node;
}
}
public boolean erase(int val) {
Node[] path = find(val);
// 检查路径是否存在
Node node = path[0].next[0];
if (node == null || node.val != val) {
return false;
}
for (int i = 0; i < MAX; i++) {
if (path[i].next[i] != node) {
break;
}
path[i].next[i] = node.next[i];
}
return true;
}
}
}
下楼梯规则
- 若 next 指针为 null，或者 next 指向的节点值 >= 目标，向下找
- 若 next 指针不为 null，且 next 指向的节点值 < 目标，向右找
节点的【高度】
- 高度并不需要额外属性来记录，而是由之前节点 next == 本节点的个数来决定，或是本节点 next 数组长度
- 本实现选择了第一种方式来决定高度，本节点的 next 数组长度统一为 MAX
4.5 最小栈-Leetcode 155
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈。实现
MinStack类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
两种实现方法，一种新建一个栈，同步加入最小值。另一种将最小值和数据组成 Data 类加入栈。
关于前者解法辅助栈的详细解释：
我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
- 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
- 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
- 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
@SuppressWarnings("all")
public class MinStackLeetcode155 {
static class MinStack {
LinkedList<Integer> stack = new LinkedList<>();
LinkedList<Integer> min = new LinkedList<>(); // 同步记录最小值的栈
public MinStack() {
min.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
min.push(Math.min(val, min.peek()));
}
public void pop() {
if (stack.isEmpty()) {
return;
}
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
static class MinStack2 {
record Data(int val, int min) {
}
LinkedList<Data> stack = new LinkedList<>();
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new Data(val, val));
} else {
stack.push(new Data(val, Math.min(stack.peek().min, val)));
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().val;
}
public int getMin() {
return stack.peek().min;
}
}
public static void main(String[] args) {
MinStack stack2 = new MinStack();
stack2.push(-2);
stack2.push(0);
stack2.push(-3);
System.out.println(stack2.getMin()); // -3
stack2.pop();
System.out.println(stack2.top()); // 0
System.out.println(stack2.getMin()); // -2
}
}
4.6 TinyURL 的加密与解密-Leetcode 535
TinyURL 是一种 URL 简化服务， 比如：当你输入一个 URL
https://leetcode.com/problems/design-tinyurl时，它将返回一个简化的URLhttp://tinyurl.com/4e9iAk。请你设计一个类来加密与解密 TinyURL 。加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。
实现
Solution类：
Solution()初始化 TinyURL 系统对象。String encode(String longUrl)返回longUrl对应的 TinyURL 。String decode(String shortUrl)返回shortUrl原本的 URL 。题目数据保证给定的shortUrl是由同一个系统对象加密的。
示例：
输入：url = "https://leetcode.com/problems/design-tinyurl" 输出："https://leetcode.com/problems/design-tinyurl" 解释： Solution obj = new Solution(); string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。 string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。
public class TinyURLLeetcode535 {
public static void main(String[] args) {
CodecHashCode codec = new CodecHashCode();
String encoded = codec.encode("https://leetcode.cn/problems/1");
System.out.println(encoded);
encoded = codec.encode("https://leetcode.cn/problems/2");
System.out.println(encoded);
for (int i = 0; i <= 62; i++) {
System.out.println(i + "\t" + CodecSequence.toBase62(i)); // 62 -> AB
}
System.out.println(CodecSequence.toBase62(237849728)); // 6j9FQ
}
/*
要让【长】【短】网址一一对应
1. 用【随机数】作为短网址标识
2. 用【hash码】作为短网址标识
3. 用【递增数】作为短网址标识
1) 多线程下可以使用吗？ 不行，没考虑并发
2) 分布式下可以使用吗？ 雪花id
3) 4e9iAK是怎么生成的？
本质是高进制的数字
a-z 0-9 A-Z 62进制的数字
0 1 2 3 4 5 6 7 8 9 a b c d e f
十进制 => 十六进制
31 1f
31 % 16 = 15
31 / 16 = 1
1 % 16 = 1
1 / 16 = 0
长网址： https://leetcode.cn/problems/encode-and-decode-tinyurl/description/
对应的短网址： http://tinyurl.com/4e9iAk
*/
static class CodecSequence {
private static final char[] toBase62 = { // Base64.java
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
};
public static String toBase62(int number) {
if (number == 0) {
return String.valueOf(toBase62[0]);
}
StringBuilder sb = new StringBuilder();
while (number > 0) {
int r = number % 62;
sb.append(toBase62[r]);
number /= 62;
}
return sb.toString();
}
private final Map<String, String> longToShort = new HashMap<>();
private final Map<String, String> shortToLong = new HashMap<>();
private static final String SHORT_PREFIX = "http://tinyurl.com/";
private static int id = 1;
public String encode(String longUrl) {
String shortUrl = longToShort.get(longUrl);
if (shortUrl != null) {
return shortUrl;
}
// 生成短网址
shortUrl = SHORT_PREFIX + toBase62(id);
longToShort.put(longUrl, shortUrl);
shortToLong.put(shortUrl, longUrl);
id++;
return shortUrl;
}
public String decode(String shortUrl) {
return shortToLong.get(shortUrl);
}
}
static class CodecHashCode {
private final Map<String, String> longToShort = new HashMap<>();
private final Map<String, String> shortToLong = new HashMap<>();
private static final String SHORT_PREFIX = "http://tinyurl.com/";
public String encode(String longUrl) {
String shortUrl = longToShort.get(longUrl);
if (shortUrl != null) {
return shortUrl;
}
// 生成短网址
int id = longUrl.hashCode();
while (true) {
shortUrl = SHORT_PREFIX + id;
if (!shortToLong.containsKey(shortUrl)) {
longToShort.put(longUrl, shortUrl);
shortToLong.put(shortUrl, longUrl);
break;
}
id++; // 避免冲突
}
return shortUrl;
}
public String decode(String shortUrl) {
return shortToLong.get(shortUrl);
}
}
static class CodecRandom {
private final Map<String, String> longToShort = new HashMap<>();
private final Map<String, String> shortToLong = new HashMap<>();
private static final String SHORT_PREFIX = "http://tinyurl.com/";
public String encode(String longUrl) {
String shortUrl = longToShort.get(longUrl);
if (shortUrl != null) {
return shortUrl;
}
// 生成短网址
while (true) { // 可能 随机到同一id，不断尝试
int id = ThreadLocalRandom.current().nextInt();
shortUrl = SHORT_PREFIX + id;
if (!shortToLong.containsKey(shortUrl)) {
longToShort.put(longUrl, shortUrl);
shortToLong.put(shortUrl, longUrl);
break;
}
}
return shortUrl;
}
public String decode(String shortUrl) {
return shortToLong.get(shortUrl);
}
}
}
4.7 设计 Twitter-Leetcode 355
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近
10条推文。实现
Twitter()初始化简易版推特对象void postTweet(int userId, int tweetId)根据给定的tweetId和userId创建一条新推文。每次调用此函数都会使用一个不同的tweetId。List<Integer> getNewsFeed(int userId)检索当前用户新闻推送中最近10条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。void follow(int followerId, int followeeId)ID 为followerId的用户开始关注 ID 为followeeId的用户。void unfollow(int followerId, int followeeId)ID 为followerId的用户不再关注 ID 为followeeId的用户。
示例：
输入 ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] 输出 [null, null, [5], null, null, [6, 5], null, [5]] 解释 Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // 用户 1 发送了一条新推文 (用户 id = 1, 推文 id = 5) twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文 twitter.follow(1, 2); // 用户 1 关注了用户 2 twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6) twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的 twitter.unfollow(1, 2); // 用户 1 取消关注了用户 2 twitter.getNewsFeed(1); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2
线性合并
static class Twitter2 {
static int time;
static class Tweet {
int id;
int time;
Tweet next;
public Tweet(int id, int time, Tweet next) {
this.id = id;
this.time = time;
this.next = next;
}
public int id() {
return id;
}
public int time() {
return time;
}
}
static class User {
Integer id;
public User(Integer id) {
this.id = id;
}
Set<Integer> followees = new HashSet<>();
Tweet head = new Tweet(-1, -1, null);
}
private final Map<Integer, User> userMap = new HashMap<Integer, User>();
public void postTweet(int userId, int tweetId) {
User user = userMap.computeIfAbsent(userId, User::new);
user.head.next = new Tweet(tweetId, time++, user.head.next);
}
public List<Integer> getNewsFeed(int userId) {
User user = userMap.get(userId);
if (user == null) {
return List.of();
}
Tweet p1 = user.head.next;
for (Integer id : user.followees) {
p1 = merge(p1, userMap.get(id).head.next);
}
LinkedList<Integer> result = new LinkedList<>();
int count = 0;
while (p1 != null && count < 10) {
result.addLast(p1.id);
p1 = p1.next;
count++;
}
return result;
}
private Tweet merge(Tweet p1, Tweet p2) {
Tweet head = new Tweet(-1, -1, null);
Tweet p0 = head;
int count = 0;
while (p1 != null && p2 != null && count < 10) {
if (p1.time > p2.time) {
p0.next = new Tweet(p1.id, p1.time, null);
p0 = p0.next;
p1 = p1.next;
} else {
p0.next = new Tweet(p2.id, p2.time, null);
p0 = p0.next;
p2 = p2.next;
}
count++;
}
while (p1 != null && count < 10) {
p0.next = new Tweet(p1.id, p1.time, null);
p0 = p0.next;
p1 = p1.next;
count++;
}
while (p2 != null && count < 10) {
p0.next = new Tweet(p2.id, p2.time, null);
p0 = p0.next;
p2 = p2.next;
count++;
}
return head.next;
}
public void follow(int userId, int followeeId) {
User user = userMap.computeIfAbsent(userId, User::new);
User followee = userMap.computeIfAbsent(followeeId, User::new);
user.followees.add(followeeId);
}
public void unfollow(int userId, int followeeId) {
User user = userMap.get(userId);
if (user != null) {
user.followees.remove(followeeId);
}
}
}
优先级队列合并
// 11ms 击败 26.10%使用 Java 的用户
public class TwitterLeetcode355 {
static class Twitter {
static class Tweet {
int id;
int time;
Tweet next;
public Tweet(int id, int time, Tweet next) {
this.id = id;
this.time = time;
this.next = next;
}
public int getId() {
return id;
}
public int getTime() {
return time;
}
}
static class User {
int id;
public User(int id) {
this.id = id;
}
Set<Integer> followees = new HashSet<>();
Tweet head = new Tweet(-1, -1, null);
}
private final Map<Integer, User> userMap = new HashMap<>();
private static int time;
// 发布文章
public void postTweet(int userId, int tweetId) {
User user = userMap.computeIfAbsent(userId, User::new);
user.head.next = new Tweet(tweetId, time++, user.head.next);
}
// 新增关注
public void follow(int userId, int followeeId) {
User user = userMap.computeIfAbsent(userId, User::new);
User followee = userMap.computeIfAbsent(followeeId, User::new);
user.followees.add(followee.id);
}
// 取消关注
public void unfollow(int userId, int followeeId) {
User user = userMap.get(userId);
if (user != null) {
user.followees.remove(followeeId);
}
}
// 获取最新10篇文章（包括自己和关注用户）
public List<Integer> getNewsFeed(int userId) {
User user = userMap.get(userId);
if (user == null) {
return List.of();
}
PriorityQueue<Tweet> queue
= new PriorityQueue<>(Comparator.comparingInt(Tweet::getTime).reversed());
if(user.head.next != null) {
queue.offer(user.head.next);
}
for (Integer id : user.followees) {
User followee = userMap.get(id);
if(followee.head.next != null) {
queue.offer(followee.head.next);
}
}
List<Integer> res = new ArrayList<>();
int count = 0;
while (!queue.isEmpty() && count < 10) {
Tweet max = queue.poll();
res.add(max.id);
if (max.next != null) {
queue.offer(max.next);
}
count++;
}
return res;
}
}
public static void main(String[] args) {
// Twitter t = new Twitter();
// t.postTweet(2, 5); //0
// t.postTweet(1, 3); //1
// t.postTweet(1, 101); //2
// t.postTweet(2, 13); //3
// t.postTweet(2, 10); //4
// t.postTweet(1, 2); //5
// t.postTweet(2, 94); //6
// t.postTweet(2, 505); //7
// t.postTweet(1, 333); //8
// t.postTweet(1, 22); //9
// System.out.println(t.getNewsFeed(2)); // -> 505 94 10 13 5
// t.follow(2, 1);
// System.out.println(t.getNewsFeed(2)); // -> 22 333 505 94 2 10 13 101 3 5
// Twitter t = new Twitter();
// t.postTweet(1, 11);
// t.postTweet(2, 21);
// t.postTweet(3, 31);
// t.postTweet(4, 41);
// t.postTweet(1, 12);
// t.postTweet(2, 22);
// t.postTweet(3, 32);
// t.postTweet(3, 33);
// t.postTweet(4, 42);
// t.follow(1, 2);
// t.follow(1, 3);
// t.follow(1, 4);
// System.out.println(t.getNewsFeed(1)); // -> 42, 33, 32, 22, 12, 41, 31, 21, 11
// Twitter t = new Twitter();
// for (int i = 0; i < 11; i++) {
// t.postTweet(1, i);
// }
// System.out.println(t.getNewsFeed(1));
Twitter t = new Twitter();
t.postTweet(1, 1);
System.out.println(t.getNewsFeed(1));
t.follow(2, 1);
System.out.println(t.getNewsFeed(2));
t.unfollow(2, 1);
System.out.println(t.getNewsFeed(2));
}
}
力扣官方题解：
方法一：哈希表 + 链表
思路和算法
根据题意我们知道，对于每个推特用户，我们需要存储他关注的用户
Id，以及自己发的推文Id的集合，为了使每个操作的复杂度尽可能的低，我们需要根据操作来决定存储这些信息的数据结构。注意，由于题目中没有说明用户的Id是否连续，所以我们需要用一个以用户Id为索引的哈希表来存储用户的信息。对于操作
3和操作4，我们只需要用一个哈希表存储，即可实现插入和删除的时间复杂度都为O(1)。对于操作
1和操作2，由于操作2要知道此用户关注的人和用户自己发出的最近十条推文，因此我们可以考虑对每个用户用链表存储发送的推文。每次创建推文的时候我们在链表头插入，这样能保证链表里存储的推文的时间是从最近到最久的。那么对于操作2，问题其实就等价于有若干个有序的链表，我们需要找到它们合起来最近的十条推文。由于链表里存储的数据都是有序的，所以我们将这些链表进行线性归并即可得到最近的十条推文。这个操作与 23. 合并K个排序链表 基本等同。
如果我们直接照搬「合并K个排序链表」的解法来进行合并，那么无疑会造成空间的部分浪费，因为这个题目不要求你展示用户的所有推文，所以我们只要动态维护用户的链表，存储最近的
recentMax个推文Id即可（题目中的recentMax为10）。那么对于操作1，当发现链表的节点数等于recentMax时，我们按题意删除链表末尾的元素，再插入最新的推文Id。对于操作2，在两个链表进行线性归并的时候，只要已合并的数量等于recentMax，代表已经找到这两个链表合起来后最近的recentMax条推文，直接结束合并即可。
class Twitter {
private class Node {
// 哈希表存储关注人的 Id
Set<Integer> followee;
// 用链表存储 tweetId
LinkedList<Integer> tweet;
Node() {
followee = new HashSet<Integer>();
tweet = new LinkedList<Integer>();
}
}
// getNewsFeed 检索的推文的上限以及 tweetId 的时间戳
private int recentMax, time;
// tweetId 对应发送的时间
private Map<Integer, Integer> tweetTime;
// 每个用户存储的信息
private Map<Integer, Node> user;
public Twitter() {
time = 0;
recentMax = 10;
tweetTime = new HashMap<Integer, Integer>();
user = new HashMap<Integer, Node>();
}
// 初始化
public void init(int userId) {
user.put(userId, new Node());
}
public void postTweet(int userId, int tweetId) {
if (!user.containsKey(userId)) {
init(userId);
}
// 达到限制，剔除链表末尾元素
if (user.get(userId).tweet.size() == recentMax) {
user.get(userId).tweet.remove(recentMax - 1);
}
user.get(userId).tweet.addFirst(tweetId);
tweetTime.put(tweetId, ++time);
}
public List<Integer> getNewsFeed(int userId) {
LinkedList<Integer> ans = new LinkedList<Integer>();
for (int it : user.getOrDefault(userId, new Node()).tweet) {
ans.addLast(it);
}
for (int followeeId : user.getOrDefault(userId, new Node()).followee) {
if (followeeId == userId) { // 可能出现自己关注自己的情况
continue;
}
LinkedList<Integer> res = new LinkedList<Integer>();
int tweetSize = user.get(followeeId).tweet.size();
Iterator<Integer> it = user.get(followeeId).tweet.iterator();
int i = 0;
int j = 0;
int curr = -1;
// 线性归并
if (j < tweetSize) {
curr = it.next();
while (i < ans.size() && j < tweetSize) {
if (tweetTime.get(curr) > tweetTime.get(ans.get(i))) {
res.addLast(curr);
++j;
if (it.hasNext()) {
curr = it.next();
}
} else {
res.addLast(ans.get(i));
++i;
}
// 已经找到这两个链表合起来后最近的 recentMax 条推文
if (res.size() == recentMax) {
break;
}
}
}
for (; i < ans.size() && res.size() < recentMax; ++i) {
res.addLast(ans.get(i));
}
if (j < tweetSize && res.size() < recentMax) {
res.addLast(curr);
for (; it.hasNext() && res.size() < recentMax;) {
res.addLast(it.next());
}
}
ans = new LinkedList<Integer>(res);
}
return ans;
}
public void follow(int followerId, int followeeId) {
if (!user.containsKey(followerId)) {
init(followerId);
}
if (!user.containsKey(followeeId)) {
init(followeeId);
}
user.get(followerId).followee.add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
user.getOrDefault(followerId, new Node()).followee.remove(followeeId);
}
}
5. 股票问题
5.1 买卖股票的最佳时机
买卖股票的最佳时机 以前做过：笔记004-3.14 其他题目
给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。
class Solution {
public int maxProfit(int[] prices) {
int minPrices = prices[0];
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrices);
minPrices = Math.min(minPrices, prices[i]);
}
return maxProfit;
}
}
5.2 买卖股票的最佳时机 II
给你一个整数数组
prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。示例 2：
输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。 总利润为 4 。示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
有利润就吃，买完隔天卖，没利润就不买。贪心。
/**
* <h3>某一天买入股票，未来任意一天卖出，只能卖了再买，但可以买卖多次，并允许同一天卖出后再买入，求最大利润</h3>
*
* 有利润就买卖，只看眼前
*
*/
public class SharesIILeetcode122 {
static int maxProfit(int[] prices) {
int i = 0;
int j = 1;
int sum = 0;
while (j < prices.length) {
if (prices[j] - prices[i] > 0) { // 有利润
sum += prices[j] - prices[i];
}
i++;
j++;
}
return sum;
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{9, 3, 12, 1, 2, 3})); // 11
System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 7
}
}
力扣动态规划：
考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。
定义状态
dp[i][0]表示第i天交易完后手里没有股票的最大利润，dp[i][1]表示第i天交易完后手里持有一支股票的最大利润（i从0开始）。考虑
dp[i][0]的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即dp[i−1][1]，这时候我们要将其卖出，并获得prices[i]的收益。因此为了收益最大化，我们列出如下的转移方程：再来考虑
dp[i][1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即dp[i−1][1]，或者前一天结束时还没有股票，即dp[i−1][0]，这时候我们要将其买入，并减少prices[i]的收益。可以列出如下的转移方程：对于初始状态，根据状态定义我们可以知道第
0天交易结束的时候dp[0][0]=0，dp[0][1]=−prices[0]。因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候
dp[n−1][0]的收益必然是大于dp[n−1][1]的，最后的答案即为dp[n−1][0]。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}
注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将
dp[i−1][0]和dp[i−1][1]存放在两个变量中，通过它们计算出dp[i][0]和dp[i][1]并存回对应的变量，以便于第i+1天的状态转移即可。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp0 = 0, dp1 = -prices[0];
for (int i = 1; i < n; ++i) {
int newDp0 = Math.max(dp0, dp1 + prices[i]);
int newDp1 = Math.max(dp1, dp0 - prices[i]);
dp0 = newDp0;
dp1 = newDp1;
}
return dp0;
}
}
5.3 买卖股票的最佳时机含手续费
给定一个整数数组
prices，其中prices[i]表示第i天的股票价格 ；整数fee代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
动态规划：
与上题一样，只不过卖出是要多减去手续费。
注意到在状态转移方程中，
dp[i][0]只会从dp[i−1][0]和dp[i−1][1]转移而来，因此我们不必使用数组存储所有的状态，而是使用两个变量sell以及buy分别表示dp[..][0]和dp[..][1]直接进行状态转移即可。结构优化：减少两个变量。
/*
sell 的 两种情况 Math.max(sell, buy + prices[i] - fee)
(1) 还是上次的sell → 没有影响
(2) sell = (buy + prices[i] - fee) - prices[i] = buy - fee -> 结果没有sell，说明与上次的 sell 无关
*/
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int sell = 0, buy = -prices[0];
for (int i = 1; i < n; ++i) {
sell = Math.max(sell, buy + prices[i] - fee);
buy = Math.max(buy, sell - prices[i]); // 这种改动虽然业务含义变化了，但对结果不影响, 根据这次 sell 计算 buy
}
return sell;
}
}
可以设置 buy 的初始值为最小，可以让循环统一从 0 开始
static int maxProfit(int[] prices, int fee) {
int buy = Integer.MIN_VALUE;
int sell = 0;
for (int price : prices) {
buy = Math.max(buy, sell - price);
/*
若 max 是 上次 buy，那么显然用这次 buy 是一样的
若 max 是 上次 sell - prices[i], 则
Math.max(sell, sell - prices[i] + prices[i] - fee);
==>
Math.max(sell, sell - fee);
显然后面的式子不可能比上次 sell 更大，此时新的 sell 只由上次 sell 决定，与 上次 buy 无关
*/
sell = Math.max(sell, buy + price - fee);
}
return sell;
}
贪心算法：
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < n; ++i) {
if (prices[i] + fee < buy) {
buy = prices[i] + fee;
} else if (prices[i] > buy) {
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
}
5.4 买卖股票的最佳时机含冷冻期
给定一个整数数组
prices，其中第prices[i]表示第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1] 输出: 0
/**
* <h3>某一天买入股票，未来任意一天卖出，可以买卖多次，卖出后只能隔天再买入，求最大利润</h3>
*/
public class SharesLeetcode309 {
/*
0 1 2 3 4
1 2 3 0 2
买 -1 -2 -3 1√ 0
等 -1√ -1√ -1 1√
卖 0 1√ 2√ -1 3√
等 0 1 2√ 2
*/
static int maxProfit(int[] prices) {
if (prices.length == 1) {
return 0;
}
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
sell[0] = 0;
buy[1] = Math.max(-prices[0], -prices[1]);
sell[1] = Math.max(sell[0], buy[0] + prices[1]);
for (int i = 2; i < prices.length; i++) {
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
}
return sell[prices.length - 1];
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{1, 2, 3, 0, 2})); // 3
}
}
力扣官方题解：
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
// 这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：
// 如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。
int[][] f = new int[n][3];
f[0][0] = -prices[0];
for (int i = 1; i < n; ++i) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);// 不卖； 今天能买并且买了；
f[i][1] = f[i - 1][0] + prices[i]; // 昨天有股票，今天卖了
f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]); // 昨天卖了，买不了； 手上没股票，又没卖，说明昨天没有股票
}
return Math.max(f[n - 1][1], f[n - 1][2]);
}
}
降维：（这里就不能省略变量）
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = Math.max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = Math.max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return Math.max(f1, f2);
}
}
5.5 买卖股票的最佳时机 III
给定一个数组，它的第
i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：
输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4：
输入：prices = [1] 输出：0
/**
* <h3>某一天买入股票，未来任意一天卖出，只能先卖再买，最多买卖两次，求最大利润</h3>
*/
public class SharesIIILeetcode123 {
static int maxProfit(int[] prices) {
/*
第一次买 不依赖之前状态，以当日价格买入
第一次卖，依赖于昨天第一次买 + 当日价格
第二次买，依赖于昨天第一次卖 - 当日价格
第二次卖，依赖于昨天第二次买 + 当日价格
*/
int buy1 = Integer.MIN_VALUE;
int sell1 = 0;
int buy2 = Integer.MIN_VALUE;
int sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
}
}
5.6 买卖股票的最佳时机 IV
给你一个整数数组
prices和一个整数k，其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成
k笔交易。也就是说，你最多可以买k次，卖k次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
/**
* <h3>某一天买入股票，未来任意一天卖出，只能先卖再买，最多买卖K次，求最大利润</h3>
*/
public class SharesLeetcode188 {
static int maxProfit(int[] prices) {
int i = 0;
int j = 1;
int sum = 0;
while (j < prices.length) {
if (prices[j] - prices[i] > 0) { // 有利润
sum += prices[j] - prices[i];
}
i++;
j++;
}
return sum;
}
static int maxProfit(int k, int[] prices) {
/*
第一次买 不依赖之前状态，以当日价格买入
第一次卖，依赖于昨天第一次买 + 当日价格
第二次买，依赖于昨天第一次卖 - 当日价格
第二次卖，依赖于昨天第二次买 + 当日价格
第三次买，依赖于昨天第二次卖 - 当日价格
第三次卖，依赖于昨天第三次买 + 当日价格
...
第 k 次买，依赖于昨天第 k-1 次卖 - 当日价格
第 k 次卖，依赖于昨天第 k 次买 + 当日价格
*/
// 买卖次数 比 天数还多，导致太多循环
if (k > prices.length / 2) {
return maxProfit(prices); // 借鉴 122题 的 无限制次数 的 贪心算法
}
int[] buy = new int[k];
int[] sell = new int[k];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
buy[0] = Math.max(buy[0], -price);
sell[0] = Math.max(sell[0], buy[0] + price);
for (int i = 1; i < k; i++) {
buy[i] = Math.max(buy[i], sell[i - 1] - price);
sell[i] = Math.max(sell[i], buy[i] + price);
}
}
return sell[k - 1];
}
public static void main(String[] args) {
System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3})); // 7
System.out.println(maxProfit(2, new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
System.out.println(maxProfit(4, new int[]{1, 2, 0, 1, 0, 3, 1, 4, 5})); // 9
}
}
- 对于天数 n = 6，最多进行 3 次交易，如果此时 k > 3，意味着不限次交易
- 对于天数 n = 7，最多进行 3 次交易，如果此时 k > 3，意味着不限次交易
附录
力扣高评价题目列表
引用自 面试最常考的 100 道算法题分类整理！ - 知乎 (zhihu.com)
带 ✔️ 是本课程讲解过的
- 1. Two Sum (两数之和), Easy, 11757 likes ✔️
- 2. Add Two Numbers (两数相加), Medium, 6524 likes ✔️
- 3. Longest Substring Without Repeating Characters (无重复字符的最长子串), Medium, 5845 likes ✔️
- 4. Median of Two Sorted Arrays (寻找两个正序数组的中位数), Hard, 4303 likes
- 5. Longest Palindromic Substring (最长回文子串), Medium, 3896 likes ✔️
- 15. 3Sum (三数之和), Medium, 3582 likes ✔️
- 53. Maximum Subarray (最大子序和), Easy, 3533 likes
- 7. Reverse Integer (整数反转), Easy, 2970 likes
- 11. Container With Most Water (盛最多水的容器), Medium, 2659 likes ✔️
- 42. Trapping Rain Water (接雨水), Hard, 2552 likes ✔️
- 20. Valid Parentheses (有效的括号), Easy, 2544 likes ✔️
- 10. Regular Expression Matching (正则表达式匹配), Hard, 2273 likes
- 26. Remove Duplicates from Sorted Array (删除有序数组中的重复项), Easy, 2146 likes ✔️
- 136. Single Number (只出现一次的数字), Easy, 1958 likes ✔️
- 22. Generate Parentheses (括号生成), Medium, 1946 likes ✔️
- 206. Reverse Linked List (反转链表), Easy, 1886 likes ✔️
- 21. Merge Two Sorted Lists (合并两个有序链表), Easy, 1832 likes ✔️
- 70. Climbing Stairs (爬楼梯), Easy, 1791 likes ✔️
- 300. Longest Increasing Subsequence (最长递增子序列), Medium, 1773 likes ✔️
- 121. Best Time to Buy and Sell Stock (买卖股票的最佳时机), Easy, 1766 likes ✔️
- 72. Edit Distance (编辑距离), Hard, 1743 likes
- 14. Longest Common Prefix (最长公共前缀), Easy, 1707 likes ✔️
- 198. House Robber (打家劫舍), Medium, 1585 likes ✔️
- 9. Palindrome Number (回文数), Easy, 1568 likes
- 146. LRU Cache (LRU 缓存机制), Medium, 1544 likes ✔️
- 19. Remove Nth Node From End of List (删除链表的倒数第 N 个结点), Medium, 1494 likes ✔️
- 33. Search in Rotated Sorted Array (搜索旋转排序数组), Medium, 1493 likes
- 46. Permutations (全排列), Medium, 1484 likes ✔️
- 101. Symmetric Tree (对称二叉树), Easy, 1483 likes ✔️
- 84. Largest Rectangle in Histogram (柱状图中最大的矩形), Hard, 1472 likes
- 39. Combination Sum (组合总和), Medium, 1466 likes ✔️
- 13. Roman to Integer (罗马数字转整数), Easy, 1436 likes
- 23. Merge k Sorted Lists (合并K个升序链表), Hard, 1436 likes ✔️
- 17. Letter Combinations of a Phone Number (电话号码的字母组合), Medium, 1436 likes
- 322. Coin Change (零钱兑换), Medium, 1414 likes ✔️
- 32. Longest Valid Parentheses (最长有效括号), Hard, 1400 likes
- 287. Find the Duplicate Number (寻找重复数), Medium, 1325 likes
- 122. Best Time to Buy and Sell Stock II (买卖股票的最佳时机 II), Easy, 1306 likes ✔️
- 160. Intersection of Two Linked Lists (相交链表), Easy, 1302 likes ✔️
- 55. Jump Game (跳跃游戏), Medium, 1292 likes
- 76. Minimum Window Substring (最小覆盖子串), Hard, 1280 likes ✔️
- 200. Number of Islands (岛屿数量), Medium, 1270 likes
- 78. Subsets (子集), Medium, 1269 likes
- 31. Next Permutation (下一个排列), Medium, 1260 likes
- 96. Unique Binary Search Trees (不同的二叉搜索树), Medium, 1257 likes ✔️
- 148. Sort List (排序链表), Medium, 1248 likes
- 236. Lowest Common Ancestor of a Binary Tree (二叉树的最近公共祖先), Medium, 1238 likes ✔️
- 25. Reverse Nodes in k-Group (K 个一组翻转链表), Hard, 1230 likes
- 6. ZigZag Conversion (Z 字形变换), Medium, 1226 likes
- 152. Maximum Product Subarray (乘积最大子数组), Medium, 1223 likes
- 215. Kth Largest Element in an Array (数组中的第K个最大元素), Medium, 1211 likes ✔️
- 8. String to Integer (atoi) (字符串转换整数 (atoi)), Medium, 1168 likes
- 41. First Missing Positive (缺失的第一个正数), Hard, 1163 likes
- 283. Move Zeroes (移动零), Easy, 1162 likes ✔️
- 141. Linked List Cycle (环形链表), Easy, 1161 likes ✔️
- 98. Validate Binary Search Tree (验证二叉搜索树), Medium, 1156 likes ✔️
- 124. Binary Tree Maximum Path Sum (二叉树中的最大路径和), Hard, 1152 likes
- 105. Construct Binary Tree from Preorder and Inorder Traversal (从前序与中序遍历序列构造二叉树), Medium, 1149 likes ✔️
- 34. Find First and Last Position of Element in Sorted Array (在排序数组中查找元素的第一个和最后一个位置), Medium, 1137 likes ✔️
- 239. Sliding Window Maximum (滑动窗口最大值), Hard, 1114 likes ✔️
- 142. Linked List Cycle II (环形链表 II), Medium, 1097 likes ✔️
- 139. Word Break (单词拆分), Medium, 1097 likes
- 45. Jump Game II (跳跃游戏 II), Medium, 1094 likes
- 169. Majority Element (多数元素), Easy, 1089 likes
- 234. Palindrome Linked List (回文链表), Easy, 1072 likes ✔️
- 62. Unique Paths (不同路径), Medium, 1072 likes ✔️
- 189. Rotate Array (旋转数组), Medium, 1057 likes
- 94. Binary Tree Inorder Traversal (二叉树的中序遍历), Easy, 1052 likes ✔️
- 56. Merge Intervals (合并区间), Medium, 1051 likes
- 88. Merge Sorted Array (合并两个有序数组), Easy, 1041 likes ✔️
- 560. Subarray Sum Equals K (和为K的子数组), Medium, 1036 likes
- 279. Perfect Squares (完全平方数), Medium, 1035 likes
- 35. Search Insert Position (搜索插入位置), Easy, 1005 likes ✔️
- 24. Swap Nodes in Pairs (两两交换链表中的节点), Medium, 996 likes
- 85. Maximal Rectangle (最大矩形), Hard, 983 likes
- 28. Implement strStr() (实现 strStr()), Easy, 982 likes ✔️
- 92. Reverse Linked List II (反转链表 II), Medium, 980 likes
- 155. Min Stack (最小栈), Easy, 979 likes ✔️
- 79. Word Search (单词搜索), Medium, 979 likes
- 27. Remove Element (移除元素), Easy, 967 likes
- 51. N-Queens (N 皇后), Hard, 965 likes ✔️
- 75. Sort Colors (颜色分类), Medium, 961 likes
- 102. Binary Tree Level Order Traversal (二叉树的层序遍历), Medium, 960 likes ✔️
- 48. Rotate Image (旋转图像), Medium, 960 likes
- 95. Unique Binary Search Trees II (不同的二叉搜索树 II), Medium, 955 likes
- 64. Minimum Path Sum (最小路径和), Medium, 954 likes
- 406. Queue Reconstruction by Height (根据身高重建队列), Medium, 947 likes
- 226. Invert Binary Tree (翻转二叉树), Easy, 941 likes ✔️
- 437. Path Sum III (路径总和 III), Medium, 937 likes
- 104. Maximum Depth of Binary Tree (二叉树的最大深度), Easy, 937 likes ✔️
- 237. Delete Node in a Linked List (删除链表中的节点), Easy, 936 likes ✔️
- 337. House Robber III (打家劫舍 III), Medium, 929 likes
- 18. 4Sum (四数之和), Medium, 918 likes ✔️
- 91. Decode Ways (解码方法), Medium, 904 likes
- 207. Course Schedule (课程表), Medium, 897 likes
- 37. Sudoku Solver (解数独), Hard, 897 likes ✔️
- 175. Combine Two Tables (组合两个表), Easy, 891 likes
- 416. Partition Equal Subset Sum (分割等和子集), Medium, 886 likes
- 238. Product of Array Except Self (除自身以外数组的乘积), Medium, 885 likes
- 114. Flatten Binary Tree to Linked List (二叉树展开为链表), Medium, 877 likes
Comments NOTHING