2019字节跳动秋招编程题

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool solu(vector<char>& vec) {
    int i, j;
    for (i = vec.size() - 1; i > 0; i--) {
        if (vec[i] > vec[i - 1]) {
            break;
        }
    }
    if (i == 0)return false;

    for (j = vec.size() - 1; j > i - 1; j--) {
        if (vec[j] > vec[i - 1]) {
            break;
        }
    }
    swap(vec[j], vec[i - 1]);
    sort(vec.begin() + i, vec.end());
    return true;
}

//测试函数
int main() {
    int N;
    string str;
    vector<char> vec;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> str;
        vec.clear();
        int L = str.length();
        for (int j = 0; j < L; j++) {
            vec.push_back(str[j]);
        }
        bool end;
        for (int j = 0; j < L; j++) {

            end = solu(vec);
            if (end == false) {
                sort(vec.begin(), vec.end());
            }
        }
        for (auto a : vec) {
            cout << a;
        }
        cout << endl;
    }

    return 0;
}

二,字符串排列字串判断

/*
判断字符串str2是不是有一种排列时字符串str1的字串

输入

ba
ab

输出

True

输入

eid1baooo
ab

输出

True

输入

eid1boaoo
ab

输出

Fales

*/

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

// class Solution {
// public:
//        bool matches(vector<int>& mapStr1,vector<int>& mapStr2){
//         for (int i = 0; i < 26; i++){
//             if (mapStr1[i] != mapStr2[i]) return false;
//         }
//         return true;
//     }
//     bool checkStringInclusion(string str1, string str2) {
//         vector<int> mapStr1(26,0);
//         vector<int> mapStr2(26,0);
//         if (str1.length() > str2.length()) return false;
//         for (unsigned int i = 0; i < str1.length();i++){
//             mapStr1[str1[i]-'a'] ++;
//             mapStr2[str2[i]-'a'] ++;
//         }
//         for (unsigned int i = 1; i <= (str2.length() - str1.length()); i++){
//             if (matches(mapStr1,mapStr2)) return true;
//             mapStr2[str2[i-1]-'a']--;
//             mapStr2[str2[i+str1.length()-1]-'a']++;
//         }
//         return matches(mapStr1,mapStr2);
//     }
// };
//解法二 更高效
class Solution {
public:
    bool checkInclusion(string str1, string str2) {
        if (str1.size() == 0) return true;
        if (str2.size() == 0) return false;
        vector<int> map(26, 0);
        for (unsigned int i = 0; i < str1.size(); ++i) {
            map[str1[i] - 'a']++;
            map[str2[i] - 'a']--;
        }
        if (isValid(map)) return true;
        for (unsigned int i = str1.size(); i < str2.size(); ++i) {
            map[str2[i] - 'a']--;
            map[str2[i-str1.size()] - 'a']++;
            if (isValid(map)) return true;
        }
        return false;
    }
    bool isValid(vector<int> map) {
        for (unsigned int i = 0; i < map.size(); ++i) {
            if (map[i] != 0) return false;
        }
        return true;
    }
};

int main()
{
 string str1;
string str2;
bool result;
 cin >> str1;
 cin >> str2;
 Solution checkStrInclusion;
 result=checkStrInclusion.checkStringInclusion(str2, str1);
 if (result)
 {
    cout<<"True"<<endl;
 }
 else
 {
    cout<<"False"<<endl;
 }


}