线性结构：数组、队列、链表、栈
- 顺序存储（地址连续）
- 链式存储（地址不一定连续）
非线性结构：二维数组、多维数组、广义表、树、图
必看：学习算法和刷题的框架思维 :: labuladong的算法小抄、我的刷题心得 :: labuladong的算法小抄
①数组
❶稀疏数组
稀疏数组是一种用来压缩数据量的数据结构，简而言之，就是记录特殊值，然后剩下大量重复的数据可以消减。
例如下方是一个普通二维数组
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 2 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
这么一个二维数组，化成稀疏数组可以表示为：
行 列 值
0 6 6 2
1 1 2 1
2 2 3 2
1. 稀疏数组第一行表示原数组有多少行，多少列，有多少个非零元素（有效值）
2. 稀疏数组是从0开始的
3. 稀疏数组的行数等于有效值+1，列数固定都为3
二维数组转稀疏数组的步骤：
- 遍历二维数组，得到有效值个数 sum
- 根据 sum 创建稀疏数组 sparseArr = int [sum+1][3]
- 将有效值存入稀疏数组
还原稀疏数组步骤：
创建一个新的数组，其行和列等于稀疏数组首行数据
遍历稀疏数组，将对应数值赋值给新的数组
最后可以验证一下原始的数组和还原后的数组是否相等
//稀疏数组：用来减少数据量
public class SparseArray {
public static void main(String[] args) {
// 一、构建原始数组
// 创建一个二维数组6*6 0：没有棋子，1：黑棋 2：白棋
int[][] chessArr = new int[6][6];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
System.out.println("原始数组:");
for (int[] row : chessArr) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
System.out.println("====================");
// 二、转换成稀疏数组
int sum = 0;
//1.先遍历二维数组，获取有效值的个数
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[0].length; j++) {
if(chessArr[i][j] != 0) {
sum++;//有效值的个数
}
}
}
//2.创建对应稀疏数组
int [][]sparseArr = new int[sum+1][3];
//第一行赋值
sparseArr[0][0] = chessArr.length;
sparseArr[0][1] = chessArr[0].length;
sparseArr[0][2] = sum;
//3.遍历初始的二维数组，将非零的值，存放到稀疏数组中
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[0].length; j++) {
if (chessArr[i][j] != 0){
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
}
}
}
//4.输出稀疏数组
System.out.println("稀疏数组:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.println(sparseArr[i][0]+"\t"+sparseArr[i][1]+"\t"+sparseArr[i][2]+"\t");
}
// 三、还原数组
int [][] ChessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
ChessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("=======================");
//打印还原的数组
System.out.println("输出还原后的数组：");
for (int[] row : ChessArr2) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//四、验证两个数组是否相等，可用Arrays工具类
int flag = 0;
for (int i = 0; i < chessArr.length; i++) {
if (!Arrays.equals(chessArr[i],ChessArr2[i])){
flag++;
}
}
if (flag==0){
System.out.println("初始数组和还原后的数组相等");
}
}
}
❷数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图
maxSize 是该队列的最大容量，两个变量 front 及 rear 分别记录队列前后端的下标
class ArrayQueue {
private int MaxSize; // 队列大小
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 数组存放数据
// 一、创建队列的构造器
public ArrayQueue(int MaxSize) {
this.MaxSize = MaxSize;
arr = new int[this.MaxSize];
front = -1;
rear = -1;
}
//二、判断队列是否满
public boolean isFull() {
return rear == MaxSize - 1;
}
//三、判断队列是否空
public boolean isEmpty() {
return rear == front;
}
//四、入队
public void addQueue(int num) {
if (isFull()) {
System.out.println("队列已满，无法在进行入队操作");
return;
}
arr[++rear] = num;
}
//五、出队
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法出队");
}
return arr[++front];
}
//六、显示队列数据
public void showQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法遍历");
}
for (int i = front+1; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
//七、显示队列头数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据");
}
return arr[front + 1];
}
}
测试
public class ArrayQueueDemo {
public static void main(String[] args) {
// 构造队列
ArrayQueue queue = new ArrayQueue(5);
// 入队
queue.addQueue(1);
queue.addQueue(2);
queue.addQueue(3);
queue.addQueue(4);
queue.addQueue(5);
// 出队
System.out.println(queue.getQueue());
// 遍历队列
queue.showQueue();
// 队首
System.out.println(queue.headQueue());
}
}
❸LeetCode真题
二分法：704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] 大于nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
if(nums[mid] == target){
return mid;
} else if(nums[mid] < target){
left = mid + 1;
} else{
right = mid -1;
}
}
return -1;
}
}
双指针：27. 移除元素
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeElement(int[] nums, int val) {
//快慢指针解法
int slow = 0; //慢指针
//快指针，无论与val值是否相同每遍历一次都要移动一位
for(int fast = 0; fast < nums.length; fast++){
//快指针先走，判断快指针指向的元素是否等于val
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++; //只有当快指针不等于val的时候，慢指针才和快指针一起移动一位
}
}
return slow;
}
}
class Solution {
public int removeElement(int[] nums, int val) {
int idx = 0;
for (int x : nums) {
if (x != val) nums[idx++] = x;
}
return idx;
}
}
双指针：977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
//时间复杂度是 O(n + nlogn)
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i = 0 ; i < nums.length; i++){
nums[i] = nums[i] * nums[i];
}
Arrays.sort(nums);
return nums;
}
}
//时间复杂度为 O(n)
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int i = 0, j = nums.length - 1, k = nums.length - 1;
while(i <= j){
if(nums[i] * nums[i] > nums[j] * nums[j]){
res[k--] = nums[i] * nums[i];
i++;
} else {
res[k--] = nums[j] * nums[j];
j--;
}
}
return res;
}
}
双指针：88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1;
int t = nums1.length - 1;
while(i >= 0 && j >= 0){
if(nums1[i] > nums2[j]){
nums1[t--] = nums1[i--];
} else {
nums1[t--] = nums2[j--];
}
}
// 因为我们本身就是在往 nums1 中放元素，所以只需考虑 nums2 是否剩元素即可
while(j >= 0){
nums1[t--] = nums2[j--];
}
}
}
滑动窗口：209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
//时间复杂度 O(n^2)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE;
int sum = 0;
int sumLen = 0;
for(int i = 0 ; i < nums.length; i++){
sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(sum >= target){
sumLen = j - i + 1;
res = res > sumLen ? sumLen : res;
break;
}
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
//时间复杂度 O(n)
class Solution {
// 滑动窗口
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left];
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
模拟法：48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
本题是顺时针旋转，逆时针旋转思路一样
规律：先把二维矩阵沿对角线反转，然后反转矩阵的每一行，结果就是顺时针反转整个矩阵。
 |
 |
|---|
// 将二维矩阵原地顺时针旋转 90 度
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 先沿左上到右下的对角线镜像对称二维矩阵
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// swap(matrix[i][j], matrix[j][i]);
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
}
// 反转一维数组
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (j > i) {
// swap(arr[i], arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
}
// 将二维矩阵原地逆时针旋转 90 度
class Solution {
void rotate2(int[][] matrix) {
int n = matrix.length;
// 沿左下到右上的对角线镜像对称二维矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
// swap(matrix[i][j], matrix[n-j-1][n-i-1])
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][n - i - 1];
matrix[n - j - 1][n - i - 1] = temp;
}
}
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
}
void reverse(int[] arr) { /* 见上文 */}
}
模拟法：54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界
| 打印方向 | 1. 根据边界打印 | 2. 边界向内收缩 | 3. 是否打印完毕 |
|---|---|---|---|
| 从左向右 | 左边界l ，右边界 r |
上边界 t 加 1 |
是否 t > b |
| 从上向下 | 上边界 t ，下边界b |
右边界 r 减 1 |
是否 l > r |
| 从右向左 | 右边界 r ，左边界l |
下边界 b 减 1 |
是否 t > b |
| 从下向上 | 下边界 b ，上边界t |
左边界 l 加 1 |
是否 l > r |
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int n = matrix[0].length, m = matrix.length;
int l = 0, r = n - 1, t = 0, b = m - 1;
while(res.size() < m * n){
if(t <= b){
for(int i = l; i <= r; i++) res.add(matrix[t][i]); // left to right.
t++; // 上边界下移
}
if(l <= r){
for(int i = t; i <= b; i++) res.add(matrix[i][r]); // top to bottom.
r--; // 右边界左移
}
if(t <= b){
for(int i = r; i >= l; i--) res.add(matrix[b][i]); // right to left.
b--; // 下边界上移
}
if(l <= r){
for(int i = b; i >= t; i--) res.add(matrix[i][l]); // bottom to top.
l++; // 左边界右移
}
}
return res;
}
}
模拟法： 59. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
思路：
- 生成一个
n×n空矩阵res，随后模拟整个向内环绕的填入过程：- 定义当前左右上下边界
l,r,t,b，初始值num = 1，迭代终止值end = n * n； - 当
num <= end时，始终按照从左到右从上到下从右到左从下到上填入顺序循环，每次填入后：- 执行
num += 1：得到下一个需要填入的数字； - 更新边界：例如从左到右填完后，上边界
t += 1，相当于上边界向内缩 1。
- 执行
- 使用
num <= end而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
- 定义当前左右上下边界
- 最终返回
res即可。
class Solution {
public int[][] generateMatrix(int n) {
int l = 0, r = n - 1, t = 0, b = n - 1;
int[][] res = new int[n][n];
int num = 1; // 需要填入矩阵的数字
while(num <= n * n){
if(t <= b){
// 从左到右
for(int i = l; i <= r; i++) res[t][i] = num++;
t++; // 上边界下移
}
if(l <= r){
// 从上到下
for(int i = t; i <= b; i++) res[i][r] = num++;
r--; // 右边界左移
}
if(t <= b){
// 从右到左
for(int i = r; i >= l; i--) res[b][i] = num++;
b--; // 下边界上移
}
if(l <= r){
// 从下到上
for(int i = b; i >= t; i--) res[i][l] = num++;
l++; // 左边界右移
}
}
return res;
}
}
模拟法： 73. 矩阵置零
给定一个 m*n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
思路一: 用 O(m+n)额外空间
两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}
class Solution {
public void setZeroes(int[][] matrix) {
Set<Integer> row_zero = new HashSet<>();
Set<Integer> col_zero = new HashSet<>();
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
row_zero.add(i);
col_zero.add(j);
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (row_zero.contains(i) || col_zero.contains(j)) matrix[i][j] = 0;
}
}
}
}
模拟法：915. 分割数组
给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
left中的每个元素都小于或等于right中的每个元素。left和right都是非空的。left的长度要尽可能小。
在完成这样的分组后返回 left 的 长度。
用例可以保证存在这样的划分方法。
示例 1：
输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]
示例 2：
输入：nums = [1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]
两次遍历：O(n)
先通过一次遍历（从后往前）统计出所有后缀的最小值
minRight（使用数组进行维护）然后再通过第二次遍历（从前往后）统计每个前缀的最大值
maxLeft（使用单变量进行维护）第一个满足
maxLeft ≤ minRight[i + 1]的 i 即为答案，此时 left 的长度为 i+1，因此答案需返回 i+1。
class Solution {
public int partitionDisjoint(int[] nums) {
int[] minRight = new int[nums.length];
minRight[nums.length - 1] = nums[nums.length - 1];
for(int i = nums.length - 2; i >= 0; i--){
minRight[i] = Math.min(nums[i], minRight[i + 1]);
}
int maxLeft = 0;
for(int i = 0; i < nums.length - 1; i++){
maxLeft = Math.max(maxLeft, nums[i]);
if(maxLeft <= minRight[i + 1]){
return i + 1;
}
}
return 0;
}
}
哈希表：1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
//暴力法O(n^2)
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
return new int[]{i,j};
}
}
}
return new int[0];
}
}
//哈希表O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]),i};
}
map.put(nums[i],i);
}
return new int[0];
}
}
摩尔投票法：169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
方法一：哈希法Map
遍历整个数组，对记录每个数值出现的次数(利用 HashMap，其中 key 为数值，value 为出现次数)； 接着遍历 HashMap ，寻找 value > nums.length / 2 的 key 即可。
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
if(map.get(num) > nums.length / 2){
return num;
}
}
return 0;
}
}
方法二：排序法
既然是寻找数组中出现次数 > ⌊ n/2 ⌋ 的元素，那排好序之后的数组中，这个元素占一半还多，则nums[nums.length / 2] 必是要找元素
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
方法三：摩尔投票法
我们维护一个候选众数
target和它出现的次数count。初始时target可以为任意值，count为0；我们遍历数组
nums中的所有元素，对于每个元素num，在判断num之前，如果count的值为0，我们先将num的值赋予target，随后我们判断num：如果
num与target相等，那么计数器count的值增加1；如果
num与target不等，那么计数器count的值减少1。
在遍历完成后，
target即为整个数组的众数。
class Solution {
public int majorityElement(int[] nums) {
int target = 0; // 候选众数
int count = 0; // 计数器
for (int num : nums) {
if (count == 0) {
target = num; // 当计数器为 0 时，假设 num 就是众数
count = 1; // 众数出现了一次
} else if (num == target) {
count++; // 如果遇到的是目标众数，计数器累加
} else {
count--; // 如果遇到的不是目标众数，计数器递减
}
//count += (num == target ? 1 : -1);
}
return target;
}
}
摩尔投票法：229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：nums = [1,2]
输出：[1,2]
方法一：哈希法Map
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
List<Integer> ans = new ArrayList<>();
for (int i : map.keySet()) {
if (map.get(i) > n / 3) ans.add(i);
}
return ans;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
方法二：摩尔投票法
class Solution {
public List<Integer> majorityElement(int[] nums) {
int target1 = 0, count1 = 0;
int target2 = 0, count2 = 0;
// 投票
for(int num : nums) { // 投票
if(num == target1) { //如果该元素为第一个元素，则计数加1
count1++;
} else if(num == target2) { //如果该元素为第二个元素，则计数加1
count2++;
} else if(count1 == 0) { // 选择第一个元素
target1 = num;
count1++;
} else if(count2 == 0) { // 选择第二个元素
target2 = num;
count2++;
} else { //如果三个元素均不相同，则相互抵消1次
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// 计数
// 找到了两个候选人之后，需要确定票数是否满足大于 n/3
for(int num : nums) {
if(num == target1) {
count1++;
} else if (num == target2) {
count2++;
}
}
List<Integer> list = new ArrayList<> (); // 统计
if(count1 > nums.length / 3) list.add(target1);
if(count2 > nums.length / 3) list.add(target2);
return list;
}
}
模拟哈希表： 448. 找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
模拟哈希表
拿一个哈希表去记录每个出现过的num，然后遍历一遍哈希表，这样没出现过的num就可以直接保存下来。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int count[] = new int[nums.length + 1];
for(int num : nums){
count[num]++;
}
List<Integer> list = new ArrayList<>();
for(int i = 1; i < count.length; i++){
if(count[i] == 0){
list.add(i);
}
}
return list;
}
}
原地哈希
把对应的值放到正确的位置上，所以，「值不配位」的情况即缺失的位置索引和重复的值数字。
排序：274. H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。
如果 h 有多种可能的值，**h 指数** 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：
输入：citations = [1,3,1]
输出：1
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0;
for(int i = citations.length - 1; i >= 0; i--){
if(citations[i] > h){
h++;
}
}
return h;
}
}
防御式编程思想：605. 种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
防御式编程思想：在 flowerbed 数组两端各增加一个 0， 这样处理的好处在于不用考虑边界条件，任意位置处只要连续出现三个 0 就可以栽上一棵花。
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n)
// 在 flowerbed 数组两端各增加一个 0
int[] arr = new int[flowerbed.length + 2];
System.arraycopy(flowerbed, 0, arr, 1, flowerbed.length);
for(int i = 1; i < arr.length - 1; i++){
// 连续出现三个 0 就可以栽上一棵花
if(arr[i - 1] == 0 && arr[i] == 0 && arr[i + 1] == 0){
arr[i] = 1; // 在 i 处栽上花
n--;
}
}
return n <= 0; // n 小于等于 0 ，表示可以栽完花
}
}
334. 递增的三元子序列
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
假设 first 和 second 是有序的，且开始 first < second，依次遍历，获得 third
- 如果 third 大于 second，说明满足条件
first<second<third，直接返回 - 否则看 third 落在哪个区间
first<third，则对 second 进行赋值为 third，这样后续遍历third > second就会满足条件first>third，则将 first 进行赋值为 third，因为在数组中肯定有比 second 小的数
class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) {
return false;
}
int first = nums[0];
int second = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
int third = nums[i];
if (third > second) {
return true;
}
if (first < third) {
second = third;
} else {
first = third;
}
}
return false;
}
}
443. 压缩字符串
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
示例 1：
输入：chars = ["a","a","b","b","c","c","c"]
输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
示例 2：
输入：chars = ["a"]
输出：返回 1 ，输入数组的前 1 个字符应该是：["a"]
解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。
解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
使用两个指针 i 和 j 分别指向「当前处理到的位置」和「答案待插入的位置」：
i指针一直往后处理，每次找到字符相同的连续一段 [i,idx)，令长度为 len；- 将当前字符插入到答案，并让
j指针后移：chars[j++] = chars[i]； - 检查长度 len 是否大于 1，如果大于 1，需要填入字符数量。
- 处理 len， 依次将个位数、十位数 。。。 填入chars数组，并更新
j指针； - 更新
i和len，代表循环处理下一字符。
class Solution {
public int compress(char[] chars) {
int n = chars.length;
int i = 0; // 当前处理到的位置
int j = 0; // 答案待插入的位置
while(i < n){
int idx = i;
while(idx < n && chars[i] == chars[idx]) idx++;
chars[j++] = chars[i]; // 填入当前字符
int len = idx - i; // 累计到的相同字符个数
// 如果当前字符个数>1，需要填入字符数量
if (len > 1) {
int count = len; // 防止直接修改 len
int lenCount = 0; // len 的位数（重复字符位数）
// 计算位数
while (count != 0) {
lenCount++;
count /= 10;
}
int t = j + lenCount - 1; // 数字要插入的位置
// 依次将个位数、十位数 。。。 填入chars数组
while (len != 0) {
int num = len % 10;
len /= 10;
chars[t--] = (char)(num + '0');
}
j += lenCount; // 更新压缩字符串待插入位置
}
// 处理下一字符
i = idx;
len = 0;
}
return j;
}
}
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[(i + k) % n] = nums[i];
}
System.arraycopy(arr, 0, nums, 0, n);
}
}
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
// 翻转数组[start,end]元素
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
巧妙记录每个元素的左右乘积
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
当前元素的所有左边元素乘积
| 左边元素 | 结果 | |
|---|---|---|
| res[0] | p=1 | 1 |
| res[1] | nums[0] | 1 |
| res[2] | nums[0]*nums[1] | 1*2 |
| res[3] | nums[0]*nums[1]*nums[2] | 6 |
当前元素的所有右边元素乘积
| 右边元素乘积 | 结果 | |
|---|---|---|
| res[0] | nums[1]*nums[2]*nums[3] | 24*1=24 |
| res[1] | nums[2]*nums[3] | 12*1=12 |
| res[2] | nums[3] | 4*2=8 |
| res[3] | q=1 | 1*6=6 |
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
int p = 1, q = 1;
// 计算左边元素乘积
for (int i = 0; i < nums.length; i++) {
res[i] = p;
p *= nums[i];
}
// 计算左边元素乘积
for (int i = nums.length - 1; i > 0 ; i--) {
q *= nums[i];
res[i - 1] *= q;
}
return res;
}
}
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
示例 2：
输入：nums = [3,4,-1,1]
输出：2
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
哈希表
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
for (int i = 1; i <= len ; i++) {
if (!set.contains(i)){
return i;
}
}
return len + 1;
}
}
原地交换
public class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 满足在指定范围内、并且没有放在正确的位置上，才交换
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
// 例如：数值 3 应该放在索引 2 的位置上
swap(nums, nums[i] - 1, i);
}
}
// [1, -1, 3, 4]
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 都正确则返回数组长度 + 1
return len + 1;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
哈希表
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums) {
if(set.contains(num)) return num;
set.add(num);
}
return -1;
}
}
原地交换
class Solution {
public int findRepeatNumber(int[] nums) {
for(int i = 0; i < nums.length; i++){
//当前元素不在对应的位置上
while(nums[i] != nums[nums[i]]) {
//交换两个元素，重复循环，继续对当前下标的元素进行下标匹配。
swap(nums, i, nums[i]);
}
}
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != i) {
return nums[i];
}
}
return -1;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
442. 数组中重复的数据
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]
示例 2：
输入：nums = [1,1,2]
输出：[1]
示例 3：
输入：nums = [1]
输出：[]
原地交换
class Solution {
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
while (nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
res.add(nums[i]);
}
}
return res;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
134. 加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
把这个题理解成下边的图就可以。
每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发，还可以回到该节点。只能顺时针方向走。
考虑暴力破解。
考虑从第 0 个点出发，能否回到第 0 个点。
考虑从第 1 个点出发，能否回到第 1 个点。
考虑从第 2 个点出发，能否回到第 2 个点。
… …
考虑从第 n 个点出发，能否回到第 n 个点。
由于是个圆，得到下一个点的时候我们需要取余数。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
//考虑从每一个点出发
for (int i = 0; i < n; i++) {
int j = i;
int remain = gas[i];
//当前剩余的油能否到达下一个点
while (remain - cost[j] >= 0) {
//减去花费的加上新的点的补给
remain = remain - cost[j] + gas[(j + 1) % n];
j = (j + 1) % n;
//j 回到了 i
if (j == i) {
return i;
}
}
}
//任何点都不可以
return -1;
}
}
4. 寻找两个正序数组的中位数 - 力扣（Leetcode）
②链表
❶单向链表
特点
- 链表是以节点的方式来存储，是链式存储
- 每个节点包含 data 域 （存储数据），next 域（指向下一个节点）
- 链表的各个节点不一定是连续存储的
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
/**
* 定义节点
*/
class StudentNode {
int id;
String name;
StudentNode next;
public StudentNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
/**
* 创建链表
*/
class singleLinkedList {
//头节点，防止被修改，设置为私有的
private StudentNode head = new StudentNode(0, "");
//插入节点
public void addNode(StudentNode node) {
//因为头节点不能被修改，所以创建一个辅助节点
StudentNode temp = head;
//找到最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
//按id顺序插入节点
public void addByOrder(StudentNode node) {
//如果没有首节点，就直接插入
if (head.next == null) {
head.next = node;
return;
}
//辅助节点，用于找到插入位置和插入操作
StudentNode temp = head;
//节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
while (temp.next != null && temp.next.id < node.id) {
temp = temp.next;
}
//如果temp的下一个节点存在，则执行该操作
//且插入操作，顺序不能换
if (temp.next != null) {
node.next = temp.next;
}
temp.next = node;
}
//遍历链表
public void traverseNode() {
if (head.next == null) {
System.out.println("链表为空");
}
StudentNode temp = head;
while (temp.next != null) {
System.out.println(temp.next);
temp = temp.next;
}
}
//根据id来修改节点信息
public void changeNode(StudentNode node) {
if (head == null) {
System.out.println("链表为空，请先加入该学生信息");
return;
}
StudentNode temp = head;
//遍历链表，找到要修改的节点
while (temp.next != null && temp.id != node.id) {
temp = temp.next;
}
//如果temp已经是最后一个节点，判断id是否相等
if (temp.id != node.id) {
System.out.println("未找到该学生的信息，请先创建该学生的信息");
return;
}
//修改信息
temp.name = node.name;
}
//删除节点
public void deleteNode(StudentNode node) {
if (head.next == null) {
System.out.println("链表为空");
return;
}
StudentNode temp = head;
//遍历链表，找到要删除的节点
while (temp.next != null && temp.next.id != node.id) {
temp = temp.next;
}
if(temp.next == null){
System.out.println("要删除的节点不存在");
return;
}
//删除该节点
temp.next = temp.next.next;
}
//得到第index个的节点
public StudentNode getNodeByIndex(int index) {
if (head.next == null) {
System.out.println("链表为空!");
}
StudentNode temp = head;
int length = 0;
while (temp.next != null) {
temp = temp.next;
length++;
}
if (index > length) {
throw new RuntimeException("链表越界");
}
temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
//逆序遍历
public void reverseTraverse() {
if (head == null) {
System.out.println("链表为空");
}
StudentNode temp = head;
//创建栈，用于存放遍历到的节点
Stack<StudentNode> stack = new Stack<>();
while (temp.next != null) {
stack.push(temp.next);
temp = temp.next;
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
public class SingleLinkedListDemo {
public static void main(String[] args) {
singleLinkedList linkedList = new singleLinkedList();
//创建学生节点，并插入链表
System.out.println("插入节点1和3：");
StudentNode student1 = new StudentNode(1, "Jack");
StudentNode student3 = new StudentNode(3, "Tom");
linkedList.addNode(student1);
linkedList.addNode(student3);
linkedList.traverseNode();
//按id大小插入
System.out.println("有序插入节点2：");
StudentNode student2 = new StudentNode(2, "Jerry");
linkedList.addByOrder(student2);
linkedList.traverseNode();
//按id修改学生信息
System.out.println("修改节点1信息：");
student2 = new StudentNode(1, "Jack2");
linkedList.changeNode(student2);
linkedList.traverseNode();
//获得第2个节点
System.out.println("获得第2个节点：");
System.out.println(linkedList.getNodeByIndex(2));
//根据id删除学生信息
System.out.println("删除学生信息：");
student2 = new StudentNode(1, "Jack2");
linkedList.deleteNode(student2);
linkedList.traverseNode();
//倒叙遍历链表
System.out.println("倒序遍历链表：");
linkedList.reverseTraverse();
}
}
链表为空
插入节点1和3：
StudentNode{id=1, name='Jack'}
StudentNode{id=3, name='Tom'}
有序插入节点2：
StudentNode{id=1, name='Jack'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
修改节点1信息：
StudentNode{id=1, name='Jack2'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
获得第2个节点：
StudentNode{id=2, name='Jerry'}
删除学生信息：
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
倒序遍历链表：
StudentNode{id=3, name='Tom'}
StudentNode{id=2, name='Jerry'}
❷双向链表
/**
* 定义节点
*/
class HeroNode {
int id;
String name;
HeroNode next;
HeroNode pre;
public HeroNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "HeroNode{id=" + id + ", name=" + name + "}";
}
}
/**
* 创建一个双向链表的类
*/
class DoubleLinkedList {
//初始化一个头节点，头节点不动，不存放具体的数据
HeroNode head = new HeroNode(0, "");
//初始化一个尾节点，指向最后一个元素，默认等于head
HeroNode tail = head;
//遍历打印双向链表的方法
public void list() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
//新增节点
public void add(HeroNode heroNode) {
tail.next = heroNode;
heroNode.pre = tail;
tail = heroNode;
}
//有序新增节点
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
// 标记添加的编号是否已经存在
boolean flag = false;
while (temp.next != null && temp.next.id <= heroNode.id) {
if (temp.next.id == heroNode.id) {
flag = true;
}
temp = temp.next;
}
// 判断flag
if (flag) {
System.out.printf("英雄编号【%d】已经存在了\n", heroNode.id);
} else {
// 插入到链表中
// 1、将【heroNode的next】设置为【temp的next】
heroNode.next = temp.next;
// 判断是不是加在链表最后
if (temp.next != null) {
// 2、将【temp的next的pre】设为为【heroNode】
temp.next.pre = heroNode;
}
// 3、将【temp的next】设置为【heroNode】
temp.next = heroNode;
// 4、将【heroNode的pre】设置为【temp】
heroNode.pre = temp;
}
}
//修改节点
public void update(HeroNode heroNode) {
// 判断是否为空
if (head.next == null) {
System.out.println("链表为空~~");
return;
}
// 找到需要修改的节点
HeroNode temp = head.next;
// 表示是否找到这个节点
boolean flag = false;
while (temp != null) {
if (temp.id == heroNode.id) {
flag = true;
break;
}
temp = temp.next;
}
// 根据flag判断是否找到要修改的节点
if (flag) {
temp.name = heroNode.name;
} else { // 没有找到
System.out.printf("没有找到编号为 %d 的节点，不能修改\n", heroNode.id);
}
}
//删除节点
public void delete(int id) {
// 判断当前链表是否为空
if (head.next == null) {
System.out.println("链表为空，无法删除");
return;
}
HeroNode temp = head;
// 标志是否找到删除节点
boolean flag = false;
while (temp.next != null) {
// 已经找到链表的最后
if (temp.id == id) {
// 找到待删除节点
flag = true;
break;
}
temp = temp.next;
}
// 判断flag，此时找到要删除的节点就是temp
if (flag) {
// 可以删除，将【temp的pre的next域】设置为【temp的next域】
temp.pre.next = temp.next;
// 如果是最后一个节点，就不需要指向下面这句话，否则会出现空指针 temp.next.pre = null.pre
if (temp.next != null) {
temp.next.pre = temp.pre;
}
}
}
}
public class DoubleLinkedListDemo {
public static void main(String[] args) {
System.out.println("双向链表:");
// 创建节点
HeroNode her1 = new HeroNode(1, "宋江");
HeroNode her2 = new HeroNode(2, "卢俊义");
HeroNode her3 = new HeroNode(3, "吴用");
HeroNode her4 = new HeroNode(4, "林冲");
// 创建一个双向链表对象
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(her1);
doubleLinkedList.add(her2);
doubleLinkedList.add(her3);
doubleLinkedList.add(her4);
doubleLinkedList.list();
// 修改
HeroNode newHeroNode = new HeroNode(4, "公孙胜");
doubleLinkedList.update(newHeroNode);
System.out.println("修改节点4:");
doubleLinkedList.list();
// 删除
doubleLinkedList.delete(3);
System.out.println("删除节点3");
doubleLinkedList.list();
// 测试有序新增
System.out.println("测试有序增加链表：");
DoubleLinkedList doubleLinkedList1 = new DoubleLinkedList();
doubleLinkedList1.addByOrder(her3);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her4);
doubleLinkedList1.addByOrder(her4);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her1);
doubleLinkedList1.list();
}
}
双向链表:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=林冲}
修改节点4:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=公孙胜}
删除节点3
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=4, name=公孙胜}
测试有序增加链表：
英雄编号【2】已经存在了
英雄编号【4】已经存在了
英雄编号【2】已经存在了
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=公孙胜}
❸循环链表
❹LeetCode真题
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
/**
* 添加虚节点方式
* 时间复杂度 O(n)
* 空间复杂度 O(1)
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
// 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
/**
* 不添加虚拟节点and pre Node方式
* 时间复杂度 O(n)
* 空间复杂度 O(1)
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//去除开头节点
while(head != null && head.val == val){
head = head.next;
}
ListNode cur = head;
while(cur != null){
while(cur.next != null && cur.next.val == val){
cur.next = cur.next.next;
}
cur = cur.next;
}
return head;
}
}
707. 设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第
index个节点的值。如果索引无效，则返回-1。 - addAtHead(val)：在链表的第一个元素之前添加一个值为
val的节点。插入后，新节点将成为链表的第一个节点。 - addAtTail(val)：将值为
val的节点追加到链表的最后一个元素。 - addAtIndex(index,val)：在链表中的第
index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 - deleteAtIndex(index)：如果索引
index有效，则删除链表中的第index个节点。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
/**
* 单链表
*/
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size) return -1;
ListNode cur = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for(int i = 0; i <= index; i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if(index > size) return;
if(index < 0) index = 0;
ListNode pre = head;
ListNode addNode = new ListNode(val);
//找到要插入节点的前驱
for(int i = 0; i < index; i++){
pre = pre.next;
}
addNode.next = pre.next;
pre.next = addNode;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
ListNode pre = head;
//找到要删除节点的前驱
for(int i = 0; i < index; i++){
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
}
/**
*双链表
*/
class ListNode {
int val;
ListNode prev, next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head, tail;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
head.next=tail;
tail.prev=head;
}
public int get(int index) {
//判断index是否有效
if(index < 0 || index >= size) return -1;
ListNode cur = head;
//判断是哪一边遍历时间更短
if(index > size / 2) {
cur = tail;
for(int i = size; i > index; i--){
cur = cur.prev;
}
} else {
//包含一个虚拟头节点，所以查找第 index+1 个节点
for(int i = 0; i <= index; i++){
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if(index > size) return;
if(index < 0) index = 0;
//找到前驱
ListNode pre = head;
for(int i = 0; i < index; i++){
pre = pre.next;
}
//新建结点
ListNode newNode = new ListNode(val);
//插入节点
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
size++;//节点数+1
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode pre = head;
//找到要删除节点的前驱
for(int i = 0; i < index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
size--;
}
}
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
迭代法
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while(cur != null){
// 先存储后面节点
ListNode tmp = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = tmp;
}
return pre;
}
}
递归法
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
public ListNode reverse(ListNode pre, ListNode cur){
if (cur == null) {
return pre;
}
// 先存储后面节点
ListNode tmp = cur.next;
// 逐个结点反转
cur.next = pre;
//指针向后移动
return reverse(cur, tmp);
}
}
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 新的头结点
ListNode last = reverseList(head.next);
// 倒数第二节点和倒数第一个节点翻转
head.next.next = head;
// head 变成了最后一个节点，要指向 null
head.next = null;
return last;
}
}
栈实现
//栈实现1(不推荐，效率不高)
class Solution {
public ListNode reverseList(ListNode head) {
Deque<ListNode> stack = new ArrayDeque<>();
while(head != null){
stack.push(head);
head = head.next;
}
ListNode dummy = new ListNode(0);
ListNode temp = dummy;
while(!stack.isEmpty()){
temp.next = stack.pop();
temp = temp.next;
}
temp.next = null; //最后节点不接null会形成环链
return dummy.next;
}
}
//栈实现2(不推荐，效率不高)
class Solution {
public ListNode reverseList(ListNode head) {
Deque<ListNode> stack = new ArrayDeque<>();
while(head != null){
stack.add(head);
head = head.next;
}
ListNode dummy = new ListNode(0),
ListNode temp = dummy;
while(stack.size() != 0){
temp.next = new ListNode(stack.pop());//防止形成环链
temp = temp.next;
}
return dummy.next;
}
}
92. 反转链表 II
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
递归法：O(n)
- 1.返回值：交换完成的子链表
- 2.调换：设需要交换的两个点为 first 和 second，first 连接后面交换完成的子链表，second 连接 first
- 3.终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
}
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) {
return head;
}
// 区间 [a, b) 包含 k 个待反转元素
ListNode a = head;
ListNode b = head;
for(int i = 0; i < 2; i++){
// 不足 k 个，不需要反转，base case
if(b == null) {
return head;
}
b = b.next;
}
// 反转前 k 个元素
ListNode newhead = reverse(a, b);
// 拼接前k个和后k个
a.next = swapPairs(b);
return newhead;
}
/* 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b){
ListNode prev = null;
ListNode curr = a;
ListNode next = null;
while(curr != b){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
迭代法：O(n)
 |
 |
|---|
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0, head); //虚拟头节点
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2; //步骤一
node1.next = node2.next; //步骤二
node2.next = node1; //步骤三
temp = node1; //后移两位，准备下一轮交换
}
return dummyHead.next;
}
}
25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
先翻转k个，再翻转k个，再拼接这2k个，以此类推
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) {
return head;
}
// 区间 [a, b) 包含 k 个待反转元素
ListNode a = head;
ListNode b = head;
for(int i = 0; i < k; i++){
// 不足 k 个，不需要反转，base case
if(b == null) {
return head;
}
b = b.next;
}
// 反转前 k 个元素
ListNode newhead = reverse(a, b);
// 拼接前k个和后k个
a.next = reverseKGroup(b, k);
return newhead;
}
/* 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b){
ListNode prev = null;
ListNode curr = a;
ListNode temp = null;
while(curr != b){
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}
class Solution {
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode cur = head;
int count = 0;
while (cur != null && count != k) {
cur = cur.next;
count++;
}
if (count == k) {
cur = reverseKGroup(cur, k);
while (count-- > 0) {
ListNode tmp = head.next;
head.next = cur;
cur = head;
head = tmp;
}
head = cur;
}
return head;
}
}
变形题：k组链表整体翻转
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
输入：head = [1,2,3,4,5], k = 2
输出：[3,4,1,2,5]
输入：head = [1,2,3,4,5], k = 3
输出：[1，2，3，4，5]
这道题可以使用递归的方法来解决，具体步骤如下：
首先，我们需要找到每一组需要翻转的链表的起始节点和结束节点。
然后，我们需要对这一组链表进行翻转操作。
最后，我们需要将翻转后的链表与下一组翻转后的链表连接起来。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
暴力法：O(n)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//计算链表长度
int length = 0;
ListNode temp = head;
while (temp != null) {
++length;
temp = temp.next;
}
//删除节点
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
for (int i = 0; i < length - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
}
双指针法：O(n)
由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first比 second超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。
具体地，初始时 first和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时 first 比 second 超前了 n 个节点。在这之后，同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first为空指针）时，second 恰好指向倒数第 n 个节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
//快指针先走n步
for (int i = 0; i < n; i++) {
first = first.next;
}
//当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
2095. 删除链表的中间节点
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
- 对于
n=1、2、3、4和5的情况，中间节点的下标分别是0、1、1、2和2。
示例 1：
输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。
示例 2：
输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。
示例 3：
输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。
使用slow记录慢指针，fast记录快指针。 当fast的再一次移动就结束时，说明slow的再一次移动也将到达中间点，那么这个时候就可以直接用slow.next = slow.next.next来去掉中间节点。
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null){
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return head;
}
}
class Solution {
public ListNode deleteMiddle(ListNode head) {
ListNode dummy = new ListNode(-1, head); // 哨兵
ListNode slow = dummy;
ListNode fast = dummy.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
328. 奇偶链表
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
用odd记录奇数节点的链表，even记录偶数节点的链表， 最后把odd尾部节点指向even的头结点，返回head即可。
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：
- 指针
A先遍历完链表headA，再开始遍历链表headB，当走到node时，共走步数为：a+(b−c) - 指针
B先遍历完链表headB，再开始遍历链表headA，当走到node时，共走步数为：b+(a−c)
a+(b−c) = b+(a−c)，此时指针 A , B 重合 ，并有两种情况：
- 若两链表 有 公共尾部 (即 c>0 ) ：指针
A,B同时指向「第一个公共节点」node。 - 若两链表 无 公共尾部 (即 c=0) ：指针
A,B同时指向 null 。
因此返回 A 即可。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A != B){
if(A != null) A = A.next;
else A = headB;
if(B != null) B = B.next;
else B = headA;
}
return A;
}
}
//简化代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A != B){
A = A != null ? A.next : headB;
B = B != null ? B.next : headA;
}
return A;
}
}
141. 环形链表
快慢指针法
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇，说明含有环
if(fast == slow) return true;
}
// 不包含环
return false;
}
}
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
进阶：你是否可以使用 O(1) 空间解决此题？
方法一：哈希表
遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode temp = head;
while(temp != null){
if(set.contains(temp)){
return temp;
}
set.add(temp);
temp = temp.next;
}
return null;
}
}
时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
方法二：快慢指针
当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 当快慢指针相遇时，让其中任一个指针指向头节点
if (fast == slow) {
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
空间复杂度：O(1)
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟头节点
ListNode dummy = new ListNode(-1);
ListNode list = dummy;
while(list1 != null && list2 != null){
// 比较 list1 和 list2 两个指针
// 将值较小的的节点接到 list 指针
if(list1.val < list2.val){
list.next = list1;
list1 = list1.next;
} else {
list.next = list2;
list2 = list2.next;
}
list = list.next;
}
if(list1 != null){
list.next = list1;
}
if(list2 != null){
list.next = list2;
}
//list.next = (list1 == null ? list2 : list1);
return dummy.next;
}
}
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
逐一合并两条链表
//时间复杂度：O(NK) K 条链表的总结点数是 N
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for (ListNode list: lists) {
res = mergeTwoLists(res, list);
}
return res;
}
//合并两条链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟头节点
ListNode dummy = new ListNode(-1);
ListNode list = dummy;
while(list1 != null && list2 != null){
// 比较 list1 和 list2 两个指针
// 将值较小的的节点接到 list 指针
if(list1.val < list2.val){
list.next = list1;
list1 = list1.next;
} else {
list.next = list2;
list2 = list2.next;
}
list = list.next;
}
if(list1 != null){
list.next = list1;
}
if(list2 != null){
list.next = list2;
}
return dummy.next;
}
}
优先队列
维护一个小顶堆，存放k个节点中的最小节点，再把最小节点接到新链表中
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头节点
ListNode dummy = new ListNode(-1);
ListNode list = dummy;
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for(ListNode head : lists){
if (head != null) {
pq.offer(head);
}
}
// 获取最小节点，接到结果链表中
while(!pq.isEmpty()){
ListNode node = pq.poll();
list.next = node;
//加入新的节点，维护k个节点
if(node.next != null){
pq.offer(node.next);
}
// list 指针不断前进
list = list.next;
}
return dummy.next;
}
}
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。
class Solution {
ListNode partition(ListNode head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode p1 = dummy1, p2 = dummy2;
// p 负责遍历原链表，类似合并两个有序链表的逻辑
// 这里是将一个链表分解成两个链表
ListNode p = head;
while (p != null) {
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
p1.next = p;
p1 = p1.next;
}
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;
}
// 连接两个链表
p1.next = dummy2.next;
return dummy1.next;
}
}
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
快慢指针法
首先通过快慢指针找到链表中间节点，再配合链表长度的奇偶找到后半部分链表，然后把链表后半部分反转，最后再用反转的后半部分和前半部分一个个比较即可，如果二者一直相等则True，如果找到一个不相等就直接False。
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//通过快慢指针找到中点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//如果fast不为空，说明链表的长度是奇数个,slow再往前一步
if (fast != null) {
slow = slow.next;
}
//反转后半部分链表
slow = reverse(slow);
//然后比较，判断节点值是否相等
// fast指向前部分开始，slow指向后部分开始
fast = head;
while(slow != null){
if(slow.val != fast.val){
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
//反转链表
ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
将值复制到列表中后用双指针法
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode cur = head;
while(cur != null){
list.add(cur.val);
cur = cur.next;
}
int left = 0;
int right = list.size() - 1;
while(left < right){
if(!list.get(left).equals(list.get(right))){
return false;
}
left++;
right--;
}
return true;
}
}
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
双指针法
这道题主要考察链表双指针技巧和加法运算过程中对进位的处理。注意这个 carry 变量的处理，在我们手动模拟加法过程的时候会经常用到。代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
具体而言，如果当前两个链表处相应位置的数字为 n1，n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry) % 10，而新的进位值为 ⌊(n1+n2+carry)/10⌋。
此外，如果链表遍历结束后，有 carry > 0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 在两条链表上的指针
ListNode p1 = l1, p2 = l2;
// 虚拟头结点（构建新链表时的常用技巧）
ListNode dummy = new ListNode(-1);
// 指针 p 负责构建新链表
ListNode p = dummy;
// 记录进位
int carry = 0;
// 开始执行加法，两条链表走完且没有进位时才能结束循环
while (p1 != null || p2 != null) {
// 先加上上次的进位
int val = carry;
if (p1 != null) {
val += p1.val;
p1 = p1.next;
}
if (p2 != null) {
val += p2.val;
p2 = p2.next;
}
// 处理进位情况
carry = val / 10;
val = val % 10;
// 构建新节点
p.next = new ListNode(val);
p = p.next;
}
//还有进位
if (carry > 0) {
p.next = new ListNode(carry);
}
// 返回结果链表的头结点（去除虚拟头结点）
return dummy.next;
}
}
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1)的空间复杂度，时间复杂度是 O(nlogn)的排序算法包括归并排序、堆排序和快速排序，快速排序的最差时间复杂度是 O(n^2)，其中最适合链表的排序算法是归并排序。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(logn)。如果要达到O(1)的空间复杂度，则需要使用自底向上的实现方式。
对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n)和递归函数调用 O(logn)组成，而根据链表特性：
- 数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
- 递归额外空间：递归调用将带来O(logn)的空间复杂度，因此若希望达到 O(1)空间复杂度，则不能使用递归。
方法一：自顶向下归并排序
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
// 归并排序
private ListNode mergeSort(ListNode head){
// 如果没有结点/只有一个结点，无需排序，直接返回
if (head == null || head.next == null) return head;
// 快慢指针找出中位点
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 对右半部分进行归并排序
ListNode right = mergeSort(slow.next);
// 链表判断结束的标志：末尾节点.next==null
slow.next = null;
// 对左半部分进行归并排序
ListNode left = mergeSort(head);
// 合并
return mergeList(left, right);
}
// 合并两个有序链表
private ListNode mergeList(ListNode left, ListNode right){
ListNode tmpHead = new ListNode(-1); // 临时头节点
ListNode res = tmpHead; // 存放结果链表
while (left != null && right != null){
if (left.val < right.val){
res.next = left;
left = left.next;
} else {
res.next = right;
right = right.next;
}
res = res.next;
}
res.next = (left == null ? right : left);
return tmpHead.next;
}
}
复杂度分析
时间复杂度：O(nlogn)，其中 n 是链表的长度。
空间复杂度：O(logn)，空间复杂度主要取决于递归调用的栈空间。
方法二：自底向上归并排序
将方法1改为迭代，节省递归占用的栈空间，每轮从链表上分别取1、2、4、8。。。。长度的子链表，两两依次合并模拟递归中的自底向上
用自底向上的方法实现归并排序，则可以达到 O(1) 的空间复杂度。
首先求得链表的长度 length，然后将链表拆分成子链表进行合并。
用 subLength表示每次需要排序的子链表的长度，初始时 subLength=1。
每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。
class Solution {
public ListNode sortList(ListNode head) {
// 如果没有结点/只有一个结点，无需排序，直接返回
if (head == null || head.next == null) return head;
// 统计链表长度
int len = 0;
ListNode curr = head;
while (curr != null) {
len++;
curr = curr.next;
}
ListNode dummy = new ListNode(-1, head);
// 外层遍历step 内层处理每step个元素进行一次merge
for (int subLength = 1; subLength < len; subLength <<= 1) {
// 用于连接合并后排序好的链表，相当于记录结果
ListNode tail = dummy;
// 记录拆分链表的位置
curr = dummy.next;
// 每次遍历整条链表，将链表拆分成若干个长度为 subLength 的子链表，然后合并。
while (curr != null) {
ListNode left = curr; // 第一个链表的头节点
// 拆分subLength长度的链表1
ListNode right = cut(left, subLength);
// 拆分subLength长度的链表2
curr = cut(right, subLength);
// 合并两个subLength长度的有序链表
tail.next = merge(left, right);
// 将tail移动到subLength × 2 的位置，以连接下一次合并的结果
while (tail.next != null) {
tail = tail.next;
}
}
}
return dummy.next;
}
// 将链表从from开始切掉前step个元素，返回后一个元素
public ListNode cut(ListNode from, int step) {
step--;
while (from != null && step > 0) {
from = from.next;
step--;
}
if (from == null) {
return null;
} else {
ListNode next = from.next;
from.next = null;
return next;
}
}
// 题21. 合并两个有序链表
private ListNode merge(ListNode left, ListNode right){
ListNode dummy = new ListNode(0);// 临时头节点
ListNode res = dummy;
while (left != null && right != null){
if (left.val < right.val){
res.next = left;
left = left.next;
} else {
res.next = right;
right = right.next;
}
res = res.next;
}
res.next = (left == null ? right : left);
return dummy.next;
}
}
方法三：快速排序
- 快排的partition操作变成了将单链表分割为<pivot 和 pivot以及 >=pivo t三个部分
- 递推对分割得到的两个单链表进行快排
- 回归时将pivot和排序后的两个单链表连接，并返回排序好的链表头尾节点
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
// 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。
ListNode newHead = new ListNode(-1);
newHead.next = head;
return quickSort(newHead, null);
}
// 带头结点的链表快速排序
private ListNode quickSort(ListNode head, ListNode end){
if (head == end || head.next == end || head.next.next == end) return head;
// 将小于划分点的值存储在临时链表中
ListNode tmpHead = new ListNode(-1);
// partition为划分点，p为链表指针，tp为临时链表指针
ListNode partition = head.next;
ListNode p = partition;
ListNode tp = tmpHead;
// 将小于划分点的结点放到临时链表中
while (p.next != end){
if (p.next.val < partition.val){
tp.next = p.next;
tp = tp.next;
p.next = p.next.next;
}else {
p = p.next;
}
}
// 合并临时链表和原链表，将原链表接到临时链表后面即可
tp.next = head.next;
// 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了）
head.next = tmpHead.next;
quickSort(head, partition);
quickSort(partition, end);
return head.next;
}
}
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = head;
while(cur != null && cur.next != null ){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
//快慢指针法
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
}
//递归
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
head.next = deleteDuplicates(head.next);
if(head.val == head.next.val) {
return head.next;
} else {
return head;
}
}
}
//哈希表
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode pre = null, cur = head;
Set<Integer> set = new HashSet<Integer>();
while(cur != null){
if(set.contains(cur.val)){
pre.next = cur.next;
} else {
set.add(cur.val);
pre = cur;
}
cur = cur.next;
}
return head;
}
}
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
// 迭代
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy; // 指向遍历节点的前一个节点
ListNode cur = head; // 指向遍历节点
while(cur != null && cur.next != null){
if(cur.val == cur.next.val){
int val = cur.val;
// 如果 cur 与下一节点相同，跳过相同节点
while(cur != null && cur.val == val){
cur = cur.next;
}
pre.next = cur;
} else {
pre = cur;
cur = cur.next;
}
}
return dummy.next;
}
}
//递归
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 当前节点和下一个节点，值不同，则head的值是需要保留的，对head.next继续递归
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
} else {
// 当前节点与下一个节点的值重复了，重复的值都不能要。
// 一直往下找，找到不重复的节点。返回对不重复节点的递归结果
ListNode notDup = head.next.next;
while (notDup != null && notDup.val == head.val) {
notDup = notDup.next;
}
return deleteDuplicates(notDup);
}
}
}
面试题 02.01. 移除重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
ListNode pre = null, cur = head;
Set<Integer> set = new HashSet<Integer>();
while(cur != null){
if(set.contains(cur.val)){
pre.next = cur.next;
} else {
set.add(cur.val);
pre = cur;
}
cur = cur.next;
}
return head;
}
}
138. 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();
// 1. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 1. 构建新链表的 next 和 random 指向
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 3. 返回新链表的头节点
return map.get(head);
}
}
2130. 链表最大孪生和
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
- 比方说，
n = 4那么节点0是节点3的孪生节点，节点1是节点2的孪生节点。这是长度为n = 4的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
示例 1：
输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。
示例 2：
输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。
示例 3：
输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。
方法 1：栈
1、遍历链表，计算总结点数。
2、遍历链表的前一半节点，并入栈。
3、遍历链表后一半节点，并和出栈的节点求和，维护求和过程中的最大值即可。
class Solution {
public int pairSum(ListNode head) {
// 1、遍历链表，计算总结点数
int n = 0; // 记录节点总数
ListNode tmp = head;
while(tmp != null){
n++;
tmp = tmp.next;
}
Stack<Integer> stack = new Stack<>();
// 2、遍历链表的前一半节点，并入栈
for(int i = 0; i < n / 2; i++){
stack.push(head.val);
head = head.next;
}
// 3、遍历链表后一半节点，并和出栈的节点求和，维护求和过程中的最大值即可
int max = 0;
for(int i = 0; i < n / 2; i++){
max = Math.max(max, stack.pop() + head.val);
head = head.next;
}
return max;
}
}
方法 2：快慢指针 + 反转链表
1、快慢指针求后一半节点的首节点。
2、反转后一半链表节点。
3、同时遍历前一半节点和反转后的节点，并求和，维护求和过程中的最大值即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int pairSum(ListNode head) {
// 1、快慢指针求后一半节点的首节点
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow = slow.next;
// 2、反转后一半链表节点
ListNode cur = slow;
ListNode pre = null;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// 3、同时遍历前一半节点和反转后的节点，并求和，维护求和过程中的最大值即可。
int max = 0;
while (head != null && pre != null) {
max = Math.max(max, head.val + pre.val);
head = head.next;
pre = pre.next;
}
return max;
}
}
③栈&队列&堆
❶普通队列-Queue
队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。
Queue<> queue = new LinkedList<>();
常用方法
| 函数 | 功能 |
|---|---|
| add(E e)/offer(E e) | 压入元素 |
| remove()/poll() | 弹出元素 |
| element()/peek() | 获取队头元素 |
| isEmpty() | 用于检查此队列是“空”还是“非空” |
| size() | 获取队列长度 |
❷双端队列-Deque
Java集合提供了接口Deque来实现一个双端队列，它的功能是：
- 既可以添加到队尾，也可以添加到队首；
- 既可以从队首获取，又可以从队尾获取。
Deque有三种用途
- 普通队列(一端进另一端出):
Deque<> queue = new LinkedList<>();
// 等价
Queue<> queue = new LinkedList<>();
| Queue方法 | 等效Deque方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
- 双端队列(两端都可进出)
//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque = new LinkedList<>();
| 第一个元素 (头部) | 最后一个元素 (尾部) | |
|---|---|---|
| 插入 | addFirst(e)/offerFirst(e) | addLast(e)/offerLast(e) |
| 删除 | removeFirst()/pollFirst() | removeLast()/pollLast() |
| 获取 | getFirst()/peekFirst() | getLast()/peekLast() |
- 堆栈(先进后出)
//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque<Integer> stack = new LinkedList<>();
Deque<Integer> stack = new ArrayDeque<>(); //速度更快
// 等价
Stack<String> stack=new Stack<>();
| 堆栈方法 | 等效Deque方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
Deque所有方法
| 方法 | 描述 |
|---|---|
| 添加功能 | |
| push(E) | 向队列头部插入一个元素,失败时抛出异常 |
| addFirst(E) | 向队列头部插入一个元素,失败时抛出异常 |
| addLast(E) | 向队列尾部插入一个元素,失败时抛出异常 |
| offerFirst(E) | 向队列头部加入一个元素,失败时返回false |
| offerLast(E) | 向队列尾部加入一个元素,失败时返回false |
| 获取功能 | |
| peek() | 获取队列头部元素,队列为空时抛出异常 |
| getFirst() | 获取队列头部元素,队列为空时抛出异常 |
| getLast() | 获取队列尾部元素,队列为空时抛出异常 |
| peekFirst() | 获取队列头部元素,队列为空时返回null |
| peekLast() | 获取队列尾部元素,队列为空时返回null |
| 删除功能 | |
| removeFirstOccurrence(Object) | 删除第一次出现的指定元素,不存在时返回false |
| removeLastOccurrence(Object) | 删除最后一次出现的指定元素,不存在时返回false |
| 弹出功能 | |
| pop() | 弹出队列头部元素,队列为空时抛出异常 |
| removeFirst() | 弹出队列头部元素,队列为空时抛出异常 |
| removeLast() | 弹出队列尾部元素,队列为空时抛出异常 |
| pollFirst() | 弹出队列头部元素,队列为空时返回null |
| pollLast() | 弹出队列尾部元素,队列为空时返回null |
❸优先队列-PriorityQueue
优先级队列其实就是一个披着队列外衣的堆，因为优先队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
PriorityQueue 是具有优先级别的队列，优先级队列的元素按照它们的自然顺序排序，或者由队列构造时提供的 Comparator 进行排序，这取决于使用的是哪个构造函数
| 构造函数 | 描述 |
|---|---|
| PriorityQueue() | 使用默认的容量（11）创建一个优队列，元素的顺序规则采用的是自然顺序 |
| PriorityQueue(int initialCapacity) | 使用默认指定的容量创建一个优队列，元素的顺序规则采用的是自然顺序 |
| PriorityQueue(Comparator<? super E> comparator) | 使用默认的容量队列，元素的顺序规则采用的是 comparator |
//默认按自然顺序（升序）检索的
PriorityQueue<Integer> numbers = new PriorityQueue<>();
PriorityQueue<Integer> numbers = new PriorityQueue<>(3); //大小为3
//使用Comparator接口自定义此顺序
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
常用方法
peek()//返回队首元素
poll()//返回队首元素，队首元素出队列
add()//添加元素
size()//返回队列元素个数
isEmpty()//判断队列是否为空，为空返回true,不空返回false
❹栈-Stack/Deque
栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。
注意：Java 堆栈 Stack 类已经过时，Java 官方推荐使用 Deque 替代 Stack 使用。Deque 堆栈操作方法：push()、pop()、peek()。
创建栈
//方法一，弃用
Stack<E> stack=new Stack<>();
Stack<String> stack=new Stack<>();
//方法二：推荐使用
//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque stack = new ArrayDeque<String>();
Deque stack = new LinkedList<String>();
stack.push("a");
stack.pop();
stack.push("b");
System.out.println(stack);
常用方法
| 函数 | 功能 |
|---|---|
| push(T t) | 压栈（向栈顶放入元素） |
| pop() | 出栈（拿出栈顶元素，并得到它的值） |
| peek() | 将栈顶元素返回，但是不从栈中移除它 |
| search(Object o) | 返回对象在此堆栈上的从1开始的位置。 |
| isEmpty() | 判断栈是否为空 |
| size() | 获取栈长度 |
❺堆-Heap
堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性：
1.堆是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
2.堆通常用数组来实现。将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。(0被废弃)
如果一个结点的位置为k，则它的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。
这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
- 3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
堆的API设计
public class Heap<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public Heap(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//交换堆中i索引和j索引处的值
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//往堆中插入一个元素
public void insert(T t) {
items[++N] = t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
//通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
while (k > 1) {
//比较当前结点和其父结点
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
//删除堆中最大的元素,并返回这个最大元素
public T delMax() {
T max = items[1];
//交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
exch(1, N);
//最大索引处的元素删除掉
items[N] = null;
//元素个数-1
N--;
//通过下沉调整堆，让堆重新有序
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
//循环对比k结点和其左子结点2k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
while (2 * k <= N) {
//获取当前结点的子结点中的较大结点
int max;//记录较大结点所在的索引
if (2 * k + 1 <= N) {
if (less(2 * k, 2 * k + 1)) {
max = 2 * k + 1;
} else {
max = 2 * k;
}
} else {
max = 2 * k;
}
//比较当前结点和较大结点的值
if (!less(k, max)) {
break;
}
//交换k索引处的值和max索引处的值
exch(k, max);
//变换k的值
k = max;
}
}
public static void main(String[] args) {
Heap<String> heap = new Heap<String>(20);
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");
String del;
//循环删除
while ((del = heap.delMax()) != null) {
System.out.print(del + ",");
}
}
}
❻LeetCode真题
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<>(); // 负责进栈
outStack = new ArrayDeque<>(); // 负责出栈
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
// 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
// 弹出输出栈顶元素（输出栈不为空直接弹出，为空时执行上面操作）
return outStack.pop();
}
public int peek() {
// 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
// 返回栈顶元素
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
}
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList(); // 存储栈内的元素，
queue2 = new LinkedList(); // 入栈操作的辅助队列
}
public void push(int x) {
queue2.offer(x); //先存入queue2
//把queue1的也存入queue2
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
//最后交换queue1和queue2，将元素都放到queue1中
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
//queue1用于存储栈内的元素，因此只需要判断queue1是否为空即可
public boolean empty() {
return queue1.isEmpty();
}
}
//一个队列实现栈
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
//入栈操作时，首先获得入栈前的元素个数n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
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.
辅助栈
class MinStack {
Deque<Integer> stack; // 记录栈中的所有元素
Deque<Integer> minStk; // 阶段性记录栈中的最小元素
public MinStack() {
stack = new ArrayDeque<>();
minStk = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
// 维护 minStk 栈顶为全栈最小元素
if(minStk.isEmpty() || val <= minStk.peek()){
minStk.push(val);
}
}
public void pop() {
if (stack.peek().equals(minStk.peek())) {
// 弹出的元素是全栈最小的
minStk.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStk.peek();
}
}
一个栈实现
可以用一个栈，这个栈同时保存的是每个数字 val 进栈的时候的值 与 插入该值后的栈内最小值。即每次新元素 val 入栈的时候保存一个元组：（当前值 val，栈内最小值）。
这个元组是一个整体，同时进栈和出栈。即栈顶同时有值和栈内最小值，
push()当栈为空，保存元组(val, val)；当栈不空，保存元组(val, min(此前栈内最小值，val)))pop()删除栈顶的元组。top()函数是获取栈顶的当前值，即栈顶元组的第一个值；getMin()函数是获取栈内最小值，即栈顶元组的第二个值；pop()函数时删除栈顶的元组。
class MinStack {
Deque<int[]> stack;
public MinStack() {
stack = new ArrayDeque<>();
}
public void push(int val) {
if(stack.isEmpty()){
stack.push(new int[]{val, val});
} else {
stack.push(new int[]{val, Math.min(val, stack.peek()[1])});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
20. 有效的括号-栈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。
//遇到左括号，就入栈右括号；遇到右括号，看是否与栈顶相等。
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for(char c : s.toCharArray()){
// 字符 c 是左括号，就入栈右括号
if(c == '(') stack.push(')');
else if(c == '{') stack.push('}');
else if(c == '[') stack.push(']');
// 字符 c 是右括号，看是否与栈顶相等。
else if(stack.isEmpty() || c != stack.pop())
return false;
}
return stack.isEmpty();
}
}
// 遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。
class Solution {
public boolean isValid(String s) {
int n = s.length();
// 如果s的长度为奇数，一定不符合要求
if (n % 2 == 1) return false;
Map<Character, Character> map = new HashMap<>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<>();
for(char c : s.toCharArray()){
//遇到右括号则将对应左括号出栈
if(map.containsKey(c)){
// 去栈中寻找最近的左括号，看是否匹配。
if (!stack.isEmpty() && stack.peek() == map.get(c)) {
stack.pop(); // 匹配上就出栈
} else {
return false; // 没匹配上
}
} else {
stack.push(c); //遇到左括号直接入栈
}
}
return stack.isEmpty();
}
}
1047. 删除字符串中所有相邻重复项-栈
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
//栈
class Solution {
public String removeDuplicates(String s) {
Deque<Character> stack = new ArrayDeque<>();
for(char ch : s.toCharArray()){
if(stack.isEmpty() || stack.peek() != ch){
stack.push(ch);
} else{
stack.pop();
}
}
String str = "";
while(!stack.isEmpty()){
str = stack.pop() + str;
}
return str;
}
}
//数组
class Solution {
public String removeDuplicates(String s) {
char[] str = s.toCharArray();
int top = -1;
for (int i = 0; i < s.length(); i++) {
if (top == -1 || str[top] != str[i]) {
str[++top] = str[i];
} else {
top--;
}
}
return String.valueOf(str, 0, top + 1);
}
}
150. 逆波兰表达式求值-栈
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for(String s : tokens){
if ("+-*/".contains(s)) {
int a = stack.pop();
int b = stack.pop();
if("+".equals(s)) stack.push(b + a);
else if("-".equals(s)) stack.push(b - a);
else if("*".equals(s)) stack.push(b * a);
else if("/".equals(s)) stack.push(b / a);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for(String s : tokens){
if ("+-*/".contains(s)) {
int a = stack.pop();
int b = stack.pop();
switch(s){
case "+":
stack.push(b + a);
break;
case "-":
stack.push(b - a);
break;
case "*":
stack.push(b * a);
break;
case "/":
stack.push(b / a);
break;
}
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
2390. 从字符串中移除星号-栈
给你一个包含若干星号 * 的字符串 s 。
在一步操作中，你可以：
- 选中
s中的一个星号。 - 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。
示例 1：
输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。
示例 2：
输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。
class Solution {
public String removeStars(String s) {
Deque<Character> stack = new ArrayDeque<>();
for(char c : s.toCharArray()){
if(c == '*'){
stack.pop();
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
for(char c : stack){
sb.append(c);
}
return sb.reverse().toString();
}
}
// StringBuilder模拟栈
class Solution {
public String removeStars(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c != '*') {
// 1.字母直接加入
sb.append(c);
} else {
// 2.*要移除栈顶字母
sb.deleteCharAt(sb.length() - 1);
}
}
return sb.toString();
}
}
735. 行星碰撞-栈
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
用栈保存当前存在的行星。
1、如果行星大于0，则不管左边行星的方向如何，都不会碰撞。
2、如果行星小于0，则判断左边行星，如果左边行星大于0，那么则会碰撞，否则不碰撞。
主要就是处理行星小于0，并且左边行星大于0的情况： 如果当前行星小于0，那么依次遍历栈顶元素，看是否会被销毁，并且记录当前行星的存活情况，最后再判断当前行星是否入栈。
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int aster : asteroids) {
boolean alive = true;
while (alive && aster < 0 && !stack.isEmpty() && stack.peek() > 0) {
//alive = stack.peek() < -aster;
// aster 是否存在
if (stack.peek() < -aster){
alive = true;
} else {
alive = false;
}
if (stack.peek() <= -aster) { // 栈顶行星爆炸
stack.pop();
}
}
if (alive) {
stack.push(aster);
}
}
int size = stack.size();
int[] ans = new int[size];
for (int i = size - 1; i >= 0; i--) {
ans[i] = stack.pop();
}
return ans;
}
}
394. 字符串解码-栈
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
- 构建辅助栈
stack， 遍历字符串s中每个字符c；- 当
c为数字时，将数字字符转化为数字k，用于后续倍数计算； - 当
c为字母时，在res尾部添加c； - 当
c为[时，将当前k和res入栈，并分别置空置 0：- 记录此
[前的临时结果res至栈，用于发现对应]后的拼接操作； - 记录此
[前的倍数k至栈，用于发现对应]后，获取k × [...]字符串。 - 进入到新
[后，res和 k 重新记录。
- 记录此
- 当
c为]时，stack出栈，拼接字符串res = restack.pop() + curk * res，其中:restack.pop()是上个[到当前[的字符串，例如"3[a2[c]]"中的a；curk是当前[到]内字符串的重复倍数，例如"3[a2[c]]"中的2。
- 当
- 返回字符串
res。
class Solution {
public String decodeString(String s) {
int k = 0; //记录数字
StringBuilder res = new StringBuilder(); //记录结果
ArrayDeque<Integer> kstack = new ArrayDeque<>();
ArrayDeque<StringBuilder> restack = new ArrayDeque<>();
for(char c : s.toCharArray()){
if(c == '[') { //入栈，记录K和当前res，归零。
kstack.push(k);
restack.push(res);
//置空置0
k = 0;
res = new StringBuilder();
} else if(c ==']'){ //出栈
int curk = kstack.pop();
StringBuilder temp = new StringBuilder();
for(int i = 0; i < curk; i++) temp.append(res);
res = restack.pop().append(temp); //合并
} else if(c >= '0' && c <= '9'){
k = c - '0' + k * 10; //如果k是多位数需要x10
} else {
res.append(c); //如果是字母则缓慢添加
}
}
return res.toString();
}
}
739. 每日温度-单调栈
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
暴力
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
for(int i = 0; i < n; i++){
int count = 0;
for(int j = i + 1; j < n; j++){
if(temperatures[j] > temperatures[i]){
count = j - i;
break;
}
}
res[i] = count;
}
return res;
}
}
单调栈
维护一个单调递减栈。
遍历整个数组，如果栈不空，且当前数字大于栈顶元素，取出栈顶元素，直接求出下标差就是二者的距离(由于当前数字大于栈顶元素的数字，所以一定是第一个大于栈顶元素的数)。
继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
// 存放元素下标
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
int x = stack.pop();
res[x] = i - x;
}
stack.push(i);
}
return res;
}
}
901. 股票价格跨度-单调栈
设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
- 例如，如果未来 7 天股票的价格是
[100,80,60,70,60,75,85]，那么股票跨度将是[1,1,1,2,1,4,6]。
实现 StockSpanner 类：
StockSpanner()初始化类对象。int next(int price)给出今天的股价price，返回该股票当日价格的 跨度 。
示例：
输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]
解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85); // 返回 6
维护一个价格单调递减的栈使用「单调栈」，栈中每个元素存放的是 (price, cnt) 数据对，其中 price 表示价格，cnt 表示当前价格的跨度。
每次调用 next(price)，我们将其与栈顶元素进行比较，如果栈顶元素的价格小于等于 price，则将当日价格的跨度 cnt 加上栈顶元素的跨度，然后将栈顶元素出栈，直到栈顶元素的价格大于 price，或者栈为空为止。
最后将 (price, cnt) 入栈，返回 cnt 即可。
class StockSpanner {
Deque<int[]> stack;
public StockSpanner() {
stack = new LinkedList<int[]>();
}
public int next(int price) {
int cnt = 1;
while(!stack.isEmpty() && stack.peek()[0] <= price){
cnt += stack.pop()[1];
}
stack.push(new int[]{price, cnt});
return cnt;
}
}
84. 柱状图中最大的矩形-单调栈-防御式编程
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
暴力
可以枚举以每个柱形为高度的最大矩形的面积。具体来说是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。
// 遍历每个柱子，以当前柱子的高度作为矩形的高 h，
// 从当前柱子向左右遍历，找到矩形的宽度 width。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int res = 0;
for(int i = 0; i < n; i++){
int curHeight = heights[i];
// 找左边最后 1 个大于等于 heights[i] 的下标
int left = i;
while(left > 0 && heights[left - 1] >= heights[i]){
left--;
}
// 找右边最后 1 个大于等于 heights[i] 的索引
int right = i;
while(right < n - 1 && heights[right + 1] >= heights[i]){
right++;
}
int width = right - left + 1;
res = Math.max(res, width * curHeight);
}
return res;
}
}
单调栈
- 上述写法中，我们需要再嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体，这个过程是 O(N) 的；
- 那么我们可以 O(1) 的获取柱体 i 左边第一个比它小的柱体吗？答案就是单调增栈，因为对于栈中的柱体来说，栈中下一个柱体就是左边第一个高度小于自身的柱体。
因此做法就很简单了，我们遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前的柱体高度小于栈顶柱体的高度，说明当前栈顶柱体找到了右边的第一个小于自身的柱体，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。
class Solution {
public int largestRectangleArea(int[] heights) {
// 防御式编程思想
// 在柱体数组的头和尾加了两个高度为 0 的柱体。
// 为了方便确定原有数组中第一个元素和最后一个元素能不能继续扩张；
int[] arr = new int[heights.length + 2];
//System.arraycopy(heights, 0, arr, 1, heights.length);
for (int i = 1; i < arr.length - 1; i++) {
arr[i] = heights[i - 1];
}
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i < arr.length; i++) {
// 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」
// 若当前柱体i高度小于栈顶柱体高度，说明i是栈顶柱体的「右边第一个小于栈顶柱体的柱体」
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
int cur = stack.pop();
// 栈顶元素弹出后，新的栈顶元素就是其左侧边界,右侧边界是当前考察的索引
int width = i - stack.peek() - 1;
res = Math.max(res, width * arr[cur]);
}
stack.push(i);
}
return res;
}
}
933. 最近的请求次数-队列
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 0 。int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new ArrayDeque<>();
}
public int ping(int t) {
queue.offer(t);
while(queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
649. Dota2 参议院-队列
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
- 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
- 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
示例 1：
输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。
示例 2：
输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
使用两个队列 radiant 和 dire 分别按照投票顺序存储天辉方和夜魇方每一名议员的投票时间。随后我们就可以开始模拟整个投票的过程：
如果此时 radiant 为空 或者 dire 为空，那么就可以宣布另一方获得胜利；
如果均不为空，那么比较这两个队列的首元素，就可以确定当前行使权利的是哪一名议员。
如果 radiant 的首元素较小，那说明轮到天辉方的议员行使权利，其会挑选 dire 的首元素对应的那一名议员禁止权利。因此，将 dire 的首元素永久地弹出，并将 radiant 的首元素弹出，增加 n 之后再重新放回队列，这里 n 是给定的字符串 senate 的长度，即表示该议员会参与下一轮的投票。
同理，如果 dire 的首元素较小，那么会永久弹出 radiant 的首元素，剩余的处理方法也是类似的。
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> radiant = new LinkedList<>();
Queue<Integer> dire = new LinkedList<>();
for(int i = 0; i < n; i++){
if(senate.charAt(i) == 'R'){
radiant.offer(i);
} else {
dire.offer(i);
}
}
while(!radiant.isEmpty() && !dire.isEmpty()){
int radiantIndex = radiant.poll();
int direIndex = dire.poll();
if(radiantIndex < direIndex) {
radiant.offer(radiantIndex + n);
} else {
dire.offer(direIndex + n);
}
}
return radiant.isEmpty() ? "Dire" : "Radiant";
}
}
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]
方法一：优先队列
初始时，我们将数组 nums 的前 k 个元素和对应坐标放入优先队列中。
每当向右移动窗口时，就把新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。
特殊情况：到目前每次滑出窗口的元素并没有都从堆中删除，就会造成前面窗口的最大值一直在优先队列中，而窗口已经移走，最大值已经更换，前面窗口的最大值应该移出队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// 1. 优先队列存放的是二元组(num,index)
// num : 是为了比较元素大小
// index : 是为了判断窗口的大小是否超出范围
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] a,int[] b){
//大顶堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
return a[0] != b[0] ? b[0] - a[0] : b[1] - a[1];
}
});
// 2. 优先队列初始化 : k个元素的堆
for(int i = 0; i < k; i++){
pq.offer(new int[]{nums[i], i});
}
// 3. 处理堆逻辑
int[] res = new int[n - k + 1]; // 初始化结果数组长度 ：一共有 n - k + 1个窗口
res[0] = pq.peek()[0]; // 初始化res[0] ： 拿出目前堆顶的元素
for(int i = k; i < n; i++){ // 向右移动滑动窗口
pq.offer(new int[]{nums[i], i}); // 加入大顶堆中
//特殊情况 当栈顶元素不在当前窗口范围就移除
while(pq.peek()[1] <= i - k){ // 将栈顶下标不在滑动窗口中就干掉
pq.poll(); // 维护：堆的大小就是滑动窗口的大小
}
res[i - k + 1] = pq.peek()[0]; // 此时堆顶元素就是滑动窗口的最大值
}
return res;
}
}
方法二：单调队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length < 2){
return nums;
}
// 维护一个单调递减的双端队列，存元素坐标(方便判断队首的值是否在窗口范围)
Deque<Integer> deque = new LinkedList<>();
// 存储最后返回结果
int[] res = new int[nums.length - k + 1];
for(int i = 0; i < nums.length; i++){
// 清理不在窗口范围的元素
if(!deque.isEmpty() && deque.peek() <= i - k){
deque.pollFirst();
}
// 删除所有比新入队元素小的旧元素
while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
deque.pollLast();
}
// 新元素入队
deque.addLast(i);
// 当窗口长度为k时 开始保存窗口中最大值
if(i + 1 >= k){
res[i + 1 - k] = nums[deque.peekFirst()];
}
}
return res;
}
}
347. 前 K 个高频元素-优先队列
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
首先，用一个 map 把每个元素出现的频率计算出来。然后，这道题就变成了 215. 数组中的第 K 个最大元素，只不过第 215 题让你求数组中元素值 e 排在第 k 大的那个元素，这道题让你求数组中元素值 map[e] 排在前 k 个的元素。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
// 队列按照键值对中的值（元素出现频率）从小到大排序
// PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a,b) -> (a[1] - b[1]));
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// 遍历map，用最小堆保存频率最大的k个元素
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
queue.offer(new int[]{num, count});
if (queue.size() > k) {
queue.poll();
}
}
// 遍历map，用最小堆保存频率最大的k个元素
// for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// int num = entry.getKey(), count = entry.getValue();
// if (queue.size() == k) {
// if (queue.peek()[1] < count) {
// queue.poll();
// queue.offer(new int[]{num, count});
// }
// } else {
// queue.offer(new int[]{num, count});
// }
// }
int[] res = new int[k];
for (int i = 0; i < k; ++i) {
res[i] = queue.poll()[0];
}
return res;
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 统计每个元素出现的次数，元素为键，元素出现的次数为值
Map<Integer, Integer> map = new HashMap<>();
for(int i : nums){
map.put(i, map.getOrDefault(i, 0) + 1);
}
// 队列按照键值对中的值（元素出现频率）从小到大排序
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
// 遍历map，用最小堆保存频率最大的k个元素
for(Integer key : map.keySet()){
if (queue.size() < k) {
queue.offer(key);
} else if (map.get(key) > map.get(queue.peek())) {
queue.poll();
queue.offer(key);
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll();
}
return ret;
}
}
295. 数据流的中位数 - 优先队列
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
- findMedian
如果元素不一样多，多的那个堆的堆顶元素就是中位数
如果元素一样多，两个堆堆顶元素的平均数是中位数
- addNum
每次调用addNum函数的时候，我们比较一下large和small的元素个数，谁的元素少我们就加到谁那里，想要往large里添加元素，不能直接添加，而是要先往small里添加，然后再把small的堆顶元素加到large中；向small中添加元素同理。（要维护两堆元素个数之差不超过 1，且 large 堆顶元素要大于 small 堆顶）
class MedianFinder {
PriorityQueue<Integer> large, small;
public MedianFinder() {
small = new PriorityQueue<>(); // 小顶堆，保存较大的一半
large = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
}
//要维护两堆元素个数之差不超过 1，且 large 堆顶元素要大于 small 堆顶
public void addNum(int num) {
if (small.size() >= large.size()) {
small.offer(num);
large.offer(small.poll());
} else {
large.offer(num);
small.offer(large.poll());
}
}
public double findMedian() {
// 如果元素不一样多，多的那个堆的堆顶元素就是中位数
if (large.size() < small.size()) {
return small.peek();
} else if (large.size() > small.size()) {
return large.peek();
}
// 如果元素一样多，两个堆堆顶元素的平均数是中位数
return (large.peek() + small.peek()) / 2.0;
}
}
215. 数组中的第K个最大元素-优先队列
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
方法一：暴力法
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
}
- 时间复杂度：O(NlogN)，这里 N 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为 O(NlogN)；
- 空间复杂度：O(logN)，这里认为编程语言使用的排序方法是「快速排序」，空间复杂度为递归调用栈的高度，为 logN。
方法二：优先队列
class Solution {
public int findKthLargest(int[] nums, int k) {
// 小顶堆，堆顶是最小元素
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int e : nums) {
// 每个元素都要过一遍二叉堆
pq.offer(e);
// 堆中元素多于 k 个时，删除堆顶元素
if (pq.size() > k) {
pq.poll();
}
}
// pq 中剩下的是 nums 中 k 个最大元素，
// 堆顶是最小的那个，即第 k 个最大元素
return pq.peek();
}
}
二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过 k，所以插入和删除元素的复杂度是 O(logk)，再套一层 for 循环，假设数组元素总数为 N，总的时间复杂度就是 O(Nlogk)。空间复杂度很显然就是二叉堆的大小，为 O(k)。
时间复杂度：
O(Nlogk)空间复杂度：
O(k)
方法三：快速选择
「快速排序」虽然快，但是「快速排序」在遇到特殊测试用例（「顺序数组」或者「逆序数组」）的时候，递归树会退化成链表，时间复杂度会变成 O(N^2)。
事实上，有一个很经典的基于「快速排序」的算法，可以通过一次遍历，确定某一个元素在排序以后的位置，这个算法叫「快速选择」。
首先，题目问「第 k 个最大的元素」，相当于数组升序排序后「排名第 n - k 的元素」，为了方便表述，后文另 target = n - k。
partition 函数会将 nums[p] 排到正确的位置，使得 nums[left..p-1] < nums[p] < nums[p+1..right]：
这时候，虽然还没有把整个数组排好序，但我们已经让 nums[p] 左边的元素都比 nums[p] 小了，也就知道 nums[p] 的排名了。
那么我们可以把 p 和 target 进行比较，如果 p < target 说明第 target 大的元素在 nums[p+1..right] 中，如果 p > target 说明第 target 大的元素在 nums[left..p-1] 中。
进一步，去 nums[p+1..right] 或者 nums[left..p-1] 这两个子数组中执行 partition 函数，就可以进一步缩小排在第 target 的元素的范围，最终找到目标元素。
注意：本题必须随机初始化 pivot 元素，否则通过时间会很慢，因为测试用例中有极端测试用例。为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第 1 个元素与任意 1 个元素的位置。
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int target = len - k;
int left = 0;
int right = len - 1;
return quickSelect(nums, left, right, target);
}
public static int quickSelect(int[] a, int l, int r, int k) {
if (l > r) {
return 0;
}
int p = partition(a, l, r);
if (p == k) {
return a[p];
} else {
return p < k ? quickSelect(a, p + 1, r, k) : quickSelect(a, l, p - 1, k);
}
}
static Random random = new Random();
public static int partition(int[] arr, int left, int right) {
// 生成 [left, 数组长度] 的随机数
int randomIndex = random.nextInt(right - left + 1) + left;
swap(arr, left, randomIndex);
int pivot = arr[left];//定义基准值为数组第一个数
int i = left;
int j = right;
while (i != j) {
//从右往左找比基准值小的数
while (pivot <= arr[j] && i < j) j--;
//从左往右找比基准值大的数
while (pivot >= arr[i] && i < j) i++;
if (i < j) { //如果i<j，交换它们
swap(arr, i, j);
}
}
//把基准值放到合适的位置
swap(arr, left, i);
return i;
}
public static void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
- 时间复杂度：O(N)，这里 N 是数组的长度
- 空间复杂度：O(logN)
2336. 无限集中的最小数字
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类：
SmallestInfiniteSet()初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest()移除 并返回该无限集中的最小整数。void addBack(int num)如果正整数num不 存在于无限集中，则将一个num添加 到该无限集中。
示例：
输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]
解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
// 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。
class SmallestInfiniteSet {
PriorityQueue<Integer> pq = new PriorityQueue<>();
public SmallestInfiniteSet() {
for (int i = 1; i <= 1000; i++) {
pq.offer(i);
}
}
public int popSmallest() {
return pq.poll();
}
public void addBack(int num) {
if(!pq.contains(num)){
pq.offer(num);
}
}
}
// 1、没有插入，或插入的都被移除，此时用一个变量记录无限集的最小值；
// 2、插入值，且比记录的最小值小，用小根堆（或二叉搜索树）记录插入的最小值；
class SmallestInfiniteSet {
private int min;
PriorityQueue<Integer> pq;
public SmallestInfiniteSet() {
min = 1;
pq = new PriorityQueue<>();
}
public int popSmallest() {
if (!pq.isEmpty()) {
return pq.poll();
}
return min++;
}
public void addBack(int num) {
if (num < min && !pq.contains(num)) {
pq.offer(num);
}
}
}
2542. 最大子序列的分数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。
对于选择的下标 i0 ，i1 ，…， ik - 1 ，你的 分数 定义如下：
nums1中下标对应元素求和，乘以nums2中下标对应元素的 最小值 。- 用公示表示：
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1])。
请你返回 最大 可能的分数。
一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
示例 1：
输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
输出：12
解释：
四个可能的子序列分数为：
- 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
- 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
- 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
- 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
所以最大分数为 12 。
示例 2：
输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
输出：30
解释：
选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
根据nums2进行降序排序，这样每次取的数都是递减并且可以获取最小的乘数，又因为要让nums1中的和为尽可能的大，那么可以使用优先队列小根堆来实现每次抛出最小的那个数使得和尽可能的大
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
Integer[] sorts = new Integer[n];
for(int i = 0; i < n; i++) {
sorts[i] = i;
}
// 根据nums2进行降序排序
// 使得 sorts 中的元素按照对应的 nums2 中的元素值降序排列
// 比如,在nums2里的是[2,1,3,4](对应的下标是[0,1,2,3]),
// 如果对nums2排序的话[4,3,2,1](对应的下标是[3,2,0,1]), 此时 sorts为[3,2,0,1]
Arrays.sort(sorts, (a, b) -> nums2[b] - nums2[a]);
// 小根堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
long sum = 0L;
for(int i = 0; i < k - 1; i++){
sum += nums1[sorts[i]];
pq.offer(nums1[sorts[i]]);
}
long ans = 0L;
for(int i = k - 1; i < n; i++){
sum += nums1[sorts[i]];
pq.offer(nums1[sorts[i]]);
ans = Math.max(ans, nums2[sorts[i]] * sum);
sum -= pq.poll();
}
return ans;
}
}
2462. 雇佣 K 位工人的总代价
给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：
- 总共进行
k轮雇佣，且每一轮恰好雇佣一位工人。 - 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
- 比方说，
costs = [3,2,7,7,1,2]且candidates = 2，第一轮雇佣中，我们选择第4位工人，因为他的代价最小[3,2,7,7,1,2]。 - 第二轮雇佣，我们选择第
1位工人，因为他们的代价与第4位工人一样都是最小代价，而且下标更小，[3,2,7,7,2]。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
- 比方说，
- 如果剩余员工数目不足
candidates人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。 - 一位工人只能被选择一次。
返回雇佣恰好 k 位工人的总代价。
示例 1：
输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出：11
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。
- 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
- 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
总雇佣代价是 11 。
示例 2：
输入：costs = [1,2,4,1], k = 3, candidates = 3
输出：4
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
- 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
- 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
总雇佣代价是 4 。
根据题意，优先元素小的元素，然后优先索引，根据此我们可以创建一个小顶堆
从candidates 前后选择对应的索引，遍历数组，将对应的索引添加到小顶堆
需要雇佣k位工人，遍历k次，弹出堆顶元素累加 result += costs[poll[0]]，每次遍历，弹出的元素不再参于下一次计算，不停的比较 left 于 right
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> {
if (costs[o1[0]] == costs[o2[0]]) {
return o1[0] - o2[0];
} else {
return costs[o1[0]] - costs[o2[0]];
}
}));
int left = 0, right = costs.length - 1;
while (left < candidates) {
queue.add(new int[]{left++, 0});
}
while (Math.max(left, costs.length - candidates) <= right) {
queue.add(new int[]{right--, 1});
}
long result = 0;
for (int i = 0; i < k; i++) {
int[] poll = queue.poll();
result += costs[poll[0]];
if (left <= right) {
if (poll[1] == 0) {
queue.add(new int[]{left++, 0});
} else {
queue.add(new int[]{right--, 1});
}
}
}
return result;
}
}
- 由于每次获取的是代价最小的工人，所以采用小顶堆来存储元素，方便每次弹出最小的元素。使用两个小顶堆（left、right）分别存储最前面 candidates 个工人和最后面 candidates 个工人，同时使用双指针（i、j）来表明小顶堆包含的元素范围；
- 初始化：[0,candidate−1] 范围内的元素加入到 left 中，[n−candidate,n−1]范围内的元素加入到 right 中，i -> candidate， 如果长度够的话，j -> n−candidate−1。
- 总共遍历 k 次，每次遍历时，比较两个小顶堆的堆顶元素，将较小的代价弹出，累加到结果中，移动相应的指针（指针都是往中间移动，i++, j--），并将代价加入到对应的小顶堆中。
代码：
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
long res = 0L;
PriorityQueue<Integer> left = new PriorityQueue<>(), right = new PriorityQueue<>();
int n = costs.length, i = 0, j = n - 1;
// 初始化：将 [0, candidates] 范围内的元素加入 left 中，将 [n - candidate, n - 1] 范围内元素加入 right 中。
while(i < candidates) left.offer(costs[i++]);
while(j >= i && j >= n - candidates) right.offer(costs[j--]);
while(k-- > 0) {
// 由于队列可能为空，需要做判断，下面会比较大小然后取较小值，如果一个为空，直接赋值最大值。
int a = left.isEmpty() ? Integer.MAX_VALUE : left.peek();
int b = right.isEmpty() ? Integer.MAX_VALUE : right.peek();
if(a <= b) {
res += a;
left.poll();
if(i <= j) left.offer(costs[i++]);
} else {
res += b;
right.poll();
if(i <= j) right.offer(costs[j--]);
}
}
return res;
}
}
④哈希表
❶基础知识
哈希表(Hash table)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。
常见的三种哈希结构
- 数组
int[] hashTable = new int[26]; //存26字母索引
//hashTable[s.charAt(i) - 'a']++; 字母存在则在对应位置加1
- set （集合）
Set<Integer> set = new HashSet<>();
//set.add(num) 插入元素
//set.contains(num) 查找键是否存在
- map（映射）
Map<Integer, Integer> map = new HashMap<>();
//map.put(key,value) 插入元素
//map.getOrDefault(ch, 0); 查询map是否存在ch,不存在设置默认值0
//map.values() 返回所有value
//map.containsKey(key) 查找键是否存在
//map.isEmpty() 判断是否为空
//map.get() 根据键获取值
//map.remove() 根据键删除映射关系
❷LeetCode真题
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
方法1：哈希表
首先判断两个字符串长度是否相等，不相等则直接返回 false
若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t
s 负责在对应位置增加，t 负责在对应位置减少
如果哈希表的值都为 0，则二者是字母异位词
//O(n)
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
int[] hashTable = new int[26];
for(int i = 0; i < s.length(); i++){
hashTable[s.charAt(i) - 'a']++;
hashTable[t.charAt(i) - 'a']--;
}
for(int i = 0; i < 26; i++){
if(hashTable[i] != 0)
return false;
}
return true;
}
}
方法2：排序
t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等即可判断。此外，如果 s 和 t 的长度不同，t 必然不是 s 的异位词。
//O(nlogn)
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
方法1：排序
遍历字符串数组，对每个字符串中的字符排序，加入map对应的key的数组中。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str : strs){
char[] arr = str.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
方法2：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
1657. 确定两个字符串是否接近
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
- 操作 1：交换任意两个 现有 字符。
- 例如，
abcde -> aecdb
- 例如，
- 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
- 例如，
aacabb -> bbcbaa（所有a转化为b，而所有的b转换为a）
- 例如，
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
示例 1：
输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"
示例 2：
输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
示例 3：
输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"
示例 4：
输入：word1 = "cabbba", word2 = "aabbss"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
把题意翻译成充要条件就是：
两字符串的长度相同
两字符串的字符种类相同， 例如，对于某个字符，要么都有，要么都没有。
符合：word1=abbccc，word2=caabbb，都有 a、b、c
不符合：word1=abbccc，word2=abbccd，word1 只有3类字符a、b、c
字符频次相同。跟具体是什么字符无关，只要频次相同即可。
符合：word1=abbccc，word2=caabbb，都有1、2、3频次
不符合，word1=abbccc，word2=aabbcc，word1 频次有1、2、3，word2 的频次只有2
所以： 解题过程实际上在验证是否满足3个条件，而不是寻求满足 word1 转换到 word2 的方法
class Solution {
public boolean closeStrings(String word1, String word2) {
// 1. 验证长度相同
if (word1.length() != word2.length()) {
return false;
}
int[] time1 = new int[26];
int[] time2 = new int[26];
for (int i = 0; i < word1.length(); i++) {
time1[word1.charAt(i) - 'a']++;
time2[word2.charAt(i) - 'a']++;
}
// 2. 验证字符种类相同
for (int i = 0; i < 26; i++) {
if ((time1[i] > 0 && time2[i] == 0) || (time2[i] > 0 && time1[i] == 0)) {
return false;
}
}
Arrays.sort(time1);
Arrays.sort(time2);
// 3. 验证字符频次相同
for (int i = 0; i < 26; i++) {
if (time1[i] != time2[i]) {
return false;
}
}
return true;
}
}
2352. 相等行列对
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
示例 1：
输入：grid = [[3,2,1],[1,7,6],[2,7,7]]
输出：1
解释：存在一对相等行列对：
- (第 2 行，第 1 列)：[2,7,7]
示例 2：
输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
输出：3
解释：存在三对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]
方法一：模拟
思路
按照题目要求，对任意一行，将它与每一列都进行比较，如果相等，则对结果加一，最后返回总数。
class Solution {
public int equalPairs(int[][] grid) {
int res = 0, n = grid.length;
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (equal(row, col, n, grid)) {
res++;
}
}
}
return res;
}
public boolean equal(int row, int col, int n, int[][] grid) {
for (int i = 0; i < n; i++) {
if (grid[row][i] != grid[i][col]) {
return false;
}
}
return true;
}
}
方法二：哈希表
map保存各行，然后遍历每列对比map中是否存在该列
class Solution {
public int equalPairs(int[][] grid) {
int n = grid.length;
Map<List<Integer>, Integer> map = new HashMap<>();
for (int[] row : grid) {
List<Integer> arr = new ArrayList<>(); // 行
for (int num : row) {
arr.add(num);
}
map.put(arr, map.getOrDefault(arr, 0) + 1);
}
int res = 0;
for (int j = 0; j < n; j++) {
List<Integer> arr = new ArrayList<>(); //列
for (int i = 0; i < n; i++) {
arr.add(grid[i][j]);
}
if (map.containsKey(arr)) {
res += map.get(arr);
}
}
return res;
}
}
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
//对nums1去重并存入set1
for(int i = 0; i < nums1.length; i++){
set1.add(nums1[i]);
}
//nums2与set对比，相同元素存入set2
for(int num : nums2){
if(set1.contains(num)){
set2.add(num);
}
}
//将set2转化为数组
int[] res = new int[set2.size()];
int index = 0;
for(int num : set2){
res[index++] = num;
}
//方法2:将set2转化为数组
//int[] res = set2.stream().mapToInt(Integer::valueOf).toArray();
return res;
}
}
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
- 给一个数字 n，循环计算下一个数字，直到等于1
- 使用Set判断我们是否进入了一个循环。
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while(n != 1 && !set.contains(n)){
set.add(n);
n = getNextNum(n);
}
return n == 1;
}
public int getNextNum(int n) {
int nextNum = 0;
while(n > 0){
int temp = n % 10;
nextNum += temp * temp;
n = n / 10;
}
return nextNum;
}
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]),i};
}
map.put(nums[i],i);
}
return new int[0];
}
}
454. 四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
该题等价于 计算 a + b + c + d = 0
- 首先定义 map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历数组1和2，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量res，用来统计 a+b+c+d = 0 出现的次数。
- 再遍历数组3和4，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value统计出来。
- 最后返回统计值 res 就可以了
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
//key放两数之和，value放两数之和出现的次数。
for(int i : nums1){
for(int j: nums2){
map.put(i + j, map.getOrDefault(i + j, 0) + 1);
}
}
int res = 0;
//如果在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for(int i : nums3){
for(int j: nums4){
if(map.containsKey(0 - (i + j))){
res += map.get(0 - (i + j));
}
}
}
return res;
}
}
383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
//map实现
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character, Integer> map = new HashMap<>();
for(char ch : magazine.toCharArray()){
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
for(char ch : ransomNote.toCharArray()){
map.put(ch, map.getOrDefault(ch, 0) - 1);
}
for(Integer value : map.values() ){
if(value < 0) return false;
}
return true;
}
}
//哈希表实现
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] hashTable = new int[26];
for(char ch : magazine.toCharArray()){
hashTable[ch - 'a']++;
}
for(char ch : ransomNote.toCharArray()){
hashTable[ch - 'a']--;
}
for(int value : hashTable){
if(value < 0){
return false;
}
}
return true;
}
}
//优化
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] hashTable = new int[26];
for (char ch : magazine.toCharArray()) {
hashTable[ch - 'a']++;
}
// 合二为一
for (char ch : ransomNote.toCharArray()) {
if (--hashTable[ch - 'a'] < 0)
return false;
}
return true;
}
}
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 。
//三重暴力循环：超出时间限制
private List<List<Integer>> directlySolution(int[] nums) {
if (nums == null || nums.length <= 2) {
return Collections.emptyList();
}
Arrays.sort(nums);
Set<List<Integer>> result = new LinkedHashSet<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
for (int k = j+1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> value = Arrays.asList(nums[i], nums[j], nums[k]);
result.add(value);
}
}
}
}
return new ArrayList<>(result);
}
//两重暴力+hash
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
//把所有数组元素载入map
for(int i = 0; i < nums.length; i++){
map.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
int c = 0 - (nums[i] + nums[j]);
if(map.containsKey(c) && map.get(c) > j){
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(c);
Collections.sort(list);//排序，方便去重
if(!result.contains(list)){
result.add(list);
}
}
}
}
return result;
}
}
//双指针
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
//如果第一个就大于0，则三数之和一定大于0，结束循环
if(nums[i] > 0) break;
//如果连续两个元素相等就跳过第二个，避免重复
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i + 1;
int R = len - 1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if (sum < 0) L++;
else if (sum > 0) R--;
else if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L < R && nums[L] == nums[L+1]) L++; // 去重
while (L < R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
}
}
return ans;
}
}
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]]
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0 && nums[i] > target) break; //去重
if(i > 0 && nums[i] == nums[i -1]) continue; //去重
for(int j = i + 1; j < nums.length; j++){
if (j > i + 1 && nums[j - 1] == nums[j]) continue; //去重
int L = j + 1, R = nums.length - 1;
while(L < R) {
int sum = nums[i] + nums[j] + nums[L] + nums[R];
if(sum > target) R--;
else if(sum < target) L++;
else {
res.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
while(L < R && nums[L] == nums[L + 1]) L++; //去重
while(L < R && nums[R] == nums[R - 1]) R--; //去重
L++;
R--;
}
}
}
}
return res;
}
}
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 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) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2