每日算法刷题Day12-跳台阶、排列、替换空格、求n累加

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。

35.跳台阶

一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第n 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤15

输入样例：

5

输出样例：

8

思路

采用递归的思路

注意这一题是要统计方法数，即到达指定数字的次数。

因此设置ans变量传输结果。有了统计结果变量，可以分别按照题意遍历所有方法，最后输出结果即可。

#include<bits/stdc++.h>
using namespace std;

int n;
int ans = 0;

void foo( int k)
{
    if( k == n)ans++;
    else if(k < n)
    {
        foo(k+1);
        foo(k+2);
    }
}


int main()
{
    cin >>n;
    foo(0);
    cout << ans <<endl;
    return 0;
    
}

当然也可以采用斐波那契的方法

#include<bits/stdc++.h>
using namespace std;

int a[20];
int n;


int main()
{
    
    cin >>n;
    a[0] = 1;
    for( int i = 1; i <= n; i++)
    {
        a[i] = a[i-1] + a[i-2];
    }
    cout <<a[n];
    return 0;
    
}

36.排列

给定一个整数 n，将数字 1∼n= 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤9

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

本题可以采用递归的思路完成。详解如下：

代码：

#include<bits/stdc++.h>
using namespace std;

int N = 10;
int n;

void dfs(int u, int num[], bool st[])
{
    if(u > n)
    {
        for(int i = 1; i <= n; i++)cout << num[i]<< " ";
        cout << endl;
    }
    else 
    {
        for(int i = 1; i <= n; i++)
            if (!st[i])
            {
                st[i] = true;
                num[u] = i;
                dfs( u +1 , num ,st);
                st[i] = false;//恢复现场
            }
    }
}


int main()
{
    int num[N];
    bool st[N] = {0};//定义状态变量
    cin >> n;
    dfs(1,num,st);//从1开始排列
    return 0;
    
}

37.替换空格

请实现一个函数，把字符串中的每个空格替换成"%20"。

数据范围

0≤ 输入字符串的长度≤1000。
注意输出字符串的长度可能大于1000。

样例

输入："We are happy."

输出："We%20are%20happy."

思路

常规思路即可，注意这里由于加的是"%20",因此必须使用字符串拼接，不能单独替换char型变量。

class Solution {
public:
    string replaceSpaces(string &str) {
        string res;
        for(auto c : str)
        {
            if(c == ' ')res += "%20";
            else res += c;
        }
        return res;
    }
};

38.求1+2+…+n

求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 (A?B:C)。

数据范围

1≤n≤1000

样例

输入：10

输出：55

思路

还是采用递归的思路

class Solution {
public:
    int getSum(int n) {
        int sum = n;
        n > 0 && (sum += getSum(n - 1));
        return sum;
    }
};