第90场周赛

用户1145562

发布于 2020-10-23 04:11:06

32000

代码可运行

文章被收录于专栏：LC刷题LC刷题

运行总次数：0

代码可运行

传送门

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; }