笔试强训day33

跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围：1≤n≤201≤n≤20
进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(1)O(1)

输入描述：

本题输入仅一行，即一个整数 n

输出描述：

输出跳上 n 级台阶的跳法

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

---

包含不超过俩种字符的最长子串

给定一个长度为 n 的字符串，找出最多包含两种字符的最长子串 t ，返回这个最长的长度。

数据范围： 1≤n≤105 1≤n≤105 ，字符串种仅包含小写英文字母

输入描述：

仅一行，输入一个仅包含小写英文字母的字符串

输出描述：

输出最长子串的长度

#include <iostream>
#include <string>using namespace std;
int n;
int cnt[26];
bool check()
{int ans = 0;for (const int& x : cnt)if (x)++ans;return ans > 2;
}
int main()
{string s;cin >> s;n = s.size();int ans = 1;for (int left = 0, right = 0; right < n; ++right){//进窗口++cnt[s[right] - 'a'];//出窗口while (check()){--cnt[s[left++]-'a'];}//更新结果ans = max(ans, right - left + 1);}cout << ans << endl;return 0;
}

---

字符串的排列

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10n<10
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。

方法一：直接用set来去重

class Solution {int n;vector<bool>vis;void dfs(set<string>&result,string&s,string&path,int u){if(u == n){result.insert(path);return;}for(int i = 0;i<n;++i){if(!vis[i]){vis[i] = true;path += s[i];dfs(result,s,path,u+1);vis[i] = false;path.pop_back();}}}
public:vector<string> Permutation(string str) {// write code hereset<string>result;string path;n = str.size();vis.resize(n);dfs(result,str,path,0);vector<string>ans;for(auto&x:result)ans.emplace_back(x);return ans;}
};

方法二：排序 + 剪枝

class Solution {int n;vector<bool>vis;void dfs(vector<string>&result,string&s,string&path,int u){if(u == n){result.push_back(path);return;}for(int i = 0;i<n;++i){if(i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;if(!vis[i]){vis[i] = true;path += s[i];dfs(result,s,path,u+1);vis[i] = false;path.pop_back();}}}
public:vector<string> Permutation(string str) {// write code herevector<string>result;string path;n = str.size();vis.resize(n);sort(str.begin(),str.end());dfs(result,str,path,0);return result;}
};