【笔试】 小马智行 2021-9-30笔试题 算法

1

排序求和，注意long long

注意我这个是不对的！dfs不行，只能过30，后面又用的sort+遍历求和

/*
 * @Description: 
 * @Author: suyunzheng
 * @Date: 2021-09-30 19:51:56
 * @LastEditTime: 2021-09-30 20:05:42
 * @LastEditors: maple
 */
#include "common.h"

vector<int> res;
vector<int> path;
int global_min = INT_MAX;

int getnum(const vector<int>& arr){
    int sum=0;
    for(int i = 0; i<arr.size()-1; i++){
        sum+=(arr[i]-arr[i+1])*(arr[i]-arr[i+1]);
    }
    return sum;
}

void dfs(vector<int>& arr, vector<bool>& visited){
    if(path.size()==arr.size()){
        // for(auto& ele : path){
        //     cout << ele << ", ";
        // }
        // cout << endl;
        global_min = min(global_min, getnum(path));
        return;
    }

    for(int i = 0; i<arr.size(); i++){
        if(visited[i]){
            continue;
        }
        path.push_back(arr[i]);
        visited[i] = true;

        dfs(arr, visited);
        path.pop_back();
        visited[i] = false;
    }
}

int main(){

    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for(int i = 0; i<n; i++){
        cin >> arr[i];
    }

    // for(auto& ele:arr){
    //     cout << ele << ", ";
    // }
    // cout << endl;

    vector<bool> visited(arr.size(), false);
    dfs(arr, visited);
    cout << global_min << endl;
    return 0;
}

2

统计每一个字符到边界的距离、两个字符之间的距离（如果string中要有两个的话），最大的作为当前字符的代价，最终在所有字符中取一个代价最小的

/*
 * @Description: 
 * @Author: suyunzheng
 * @Date: 2021-09-30 20:20:16
 * @LastEditTime: 2021-09-30 20:51:18
 * @LastEditors: maple
 */
#include "common.h"

// 计算str中两个flag之间的最近距离
int helper(string& str){
    // 使用一个map key：char value:index
    vector<int> dis;
    unordered_map<char, vector<int>> umap;
    int i = 0;
    for(char& c:str){
        umap[c].push_back(i);
        i++; 
    }
    for(auto& vec_p:umap){
        vector<int> index_vec = vec_p.second;
        if(index_vec.size()==1){
            dis.push_back(max(index_vec[0]+1, static_cast<int>(str.size())-index_vec[0]));
        }
        if(index_vec.size()>1){
            vector<int> tmp_dis;
            tmp_dis.push_back(max(index_vec[0]+1, static_cast<int>(str.size())-index_vec[index_vec.size()-1]));

            for(int i = 0; i<index_vec.size()-1; i++){
                tmp_dis.push_back(index_vec[i+1]-index_vec[i]);
            }
            int max_dis = -1;
            for(auto& ele:tmp_dis){
                max_dis = max(max_dis, ele);
            }

            dis.push_back(max_dis);
        }
    }

    int res_dis = INT_MAX;
    for(auto& ele:dis){
        res_dis = min(res_dis, ele);
        // cout << ele << ", ";
    }
    // cout << endl;
    // cout << res_dis << endl;
    return res_dis;

}

// int test2(string& str){
//     unordered_set<char> c_set(str.begin(), str.end());



// }

int main(){

    string str;
    cin >> str;


    auto res = helper(str);
    cout << res << endl;




    return 0;
}

3

不会，感觉有点像岛屿问题，只要能找到每一个岛屿中的index，然后每个岛屿（朋友圈）中取最小的代价，然后加上独立的村民就可以，请大家评论区赐教~

/*
 * @Description: 
 * @Author: suyunzheng
 * @Date: 2021-09-30 21:17:08
 * @LastEditTime: 2021-09-30 22:00:35
 * @LastEditors: maple
 */
#include "common.h"

vector<set<int>> global_vec;
set<int> path;

void helper(unordered_map<int, pair<int, bool>>& umap, int& head){


    auto iter = umap.find(head);
    auto ele = *iter;
    auto& ele_f = ele.first;
    auto& ele_s = ele.second.first;
    auto& visited = ele.second.second;
    if(!visited){
        path.insert(ele_s);
        visited = true;
        helper(umap, ele_s);

    }
    global_vec.push_back(path);
    path.clear();

    for(auto& ele:umap){
        auto& ele_f = ele.first;
        auto& ele_s = ele.second.first;
        auto& visited = ele.second.second;
        if(!visited){
            path.insert(ele_f);
            visited=true;
            helper(umap, ele_s);

        }
    }


}


int main(){

    int n, m;
    cin >> n >> m;
    vector<int> cost(n, 0);
    for(int i = 0; i<n; i++){
        cin >> cost[i];
    }
    //debug
    cout << "---" << endl;
    for(auto& ele:cost){
        cout << ele << " ";
    }
    cout << endl;

    vector<pair<int, int>> mat(m, {0, 0});
    for(int i = 0; i<m; i++){
        cin >> mat[i].first >> mat[i].second;
    }

    unordered_map<int, pair<int, bool>> umap;
    for(auto& ele:mat){
        umap[ele.first] = {ele.second, false};
    }

    auto iter = umap.begin();
    int head = iter->first;
    path.insert(head);
    iter->second.second = true;
    helper(umap, head);

    for(auto& line:global_vec){
        for(auto& ele:line){
            cout << ele << ", ";
        }
        cout << endl;
    }


    return 0;
}

4

不会

请大家评论区赐教~