周赛158

分割平衡字符串

题目

在一个「平衡字符串」中，’L’ 和 ‘R’ 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。

分析

典型的栈思路。
不过本体只取思路，不用结构。因为完全可以省下这部分的空间消耗。

代码

class Solution {
public:
    int balancedStringSplit(string s) {
        int n = s.length(),count = 0,res = 0;
        for(int i = 0; i< n; i++){
            if(s[i] == s[0]) count++;
            else count--;
            if(count == 0) res++;
        }
        return res;
    }
};

时间消耗:O(n)
空间消耗:O(1)

可以攻击国王的皇后

题目1

传送门

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。
「黑皇后」在棋盘上的位置分布用整数坐标数组 queens 表示，「白国王」的坐标用数组 king 表示。
「黑皇后」的行棋规定是：横、直、斜都可以走，步数不受限制，但是，不能越子行棋。
请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标（任意顺序）。

分析1

构建稀疏矩阵，然后从国王的位置向 8 个方向查找，找到即停止。
一个值得注意的地方是，矩阵的边界应该由 queens 和 king 共同决定。
存在数学解法。

代码1

class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        int m = 0, n = 0;
        for(auto i:queens){
            if(m < i[0]) m = i[0];
            if(n < i[1]) n = i[1];
        }
        if(m < king[0]) m = king[0];
        if(n < king[1]) n = king[1];
        m++;
        n++;
        vector<vector<int>> tmp(m,vector<int>(n,0)) , res;
        for(auto i:queens)
            tmp[i[0]][i[1]] = 1;

        int i = king[0],j = king[1];
        while(i>0 && i<m)
            if(tmp[--i][j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(i>=0 && i<m-1)
            if(tmp[++i][j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(j>0 && j<n)
            if(tmp[i][--j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(j>=0 && j<n-1)
            if(tmp[i][++j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(i>0 && i<m && j>0 && j<n)
            if(tmp[--i][--j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(i>=0 && i<m-1 && j>=0 && j<n-1)
            if(tmp[++i][++j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(i>0 && i<m && j>=0 && j<n-1)
            if(tmp[--i][++j] == 1){
                res.push_back({i,j});
                break;
            }

        i = king[0],j = king[1];
        while(i>=0 && i<m-1 && j>0 && j<n)
            if(tmp[++i][--j] == 1){
                res.push_back({i,j});
                break;
            }

        return res;
    }
};

最大相等频率

题目2

传送门

给出一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回其长度：
从前缀中删除一个元素后，使得所剩下的每个数字的出现次数相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

分析2

构建双哈希表，第一张表存放每个元素出现的次数，第二张表存放每个次数(第一张表的元素)出现的次数。

代码2

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        map<int,int> ma;
        int n = nums.size();
        for(int i = 0;i < n;i++)
            ma[nums[i]]++;
        if(ma.size() == 1) return n;
        for(int i = n-1 ; i >=0 ; i--){
            map<int,int> matmp;
            for(const auto& m:ma)
                matmp[m.second]++;
            std::map<int,int>::iterator iter=matmp.begin();
            for (iter;iter!=matmp.end();){
                if (iter->first==0)
                    matmp.erase(iter++);
                else
                    iter++;
            }
            ma[nums[i]]--;
            if(i == n-1 && matmp.size() == 1 && ma[nums[0]] == 1) return n;
            if(matmp.size() != 2) continue;
            vector<int> vec1,vec2;
            for(const auto& m:matmp){
                vec1.push_back(m.first);
                vec2.push_back(m.second);
            }
            int min = vec1[0] > vec1[1] ? 0 : 1;
            if((vec2[min] == 1 && abs(vec1[0]-vec1[1]) == 1) || (vec1[0] == 1 && vec2[0] == 1)) return i+1;
        }
        return 0;
    }
};

后记

又是快要饿死的一天。