zhangas

Pay more attention

0%

data_structure_2024_04_06

Posted on Edited on

请利用一个栈,将下面的代码改写成非递归版本

1
2
3
4
5
6
7
int ans = 0;
int play(int n){
    ans += n;
    if(n == 1 || n == 2) return;
    play(n - 1);
    play(n - 2);
}

参考

1
2
3
4
5
6
7
8
9
10
11
stack<int> stk;
int ans = 0;
stk.push(n);
while(stk.size()){
	int t = stk.top();
	ans += t;
	stk.pop();
	if(t == 1 || t == 2) continue;
	stk.push(t - 1);
	stk.push(t - 2);
}

P4387 【深基15.习9】验证栈序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
   void solve(){
int n = read();
for(int i = 1; i <= n; ++ i) a[i] = read();
for(int i = 1; i <= n; ++ i) b[i] = read();
stack<int> stk;
int idx = 1;
for(int i = 1; i <= n; ++ i){
	stk.push(a[i]);
	while(stk.size() && stk.top() == b[idx]){
		++ idx;
		stk.pop();
	}
}
if(stk.size() == 0){
	cout << "Yes" << endl;
}
else cout << "No" << endl;
   }