| 07. 斐波那契数列 | 递推递归 - 两变量写法- | |
| 08. 跳台阶 | 同上 | |
| 09. 变态跳台阶 | dp | |
| 10. 矩形覆盖 | 同上 | |
| 05. 用两个栈实现队列 | 模拟 | |
| ☆ | 20. 包含min函数的栈 | 栈 |
| 21. 栈的压入弹出序列 | 模拟出栈序列 | |
| 65. 矩阵中的路径 | 回溯 | |
| 66. 机器人的运动范围 | dfs 求连通块大小 |
07 - 10 斐波那契数列 - 递推递归 - 两变量写法
07. 斐波那契数列
class Solution {
public:
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
};
08. 跳台阶
// 两变量
class Solution {
public:
int jumpFloor(int number) {
if(number==0)return 1;
if(number==1)return 1;
if(number==2)return 2;
int f=1,g=2;
number-=2;
while(number--){
g=f+g;
f=g-f;
}
return g;
}
};
09. 变态跳台阶
// dp
class Solution {
public:
int jumpFloorII(const int number) {
int** dp=new int*[number+10];
for(int i=0;i<number+10;i++){
dp[i]=new int[number+10];
}
memset(dp,0,sizeof dp);
for(int i=1;i<=number;i++){
dp[1][i]=1;
}
// dp[i][j] 用i步跳上台阶j
for(int i=2;i<=number;i++){
for(int j=i;j<=number;j++){
for(int k=i-1;k<j;k++){
dp[i][j]+=dp[i-1][k];
}
}
}
int ans=0;
for(int i=1;i<=number;i++){
ans+=dp[i][number];
}
return ans;// 返回的变量打错，不可原谅，，
}
};
10. 矩形覆盖
类似于前面几题。
class Solution {
public:
int rectCover(int number) {
if(number==0) return 0;
if(number==1) return 1;
if(number==2) return 2;
int f=1,g=2;
number-=2;
while(number--){
g=f+g;
f=g-f;
}
return g;
}
};
05. 用两个栈实现队列
栈1接收入队列元素，栈2存储出队列元素，当栈2空时，把栈1元素倒到栈2中。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.size()==0){
while(!stack1.empty()){
int x=stack1.top();
stack1.pop();
stack2.push(x);
}
}
int x=stack2.top();
stack2.pop();
return x;
}
private:
stack<int> stack1;
stack<int> stack2;
};
20. 包含min函数的栈
栈
每次对压入一对元素（当前元素和目前的最小值）。
更省空间的做法如下：
应用一个辅助栈，压的时候，如果A栈的压入比B栈压入大，B栈不压，，，，小于等于，AB栈同时压入，出栈，如果，AB栈顶元素不等，A出，B不出。
21. 栈的压入弹出序列
模拟
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> s = new Stack<Integer>();
//用于标识弹出序列的位置
int popIndex = 0;
for(int i = 0; i< pushA.length;i++){
s.push(pushA[i]);
//如果栈不为空，且栈顶元素等于弹出序列
while(!s.empty() &&s.peek() == popA[popIndex]){
//出栈
s.pop();
//弹出序列向后一位
popIndex++;
}
}
return s.empty();
}
}
65. 矩阵中的路径
回溯
dfs回溯。
66. 机器人的运动范围
dfs求连通块大小
dfs求连通块大小。注意要用vis数组避免重复计数。