3月20日阿里笔试第二题解法
2020春招阿里第一场笔试第二题
题目：
给出n个不下降字符串（即string[i]>=string[i-1），求用给出的原始字符串，拼出不下降字符串的字符串最大个数？
思路： 先排序，排序后使用滑窗思想，使用head和tail两个哨兵。如果发现不能继续加长，则head直接跳至tail处。相当于排序后的一种 贪心思想。
代码：
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
int main() {
vector<string> store;
int n = 0;
cin >> n;
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
store.push_back(tmp);
}
sort(store.begin(), store.end());
int head = 0, tail = 1;
deque<string> result;
result.push_back(store[0]);
int maxNum = 1;
while (head < n && tail < n) {
string tmp = result.back();
if (store[tail][0] >= tmp[tmp.size() -1]) {
result.push_back(store[tail++]);
if (result.size()>maxNum) {
maxNum = result.size();
}
}
else {
result.clear();
result.push_back(store[tail]);
head = tail;
tail++;
}
}
cout << maxNum;
}
#2020阿里第一场笔试##笔试题目##阿里巴巴#
小天才公司福利 1370人发布