笔试——Day33

第一题

题目

跳台阶扩展问题

思路

考虑青蛙跳到第n级台阶的跳法。青蛙在最后一步可以
跳1级：那么在此之前，它需要跳到第n-1级，有f(n-1)种方法
跳2级：在此之前，它需要跳到第n-2级，有f(n-2)种方法
跳n-1级：在此之前，它需要跳到第1级，有f(1)种方法
直接跳n级：这是一种新的方法，即直接从地面跳到第n级

因为：
f(n) = f(n-1) + f(n-2) + ... + f(1) + 1
f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1
所以：
f(n) - f(n-1) = f(n-1)
f(n) = 2 * f(n-1)
即：
f(n) = 2^(n-1)

代码

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n = 0; cin >> n;
    
    cout << pow(2, n - 1) << endl;

    return 0;
}

第二题

题目：

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

思路

滑动窗口： 使用一个kind来标记窗口中字符的种类数量，
<2时，进窗口；
>2时，出窗口；
出完后，更新当前结果

代码

#include <iostream>
#include <string>
using namespace std;

int main() 
{
    int hash[26] = {0};
    string s; cin >> s;

    int left = 0, right = 0;
    int res = 0;
    int kind = 0;
    while(right < s.size())
    {
        if(hash[s[right] - 'a']++ == 0) kind++;
        while (kind > 2) 
        {
            if(hash[s[left++] - 'a']-- == 1) kind--;
        }
        res = max(res, right - left + 1);
        right++;
    }
    cout << res << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

第三题

题目：

字符串的排列

思路

递归DFS

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    bool visited[20] = {0};
    vector<string> res;
    string path;
    string s;
    int n;
    vector<string> Permutation(string str) {
        // write code here
        n = str.size();
        sort(str.begin(), str.end());
        s = str;
        dfs(0);
        return res;
    }
    void dfs(int pos){
        if(pos == n){
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < n; i++){
            if(!visited[i]){
                if(s[i] == s[i - 1] && !visited[i - 1]) 
                    continue;
                path.push_back(s[i]);
                visited[i] = true;
                dfs(pos + 1);
                visited[i] = false;
                path.pop_back();
            }
        }
        
    }
};