栈考研经典题目
思路：
利用栈的后进先出特性，恰好可以判断‘最内层’的左右括号是否对应；例如最内层的左括号为‘（’，则下一个右括号必须为‘ ）’；
- 利用哈希表存储右括号和其对应括号
- 遍历字符串，如果是左括号则直接入栈
- 若是右括号，则查表得出应该对应的左括号，与栈顶字符（最内层左括号）对比
class Solution { public: bool isValid(string s) { unordered_map<char,char> ump={ {')','('}, {']','['}, {'}','{'} }; stack<char> stk; for(char ch:s) { if(ump.count(ch))//如果是右括号 { if(stk.empty()||stk.top()!=ump[ch]) return false; stk.pop(); } else stk.push(ch); } return stk.empty(); } };
二进制加法
思路：
求和后当前位的数据：简便的计算方法就是两个数进行异或 00000001 ^ 00000010 -> 00000011
求和后进位的数据：简便的计算方法就是两个数相与后左移一位 (00000010 & 00000010) << 1
最终结果其实就是 A^B + (A&B)<<1
例子：
1 + 2； 00000001 + 00000010
求和后当前位的数据： 00000011 ； 求和后的进位数据： 没有进位，则 00000000
两者相加，则得到： 00000011 就是3
2 + 2； 00000010 + 00000010
求和后当前位的数据： 00000000， 1和1进位后当前为变成0了
求和后进位的数据： 00000100， 两个1求和后进位了
相加后得到： 00000100 就是4
发现规律：不断相加进位，知道有一项为0，则合为了一项
class UnusualAdd { public: int addAB(int A, int B) { while(A&&B){ int a=A^B; //当前位 int b=(A&B)<<1; //进位 A=a; B=b; } if(A==0) return B; return A; } };
走方格 - 经典DP优化
输入样例：
2 3
输出样例：
10
算法1
暴搜 O(2^(n+m))
#include <bits/stdc++.h> using namespace std; int n, m; int res; void dfs(int x, int y) { if (x == n && y == m) // 如果搜到了点 (n, m), 那么 res ++ 并返回 { res ++ ; return ; } if (x < n) dfs(x + 1, y); // 如果不是最下面的点，那么搜该点下面的点 if (y < m) dfs(x, y + 1); // 如果不是最右边的点，那么搜该点右边的点 } int main() { scanf("%d %d", &n, &m); dfs(0, 0); // 从点 (0, 0) 开始爆搜 printf("%d\n", res); return 0; }
数据范围不大，可以使用爆搜，但是一般来说数据范围不会这么小，所以多数情况用暴搜会超时
算法2
动态规划O(nm)
f[i][j] 表示走到点 (i,j) 的方案数，由于每次只能往下走或往右走，所以点 (i,j) 只能从点 (i−1,j) 或点 (i,j−1) 上走过来
所以走到点 (i,j) 的方案数是走到点 (i−1,j) 的方案数与走到点 (i,j−1) 的方案数之和，推出 f[i][j]=f[i−1][j]+f[i][j−1]
边界：f[i][0]=f[0][j]=1
#include<iostream> using namespace std; int n, m; int f[11][11]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) if (!i || !j) f[i][j] = 1; else f[i][j] = f[i - 1][j] + f[i][j - 1]; printf("%d\n", f[n][m]); return 0; }
线性DP - 尝试并记录最小步数
采用动态规划思想求解。创建一个vector容器steps，steps[i]表示到达i号石板所需的最小步数。初始化为steps容器为INT_MAX。从序号N的石板开始逐个遍历，若steps[i]为INT_MAX，表示该点不可到达，直接开始下次循环。若steps[i]不为INT_MAX，表示该点可以到达，下面求解编号i的约数，进行动态规划。动态规划的转移方程为
steps[i+j] = min(steps[i]+1,steps[i+j]) //i为石板编号，j为i的约束 steps[N] = 0
求约数方法：
遍历2到sqrt（n），如果取模等于0，则 j 和 n/j 都是该数的约数
#include <iostream> #include<cstring> #include<cmath> using namespace std; const int N=0x3f3f3f3f; //设无穷距离INT_MAX int main() { int n,m; cin>>n>>m; int steps[100010]; memset(steps,0x3f,sizeof(steps)); steps[n]=0; for(int i=n;i<=m;i++) { if(steps[i]==N) continue; for(int j=2;j<=sqrt(i);j++) if(i%j==0) //是K的约数 { //尝试所有在范围内的约数， if(i+j<=m) steps[i+j]=min(steps[i]+1,steps[i+j]); if(i+i/j<=m) steps[i+i/j]=min(steps[i]+1,steps[i+i/j]); } } if(steps[m]==N) steps[m]=-1;//若无法到达 cout<<steps[m]<<endl; }
