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阿里第一场笔试##笔试题目##阿里巴巴#
全部评论
感觉跟leetcode646题是不是有点像呢
点赞 回复 分享
发布于 2020-03-21 20:56

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
1
10
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务