第90场周赛
859. 亲密字符串
题解：根据描述，找出A与B字符不同的位置，如果没有这样的位置，那么需要在A中找到重复的字符即可判断是亲密的。如果有这样的位置，那么在这样的位置有两个情况，判断这两处位置交换后是否一样。如果这样的位置个数不是2个，肯定不是亲密字符串。
bool buddyStrings(string A, string B)
{
if(A.size()!=B.size()) return false;
vector<int>diff;
for(int i=0;i<A.size();i++)
{
if(A[i]!=B[i]) diff.push_back(i);
}
if(diff.size()==0){
//说明ab一样，那么则需要在a中找到重复的字符
map<char,int>m;
for(int i=0;i<A.size();i++)
{
m[A[i]]++;
if(m[A[i]]>1) return true;
}
return false;
}
else if(diff.size()==2)
{
return ((A[diff[0]])==(B[diff[1]]))&&(A[diff[1]]==B[diff[0]]);
}
return false;
}856. 括号的分数
题解:不知道怎么描述。把每次计算的分数，顺带把由哪个位置括号计算的到的一起压入。
int scoreOfParentheses(string S) {
int ret = 0;
stack<int>brackets;
stack<pair<int,int>>scores;//前一个int存socre，后一个int存下标
for(int i=0;i<S.size();i++){
if(S[i]=='(') {
brackets.push(i);
}
else {
if(i-brackets.top()==1) {
scores.push(make_pair(1,brackets.top()));
brackets.pop();
}
else{
int tmp = 0;
int d = brackets.top();
while(!scores.empty()&&scores.top().second>d)
{
tmp+=scores.top().first;
scores.pop();
}
scores.push(make_pair(2*tmp,d));
brackets.pop();
}
}
}
while(!scores.empty()){
ret+=scores.top().first;
scores.pop();
}
return ret;
}858. 镜面反射
题解：
- 模拟法：光线的运动可以分解为x方向运动，y方向运动。 X方向的运动，光线在正方形的左右边界不断跳转，y方向的运动，一开始不断向上前进q哥单位，达到上边界后，反射，之后向下前进q个单位，在达到下边界，变为向上前进q个单位。 int mirrorReflection(int p, int q) { vector<int> position = {0,0};//起始位置，左下角 vector<vector<int>> catchers = {{p,0},{p,p},{0,p}}; //探测器坐标 int directx = 1,directy = 1;//方向向量 while(true) { position[0] += directx*p;//x方向变动p个单位 directx *= -1;//每次反射，光线X轴方向变反 position[1] += directy*q;//y方向变动q个单位 if(position[1] > p) {//计算y方向变动后，被上边界反射后实际坐标 position[1] = p-(position[1]%p); directy *= -1; //注意方向，变反 } if(position[1] < 0) {//计算y方向变动后，被上边界反射后实际坐标 position[1] = -position[1]; directy *= -1; //方向 } for(int i=0;i<catchers.size();++i) if(position == catchers[i]) return i; //检测是否到达探测器 } return 0; }
857. 雇佣 K 名工人的最低成本
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-122，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录