清华大学机试 需要二刷 *贪心算法，比较虎人

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了清华大学机试 需要二刷 *贪心算法，比较虎人，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含892字，纯文字阅读大概需要2分钟。

内容图文

基本思想：

想到贪心，但是觉得时间复杂度太高，结果一不小心写出来个更复杂的贪心；

 

关键点：

注意特殊用例，有可能无法遍历出正确结果，即没有切换得到正确的值，此时要避免进入死循环；

 

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

const int maxn = 5010;
int n,m;
int dp[maxn][maxn];

vector<string>v1;
vector<string>v2;

int main() {
    while (cin>>n){
        string s;
        for (int i = 0; i < n; i++) {
            cin >> s;
            v1.push_back(s);
        }
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> s;
            v2.push_back(s);
        }
        int cnt = 0;
        int index = 0;
        bool flag = true;
        while (index != m&&flag) {
            int mx = 0;
            int mindex = 0;
            int st = index;
            for (int i = 0; i < n; i++) {
                int j = st;
                while (j<m&&v1[i] != v2[j]){
                    j++;
                }
                if (mx < j - index) {
                    mx = j - index;
                    mindex = j;
                }
            }
            if (mindex == 0)
                flag = false;
            cnt++;
            index = mindex;
        }
        if(flag)
            cout << cnt-1 << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的清华大学机试 需要二刷 *贪心算法，比较虎人全部内容，希望文章能够帮你解决清华大学机试 需要二刷 *贪心算法，比较虎人所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---