leetcode--hot100--思路+知识点（I）

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出target的那整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。[0,1]因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。#include <utility> // 包含 pair 头文件// 1. 初始化// 2.两个元素通过公

weixin_45859446

674人浏览 · 2025-10-29 22:09:58

weixin_45859446 · 2025-10-29 22:09:58 发布

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

思路:排序后使用双指针，由于需要返回下标，需要使用pair结构

#include <utility> // 包含 pair 头文件

// 1. 初始化

std::pair<int, std::string> p(10, "hello")

auto p2 = std::make_pair(2, "two");

// 2.两个元素通过公有成员 first 和 second 直接访问

std::cout << p.first; // 输出：10

std::cout << p.second; // 输出：hello

vector<int> twoSum(vector<int>& nums, int target) {

vector<pair<int,int>>Nums;

for(int i=0;i<nums.size();++i){

Nums.push_back({nums[i], i}); //Nums.emplace_back(nums[i], i);也可

}

sort(Nums.begin(),Nums.end());

int i=0,j=nums.size()-1; //双指针初始化

while(i<j)

{

if(Nums[i].first+Nums[j].first==target)

{return {Nums[i].second, Nums[j].second };}

else if(Nums[i].first+Nums[j].first<target)

{

i++;

}

else{

j--;

}

}

return {};

}

优化：pair排序需要nlogn—>使用哈希表存储元素值与索引只要n

#include <unordered_map>

// 定义 unordered_map（键为 int，值为 string）

unordered_map<int, string> myMap;

// 2. 初始化列表赋值（C++11）

unordered_map<int, string> map2 = { {1, "apple"}, {2, "banana"}, {3, "cherry"} };

//插入
myMap[1] = "one"; // 插入 {1, "one"}
myMap[1] = "first"; // 覆盖值，变为 {1, "first"}
myMap.insert({2, "two"}); // 插入 {2, "two"}
myMap.emplace(4, "four"); // 插入 {4, "four"}

//查找

auto it = myMap.find(1); // 查找键为 1 的元素

//删除

myMap.erase(2); // 删除键为 2 的元素
myMap.clear(); // 清空 map，size 变为 0

//遍历

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
cout << it->first << " => " << it->second << endl;
}

class Solution {

public: vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> numMap;

for (int i = 0; i < nums.size(); ++i)

{

int complement = target - nums[i];

// 在哈希表查找是否有键为complement

if (numMap.find(complement) != numMap.end()) {

// 若存在，返回差值的索引和当前元素的索引

return {numMap[complement], i}; }

// 若不存在，将当前元素及其索引存入哈希表

numMap[nums[i]] = i;

}

return {}; }

};

2.字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路：哈希表，同一组异位词用一个键--> unordered_map<string, vector<string>> hashMap;

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

unordered_map<string, vector<string>> hashMap;

for (string s : strs) {

string key = s; // 复制

sort(key.begin(), key.end()); // 排序生成key

hashMap[key].push_back(s); // 加入对应分组

}

//返回哈希表每个键的值即可

vector<vector<string>> result;

for (auto& pair : hashMap) { //注：不加&会进行值拷贝

result.push_back(pair.second);

}

//也可以写成这样

for (auto it = hashMap.begin(); it != hashMap.end(); ++it) {

result.push_back(it->second); //或result.push_back（(*it).second）

}

//注：pair 是 “对象”，it 是指针（迭代器）

return result;

}

};

3.连续最长序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：利用unordered_set特性去重，然后找到每个序列的开端（起点），更新序列长度

#include <unordered_set>

unordered_set<int> s = {1, 2, 3, 4};

// 用迭代器范围构造（从其他容器复制元素）

vector<int> vec = {5, 6, 7};

unordered_set<int> s2(vec.begin(), vec.end());

// 复制构造

unordered_set<int> s3(s2);

//插入

unordered_set<int> s;

s.insert(5);

//查找

if (s.find(1) != s.end()) {
cout << "元素 1 存在" << endl;
} else {
cout << "元素 1 不存在" << endl;
}

//删除

s.erase(1); // 删除元素 1

class Solution {

public:

int longestConsecutive(vector<int>& nums) {

if (nums.empty()) return 0;

unordered_set<int> numSet(nums.begin(), nums.end());

int maxLen = 0;

for (int x : numSet) {

if (numSet.find(x - 1) == numSet.end()) { //判断x是否是某序列起点

int current = x;

int currentLen = 1;

// 循环扩展序列

while (numSet.find(current + 1) != numSet.end()) {

current++;

currentLen++;

}

maxLen = max(maxLen, currentLen); //返回所有序列长度的最大值

}

}

return maxLen;

}

};

4.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

思路：快慢双指针，快指针遍历数组，遇到非0则保存到慢指针

class Solution {

public:

void moveZeroes(vector<int>& nums) {

int slow = 0; // 慢指针：指向当前已处理好的非零元素的下一个位置

for (int fast = 0; fast < nums.size(); ++fast) {

if (nums[fast] != 0) {

swap(nums[slow], nums[fast]);

slow++; // 慢指针前移，指向新的待填充位置

}

}

}

};

5.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49

思路：双指针。容积=(right-left)×min{height[left],height[right]}，遍历，移动短边使得后一项变大

class Solution {

public:

int maxArea(vector<int>& height) {

int max_a=0;

int left=0;

int right= height.size()-1;

while(left<right){

int current_height = min(height[left], height[right]);

int curr_area=(right-left)*current_height;

max_a=max(max_a,curr_area);//更新最大值

if(height[left]<height[right])

{left++;}

else{right--;}

}

return max_a;

}

};

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路：关键点在于去重。排序后遍历（固定最左边一个），使用双指针。

class Solution {

public:

vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> res;

sort(nums.begin(), nums.end()); // 排序（升序）

int n = nums.size();

for (int i = 0; i < n-2; ++i) {

if (nums[i] > 0) break; //是正数则直接退出循环

// 去重

if (i > 0 && nums[i] == nums[i-1]) continue;

// 双指针

int left = i + 1;

int right = n - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {

// 找到符合条件的三元组，加入结果

res.push_back({nums[i], nums[left], nums[right]});

// 去重：跳过left和right的重复元素

while (left < right && nums[left] == nums[left+1]) left++;

while (left < right && nums[right] == nums[right-1]) right--;

// 移动双指针继续寻找

left++;

right--;

} else if (sum < 0) {

left++;

} else {

right--;

}

}

}

return res;

}

};

7.接雨水

定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

思路：双指针，较低一侧的柱子，left值<=right值，更新left_max或result，反之同理。

int trap(vector<int>& height) {
if (height.empty()) return 0;
int left = 0, right = height.size() - 1;
int left_max = 0, right_max = 0;
int result = 0;

while (left < right) {
if (height[left] <= height[right]) {
// 左侧为较低屏障，处理左指针
if (height[left] >= left_max) {
left_max = height[left];
} else {
result += left_max - height[left];
}
left++;
} else {
// 右侧为较低屏障，处理右指针
if (height[right] >= right_max) {
right_max = height[right];
} else {
result += right_max - height[right];
}
right--;
}
}
return result;
}

8.无重复字符最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "pwwkew"
输出: 3

思路：遍历一遍字符串，维护一个窗口，用于维护子串，并记录窗口长度

lastOccur数组记录每个字符最后一次在字符串中出现的索引位置

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int lastOccur[128] ;

fill(lastOccur, lastOccur + 128, -1); // 初始化为-1（表示未出现）

//注：若c = 'a'，那么lastOccur[97]==lastOccur[c]

int maxLen = 0;

int left = 0;

for (int right = 0; right < s.size(); ++right) {

char c = s[right]; //当前正在处理的字符

if (lastOccur[c] >= left) {

left = lastOccur[c] + 1;//左边界，移动到 “字符 c 上一次出现位置的下一位”

}

lastOccur[c] = right;//更新字符 c 最后一次出现的索引为当前 right

maxLen = max(maxLen, right - left + 1);

}

return maxLen;

}

};

9.字符串的字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路：同上题，统计 p 中每个字符的出现次数，在s中维护滑动窗口，与 pCount 对比

int pCount[26] = {0};
int sCount[26] = {0}; // 滑动窗口
vector<int> res;
// 初始化p的字符计数，以及s中第一个窗口的字符计数
for (int i = 0; i < p.size(); ++i) {
pCount[p[i] - 'a']++; // 'a'-'a'=0, 'b'-'a'=1, ...
sCount[s[i] - 'a']++;
}

if (isEqual(pCount, sCount)) {
res.push_back(0); // 起始索引为0
}

// 滑动窗口
for (int i = pLen; i < sLen; ++i) {
// 移除窗口左侧的字符 （i-pLen是左边界索引）
sCount[s[i - pLen] - 'a']--;
// 加入窗口右侧的新字符 （i是右边界索引）
sCount[s[i] - 'a']++;

// 检查当前窗口是否匹配
if (isEqual(pCount, sCount)) {
res.push_back(i - pLen + 1); // 左边界 = i - pLen + 1
}
}

return res;

bool isEqual(int a[], int b[]) {
for (int i = 0; i < 26; ++i) {
if (a[i] != b[i]) return false;
}
return true;
}

10.和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

输入：nums = [1,1,1], k = 2
输出：2

思路：前缀和，即构造数组prefix，其中prefix[i] 表示数组前 i 个元素的和

-->寻找子数组nums[i to j] = k = prefix[j] - prefix[i]

int subarraySum(vector<int>& nums, int k) {

unordered_map<int, int> prefix;

prefix[0] = 1; // 初始化：前缀和为0出现1次

int currentSum = 0; // 当前前缀和

int result = 0; // 结果计数

for (int num : nums) {

currentSum += num; // 更新当前前缀和

// 查找是否存在 prefix[j] = currentSum - k

if (prefix.find(currentSum - k) != prefix.end()) {

result += prefix[currentSum - k];

}

// 将当前前缀和加入哈希表（次数+1）

prefix[currentSum]++;

}

return result;

}

11.滑动窗口最大值***

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

思路：暴力破解需要n*k，单调队列只需要n

初始化队列：用于存储窗口内元素的索引，保持队列单调递减。

遍历数组元素：

移除过期元素：如果队首元素的索引已经超出当前窗口范围（即 索引 <= 当前索引 - k），则从队首移除（因为它不再属于当前窗口）。

维护单调性：对于当前元素，从队尾开始移除所有值小于当前元素的索引（因为这些元素在当前元素右侧，且值更小，永远不可能成为后续窗口的最大值）。

加入当前元素：将当前元素的索引加入队尾。

记录最大值：当遍历到第 i >= k-1 个元素时（窗口已形成），队首元素就是当前窗口的最大值，将其加入结果列表

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
deque<int> q; // 存储索引
int n = nums.size();

for (int i = 0; i < n; ++i) {
// 1. 移除窗口外的元素
if (!q.empty() && q.front() <= i - k) {
q.pop_front();
}

// 2. 维护队列单调性
// 这些元素在当前元素右侧，且值更小，永远不可能成为最大值
while (!q.empty() && nums[q.back()] < nums[i]) {
q.pop_back();
}

// 3. 将当前元素索引加入队列
q.push_back(i);

// 4. 当窗口大小达到 k 时，开始记录最大值（队首元素）
if (i >= k - 1) {
result.push_back(nums[q.front()]);
}
}

return result;
}
};

12.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

思路：更新当前子数组(加入新值或者从新值开始），更新最大值

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int max_sum = nums[0]; // 初始化为第一个元素

int current_sum = nums[0];//以当前元素结尾的子数组的最大和

for (int i = 1; i < nums.size(); ++i) {

current_sum = max(nums[i], current_sum + nums[i]);//当前元素自己开始还是接着之前子数组累加

max_sum = max(max_sum, current_sum);

}

return max_sum;

}

};

13.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：首先把数组按照start进行sort排序，然后合并条件是intervals[i][1]>intervals[i+1][0]

补充知识：

int rows = intervals.size(); // 行数

int cols = intervals[0].size(); // 列数

class Solution {

public:

vector<vector<int>> merge(vector<vector<int>>& intervals) {

if (intervals.empty()) {

return {};

}

sort(intervals.begin(), intervals.end());

vector<vector<int>> res;

res.push_back(intervals[0]);

for(int i = 1; i < intervals.size(); ++i) {

auto& last = res.back();

// 当前区间的起始和结束

int curr_start = intervals[i][0];

int curr_end = intervals[i][1];

if (curr_start > last[1]) {

// 不重叠，直接加入

res.push_back(intervals[i]);

} else {

// 重叠，合并区间（更新结束值为两者最大值）

last[1] = max(last[1], curr_end);

}

}

return res;

}

};

14.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

思路：n=nums.size()，轮转k1=k%n，首先保存nums[0]到nums[n-k1-1]为A，

然后nums[n-k1]到nums[n-1]覆盖原来的部分

A塞入nums[k1]到nums[n-1]部分

class Solution {

public:

void rotate(vector<int>& nums, int k) {

int n=nums.size();

int k1=k%n;

vector<int>A;

for(int i=0;i<n-k1;i++){

A.push_back(nums[i]);

}

for(int i=n-k1;i<n;++i){

nums[i-n+k1]=nums[i];

}

for(int i=0;i<n-k1;i++){

nums[k1+i]=A[i];

}

}

};

15.除以自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

输入: nums = [1,2,3,4]

输出: [24,12,8,6]

思路：首先计算前缀乘积，然后再与后缀乘积相乘

vector<int> productExceptSelf(vector<int>& nums) {

int n = nums.size();

vector<int> answer(n, 1);

// 计算前缀乘积

int prefix = 1;

for (int i = 0; i < n; ++i) {

answer[i] = prefix;

prefix *= nums[i];

}

// 计算后缀乘积并与前缀乘积相乘

int suffix = 1;

for (int i = n - 1; i >= 0; --i) {

answer[i] *= suffix;

suffix *= nums[i];

}

return answer;

}

15.缺失的第一个正数***

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

输入：nums = [1,2,0]
输出：3

思路：让数值为 x 的元素（如果 x 是 1~n 之间的正整数），放到索引为 x-1 的位置上。比如数值 1 应该在索引 0，数值 2 应该在索引 1。最后只要检查哪个索引 i 上的元素不是 i+1，那 i+1 就是没出现的最小正整数。

class Solution {

public:

int firstMissingPositive(vector<int>& nums) {

int n = nums.size();

// 第一步：将每个正整数放到正确的位置上

for (int i = 0; i < n; ++i) {

// 只处理范围内的正整数，且确保交换后不会重复处理

while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {

// 将nums[i]放到索引nums[i]-1的位置

swap(nums[i], nums[nums[i] - 1]);

}

}

// 第二步：检查哪个位置的元素不匹配

for (int i = 0; i < n; ++i) {

if (nums[i] != i + 1) {

return i + 1;

}

}

// 所有位置都匹配，返回n+1

return n + 1;

}

};

16.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

思路：先用两个flag标记第一行和第一列是否有0；

然后从遍历矩阵，如果matrix[i][j]==0,那么把matrix[i][0]==0，matrix[0][j]==0；

遍历矩阵第一行，如果有0，把这一列都变为0，列同理；

根据flag操作第一行和第一列

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

int m = matrix.size();

if (m == 0) return;

int n = matrix[0].size();

// 标记第一行和第一列是否原本就有0

bool row0_has_zero = false;

bool col0_has_zero = false;

// 检查第一行是否有0

for (int j = 0; j < n; ++j) {

if (matrix[0][j] == 0) {

row0_has_zero = true;

break;

}

}

// 检查第一列是否有0

for (int i = 0; i < m; ++i) {

if (matrix[i][0] == 0) {

col0_has_zero = true;

break;

}

}

// 遍历矩阵，用第一行和第一列记录0的位置

for (int i = 1; i < m; ++i) {

for (int j = 1; j < n; ++j) {

if (matrix[i][j] == 0) {

matrix[i][0] = 0; // 标记当前行需要置0

matrix[0][j] = 0; // 标记当前列需要置0

}

}

}

// 根据第一列的标记，将对应行置0

for (int i = 1; i < m; ++i) {

if (matrix[i][0] == 0) {

for (int j = 1; j < n; ++j) {

matrix[i][j] = 0;

}

}

}

// 根据第一行的标记，将对应列置0

for (int j = 1; j < n; ++j) {

if (matrix[0][j] == 0) {

for (int i = 1; i < m; ++i) {

matrix[i][j] = 0;

}

}

}

// 处理第一行

if (row0_has_zero) {

for (int j = 0; j < n; ++j) {

matrix[0][j] = 0;

}

}

// 处理第一列

if (col0_has_zero) {

for (int i = 0; i < m; ++i) {

matrix[i][0] = 0;

}

}

}

};

17.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

思路：用4个int变量表示上下左右4个边界，然后用一个int flag变量表示当前返回的路径方向，进行处理

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

vector<int> result;

if (matrix.empty()) return result;

// 定义上下左右四个边界

int top = 0; // 上边界（初始为第一行）

int bottom = matrix.size() - 1; // 下边界（初始为最后一行）

int left = 0; // 左边界（初始为第一列）

int right = matrix[0].size() - 1; // 右边界（初始为最后一列）

// 方向标记：0-右移，1-下移，2-左移，3-上移

int flag = 0;

while (top <= bottom && left <= right) {

if (flag == 0) { // 从左到右遍历上边界

for (int i = left; i <= right; ++i) {

result.push_back(matrix[top][i]);

}

top++; // 上边界下移一行

flag = 1; // 切换方向为下移

}

else if (flag == 1) { // 从上到下遍历右边界

for (int i = top; i <= bottom; ++i) {

result.push_back(matrix[i][right]);

}

right--; // 右边界左移一列

flag = 2; // 切换方向为左移

}

else if (flag == 2) { // 从右到左遍历下边界

for (int i = right; i >= left; --i) {

result.push_back(matrix[bottom][i]);

}

bottom--; // 下边界上移一行

flag = 3; // 切换方向为上移

}

else { // flag == 3，从下到上遍历左边界

for (int i = bottom; i >= top; --i) {

result.push_back(matrix[i][left]);

}

left++; // 左边界右移一列

flag = 0; // 切换方向为右移

}

}

return result;

}

};

18.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

思路：顺时针旋转 90 度 = 转置 + 行翻转

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

int n = matrix.size();

// 第一步：矩阵转置（只遍历上三角，避免重复交换）

for (int i = 0; i < n; ++i) {

for (int j = i + 1; j < n; ++j) {

swap(matrix[i][j], matrix[j][i]);

}

}

// 第二步：翻转每一行

for (int i = 0; i < n; ++i) {

reverse(matrix[i].begin(), matrix[i].end());

}

}

};

旋转操作对比表

顺时针旋转 90 度	先对矩阵进行转置（将矩阵中`matrix[i][j]`的元素和`matrix[j][i]`的元素交换，只交换上三角和下三角部分），然后翻转每一行（将每一行的元素左右翻转）
逆时针旋转 90 度	先对矩阵进行转置，然后翻转每一列（将每一列的元素上下翻转）
旋转 180 度	先翻转每一行，然后再翻转每一列；或者直接将矩阵中`matrix[i][j]`的元素和`matrix[n - 1 - i][n - 1 - j]`的元素交换

19.搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路：从右上角开始遍历，如果比这个数小就左移，比这个数大就下移

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty() || matrix[0].empty()) return false;

int m = matrix.size(); // 行数

int n = matrix[0].size(); // 列数

int row = 0;

int col = n - 1;

while (row < m && col >= 0) {

if (matrix[row][col] == target) {

return true; // 找到目标值

} else if (matrix[row][col] > target) {

col--; // 当前值太大，左移一列

} else {

row++; // 当前值太小，下移一行

}

}

return false; // 遍历完未找到

}

};

20.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

知识点：链表（Linked List）是一种常见的线性数据结构，它由一系列节点（ListNode）组成，每个节点包含数据域（存储数据）和指针域（指向后续节点）。

struct ListNode {

int val; // 数据域：存储节点的值

ListNode *next; // 指针域：指向后一个节点的指针

// 构造函数：初始化节点值，默认 next 为 NULL

ListNode(int x) : val(x), next(NULL) {}

};

手动连接节点形成链表（以 1 -> 2 -> 3 为例）：

ListNode* head = new ListNode(1); // 头节点

head->next = new ListNode(2); // 连接第二个节点

head->next->next = new ListNode(3); // 连接第三个节点

思路：用两个指针同时从A和B的头结点出发，走完当前链表后移动到另一条链表，如果两个指针指向同一个节点，那么说明相交。

class Solution {

public:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

if (headA == nullptr || headB == nullptr) {

return nullptr;

}

ListNode *pA = headA;

ListNode *pB = headB;

while (pA != pB) {

// pA走完A则转向B，否则继续走A

pA = (pA == nullptr) ? headB : pA->next;

// pB走完B则转向A，否则继续走B

pB = (pB == nullptr) ? headA : pB->next;

}

return pA;

}

};

21.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路：本质是逐个改变节点的 next 指针方向。使用三个指针遍历链表：prev（前一个节点）、cur（当前节点）、next（临时保存下一个节点）。

class Solution {

public:

ListNode* reverseList(ListNode* head) {

// 本质是逐个改变节点的 next 指针方向。

// 使用三个指针遍历链表：prev（前一个节点）、cur（当前节点）、next（临时保存下一个节点）。

ListNode* prev = nullptr;

ListNode* cur = head;

//遍历过程中，逐个反转 cur 的指向（cur->next = prev），

//同时更新三个指针的位置，直到 cur 指向 null（遍历结束）。

while (cur != nullptr) {

ListNode* next = cur->next; // 保存cur->next 2

cur->next = prev; // cur指向改为prev

prev = cur; // prev后移 0->1

cur = next; // cur后移 1->2

}

//最后一轮cur==nullptr, prev成为新的头节点

return prev;

}

};

22.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

思路：先用快慢指针找到链表的中点，然后用栈判断

        stack<int> st;

        ListNode* slow = head;
        ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);  // 前半部分节点值入栈
        slow = slow->next;   // 慢指针走1步
        fast = fast->next->next;  // 快指针走2步
    }
// 注意，若链表长度为奇数，如1,2,3,2,1慢指针需跳过中间节点
if (fast != nullptr) { // 此时fast指向最后一个节点，说明长度为奇数
slow = slow->next;
}

    while (slow != nullptr) {
        int top = st.top();
        st.pop();
        if (slow->val != top) {
            return false;  // 不相等则不是回文
        }
        slow = slow->next;
    }

    return true;  // 所有对比都相等，是回文

用栈处理会引入额外的栈空间，可改为翻转链表，slow->next作为后半部分的头结点。

（翻转链表代码参考上一题）

bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return true;  // 空链表或单个节点是回文
    }

    // 第一步：快慢指针找中点
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;       // 慢指针走1步
        fast = fast->next->next; // 快指针走2步
    }
    // 此时slow指向中间节点（奇数长度）或左半部分末尾（偶数长度）

    // 第二步：反转后半部分链表（从slow->next开始）
    ListNode* secondHalf = reverseList(slow->next);

    // 第三步：对比前半部分和反转后的后半部分
    ListNode* p1 = head;         // 前半部分指针
    ListNode* p2 = secondHalf;   // 反转后后半部分指针
    bool result = true;
    while (result && p2 != nullptr) {
        if (p1->val != p2->val) {
            result = false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    // （可选）还原链表（若题目允许修改原链表，可省略此步）
    slow->next = reverseList(secondHalf);

    return result;
}

23.环形链表（I）

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

解题思路同下一题

24.环形链表（II）

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点

思路：快慢指针，若快指针到达尾部（无环），快慢指针相遇则有环

.注：从头节点和相遇点分别出发的两个指针（均走 1 步 / 次），最终会在入环点相遇。

ListNode *detectCycle(ListNode *head) {

if (head == nullptr || head->next == nullptr) {

return nullptr; // 空链表或单节点无环

}

// 第一步：快慢指针判断是否有环，并找到相遇点

ListNode* slow = head;

ListNode* fast = head;

bool hasCycle = false;

while (fast != nullptr && fast->next != nullptr) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast) {

hasCycle = true;

break;

}

}

if (!hasCycle) {

return nullptr; // 无环

}

// 第二步：头节点和相遇点各出发一个指针，相遇点即为入环点

ListNode* p1 = head;

ListNode* p2 = slow; // slow和fast的相遇点

while (p1 != p2) {

p1 = p1->next;

p2 = p2->next;

}

return p1; // 入环点

}

25. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：用一个虚拟头结点简化操作，即无论 l1 和 l2 是否为空，都可以统一从虚拟头结点开始操作，无需单独判断初始状态。

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// 创建一个虚拟头节点，简化操作

ListNode* dummy = new ListNode(0);

ListNode* current = dummy; // 用于构建新链表的指针

// 遍历两个链表，选择较小的节点连接到新链表

while (l1 != nullptr && l2 != nullptr) {

if (l1->val < l2->val) {

current->next = l1; // 连接l1节点

l1 = l1->next; // 移动l1指针

} else {

current->next = l2; // 连接l2节点

l2 = l2->next; // 移动l2指针

}

current = current->next; // 移动current指针

}

// 如果l1或l2还有剩余节点，直接连接到新链表末尾

if (l1 != nullptr) {

current->next = l1;

} else if (l2 != nullptr) {

current->next = l2;

}

// 返回新链表的头节点（跳过虚拟头节点）

return dummy->next;

}

};

26.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

思路：链表是逆序存储，直接相加，保存进位标志即可

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点

ListNode* current = dummy; // 用于构建新链表的指针

int carry = 0; // 进位标志

// 遍历两个链表，直到两个链表都为空且没有进位

while (l1 != nullptr || l2 != nullptr || carry != 0) {

int sum = carry; // 初始化sum为进位值

if (l1 != nullptr) {

sum += l1->val; // 加上l1的当前节点值

l1 = l1->next; // 移动l1指针

}

if (l2 != nullptr) {

sum += l2->val; // 加上l2的当前节点值

l2 = l2->next; // 移动l2指针

}

carry = sum / 10; // 更新进位值

current->next = new ListNode(sum % 10); // 创建新节点并连接到新链表

current = current->next; // 移动current指针

}

return dummy->next; // 返回新链表的头节点（跳过虚拟头节点）

}

};

27.删除链表的倒数第 `n` 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：虚拟结点，让fast先走n+1步，结束时slow正好在倒数第n个节点的前一个节点

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

// 创建一个虚拟头节点，简化操作

ListNode* dummy = new ListNode(0);

dummy->next = head;

ListNode* fast = dummy;

ListNode* slow = dummy;

// 让fast先走n+1步

for (int i = 0; i <= n; ++i) {

fast = fast->next;

}

// 同时移动fast和slow，直到fast到达末尾

while (fast != nullptr) {

fast = fast->next;

slow = slow->next;

}

// 删除倒数第n个节点

ListNode* nodeToDelete = slow->next;

slow->next = slow->next->next;

delete nodeToDelete; // 释放被删除节点的内存

// 返回新链表的头节点（跳过虚拟头节点）

ListNode* newHead = dummy->next;

delete dummy; // 释放虚拟头节点的内存

return newHead;

}

};

28.两两交换其中相邻的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

思路：虚拟头结点，prev + first + second + second->next

每次操作如下：prev先指向second，然后first指向second->next，最后second指向first

操作完成后变成了 prev+ second+ first + second->next

那么新一轮的prev=first，或者写成prev=prev->next->next

class Solution {

public:

ListNode* swapPairs(ListNode* head) {

// 创建一个虚拟头节点，简化操作

ListNode* dummy = new ListNode(0);

dummy->next = head;

ListNode* prev = dummy; // 用于连接交换后的节点

while (prev->next != nullptr && prev->next->next != nullptr) {

ListNode* first = prev->next; // 第一个节点

ListNode* second = prev->next->next; // 第二个节点

// 交换节点

prev->next = second; // 连接前一个节点到第二个节点

first->next = second->next; // 连接第一个节点到第二个节点的下一个节点

second->next = first; // 连接第二个节点到第一个节点

// 移动prev指针到下一个待交换的节点对前面

prev = first;

}

// 返回新链表的头节点（跳过虚拟头节点）

return dummy->next;

}

};

29.每 k 个节点一组进行翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

思路：创建虚拟头节点，分组遍历，若不足 k 个则停止。翻转当前组：调整节点间的指针，完成翻转。连接各组：将翻转后的组与前一组、后一组正确连接。翻转链表代码同21

ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k == 1) return head; // 空链表或k=1无需翻转

// 虚拟头节点，简化头节点处理
ListNode* dummy = new ListNode(0);
dummy->next = head;

// pre：当前组的前一个节点（翻转后作为组的尾节点的前一个）
// end：当前组的尾节点（初始指向pre，用于寻找组的范围）
ListNode* pre = dummy;
ListNode* end = dummy;

while (end->next != nullptr) {
// 移动end，找到当前组的尾节点（共k个节点）
for (int i = 0; i < k && end != nullptr; ++i) {
end = end->next;
}
if (!end) break; // 剩余节点不足k个，停止处理

// 记录当前组的头节点（翻转后变为尾节点）和下一组的头节点
ListNode* start = pre->next;
ListNode* nextGroup = end->next;

// 断开当前组与下一组的连接（便于单独翻转当前组）
end->next = nullptr;

// 翻转当前组，并将翻转后的头节点连接到pre后面
pre->next = reverseList(start);

// 翻转后，原start变为当前组的尾节点，连接到下一组
start->next = nextGroup;

// 更新pre和end，准备处理下一组
pre = start;
end = pre;
}

return dummy->next;
}

30.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) 的平均时间复杂度运行。

思路：LRU 缓存是 “最近最少使用” 的缓存淘汰策略，解题核心是用「哈希表 + 双向链表」组合，实现 O (1) 时间的查找、插入和淘汰操作。

哈希表：负责 O (1) 查找。key 映射到对应的节点，能瞬间找到目标数据，不用遍历。
双向链表：负责 O (1) 维护 “使用顺序” 和淘汰。
- 链表头部：存「最近使用」的节点（每次使用就移到头部）。
- 链表尾部：存「最久未使用」的节点（超容时直接删尾部）。
- 双向链表能通过前驱 / 后继指针，实现 O (1) 时间的节点插入、移动和删除。

class LRUCache {
public:
struct ListNode{ // 双向链表节点结构：存储键、值，以及前后指针

int val = 0; //值
int key = 0; //键
ListNode* pre = nullptr;
ListNode* next = nullptr;
ListNode(int _key, int _val) : key(_key), val(_val), pre(nullptr), next(nullptr) {}
};

int size = 0; //当前节点数量
int capacity = 0;//容量
ListNode* head;
ListNode* tail; // 虚拟头/尾节点（不存储实际数据，简化边界处理）

unordered_map<int, ListNode*> um; // 虚拟头节点（不存储实际数据，简化边界处理）

LRUCache(int capacity) {
this->capacity = capacity;
head = new ListNode(0,0);
tail = new ListNode(0,0);
head->next = tail;
tail->pre = head;
}

int get(int key) {//哈希表中存在该key，说明缓存命中

if(um.find(key) != um.end()){
updateNode(um[key]);
return um[key]->val;
} else{
return -1;
}
}

void put(int key, int value) {

        //情况1：该key已存在（更新操作）

if(um.find(key) != um.end()){
um[key]->val = value;
updateNode(um[key]);
} else{
if(size < capacity){//缓存未满，直接插入新节点

size++;
ListNode* node = new ListNode(key,value);
um[key] = node;

ListNode* next = head->next;
head->next = node;
node->pre = head;
node->next = next;
next->pre = node;
} else{// 缓存已满，需要淘汰最久未使用的节点（链表尾部）

ListNode* node = tail->pre;
um.erase(node->key);
node->key = key;
node->val = value;
um[key] = node;
updateNode(node);
}
}
}

void updateNode(ListNode* node){

        // 步骤1：将节点从原位置移除

ListNode* pre = node->pre;
ListNode* next = node->next;
pre->next = next;
next->pre = pre;
   // 步骤2：将节点插入到虚拟头节点之后（链表头部）

next = head->next;
next->pre = node;
node->next = next;
node->pre = head;
head->next = node;
}
};