Leetcode第274场周赛总结

检查是否所有A都在B之前

https://leetcode-cn.com/problems/check-if-all-as-appears-before-all-bs/

题目描述

给你一个仅由字符 'a' 和 'b' 组成的字符串 s 。如果字符串中 每个 'a' 都出现在 每个 'b' 之前，返回 true ；否则，返回 false 。

示例 1：
输入：s = "aaabbb"
输出：true
解释：
'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。
示例 2：
输入：s = "abab"
输出：false
解释：
存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false 。
示例 3：
输入：s = "bbb"
输出：true
解释：
不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

提示：

My Original Solution

class Solution {
public:
    bool checkString(string s) {
        int a = 0, b = 1000;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'a')
                a = max(i, a);
            else
                b = min(i, b);
        }
        if (a > b)
            return false;
        else
            return true;
    }
};

评价：我的想法是，a位置最大的在b位置最小的之前。

Elegant Solution

class Solution {
public:
    bool checkString(string s) {
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == 'a' and s[i - 1] == 'b') return false;
        }
        return true;
    }
};

class Solution {
public:
    bool checkString(string s) {
        return s.find("ba") == string::npos; // 没找到"ab"
    }
};

银行中的激光束数量

https://leetcode-cn.com/problems/number-of-laser-beams-in-a-bank/

题目描述

My Original Solution

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        vector<int> result;
        for (int i = 0; i < bank.size(); i++) {
            int k = 0;
            for (int j = 0; j < bank[i].size(); j++) {
                if (bank[i][j] == '1')
                    k++;
            }
            if (k)
                result.push_back(k);
        }
        if (result.size() <= 1)
            return 0;
        int total = 0;
        for (int i = 0; i < result.size() - 1; i++) {
            total += result[i]*result[i+1];
        }
        return total;
    }
};

评价：思路挺好，就是有点麻烦。

Elegant Solution

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int result = 0, previous = 0;
        for (auto& s : bank) {
            int current = count(s.begin(), s.end(), '1');
            if (!current) continue;
            result += previous * current;
            previous = current;
        }
        return result;
    }
};

摧毁小行星

https://leetcode-cn.com/problems/destroying-asteroids/solution/

题目描述

My Original Solution

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        int num = asteroids.size();
        for (int i = 0; i < num; i++) {
            if (asteroids[i] <= mass) {
                mass+=asteroids[i];
                if (mass >= asteroids[num - 1]) {
                    return true;
                }
            } else {
                return false;
            }
        }
        return true;
    }
};

评价：没有拿捏细节。mass应该用long long 来存储，因为，直接用int来存，mass可能会溢出。

Elegant Solution

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        long long _mass = mass;

        for (const int &asteroid : asteroids) {
            if (asteroid <= _mass) _mass += asteroid;
            else return false;
        }
        return true;
    }
};

参加会议的最多员工数

https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting/

题目描述

My Original Solution

无

Elegant Solution

基环内向树：拓扑排序+分类讨论
https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting/solution/can-jia-hui-yi-de-zui-duo-yuan-gong-shu-u8e8u/