算法打卡12天

19.链表相交

（力扣面试题 02.07. 链表相交）

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

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,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 。

解题思路

题目要求找到两个单链表的第一个公共节点。核心思路是利用链表长度的差值来对齐链表尾部，从而让两个指针能够同时遍历并找到交点。

1. 计算链表长度：
   • 遍历链表 A 和链表 B，分别计算它们的长度 lenA 和 lenB。
2. 对齐链表尾部：
   • 如果链表 B 比链表 A 长，交换它们的长度和头指针，确保链表 A 是较长的链表。
   • 计算长度差 gap = lenA - lenB，让较长的链表（链表 A）的指针先走 gap 步，这样两个链表的尾部对齐。
3. 同时遍历链表：
   • 从对齐后的起点开始，同时遍历链表 A 和链表 B。
   • 如果两个指针相遇（即 curA == curB），说明找到了第一个公共节点，直接返回该节点。
   • 如果遍历完都没有相遇，则返回 NULL，表示两个链表没有交点。

代码

#include <iostream>
#include <algorithm>struct ListNode
{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution
{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){// 交点不是数值相等，而是指针相等ListNode *curA = headA;ListNode *curB = headB;int lenA = 0;int lenB = 0;// 求链表A的长度while (curA != NULL){lenA++;curA = curA->next;}// 求链表B的长度while (curB != NULL){lenB++;curB = curB->next;}// 重新指向链表A和B的头节点   curA 和 curB现在是NULLcurA = headA;curB = headB;// 如果链表B比链表A长，交换它们的长度和头指针if (lenB > lenA){std::swap(lenA, lenB);std::swap(curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA先走gap步，这样两个链表的尾部对齐while (gap--){curA = curA->next;}// 同时遍历curA和curBwhile (curA != NULL){// 如果两个指针相遇，说明找到了第一个公共节点(返回指针)if (curA == curB){return curA;}// 移动链表的指针curA = curA->next;curB = curB->next;}return NULL;}
};

• 时间复杂度：O(n + m)
• 空间复杂度：O(1)

39.逆波兰表达式求值

（力扣150题）

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 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

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

解题思路

1. 初始化栈：
   • 使用一个栈（stack<long long>）来存储操作数。栈的类型为 long long，以支持较大的整数运算。
2. 遍历表达式：
   • 遍历 RPN 表达式的每个元素（tokens）。每个元素可以是数字或运算符。
3. 处理数字：
   • 如果当前元素是数字（即不是运算符），将其转换为 long long 类型并压入栈中。这里使用 std::stoll 函数将字符串转换为数字。
4. 处理运算符：
   • 如果当前元素是运算符（+, -, *, /），需要从栈中弹出两个操作数。
   • 检查栈中是否有足够的操作数（至少两个）。如果不足，说明表达式不合法，打印错误信息并返回错误码 0。
   • 弹出栈顶的两个操作数（num1 和 num2），注意顺序：num1 是栈顶元素，num2 是第二个元素。
   • 根据运算符对两个操作数进行运算，并将结果压入栈中。
5. 检查最终结果：
   • 遍历结束后，检查栈中是否只剩下一个元素。如果栈中不止一个元素，说明表达式不合法，打印错误信息并返回错误码 0。
   • 如果栈中只剩下一个元素，该元素即为 RPN 表达式的结果。
6. 返回结果：
   • 弹出栈顶元素并返回其值。

代码实现的逻辑

• 栈的使用：栈用于存储操作数，支持后进先出（LIFO）的操作，非常适合处理 RPN 表达式。
• 错误处理：通过检查栈的大小来确保每次运算符操作时有足够的操作数，避免运行时错误。
• 最终检查：确保栈中只剩下一个元素，验证 RPN 表达式的合法性

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;class Solution
{public:int evalRPN(vector<string> &tokens){// 栈stack<long long> st;for (int i = 0; i < tokens.size(); i++){// 如果遍历到运算符if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){// 检查栈中是否有足够的元素if(st.size() < 2){perror("Error: Not enough operands for the operator");return 0;}// 获取栈顶元素 就是要运算的数字long long num1 = st.top();// 弹出栈st.pop();long long num2 = st.top();st.pop();// 计算数值 再加入栈里面if (tokens[i] == "+"){st.push(num2 + num1);}if (tokens[i] == "-"){st.push(num2 - num1);}if (tokens[i] == "*"){st.push(num2 * num1);}if (tokens[i] == "/"){st.push(num2 / num1);}}// 如果遍历到数字 加入栈else{//  std::stoll，表示 “string to long long”，也就是将字符串转换为 long long 类型的整数。st.push(std::stoll(tokens[i]));}}// 如果最后结果不是一个元素 表达式不合法if(st.size() != 1){perror("Error: Invalid RPN expression");return 0;}// 统计最后的数值 此时栈就一个元素（结果）long long result = st.top();//  弹出st.pop();return result;}
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

40.滑动窗口最大值

（力扣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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

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

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

解题思路

本题的目标是求解滑动窗口中的最大值。滑动窗口的大小为 k，随着窗口的滑动，我们需要高效地找到每个窗口的最大值。为了实现这一目标，我们使用了一个自定义的单调队列（Mydeque）来维护窗口内的元素。

单调队列的特性

• 单调递减：队列中的元素从大到小排列。队列头部始终是当前窗口的最大值。
• 高效移除：当窗口滑动时，窗口外的元素需要被移除。通过 pop 方法，我们检查队列头部是否是窗口外的元素，如果是，则移除。
• 动态维护：当新元素加入窗口时，通过 push 方法，将队列尾部所有小于新元素的值移除，确保队列始终保持单调递减。

算法步骤

1. 初始化窗口：将前 k 个元素加入单调队列。
2. 记录第一个窗口的最大值：队列头部即为第一个窗口的最大值。
3. 滑动窗口：
   • 移除窗口外的元素：通过 pop 方法，移除队列头部的窗口外元素。
   • 加入新元素：通过 push 方法，将新元素加入队列，并维护队列的单调性。
   • 记录当前窗口的最大值：队列头部即为当前窗口的最大值。
4. 返回结果：所有窗口的最大值存储在结果数组中。

#include <iostream>
#include <deque>
#include <vector>
class Solution
{// 单调队列（从大到小）
private:class Mydeque{public:// 使用deque来实现单调队列std::deque<int> que;// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则// 同时pop之前判断队列当前是否为空void pop(int value){if (!que.empty() && value == que.front()){que.pop_front();}}void push(int value){// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。while (!que.empty() && value > que.back()){// 列尾部的值在滑动窗口中不再有用，可以移除。que.pop_back();}// 没有的话就单纯把值添加到单调队列里que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front(){return que.front();}};public:std::vector<int> maxSlidingWindow(std::vector<int> &nums, int k){Mydeque que;std::vector<int> result;// 先将前k的元素放进队列for (int i = 0; i < k; i++){que.push(nums[i]);}// result 记录前k的元素的最大值result.push_back(que.front());for (int i = k; i < nums.size() ; i++){// 滑动窗口移除最前面元素que.pop(nums[i - k]);// 滑动窗口前加入最后面的元素que.push(nums[i]);// 记录对应的最大值result.push_back(que.front());}return result;}
};

时间复杂度

每个元素最多被加入和移除队列一次，因此时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度

单调队列的空间复杂度为 O(k)，因为队列中最多存储窗口大小的元素。

通过单调队列，我们能够高效地解决滑动窗口的最大值问题，避免