[美团笔试08.13] 5道题全题解分享

美团笔试08.13题解分享：

[1] 会魔法的外卖员：

需要对时间排序，不排序的无法AC!

外卖员派送的时间点只能是派送时间的整数倍，只有大于派送时间点的外卖才能正常配送，其余使用魔法。

//
// Created by Harold on 2022/8/13/0013.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution{
private:
    int n_nums;
    int t_time;
    vector<int> timeList;
public:
    void getInput(){
        cin>>n_nums>>t_time;
        vector<int> timeInput(n_nums);
        for(int i = 0; i < n_nums; i++){
            cin>>timeInput[i];
        }
        timeList = timeInput;
    }
    void getTheAns(){
        int useMagic = 0;
        int currenTime = 0;
        int currentTimeCount = 1;
        sort(timeList.begin(),timeList.end());

        for(int i = 0; i < n_nums; i++){
            currenTime = currentTimeCount * t_time;
            if(currenTime <= timeList[i]){
                currentTimeCount++;
            }
            else{
                useMagic++;
            }
        }
        cout<<useMagic;
    }
    void run(){
    getInput();
    getTheAns();
}
};
int main(){
    Solution s;
    s.run();
    return 0;
}

[2] 扫地机器人:

//
// Created by Harold on 2022/8/13/0013.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution{
private:
    int n;
    int m;
    int k;
    int needFlashNum;
    string cmd;
    vector<vector<int>> theMap;
public:
    void getInput()
    {
        cin>>n>>m>>k;
        cin>>cmd;
        vector<vector<int>> mapInput(n,vector<int>(m,0));
        mapInput[0][0] = 1;
        needFlashNum = n * m - 1;
        theMap = mapInput;
    }
    void run(){
        getInput();
//        showInput();
        getTheAns();
    }
    void showInput(){
        cout<<"n = "<<n<<", m = "<<m<<", k = "<<k<<endl;
        cout<<"cmd = "<<cmd<<endl;
        cout<<"map size = "<<theMap.size()<<endl;
    }
    void getTheAns(){
        int currentRow = 0;
        int currentCol = 0;
        for(int i = 0; i < k; i++){
            switch (cmd[i]) {
                case 'W':{
                    if(currentRow-1 >= 0){
                        currentRow--;
                        if(theMap[currentRow][currentCol] == 0){
                            needFlashNum--;
                            theMap[currentRow][currentCol] = 1;
                        }
                    }
                    break;
                }
                case 'A':{
                    if(currentCol-1 >= 0){
                        currentCol--;
                        if(theMap[currentRow][currentCol] == 0){
                            needFlashNum--;
                            theMap[currentRow][currentCol] = 1;
                        }

                    }
                    break;
                }
                case 'S':{
                    if(currentRow+1 < n){
                        currentRow++;
                        if(theMap[currentRow][currentCol] == 0){
                            needFlashNum--;
                            theMap[currentRow][currentCol] = 1;
                        }
                    }
                    break;
                }
                case 'D':{
                    if(currentCol+1 < m){
                        currentCol++;
                        if(theMap[currentRow][currentCol] == 0){
                            needFlashNum--;
                            theMap[currentRow][currentCol] = 1;
                        }
                    }
                    break;
                }
                default:{
                    break;
                }
            }
            if(needFlashNum == 0){
                cout<<"Yes"<<endl;
                cout<<i+1<<endl;
                return;
            }

        }
        if(needFlashNum > 0){
            cout<<"No"<<endl;
            cout<<needFlashNum;
        }
    }
};

int main(){
    Solution s;
    s.run();
    return 0;
}

[3] 玩扑克牌

先用牌的索引模拟洗牌翻牌的过程，最后根据索引从输入中对应取出。

//
// Created by Harold on 2022/8/13/0013.
//
#include<iostream>
#include <deque>
#include <vector>
using namespace std;
class Solution{
private:
    int n_nums;
    vector<int> inputNumList;
public:
    void getInput(){
        cin>>n_nums;
        vector<int> inputList(n_nums);
        for(int i = 0; i < n_nums; i++){
            cin>>inputList[i];
        }
        inputNumList = inputList;
    }
    void getTheAns(){
        deque<int> simulationQueue;
        deque<int> positionQueue;
        vector<int> res(n_nums,0);
        for(int i = 0; i < n_nums; i++){
            simulationQueue.push_back(i);
        }
        while(!simulationQueue.empty()){
            simulationQueue.push_back(simulationQueue.front());
            simulationQueue.pop_front();
            simulationQueue.push_back(simulationQueue.front());
            simulationQueue.pop_front();

            positionQueue.push_back(simulationQueue.front());
            simulationQueue.pop_front();
        }
        for(int i = 0; i < n_nums; i++){
            res[positionQueue[i]] = inputNumList[i];
        }
        cout<<res[0];
        for(int i = 1; i < n_nums; i++){
            cout<<" "<<res[i];
        }
    }
    void run(){
        getInput();
        getTheAns();
}
};
int main(){
    Solution s;
    s.run();
    return 0;
}

[4] 三元组

暴力法求解

//
// Created by Harold on 2022/8/13/0013.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution{
private:
    int n_nums;
    vector<int> numList;
public:
    void getInput(){
        cin>>n_nums;
        vector<int> numInput(n_nums);
        for(int i = 0; i < n_nums; i++){
            cin>>numInput[i];
        }
        numList = numInput;
}
    void run(){
    getInput();
    getTheAns();
}
    void getTheAns(){
        int diff_ij,diff_jk;
        int res = 0;
        for(int i = 0; i < n_nums; i++){
            for(int j = i+1; j < n_nums; j++){
                diff_ij = numList[i] - numList[j];
                for(int k = j+1; k < n_nums; k++){
                    diff_jk = 2 * numList[j] - numList[k];
                    if(diff_ij == diff_jk){
                        res++;
                    }
                }
            }
        }
        cout<<res;
}
};
int main(){
    Solution s;
    s.run();
}

[5] 二叉树上摘金币

使用数组表示二叉树，深度优先进行搜索。

//
// Created by Harold on 2022/8/13/0013.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution{
private:
    int n_nums;
    vector<int> moneyList;
    int maxMoney = 0;
public:
    void getTheAns(){
        dfs(1,0);
        cout<<maxMoney;
}
    void dfs(int currentIndex, int moneyObtain){
        if(currentIndex > n_nums){
            return;
        }
        moneyObtain += moneyList[currentIndex];
        if(moneyObtain > maxMoney){
            maxMoney = moneyObtain;
        }
        dfs(2*currentIndex,moneyObtain);
        dfs(2*currentIndex+1,moneyObtain);
    }
    void getInput(){
        cin>>n_nums;
        vector<int> moneyInput(n_nums+1);
        for(int i = 1; i <= n_nums; i++){
            cin>>moneyInput[i];
        }
        moneyList = moneyInput;
}
    void run(){
    getInput();
    getTheAns();
}

};
int main()
{
    Solution s;
    s.run();
    return 0;
}

#美团笔试##美团#