Leetcode 160. 相交链表
Leetcode 160. 相交链表
方法一：哈希表
遍历ListNodeA，用哈希表存储链表节点，再遍历ListNodeB，如果ListNodeB的节点在哈希表中，则返回该节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set <ListNode *> set;
while(headA!=nullptr){
set.insert(headA);
headA=headA->next;
}
while(headB!=nullptr){
if(set.find(headB)!=set.end()){
return headB;
}
headB=headB->next;
}
return nullptr;
}
};
|
方法二：双指针
定义两个指针分别指向头节点，同时遍历向后进行遍历，若遍历为nullptr，则将指针指向另一条链表的头节点，直至两指针相遇，或者两个指针都为nullptr。
- 若两链表相交
$$length.A=a+m$$$$length.B=b+m$$
其中a、b分别为相交前分别独有长度，m为两链表相交的长度对于指针A、B遍历的长度相等：$$a+m+b=b+m+a$$
此时两指针恰好相遇于两链表交点
- 若两链表不相交
则两指针将AB均遍历结束，同时指向nullptr。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA=headA, *pB=headB;
while(pA!=pB){
pA=pA==nullptr?headB:pA->next;
pB=pB==nullptr?headA:pB->next;
}
return pA;
}
};
|
Leetcode 21. 合并两个有序链表
Leetcode 21. 合并两个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *dummy=new ListNode(0);
ListNode * curr=dummy;
ListNode *p1=list1,*p2=list2;
while(p1!=nullptr && p2!=nullptr){
if(p1->val<=p2->val){
curr->next=p1;
p1=p1->next;
}
else{
curr->next=p2;
p2=p2->next;
}
curr=curr->next;
}
if(p1==nullptr){
curr->next=p2;
}
else curr->next=p1;
return dummy->next;
}
};
|
Tips : 哑结点
在链表操作中，很多操作都依赖于当前节点的前驱节点来完成，而头节点没有前驱节点，因此需要特殊处理。
以删除一个节点为例：
- 对于非头节点：只需找到它的前驱节点
prev，执行prev->next = prev->next->next即可。 - 对于头节点：由于没有前驱，只能直接修改头指针（
head = head->next）。
当我们尝试使用对头节点和普通节点统一逻辑进行删除：
1
2
3
4
5
6
7
8
9
10
11
12
13
| ListNode* removeElements(ListNode* head, int val) {
ListNode* current = head;
while (current != nullptr) {
if (current->next != nullptr && current->next->val == val) {
current->next = current->next->next;
} else {
current = current->next;
}
}
return head;
}
|
方法一：常规方法
采用头节点特殊的显式处理：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ListNode* removeElements(ListNode* head, int val) {
while (head != nullptr && head->val == val) {
head = head->next;
}
if (head == nullptr) return nullptr;
ListNode* current = head;
while (current->next != nullptr) {
if (current->next->val == val) {
current->next = current->next->next;
} else {
current = current->next;
}
}
return head;
}
|
方法二：使用哨兵节点（统一逻辑）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* current = dummy;
while (current->next != nullptr) {
if (current->next->val == val) {
current->next = current->next->next;
} else {
current = current->next;
}
}
return dummy->next;
}
|
这时我们就可以采用哑结点来简化边界情况的处理，哑结点是一个不存储实际数据的特殊节点，通常作为链表的"虚拟头节点" 存在，它的next指针指向真正的头节点：
1
2
3
4
5
| ListNode *dummy=new ListNode(0);
dummy->next=head;
ListNode* result = dummy->next;
delete dummy;
return result;
|
⚠️ 注意事项:
- 哑结点是临时的辅助节点，最后需要释放内存（避免内存泄漏）
- 操作完成后，真正的头节点是
dummy->next
方法一：递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==nullptr){
return list2;
}
else if(list2==nullptr){
return list1;
}
else if(list1->val<list2->val){
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}
else{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
}
};
|
方法二：迭代（本质是常规解法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *prehead=new ListNode(-1);
ListNode *pre=prehead;
while(list1!=nullptr && list2!=nullptr){
if(list1->val<=list2->val){
pre->next=list1;
list1=list1->next;
}
else {
pre->next=list2;
list2=list2->next;
}
pre=pre->next;
}
pre->next=list1==nullptr?list2:list1;
return prehead->next;
}
};
|
Leetcode 53. 最大子数组和
Leetcode 53. 最大子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
int max=-100000;
for(int i=0;i<n;i++){
int sum=0;
for(int j=i;j<n;j++){
sum+=nums[j];
if(sum>max){
max=sum;
}
}
}
return max;
}
};
|
方法一：动态规划
我们维护一个函数f(i)，表示以第i个数结尾的最大子数组和，那么显然我们就是要求f(i)的最大值：
$$max_{i=1}^n f(i)$$
而f(i)仅仅与f(i-1)有关，取f(i-1)+nums[i]和nums[i]中的最大值，写出动态规划状态转移方程，即：
$$f(i)=max(f(i-1)+nums[i],nums[i])$$
然而还可以进行优化，我们无需显式的表示出f(i)，采用“滚动数组”的思想，只需要用一个变量pre来维护前i-1个f(x)的最大值即可。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxAns=nums[0],pre=0;
for(const auto& it:nums){
pre=max(pre+it,it);
maxAns=max(maxAns,pre);
}
return maxAns;
}
};
|
Leetcode 739.每日温度
Leetcode 739. 每日温度
▶
Time Error Version
❌
双重循环暴力搜索时间复杂度为$O(n^2)$，会超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
vector<int> ans;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(temperatures[i]<temperatures[j]){
ans.push_back(j-i);
break;
}
if(j==n-1){
ans.push_back(0);
}
}
}
ans.push_back(0);
return ans;
}
};
|
方法一：暴力 2.0
考虑到正向暴力解法中，每个天数都需要遍历其后面的所有数字，时间复杂度过高；而题给温度在$[30,100]$范围内，我们不妨维护一个数组posttem初始化为INT_MAX，对数组从后向前遍历，在遍历过程中更新每个温度出现的最早索引。
反向遍历温度列表。对于每个元素temperatures[i]，在数组posttem中找到从temperatures[i] + 1到100中每个温度第一次出现的下标，将其中的最小下标记为warmer，则warmer为下一次温度比当天高的下标。如果warmer不为无穷大，则warmer - i即为下一次温度比当天高的等待天数，最后更新令posttem[temperatures[i]] = i。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
vector <int> posttem(101,INT_MAX);
vector <int> ans(n);
for(int i=n-1;i>=0;i--){
int warmer=INT_MAX;
for(int j=temperatures[i]+1;j<=100;j++){
warmer=min(warmer,posttem[j]);
}
if(warmer!=INT_MAX){
ans[i]=warmer-i;
}
posttem[temperatures[i]]=i;
}
return ans;
}
};
|
方法二：单调栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
stack <int> st;
vector <int> ans(n);
for(int i=0;i<n;i++){
while(!st.empty()&&temperatures[i]>temperatures[st.top()]){
int pre=st.top();
ans[pre]=i-pre;
st.pop();
}
st.push(i);
}
return ans;
}
};
|
补充：单调栈
单调栈是一种在普通栈的基础上增加了 “维护单调性” 的核心规则的特殊栈结构——在元素入栈时，通过弹出栈顶不满足单调性的元素，确保栈内元素始终有序。
例如，在本题中，我们需要找到每个元素的下一个更大元素，即对于每个元素temperatures[i]，找到第一个比它大的元素temperatures[j]，其中i < j。我们维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。正向遍历温度列表：
适用场景：
题目描述
给定 $n$ 个整数 $ a_1, a_2, \cdots, a_n $，求它们两两相乘再相加的和，即
$S = a_1 \cdot a_2 + a_1 \cdot a_3 + \cdots + a_1 \cdot a_n + a_2 \cdot a_3 + a_2 \cdot a_4 + \cdots + a_2 \cdot a_n + \cdots + a_{n - 2} \cdot a_{n - 1} + a_{n - 2} \cdot a_n + a_{n - 1} \cdot a_n$
输入
输入的第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $ a_1, a_2, \cdots, a_n $。
输出
输出一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。
样例输入
样例输出
利用数学公式进行优化
$(a_1 + a_2 + \cdots + a_n)^2 $
$= a_1^2 + a_2^2 + \cdots + a_n^2 + 2\left(a_1a_2 + a_1a_3 + \cdots + a_{n-1}a_n\right)$
Leetcode 209. 长度最小的子数组
Leetcode 209. 长度最小的子数组
方法一：前缀和+二分查找
我们额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）。
因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
int ans=INT_MAX;
vector<int> sums(n+1);
for(int i=1;i<n+1;i++){
sums[i]=nums[i-1]+sums[i-1];
}
for(int i=1;i<n+1;i++){
int search=target+sums[i-1];
auto bound=lower_bound(sums.begin(),sums.end(),search);
if(bound!=sums.end()){
ans=min(ans,static_cast<int>((bound - sums.begin()) - (i - 1)));
}
}
return ans==INT_MAX?0:ans;
}
};
|
函数
lower_bound函数是<algorithm>头文件中的一个函数，用于在有序数组中查找（二分查找）第一个大于等于指定值的元素的迭代器。
- 找到第一个大于等于目标值
search 的元素的位置（迭代器）。
- 如果序列中所有元素都小于
search，则返回末尾迭代器（如 sums.end()）
lower_bound(first, last, value)
- first：序列的起始迭代器
- last：序列的结束迭代器
- value：要查找的目标值
相关的同源函数：
upper_bound 大于（无等于）目标值的第一个元素的迭代器equal_bound 等于目标值的第一个元素的迭代器
若是降序排列的则需要手动传入比较器：
1
2
|
auto it = lower_bound(begin, end, value, greater<int>());
|
补充：前缀和
前缀和指的是数组中从第一个元素到当前元素之间所有元素的累加和。具体来说，给定一个数组nums，它的前缀和数组prefix定义为：prefix[i]=nums[0]+nums[1]+…+nums[i-1]，通过前缀和我们可以轻松计算任意连续子区间的和，如prefix[i]-prefix[j]。
Leetcode 3076. 数组中的最大字符串值
由于末尾的n-k为循环终点，必会被取到，因而采用逆序遍历的“前缀和”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maximumEnergy(vector<int>& energy, int k) {
int n=energy.size(),ans=INT_MIN;
int sum;
for(int i=n-k;i<n;i++){
sum=0;
for(int j=i;j>=0;j-=k){
sum+=energy[j];
ans=max(ans,sum);
}
}
return ans;
}
};
|
方法二：滑动窗口
我们使用两个指针 start 和 end 表示当前子数组的开始位置和结束位置，sum 表示当前子数组的和。初始时，start 和 end 都指向数组的第一个元素，sum 为 0。
- 当
sum < target时，将 end 向后移动一位，sum加上nums[end]
- 当
sum >= target时，将 start 向后移动一位，sum减去nums[start]，并更新最短子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
int start=0,end=0;
int sum=0;
int ans=INT_MAX;
while(end<n){
sum+=nums[end];
while(sum>=target){
ans=min(ans,end-start+1);
sum-=nums[start];
start++;
}
end++;
}
return ans==INT_MAX?0:ans;
}
};
|
补充：注意前缀和的使用场景(有些题目用前缀和+滑动窗口也要注意数组是否恒为正数y)
Leetcode.560 和为k的子数组
Leetcode.560 和为k的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int left=0,right=0;
int n=nums.size();
int sum=nums[0],count=0;
while(right!=n){
if(sum>k) {
if(right==left){
left++;
right++;
sum=nums[left];
}
sum-=nums[left];
left++;}
else if(sum<k) {
right++;
sum+=nums[right];
}
else {
count++;
sum-=nums[left];
left++;}
}
return count;
}
};
|
方法一：哈希表+前缀和
初始化哈希表记录前缀和0出现1次（对应从数组开头开始的子数组）。遍历每个数时累加得到当前前缀和，检查 当前前缀和 - k 是否在哈希表中，如果在则累加其出现次数到结果中，最后将当前前缀和加入哈希表并更新出现次数。(需要查找用unordered_map时间复杂度为 $O(1)$，不需要有序的map，效率更高)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count=0;
int sum=0;
unordered_map<int,int> mp;
mp[0]=1;
for(int num:nums){
sum+=num;
if(mp.find(sum-k)!=mp.end()){
count+=mp[sum-k];
}
mp[sum]++;
}
return count;
}
};
|