一、数据结构⚙️
线性结构：数组、队列、链表、栈
- 顺序存储（地址连续）
- 链式存储（地址不一定连续）
非线性结构：二维数组、多维数组、广义表、树、图
必看：学习算法和刷题的框架思维 :: 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) {
// 当计数器为 0 时，假设 num 就是众数
target = 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 ，表示可以栽完花
}
}
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) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
| res[0] = | 1 | num[1] | … | num[n-2] | num[n-1] |
|---|---|---|---|---|---|
| res[1] = | num[0] | 1 | … | num[n-2] | num[n-1] |
| … | … | … | … | num[n-2] | num[n-1] |
| res[n-2] = | num[0] | num[1] | … | 1 | num[n-1] |
| res[n-1] = | num[0] | num[1] | … | num[n-2] | 1 |
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;
}
}
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) {
if (head == null || head.next == null) {
return head;
}
// 新的头结点
ListNode last = reverseList(head.next);
// 倒数第二节点和倒数第一个节点翻转
head.next.next = head;
// head 变成了最后一个节点，要指向 null
head.next = null;
return last;
}
}
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);
}
}
栈实现
//栈实现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;
}
}
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;
}
}
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);
}
}
③栈&队列&堆
❶普通队列-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();
}
}
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;
}
}
防御式编程思想：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;
}
}
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;
}
}
④哈希表
❶基础知识
哈希表(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());
}
}
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], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
LRU：把最不常用的淘汰。把所有元素按使用情况排序，最近使用的移动到末尾，缓存满了就从头删除。
方法一：用 Java 的内置类型 LinkedHashMap 实现
哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢，所以结合二者的长处，可以形成一种新的数据结构：哈希链表
LinkedHashMap
首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
this.cap = capacity;
cache = new LinkedHashMap<>();
}
public int get(int key) {
if(cache.containsKey(key)){
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
} else{
return -1;
}
}
public void put(int key, int value) {
if(cache.containsKey(key)){
cache.put(key, value);
// 将 key 变为最近使用
makeRecently(key);
} else{
//若容量已满，逐出最久未使用的关键字
if(cache.size() >= this.cap){
// 链表头部就是最久未使用的 key
int lruKey = cache.keySet().iterator().next();
cache.remove(lruKey);
}
// 将新的 key 添加链表尾部
cache.put(key, value);
}
}
//将 key 变为最近使用, 删除 key，重新插入到队尾
public void makeRecently(int key){
int value = cache.get(key);
cache.remove(key);
cache.put(key, value);
}
}
//写法2
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
//写法3
class LRUCache {
int capacity;
LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return cache.size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
方法二：自己实现LinkeHashMap
class LRUCache {
// key -> Node(key, val)
private HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
private DoubleList cache;
// 最大容量
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
// 将该数据提升为最近使用的
makeRecently(key);
return map.get(key).val;
}
public void put(int key, int val) {
if (map.containsKey(key)) {
// 如果 key 存在，修改 value
Node node = map.get(key);
node.val = val;
// 将 key 变为最近使用
makeRecently(key);
} else{
//若容量已满，逐出最久未使用的关键字
if(cache.size() >= this.cap){
// 删除最久未使用的元素
removeLeastRecently();
}
// 将新的 key 添加链表尾部,即添加为最近使用的元素
addRecently(key, val);
}
}
/* 将某个 key 提升为最近使用的 */
private void makeRecently(int key) {
Node x = map.get(key);
// 先从链表中删除这个节点
cache.remove(x);
// 重新插到队尾
cache.addLast(x);
}
/* 添加最近使用的元素 */
private void addRecently(int key, int val) {
Node x = new Node(key, val);
// 链表尾部就是最近使用的元素
cache.addLast(x);
// 别忘了在 map 中添加 key 的映射
map.put(key, x);
}
/* 删除最久未使用的元素 */
private void removeLeastRecently() {
// 链表头部的第一个元素就是最久未使用的
Node deletedNode = cache.removeFirst();
// 同时别忘了从 map 中删除它的 key
map.remove(deletedNode.key);
}
}
class Node{
int key, val;
Node prev, next;
public Node(){}
public Node(int key, int val){
this.key = key;
this.val = val;
}
}
//构建一个双链表,实现几个 LRU 算法必须的 API
class DoubleList{
// 头尾虚节点
private Node head, tail;
// 链表元素数
private int size;
//构造函数
public DoubleList(){
// 初始化双向链表的数据
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
// 在链表尾部添加节点 x，时间 O(1)
public void addLast(Node x) {
x.prev = tail.prev;
x.next = tail;
tail.prev.next = x;
tail.prev = x;
size++;
}
//删除链表中的 x 节点（x 一定存在），时间 O(1)
public void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
size--;
}
// 删除链表中第一个节点，并返回该节点，时间 O(1)
public Node removeFirst() {
if(head.next == tail){
return null;
}
Node first = head.next;
remove(first);
return first;
}
// 返回链表长度，时间 O(1)
public int size() {
return size;
}
}
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
排序
// 时间复杂度：O(nlog(n))、空间复杂度：O(1)
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums);
// max 最终结果, curr 当前长度, last 上个数字
int max = 1, curr = 1, last = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] == last) continue;
if (nums[i] == last + 1) curr++; // 符合连续，长度 +1
else {
max = Math.max(max, curr); // 连不上了，记录长度
curr = 1; // 重新开始
}
last = nums[i];
}
max = Math.max(max, curr); // 别忘了最后一段的连续区间
return max;
}
}
哈希表
想找连续序列，首先要找到这个连续序列的开头元素，然后递增，看看之后有多少个元素还在 nums 中，即可得到最长连续序列的长度了。
我们可以用空间换时间的思路，把数组元素放到哈希集合里面，然后去寻找连续序列的第一个元素，即可在 O(N) 时间找到答案。
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
// 转化成哈希集合，方便快速查找是否存在某个元素
Set<Integer> set = new HashSet<>();
for(int num : nums){
set.add(num);
}
for(int num : set){
// num 不是连续子序列的第一个，跳过
if(set.contains(num - 1)) continue;
// num 是连续子序列的第一个，开始向上计算连续子序列的长度
int curNum = num; //「以 num 开头，能连续到多少」
while(set.contains(curNum + 1)){
curNum++;
}
res = Math.max(res, curNum - num + 1);
}
return res;
}
}
⑤字符串
双指针：344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中
s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
l++;
r--;
}
}
}
双指针： 541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
题意：每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转
for (int i = 0; i < n; i += 2 * k) {
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= n) {
reverse(arr, i, i + k - 1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转
reverse(arr, i, n - 1);
}
return new String(arr);
}
// 定义翻转函数
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for (int i = 0; i < n; i += 2 * k) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
reverse(arr, i, Math.min(i + k, n) - 1);
}
return String.valueOf(arr);
}
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
双指针：345. 反转字符串中的元音字母
给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
示例 1：
输入：s = "hello"
输出："holle"
示例 2：
输入：s = "leetcode"
输出："leotcede"
class Solution {
public String reverseVowels(String s) {
//定义两个哨兵
int l = 0, r = s.length() - 1;
char[] arr = s.toCharArray();
while (l < r) {
//从左往右找元音字母，找到就停止，没找到就继续右移
while (!"aeiouAEIOU".contains(String.valueOf(arr[l])) && l < r) l++;
//从右往左找元音字母，找到就停止，没找到就继续左移
while (!"aeiouAEIOU".contains(String.valueOf(arr[r])) && l < r) r--;
//两边都找到就交换它们
if (l < r) {
char temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
}
return new String(arr);
}
}
双指针：1768. 交替合并字符串
给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
返回 合并后的字符串 。
示例 1：
输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1： a b c
word2： p q r
合并后： a p b q c r
示例 2：
输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1： a b
word2： p q r s
合并后： a p b q r s
示例 3：
输入：word1 = "abcd", word2 = "pq"
输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1： a b c d
word2： p q
合并后： a p b q c d
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int m = word1.length(), n = word2.length();
int i = 0, j = 0;
while(i < m && j < n){
sb.append(word1.charAt(i));
sb.append(word2.charAt(j));
i++;
j++;
}
while(i < m){
sb.append(word1.charAt(i));
i++;
}
while(j < n){
sb.append(word2.charAt(j));
j++;
}
return sb.toString();
}
}
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int m = word1.length(), n = word2.length();
int i = 0, j = 0;
while(i < m || j < n){
if(i < m){
sb.append(word1.charAt(i));
i++;
}
if(j < n){
sb.append(word2.charAt(j));
j++;
}
}
return sb.toString();
}
}
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
输入：s = "We are happy."
输出："We%20are%20happy."
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){
sb.append("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
剑指 Offer 58 - I. 翻转单词顺序
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
class Solution {
public String reverseWords(String s) {
// 除去开头和末尾的空白字符
s = s.trim();
// 正则匹配连续的空白字符作为分隔符分割
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}
// 分割 + 倒序
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
if(strs[i].equals("")) continue; // 遇到空则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
}
}
// 双指针
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
for(int i = n; i < s.length(); i++){
sb.append(s.charAt(i));
}
for(int i = 0; i < n; i++){
sb.append(s.charAt(i));
}
return sb.toString();
}
}
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
暴力破解
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
// 枚举原串的「发起点」
for(int i = 0; i <= n - m; i++){
boolean flag = true;
for(int j = 0; j < m; j++){
// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
if(haystack.charAt(i + j) != needle.charAt(j)){
flag = false;
break;
}
}
// 如果能够完全匹配，返回原串的「发起点」下标
if(flag) return i;
}
return -1;
}
}
KMP算法
class Solution {
public static int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
// 1.构建 next 数组
int[] next = new int[m]; //next[0]=0
for (int i = 1, j = 0; i < m; i++) {
// 匹配不成功的话，j = next(j-1)
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
// 匹配成功的话，j++
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
// 更新 next[i]
next[i] = j;
}
// 2.匹配过程
for (int i = 0, j = 0; i < n; i++) {
// 匹配不成功 j = next(j-1)
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
// 匹配成功的话，j++
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
}
459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
方法一：枚举
如果一个长度为 n 的字符串 s 可以由它的一个长度为 m 的子串 s′ 重复多次构成，那么：
- n 一定是 m 的倍数；
- s′ 一定是 s 的前缀；
- 对于任意的
i∈[m,n)，有s[i] = s[i − m]。
小优化：因为子串至少需要重复一次，所以 m 不会大于 n 的一半，所以只需在 [1,n/2]的范围内枚举 m 即可。
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for(int m = 1; m <= n/2; m++){
if(n % m == 0){
boolean match = true;
for(int i = m; i < n; i++){
if(s.charAt(i) != s.charAt(i - m)) {
match = false;
break;
}
}
if(match){
return true;
}
}
}
return false;
}
}
415. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
示例 2：
输入：num1 = "456", num2 = "77"
输出："533"
示例 3：
输入：num1 = "0", num2 = "0"
输出："0"
- 算法流程： 设定
i，j两指针分别指向num1，num2尾部，模拟人工加法；- 计算进位： 计算
carry = tmp / 10，代表当前位相加是否产生进位； - 添加当前位： 计算
tmp = n1 + n2 + carry，并将当前位tmp % 10添加至res头部； - 索引溢出处理： 当指针
i或j走过数字首部后，给n1，n2赋值为 0，相当于给num1，num2中长度较短的数字前面填 0，以便后续计算。 - 当遍历完
num1，num2后跳出循环，并根据carry值决定是否在头部添加进位 1，最终返回res即可。
- 计算进位： 计算
- 复杂度分析：
- 时间复杂度 O(max(M,N)))：其中 M，N 为num1 和 num2长度；
- 空间复杂度 O(1)：指针与变量使用常数大小空间。
char 转 int ：字符的ASCII码值减去0的ASCII码值等于数值本身。 即num1.charAt(i) - '0'
进位操作：2. 两数相加、本题解题思路参考：415. 字符串相加 -题解
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder("");
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while(i >= 0 || j >= 0){
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int tmp = n1 + n2 + carry;
carry = tmp / 10; //进位
res.append(tmp % 10);
i--; j--;
}
if(carry == 1) res.append(1);
return res.reverse().toString();
}
}
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
- 乘数 num1 位数为 m，被乘数 num2 位数为 n， num1 x num2 结果 res 最大总位数为 m+n
- num1[i] x num2[j] 的结果为 tmp(位数为两位，”0x”, “xy” 的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int m = num1.length(), n = num2.length();
// 结果最多为 m + n 位数
int[] res = new int[m + n];
// 从个位数开始逐位相乘
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int n1 = num1.charAt(i) - '0';
int n2 = num2.charAt(j) - '0';
int p1 = i + j, p2 = i + j + 1;
// 叠加到 res 上
int sum = (res[p2] + n1 * n2);
// 乘积在 res 对应的索引位置
// num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。
res[p2] = sum % 10;
res[p1] += sum / 10;
}
}
// 将计算结果转化成字符串
StringBuilder result = new StringBuilder();
for (int i = 0; i < res.length; i++) {
// 结果前缀可能存的 0（未使用的位）
if (i == 0 && res[i] == 0) continue;
result.append(res[i]);
}
return result.toString();
}
}
num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。
 |
 |
|---|
8. 字符串转换整数 (atoi)
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"
辅助栈
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();
}
}
数学：1071. 字符串的最大公因子
对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""
辗转相除法， 又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数。
class Solution {
public String gcdOfStrings(String str1, String str2) {
// 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。
if(!(str1 + str2).equals(str2 + str1)){
return "";
}
// 辗转相除法求gcd。
return str1.substring(0, gcd(str1.length(), str2.length()));
}
// 辗转相除法
public int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
}
//辗转相除法
public int gcd(int a, int b) {
int remainder = a % b; // 余数
while (remainder != 0) {
// 除数和余数交换
a = b;
b = remainder;
remainder = a % b;
}
return b;
}
⑥双指针
344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中
s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
l++;
r--;
}
}
}
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;
}
}
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
class Solution {
public void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0
// 返回去除 0 之后的数组长度
int p = removeElement(nums, 0);
// 将 p 之后的所有元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 双指针技巧，复用 [27. 移除元素] 的解法。
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
快排思想，用 0 当做这个中间点，把不等于 0的放到中间点的左边，等于 0 的放到其右边。使用两个指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]
class Solution {
public void moveZeroes(int[] nums) {
if(nums==null) {
return;
}
//两个指针i和j
int j = 0;
for(int i=0;i<nums.length;i++) {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if(nums[i]!=0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j++] = tmp;
}
}
}
}
剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
输入：s = "We are happy."
输出："We%20are%20happy."
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){
sb.append("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
151. 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
class