阿里2017编程笔试题

ゝ一纸荒年。 2022-06-09 03:24 161阅读 0赞

## 题目1 ##

单词切割题  
题目为：  
给定一个字符串S和有效单词的字典D，请确定可以插入到S中的最小空格数，使得最终的字符串完全由D中的有效单词组成，并输出解。  
如果没有解则应该输出n/a  
例如  
输入  
S = “ilikealibaba”  
D = \[“i”, “like”, “ali”, “liba”, “baba”, “alibaba”\]  
Example Output:  
输出  
“i like alibaba”  
解释：  
字符串S可能被字典D这样拆分  
“i like ali baba”  
“i like alibaba”  
很显然，第二个查分结果是空格数最少的解。  
以下为100%通过率代码

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <utility>
    #include <vector>
    #include <stack>
    #include <unordered_set>
    #include <queue>
    #include <set>
    
    using namespace std;
    
    string g_out;
    
    void dfsfind(string str, const set<string>& dict, string out)
    {
        if (0 == str.size() && (g_out.size() > out.size() || ))
        {
            g_out = out;
            return;
        }
    
        string tmp;
        int srcStrSize = out.size();
    
        for (int i = 1; i <= str.size(); i++)
        {
            set<string>::iterator it;
    
            tmp = str.substr(0, i);
            it = dict.find(tmp);
            if (it != dict.end())
            {
                out += ' ' + tmp;
    
                dfsfind(str.substr(i, str.size() - i), dict, out);
    
                out = out.substr(0, srcStrSize);
            }
        }
    }
    
    void mincut(const string& str, const set<string>& dict)
    {
        if (0 == str.size()) return;
    
        string out;
        string tmp;
        string strTmp = str;
        for (int i = 1; i <= strTmp.size(); i++)
        {
            set<string>::iterator it;
    
            tmp = strTmp.substr(0, i);
            it = dict.find(tmp);
            if (it != dict.end() )
            {
                out = tmp;
    
                dfsfind(strTmp.substr(i , strTmp.size() - i), dict, out);
    
                out.clear();
            }
        }
    
        if (g_out.size() != 0)
        {
            printf("%s\n", g_out.c_str());
        }
        else
        {
            printf("n/a\n");
        }
    
    
        return;
    }
    
    
    int main(int argc, const char * argv[])
    {
        string strS;
        string dictStr;
        int nDict;
        set<string> dict;
    
        cin >> strS;
        cin >> nDict;
        for (int i = 0; i < nDict; i++)
        {
            cin >> dictStr;
            dict.insert(dictStr);
        }
        mincut(strS, dict);
    
        return 0;
    }

## 题目2 ##

题目为：  
中国历史上曾出现过多次诸侯割据的时期，诸侯之间通过各种方式派出间谍来刺探军情，留下了许多惊心动魄的谍战故事，其中有一个是这样的：A国在B国安插了多名间谍，有一次这些间谍刺探到B国将在T时间攻打A国，如果A国不做防备则A国必败；如果A国能提前埋伏则A国必胜，所以A国的间谍需要在T之前将情报安全的送回A国。为了避免情报被B国截获而取消攻打计划：A国的间谍采用了一种特殊的编码算法，会将情报编码在m份数据中，只有同时拿到至少任意的n份数才能解码出情报；这m份数据会由m个间谍分别送出，避免同时被B国捕获。由于输送情报的过程中要躲避B国的随机检查，输送情报的时间是不固定的，A国间谍已经将之前情报的输送时间都记录下来。A国间谍需要估算出A国拿到完整情报时间的期望值。  
注：为了简单起见，m个间谍都会成功的把各自的情报送回A国；所耗费的时间是独立的。  
概念抽象：A国间谍记录的情报输送时间的情况：会记录每个时间总共出现的次数，以Point结构表示：  
struct Point  
\{  
int value; // 情报输送时间  
int num; // value出现过的次数。  
double ratio; // value在所有情报输送占的概率。  
\};  
考试时是40%通过率，后来又修改了一下

#include <stdlib.h>
    #include <string.h>
    
    #include <iostream>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <iomanip>
    
    using namespace std;
    
    struct Point
    {
        int value;
        int num;
        double ratio;
    };
    
    void input(vector<Point>* points);
    
    double calculateExpectation(const vector<Point>& points, const int total, const int min);
    int main()
    {
        int total = 0;
        cin >> total;
        int min = 0;
        cin >> min;
    
        vector<Point> points;
        input(&points);
    
        double res = calculateExpectation(points, total, min);
        cout << setiosflags(ios::fixed) << setprecision(6) << res << endl;
        return 0;
    }
    
    void input(vector<Point>* points)
    {
        int n = 0;
        cin >> n;
        points->resize(n);
    
        double sum = 0;
        for (int i = 0; i < n; ++i)
        {
            Point& point = (*points)[i];
            cin >> point.value;
            cin >> point.num;
            sum += point.num;
        }
    
        for (int i = 0; i < n; ++i)
        {
            Point& point = (*points)[i];
            point.ratio = point.num / sum;
        }
    }
    
    double calculateExpectation(const vector<Point>& points, const int total, const int min)
    {
        int curnum = 0;
        double value = 0;
        if (total < min) return 0;
        for (int i = 0; i < points.size(); i++)
        {
            value = points[i].value * points[i].ratio;
            curnum += points[i].num;
            if (curnum > min)
            {
                return points[i].value;
            }
        }
        return value;
    }