快手笔试四道AC c++

第一次将所有编程题全部AC，还提前交卷，以为自己水平提高了，，原来是题目简单了😌

第一题：

判断输入的表达式中配对的括号数量，左括号的数量，右括号的数量

#include<iostream>
#include<string>
#include <stack>
using namespace std;

int main(){
    string myString;
    getline(cin,myString);
    int a=0,left=0,right=0;  // 表示对数，落单左括号，落单右括号
    stack<char> myChar;
    for(int i=0;i<myString.size();i++){
        if(myString[i] == '(' || myString[i] == ')'){
            if(myString[i] == ')'){
                if(!myChar.empty()){
                    if(myChar.top() == '('){
                        a++;
                        myChar.pop();
                    } else
                        right++;
                } else{
                    right++;
                }
            } else{
                myChar.push(myString[i]);
            }
        }
    }
    left = myChar.size();
    cout<<a<<' '<<left<<' '<<right;
    return 0;
}

第二题：

判断一个数是否是完美数幂因子，

解法：模拟除二取余，判断所有余数是否都是1

#include<iostream>
#include<string>
#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * 返回无重复幂因子的 N进制完美数之和的所有幂因子
     * @param R int整型
     * @param N int整型 N进制
     * @return int整型vector
     */
    vector<int> GetPowerFactor(int R, int N) {
        // write code here

        vector<int> yu;
        vector<int> result;
        while(R > 0){
            int temp = R % N;
            yu.push_back(temp);
            R = R / N;
        }
        for(int i=0;i<yu.size();i++){
            if(yu[i] == 1)
                result.push_back(i);
            else if(yu[i] > 1)
                return vector<int>(0,0);
        }
        return result;
    }
};

int main(){
    Solution solution;
    vector<int> result = solution.GetPowerFactor(39,3);
    for(auto i:result)
        cout<<i<<' ';
    return 0;
}

第三题：

顾客排队，每一个人有两个属性a和b，每个人的满意度是a*（自己前面的人数）+ b*(后面的人数)
解法：计算每个人的a-b的值，对差进行排序，差大的排在前面

#include<iostream>
#include<string>
#include <stack>
#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    /**
     * 根据顾客属性计算出顾客排队顺序
     * @param a int整型vector 顾客a属性
     * @param b int整型vector 顾客b属性
     * @return int整型vector
     */
    vector<int> WaitInLine(vector<int>& a, vector<int>& b) {
        // write code here
        multimap<int,int,greater<> > diff;
        for(int i=0;i<a.size();i++){
            int temp = a[i]-b[i];
            diff.insert(pair<int,int>(temp,i));
        }
        vector<int> result;
        for(auto i:diff)
            result.push_back(i.second + 1);
        return result;
    }
};

int main(){
    Solution solution;
    vector<int> a{8,9,7};
    vector<int> b{5,8,3};
    vector<int> result;
    result = solution.WaitInLine(a,b);
    for(auto i:result)
        cout<<i<<' ';
}

第四题：

工位上可以坐的最多人数 [[* , .],[* , .]] 用来表示工位的状态，*表示没有点，每个人前后左右都不可以有人。

解法：从左上角开始，一行一行扫描判断是否可以坐人，没有用DFS的方法。

class Solution {
public:
    /**
     * 获取最大可同事办公员工数
     * @param pos char字符型vector<vector<>> 工位分布
     * @return int整型
     */
    int GetMaxStaffs(vector<vector<char> >& pos) {
        // write code here
        int rows = pos.size();       // 行数
        int columns = pos[0].size();    // 列数
        int count = 0;  // 可以坐的人数
        //-1表示无电源，0表示有电源无人坐，1表示有人坐
        vector<vector<int> > people(rows,vector<int>(columns,-1));
        for(int i=0;i<pos.size();i++){
            for(int j=0;j<pos[0].size();j++){
                if(pos[i][j] == '.')
                    people[i][j] = 0;
            }
        }
        for(int i=0;i<pos.size();i++){
            for(int j=0;j<pos[0].size();j++){
                if(people[i][j] == 0 && can(people,i,j)){
                    count++;
                    people[i][j] = 1;   // 设置已坐标志
                }
            }
        }
        return count;
    }
    // 是否可以坐
    bool can(const vector<vector<int> >& people,int i,int j){
        int rows = people.size();
        int columns = people[0].size();
        if(i < rows && i >= 0 && j < columns && j >= 0){
            if(havePeople(people,i,j-1) || havePeople(people,i,j+1) || havePeople(people,i-1,j)
            || havePeople(people,i+1,j)){
                return false;
            }
            return true;
        }
        return false;
    }
    // 是否有人
    bool havePeople(const vector<vector<int> >& people,int i,int j){
        int rows = people.size();
        int columns = people[0].size();
        bool have = false;
        if(i < rows && i >= 0 && j < columns && j >= 0){
            if(people[i][j] == 1)
                have = true;
        }
        return have;
    }
};

#快手笔试##笔试题目#