快手 笔试四道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的值，对差进行排序，差大的排在前面
解法：计算每个人的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;
}
}; 
