目录

097:跳台台阶扩展问题

098:包含不超过两种字符的最长子串

099:字符串的排列

---

097:跳台台阶扩展问题

题目链接:跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)

题目：

题解：

规律题:

1.跳上n级台阶的跳法等于前面1~(n-1)级台阶跳法的总和+1。

2.跳上n级台阶的跳法等于2^(n-1)。

//1.
#include <iostream>
using namespace std;
int n=0,ret=0,sum=0;
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        ret=sum+1;
        sum+=ret;
    }
    cout<<ret<<endl;
    return 0;
}


//2.
#include <iostream>
using namespace std;
int n=0;
int main() 
{
    cin>>n;
    cout<<(1<<(n-1))<<endl;
    return 0;
}

098:包含不超过两种字符的最长子串

题目链接:包含不超过两种字符的最长子串_牛客题霸_牛客网 (nowcoder.com)

题目：

题解：

滑动窗口

#include <iostream>
#include<string>
using namespace std;
string s;
int cnt[26];
int flag = 0, ret = 0;
int main() {
    cin >> s;
    int n = s.size();
    int left = 0, right = 0, ret = 0;
    while (right < n) 
    {
        if(cnt[s[right]-'a']++ == 0) flag++;
        while(flag>2)
        {
            if(cnt[s[left++]-'a']-- == 1) flag--;
        }
        ret=max(ret,right-left+1);
        right++;
    }

    cout << ret << endl;
    return 0;
}

 

099:字符串的排列

题目链接:字符串的排列_牛客题霸_牛客网 (nowcoder.com)

题目：

题解:

排序+递归dfs（全排列）

画树形图，注意剪枝的情况

class Solution {
public:
    vector<string> ret; //收集叶子节点
    string path; //路径信息
    bool vis[11]={0}; //标记位置已经使用过
    int n;
    string s;

    vector<string> Permutation(string str) 
    {
        n=str.size();
        sort(str.begin(),str.end());
        s=str;

        dfs(0);
        return ret;
    }
    void dfs(int pos)//要填的位置
    {
        //回溯条件
        if(pos==n)
        {
            ret.push_back(path);
            return;
        }
        for(int i=0;i<n;i++) //完整遍历一遍字符串，确定要填的字符
        {
            if(!vis[i])
            {
                //剪枝
                if(i>0 && s[i]==s[i-1] && !vis[i-1]) continue;
                path.push_back(s[i]);
                vis[i]=true;
                dfs(pos+1);
                //恢复原样
                vis[i]=false;
                path.pop_back();
            }
        }
    }
};