1.必备的2个数据结构和3个算法技巧
2025/12/28大约 20 分钟
1.必备的2个数据结构和3个算法技巧
任何计算机语言，本质你只需要考虑2个数据结构，3个算法技巧；
即可快速解决绝大部分的工程问题+面试问题，他们是一切的地基，无论什么高阶的双链表、树，BFS、DFS啥的
注意
2个必备数据结构：
- 1、数组【扩展的：链表/数组】
- 2、映射
3个必备算法技巧
- 1、递归/迭代
- 2、空间换时间：打表，记忆化
- 3、稳住心态，观察世界，找数学规律
以前，对于很多概念都混淆，现在用自己的理解，将概念进行分类：
将具体实现代码的手法，我称之为『编程技巧』，不用“算法思想”那么高的高度进行描述。📑 目录
- ⭐️1、双指针『应对-数组』
- ✡️2、递归『应对-链表-树』
- 🍀3、将『栈和递归』转换得炉火纯青
- ✏️4、迭代
- ☁️5、空间换时间之打表、记忆化（前、后缀等）
专题模板
1.哨兵
- 参考CSDN
sentry，哨兵- 哨兵，顾名思义，是用来解决国家之间边界问题的，不直接参与生产活动。
- 同样，计算机科学中提到的哨兵，也用来解决边界问题。
A sentinel is a dummy object that allows us to simplify boundary conditions.
哨兵是用来简化边界问题的虚设对象
比如：我们在判断链表是否为空，加不加一个头结点，就能看见代码的改善与否。
2.数组和链表专题
2.1.数组和链表专题
排序数组中的搜索问题，首先想到 二分法 解决。
排序数组使用双指针也是高频选项
2.2.指针的题目
- 1）首先记得想，会不会是NULL（顺路也考虑了程序的健壮性）
- 2）指针的题目，就是不断的移动指针达到题目要求
2.3.链表的常见技巧
3.树专题
树和链表都是递归结构，很多树的问题可以使用递归来处理。
几种遍历，
其中，主要考察，我们对递归的实现？
但是其实有非递归的实现，（面试可能考！！！）
树—常考题型之一
- 完全二叉树共有700结点，该二叉树有多少个叶子结点？
3.1关于递归到底好不好？
- 可能以前在做ACM题目的时候，个人对递归有偏见
- 但是面试以来，递归是很好的，它能保证递归有足够的空间去，一般不会爆栈！！！！
- 此外面试的时候是有时间控制的，你需要做的是『精简代码、快速解答』
- 110平衡二叉树+剑指offer55
借助做过的求树的高度的题目进行递归
其实自己都不知道为什么AC了，但是获得了经验
1、递归不一定只是递归本身。可以几个不同函数一起递归，分解问题
3.2.树的层序遍历（BFS）
牛客上，没有return最终结果，竟然还能出现内存超限的情况。
我在LeetCode上，有用过两个vector模拟队列，但是在这，我用len控制了遍历的节点数。就能只用一个队列。
3.3.树的三大遍历
3.3.1.递归写法
- 递归写法（习惯递归这种技巧，强化）
前序、中序、后序遍历，一套框架（伪代码）
void DFS( TreeNode * root )
{
if( nullptr==root )
{
return ;
}
//前序遍历visit
DFS( root->left );
//中序遍历visit
DFS( root->right );
//后序遍历visit
}3.3.2.栈模拟写法（非递归）
- 非递归写法一（重点掌握，防止爆内存栈）——借助栈实现
1、前序遍历
原理：
根-》左-》右
变为
先访问根
stack先入右边，后入左边，这样，出栈遍历就OK
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> ret;//返回值
if( nullptr==root )
{
return ret;
}
stack<TreeNode *> st;
st.push( root );
while( !st.empty() )
{
TreeNode * temp=st.top();
st.pop();
if( nullptr==temp )
{
continue;
}
ret.push_back( temp->val );//先访问根节点val
//下面是核心代码：先右后左，这样就能在出栈的时候保证，左子树先被遍历
st.push( temp->right );
st.push( temp->left );
}
return ret;
}2、后序遍历
原理：借鉴了前序的，想办法，将两者的写法尽量统一！
前序遍历为root->left->right
后序遍历为left->right->root
我们如果可以修改前序遍历为root->right->left
显然就可以用STL的reverse算法反转就OK了
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> ret;
if( nullptr==root )
{
return ret;
}
stack<TreeNode * > st;
st.push(root);
while( !st.empty() )
{
TreeNode * temp=st.top();
st.pop();
if( nullptr==temp )
{
continue;
}
ret.push_back( temp->val );
st.push( temp->left );
st.push( temp->right );
}
//反转
reverse( ret.begin(), ret.end() );
return ret;
}3、中序遍历
- 1、这个的理解和前面两个不一样，这个需要借助DFS的角度来看
- 2、可以借助《算法笔记》中DFS走迷宫来理解代码。
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ret;
if( nullptr == root )
{
return ret;
}
stack<TreeNode * > st;
TreeNode * cur=root;
//注意是或
while( nullptr!=cur || (!st.empty()) )
{
//DFS之一条路走到最左的
while( nullptr!=cur )
{
st.push( cur );
cur=cur->left;
}
TreeNode * temp=st.top();
st.pop();
ret.push_back( temp->val );//放入输出的数组
//注意是变成temp的右边
cur= temp->right;//开始到当前节点的右边去遍历，如果没有，显然会先经过根
}
return ret;
}3.3.3.Morris遍历、化树为链表（非递归）
1、中序遍历
特点，改变了二叉树结构，将二叉树变成了“链表”
- 时间复杂度：$O(n)$ $O(n)$，其中 nn 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)$=$O(n)$$O(2n)$=$O(n)$。
- 空间复杂度：$O(1)$ $O(1)$。
2、讲解算法
思路与算法
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）- 代码
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> rt;
TreeNode * preNode=nullptr;
while( nullptr!=root )
{
//1.链表的左边，要先遍历的
if( nullptr!=(root->left) )
{
//（1）第1步，preNode节点就是当前 root 节点向左走一步，
//然后一直向右走至无法走为止（理解）
preNode=root->left;
while( nullptr!= (preNode->right) && (preNode->right) != root )
{
preNode=preNode->right;
}
//（2）第2步，如果，这个preNode的右边节点是nullptr
//显然我还没有改变成链表
if( nullptr==(preNode->right) )
{
//改变为“链表”
preNode->right=root;
//局部改变之后，我们移动root，准备下一次的改变成链表
root=root->left;
}
else
{
//（2）第2步，如果，preNode->right == root
//说明左子树已经访问完了，我们可以直接开始遍历了
//此外我们需要断开链接？？
rt.push_back( root->val );
preNode->right=nullptr;//断开？？？这步需要吗？
root=root->right;
}
}
else
{
//2.没有左孩子，则直接访问右孩子
rt.push_back( root->val );
root=root->right;//不断看被改成的链表右侧
}
}
return rt;
}3.3.4.线索化二叉树（非递归）
实际做OJ的时候，这种解法可能有局限，毕竟要修改结构体。
新增两个指针。
3.4.重建二叉树『模板』
3.4.1.需要熟练的树的代码
- 效果：手到码出
- 递归：前、中、后序遍历
- 迭代：前、中、后序遍历
3.4.2.重建二叉树『模板』
有2个新名词：
- 1、序列化：必须保存1个中序遍历的结果，然后外加1个前序or后序遍历的结果
- 2、反序列化：根据2次遍历生成的结果恢复二叉树
1、中序+前序->二叉树『树无重复元素』
（1）递归模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
TreeNode * solve
(
vector<int>::iterator preBegin, vector<int>::iterator preEnd,
vector<int>::iterator inBegin, vector<int>::iterator inEnd
)
{
if( preBegin==preEnd || inBegin==inEnd )
{
return nullptr;
}
TreeNode * root= new TreeNode( *preBegin );
//不记得下面这个函数，也可以用for循环自行查找。
vector<int>::iterator it= find( inBegin, inEnd, root->val );
int num=(it-inBegin);
//递归，左闭右开『注意事项』
root->left=solve( preBegin+1, preBegin+1+num, inBegin,inBegin+num);
root->right=solve( preBegin+1+num, preEnd, inBegin+num+1, inEnd);
return root;
}
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
return solve
(
preorder.begin() , preorder.end() ,
inorder.begin() , inorder.end()
);
}
};2、中序+后序->二叉树『树无重复元素』
（1）递归模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
TreeNode * solve
(
vector<int>::iterator inBegin, vector<int>::iterator inEnd,
vector<int>::iterator postBegin, vector<int>::iterator postEnd
)
{
if( inBegin==inEnd || postBegin==postEnd )
{
return nullptr;
}
TreeNode * root=new TreeNode( *(postEnd-1) );
vector<int>::iterator it;
for( it=inBegin; it<inEnd; ++it)
{
if( *it==root->val )
{
break;
}
}
//注意：左闭右开
int num=it-inBegin;
root->left=solve( inBegin, inBegin+num, postBegin, postBegin+num );
root->right=solve( inBegin+num+1, inEnd, postBegin+num, postEnd-1 );
return root;
}
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return solve( inorder.begin(), inorder.end(), postorder.begin(), postorder.end() );
}
};3、中序+层序->二叉树
- 这个结论，是在『算法笔记』上看到的，我们写出下面的模板代码
- 注意：区间的开闭
4、前序+后序->二叉树『不唯一』
（显然树不唯一）
4.『贪心』解决过桥问题
4.1.题面
- N个人在晚上想通过桥。每次最多过去2个人，需要有手电筒。现在只有1个手电筒。每个人过桥的速度都不一样，过桥的时间以慢的为准。你的工作是找到最少的过桥的方法;
输入:
首先是n,然后n行是过桥的时间。
人数不超过1000，而且没有人过桥的时间超过100秒;
输出:
首先输出总共所需最少时间;下面表示过桥的过程(见样例)，如果有多种过桥方案，输出其中一种。- 来源：IBM面试题，一道标准的贪心题目
样例输入：
输入样例
4 //4个人
1
2
5
10
样例输出：
输出样例
17
1 2 //1和2先过去
1 //1回来
5 10 //5和10过去
2 //2回来
1 2 //1 2 过去4.2.解法
算法复杂度在于排序
样例：
4
1 2 5 101）贪心第1部分——贪心策略1（表述不如，算法清晰）
- 1）每次过桥2个人，
希望一起过去的人时间相差最小，选领近的两个，所以采用贪心技术。（第1个要贪心的） - 理解：比如，上面的最大的10是肯定没有办法避免的，但是我就希望这个5就不要在出现在我的和式里面了
时间相差最小：比如，时间最多的人和时间次多的人一起过，这样我们最大的那个时间10就只出现一次
怎么办？所以，我希望在过桥的时候，是5和10一起过 - 2）而且返回的时间要少，所以用时间最少的人返回;往回送手电筒的人，时间要少（第2个贪心）
2）贪心策略1的算法：
预处理：我们将过桥的时间从小到大排好序，标记为T1,T2,T3..Tn
- 1.首先让时间最少的两人过去，T1，T2（这2个人的使命是：用来往回送手电筒的）
- 2.然后，返回T1和T2中的哪一个呢？
-- Q：难道返回任何一个都没有关系？
-- A：T1不是这次返回的话，反正下次还是要返回的
但是，请看这个样例：如果只有3个人，1 2 3，显然如果要T2回去送，返回的时候会长一点点，会影响时间- 3.让Tn和Tn-1一起过去，我们希望在时间的总和里面，Tn出现，但是比他稍微小一点的Tn-1就不用再出现了
- 4.然后余下的T2返回
显然，观察容易知道，经过以上4个步骤会出现：
T1和T2又回到了最初的位置，Tn和Tn-1却过河了
这样，我们就从n个人转换为了n-2个人过河
来回2趟，送过去2个人，得到一个部分最优解。
在这个基础上，不断的分解
3）贪心第2部分——贪心策略2
Q：先前的策略是，时间最小的2个人来送手电筒，那么能否只让时间最小的1个人来送手电筒？
A：不能，因为从数学上可以证明
显然，我们上面的样例中，那个时间5会加到我们的总和中去，
广义的数学证明这个贪心策略不行：
抽象从小到大的4个数，T1，T2，Tn-1，Tn
贪心策略1：
比如，Tn-1不会出现在最终和式中
T1 T2过去 （T2）
T1回来 （T1）
Tn-1和Tn过去 （Tn)
T2回来 (T2)
sum1=Tn+2*T2+T1;
贪心策略2：
Tn,Tn-1啥的都会出现在最终和式
T1 Tn过去 （Tn）
T1回来 （T1）
T1和Tn-1过去 （Tn-1)
T1回来 (T1)
sum2=Tn+T（n-1）1+2*T1显然
sum2-sum1<0的时候，需要满足Tn-1< 2*T2-T1才能使用
比如这个样例
4
1 4 5 10
贪心策略1：
10+2*4+1=19
贪心策略2：
10+5+2*1=17所以，我们使用贪心策略1还是2的时候，需要判别Tn-1< 2*T2-T1的成立与否
3、结合两种贪心策略的最终代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int test[maxn];
//伪代码，时间复杂度是O（n）
void solve()
{
//t表示的意识是
t=2*T2- T1 （最小的T1，次小的T2）
//2个人来回送手电筒贪心策略
for(int i=n-l; (s[i-l]>t)&(i>2) ;i-=2)
{
printf ("%d %d\n",s[0],s[1]);
printf ("%d\n",s[0]);
printf ("%d %d\n",s[i-1],s[i]);
printf ("%d\n",s[1]);
}
//Tn-1< 2*T2-T1才能使用
//1个人来回送手电筒贪心策略
for(int j=i; j>l ; --j)
{
printf("%d %d\n", s[0],s[j]);
printf("%d\n", s[0]);
}
}
//真实代码
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0;i<n;++i)
{
scanf("%d",&test[i]);
}
sort(test,test+n);//将所有的时间排序是贪心法的预备工作
}
return 0;
}5.『分治』算法
很显然，递归这种『编码技巧』，就是分治算法的完美体现之一
1、使用情况
问题规模比较大的时候，难以求解
想办法减少
贪心，DP，分治，减治
减治，由于时间的关系，我们就不举例子了。
分治：
我们用得比较多的也是二分法，或者三分法
2、分治法-到底如何分解问题
到底如何分解问题，其实我一直很迷惑，9.2号。我突然想到一个好像不错的方法：
1）找到最大的问题
2）找到最简化的问题（最小的问题）
3）分析如何从最大的问题一步步转换为最小的问题我后面，自己找了一个3人，3鬼的方法验证
3人3鬼过河，人的数目要比鬼多，否则鬼会吃掉人
3、最大问题
人人人 鬼鬼鬼| |4、最小问题
人 鬼| |
这个容易解决，一次性过去。5、中等问题
人人鬼鬼| |显然，中等问题要成功，最后的状态要是
人鬼| |人鬼或者
鬼| |人人鬼转换关系
最大要转换为
人人鬼鬼|（船在这） |人鬼中等问题要转换为
人鬼|（船在这） |人鬼6.面试—字符串
- 参考文章：一个模板刷遍所有字符串句子题目！（归纳总结+分类模板+题目分析）
- 注意点：字符串的遍历，记得“擦屁股”—也就是收拾最后的残局
7.KMP算法
#include<bits/stdc++.h>
using namespace std;
class KMP
{
public:
void getNext( vector<int> & next, string s )
{
//我的理解，getNext其实本质也是个strStr的函数，
//其中，文本串是『后缀XXX』，needle__也就是s是『前缀XXX』
int prefixPos=0;//初始化『前缀末尾位置』
next[0]=0;//初始化next[0]的回退位置
//i意义1：表示『后缀末尾的位置』,初始化next[i]
//意义2：此外，i还代表当前XXX
for (int suffixPos = 1; suffixPos < s.size(); ++suffixPos)
{
//易错，不能是if，因为可能借助next多次回退
while( prefixPos>0 && s[prefixPos]!=s[suffixPos] )
{
prefixPos=next[prefixPos-1];
}
if( s[prefixPos]==s[suffixPos] )
{
++prefixPos;
}
//初始化next
next[suffixPos]=prefixPos;
}
}
int strStr( string haystack, string needle )
{
if( 0==needle.size() )
{
return 0;
}
vector<int> next( needle.size() );
getNext( next, needle );
int j=0;//needle串，当前需要测试匹配性的位置
for(int i=0; i<haystack.size(); ++i)
{
//易错：不能用if，因为可能多次借助next数组回退
while( j>0 && haystack[i]!=needle[j] )
{
j=next[j-1];
}
//如果匹配了1个字符，显然会后移
if( haystack[i]==needle[j] )
{
++j;
}
//完全匹配
if( j==needle.size() )
{
//注意，因为i还来不及+1，所以，返回前要+1然后才能减掉
return ( i+1-needle.size() );
}
}
return -1;//匹配失败
}
}
int main()
{
return 0;
}1.双指针
- 有的书上叫“尺取法”
1.1.综述：双指针的常见技巧
- 快慢指针（fast和low）
- 左右指针（left和right）
- 滑动窗口
1.2.low和fast指针『快慢指针』
//框架开始
ListNode * low=pHead;
ListNode * fast=pHead;
while( nullptr!=fast->next && nullptr!=fast->next->next )
{
//记得一定要先走
low=low->next;
fast=fast->next->next;
//框架结束
if( low==fast )
{
low=pHead;
while( low!=fast )
{
low=low->next;
fast=fast->next;
}
return fast;
}1.3.左右指针
- 二分查找用到了
- 判断是否回文
1.4.滑动窗口『模板』
- 框架
string str;
int Left=0,Right=0,Len=str.size();
while( Right<Len )
{
//右侧强制更新的,下面必须保留，否则++Right之后会更新
char CurChar=s[Right];
WindowsHash[ CurChar ]++;
++Right;
//右侧非强制更新的，本部分不需要更新
//『何时使得窗口不符合条件』，使得左侧需要更新？收缩？
//用的while循环收缩，毕竟可能要收缩很多次
while( how to shrink)
{
char c=s[Left];
WindowsHash[c]--;
++Left;
//其他的
}
}例题1-26. 删除有序数组中的重复项
- 严格来说是“左右指针”，不全是“滑动窗口”
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int Left=0;
int Right=1; //“滑动窗口”在本题中的改进点1
int Len=nums.size();
while( Right<Len )
{
//改进点2
if( nums[Right]==nums[Left] )
{
nums.erase( nums.begin()+Right, nums.begin()+Right+1 );
--Len;
}
else if( nums[Right]!=nums[Left] )
{
++Left;
++Right;
}
}
return Len;
}
};例题2-3. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res=0;
unordered_map<char,int> WindowsHash;
int Left=0,Right=0;
int Len=s.size();
while( Right<Len )
{
//右侧强制更新的,下面必须保留，否则++Right之后会更新
char CurChar=s[Right];
WindowsHash[ CurChar ]++;
++Right;
//右侧非强制更新的，本部分不需要更新
//『何时使得窗口不符合条件』，使得左侧需要更新？收缩？
while( WindowsHash[ CurChar ] >1 )
{
char c=s[Left];
WindowsHash[c]--;
++Left;
}
res=max( res, Right-Left );
}
return res;
}
};2.递归⭐️
2.1.递归套路『重要』⭐️
- 来自《算法基础与在线实践》
#include<bits/stdc++.h>
using namespace std;
int n;
//表示，begin借助help杆子，到end上面去，这次的目标是移动n个元素
void hanota(char begin, char help, char end, int n)
{
if( n<1 ) return ;
if( 1==n )
{
printf("%c->%c\n", begin, end);
return ;
}
//这个递归，是观察小部分的调用获得的idea
hanota( begin, end, help, n-1);
printf("%c->%c\n", begin, end);
hanota( help, begin, end, n-1);
}
int main()
{
while( ~scanf("%d",&n) )
{
hanota( 'A', 'B', 'C', n);
}
return 0;
}3.将『栈和递归』转换得炉火纯青⭐️
- 二叉树的前序遍历
3.1.递归转栈『万能模板』⭐️
0、使用结构体量的成员变量或指针变，抽象原先解决问题的『递归函数』的形式参数
1、设置 『问题栈』并且，画出和书上差不多的解决问题，栈变化表
2、初始化『第1个问题』
st.push( root );
3、用while循环，模拟栈3.2.递归解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
vector<int> ret;
void trave( TreeNode * root )
{
if( nullptr==root )
{
return ;
}
ret.push_back( root->val );
trave( root->left );
trave( root->right );
}
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
ret.clear();
trave( root );
return ret;
}
};3.3.栈解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
vector<int> ret;
stack< TreeNode * > st;//第1步，设置 『问题栈』
void trave( TreeNode * root )
{
//第2步，初始化『第1个问题』
st.push( root );
//第3步，用while循环，模拟栈
while( !st.empty() )
{
TreeNode * top=st.top();
st.pop();
if( nullptr!=top )
{
st.push ( top->right );
st.push( top->left );
ret.push_back( top->val ); //着手解决问题
}
}
}
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
ret.clear();
while( !st.empty() )
{
st.pop();
}
trave( root );
return ret;
}
};4.迭代
- 链表遍历
void MyReverse( ListNode * root )
{
while( nullptr!=root )
{
cout<< (root->val) <<endl;
root = root->next;
}
}5.空间换时间
- 比如，求素数
6.前缀/中缀/后缀表达式⭐️
#include<bits/stdc++.h>
using namespace std;
struct node
{
double num; //操作数字
char op; //操作符
bool flag; //true表示操作数，false表示操作符
};
string str;
stack<node> s;//操作符栈
queue<node> q;//后缀表达式序列
map<char,int> op;
//将中缀表达式转换为后缀表达式
void Change();
void Cal();
int main()
{
op['+']=op['-']=1; //设定操作符的优先级
op['*']=op['/']=2;
while( getline(cin,str), str!="0" )
{
for( string::iterator it=str.end(); it!=str.begin(); it-- )
{
//将表达式中的空格删掉
if( ' '==(*it) ) str.erase(it);
}
while( !s.empty() )
{
s.pop(); //初始化栈
}
//将中缀表达式转换为后缀表达式
Change();
//计算后缀表达式
printf("%.2f\n", Cal() );
}
return 0;
}6.1.中缀表达式转换为后缀表达式
void Change()
{
double num;
node temp;
for( int i=0; i<str.length(); )
{
if( isdigt(str[i]) )
{
temp.flag=true;//标记是数字
temp.num=str[i++]-'0';//记录这个操作数的的1个数位
while( i<str.length() && isdigt(str[i]) )
{
//更新该操作数『常见编程技巧』
temp.num=temp.num*10+( str[i]-'0' );
++i;
}
//将这个操作数压入后缀表达式的队列
q.push(temp);
}
else
{
//如果是操作符
temp.flag=false;
//只要操作符的栈顶元素比该操作符优先级高
//就把操作符栈顶元素弹出到后缀表达式的队列中
while( s.empty() && op[ str[i] ]<=op[ s.top().op ] )
{
q.push( s.top() );
s.pop();
}
temp.op=str[i];
s.push(temp); //把该操作符压入操作符栈中
++i;
}//#end inner if
//如果操作符栈中还有操作符，就把它弹出到后缀表达式中
while( !s.empty() )
{
q.push( s.top() );
s.pop();
}
}//#end for
}6.2.计算后缀表达式
void Cal()
{
double temp1,temp2;
node cur,temp;
while( !q.empty() )
{
//cur记录队首元素
cur=q.front();
q.pop();
//如果是操作数，直接压入栈
if( true==cur.flag )
{
s.push(cur);
}
else
{
//如果是操作符，号
temp2=s.top().num; //弹出第2操作数
s.pop();
temp1=s.top().num; //弹出第1操作数
s.pop();
//临时记录操作数
temp.flag=true;
if( '+'==cur.op )
{
temp.num=temp1+temp2;
}
else if( '-'==cur.op )
{
temp.num=temp1-temp2;
}
else if( '*'==cur.op )
{
temp.num=temp1*temp2;
}
else
{
temp.num=temp1/temp2;
}
//将该操作数压入栈
s.push( temp );
}//#end inner if & else
}//#end while
//栈顶元素就是后缀表达式的值
return s.top().num;
}6.3.启发性的方法
- NC137 表达式求值
请写一个整数计算器，支持加减乘三种运算和括号。- 参考思路：labuladong
7.负数取模
- 差分数组+重点是（负数取模）技巧
- 2381. 字母移位 II
class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
vector<int> diff( s.size()+1 );
for(auto & t : shifts )
{
if( 0==t[2] )
{
diff[ t[0] ]--;
diff[ t[1]+1 ]++;
}
else
{
diff[ t[0] ]++;
diff[ t[1] +1]--;
}
}
for(int i=1; i<s.size(); ++i)
{
diff[i]+=diff[i-1];
diff[i]%=26;
}
for(int i=0; i<s.size(); ++i)
{
//核心的地方，如何处理取模
int c = s[i] - 'a';
c = ((c + diff[i]) % 26 + 26) % 26; //核心：差分数组+重点是（负数取模）技巧
s[i] = (char) (c + 'a');
}
return s;
}
};