Leet Code Weekly Contest 274

1. Check if All A's Appears Before All B's

It can be done in $O(n)$ time. But to save time, $O(n^2)$ brute-force is enough :).

c++

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

2. Number of Laser Beams in a Bank

Filter-out empty lines.
Let's say $M_i$ is the number of devices in row $i$ .
The answer is $\sum_{i = 1}^{i < n}{M_i \times M_{i - 1}}$ .

c++

class Solution
{
public:
    int numberOfBeams(vector<string>& bank)
    {
        vector<int> nums;
        
        for (auto &row : bank)
        {
            int count = 0;
            
            for (auto &c : row)
            {
                if (c == '1')
                {
                    count++;
                }
            }
            
            if (count > 0)
            {
                nums.push_back(count);
            }
        }
        
        int ret = 0;
        
        for (int i = 1; i < nums.size(); i++)
        {
            ret += nums[i] * nums[i - 1];
        }
        
        return ret;
    }
};

3. Destroying Asteroids

Greedy. We can prove that it is always better to take smallest asteroid first.
Sort and linear-scan.
Don't forget long long!

c++

class Solution
{
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids)
    {
        sort(asteroids.begin(), asteroids.end());
     
        long long now = mass;
        
        for (auto x : asteroids)
        {
            if (now >= x)
            {
                now += x;
            }
            else
            {
                return false;
            }
        }
        
        return true;
    }
};

4. Maximum Employees to Be Invited to a Meeting

First, DFS to find all circles with more than 2 nodes. They can be candidate answers and remove them from the graph.
After that, we have only circles with 2 nodes.
Exclude these edges within 2-nodes circles, we can perform a DP to find all longest paths.
So the answer can be either a big circle (with more than 2 nodes) or several sub-graphs (each sub-graph is built with two chains and a 2-nodes circle).

Case 1 Example (big circle).

Case 2 Example (several sub-graphs with two chains).

c++

class Solution
{
public:
    
    int ans = INT_MIN;
    
    bool visit[100000], in_path[100000], removed[100000];
    
    vector<int> path;
    
    void dfs(int x, vector<int>& favorite)
    {
        // cout << "visit " << x << endl;
        
        visit[x] = true;
        
        path.push_back(x);
        in_path[x] = true;
        
        int y = favorite[x];
        
        if (favorite[y] != x && !removed[y])
        {
            if (in_path[y])
            {
                for (int i = path.size() - 1; i >= 0; i--)
                {
                    // cout << path[i] << ", ";

                    removed[path[i]] = true;

                    if (path[i] == y)
                    {
                        int circle_size = path.size() - i;
                        ans = max(ans, circle_size);

                        // cout << "circle with " << circle_size << " nodes" << endl;

                        break;
                    }
                }
            }
            else if (!visit[y])
            {
                dfs(y, favorite);
            }
        }
        
        in_path[x] = false;
        path.pop_back();
    }
    
    vector<int> parent[100000];
    
    int f[100000];
    
    int get_f(int x)
    {
        if (f[x] == -1)
        {
            f[x] = 1;
            
            for (auto &y : parent[x])
            {
                f[x] = max(f[x], get_f(y) + 1);
            }
            
            // cout << "f[" << x << "] = " << f[x] << endl;
        }
        
        return f[x];
    }

    int maximumInvitations(vector<int>& favorite)
    {
        int n = favorite.size();
        
        for (int i = 0; i < n; i++)
        {
            visit[i] = false;
            in_path[i] = false;
            removed[i] = false;
        }
        
        for (int i = 0; i < n; i++)
        {
            if (!visit[i] && !removed[i])
            {
                dfs(i, favorite);
            }
        }
        
        for (int i = 0; i < n; i++)
        {
            int x = i, y = favorite[x];
            
            if (removed[x] || removed[y] || favorite[y] == x)
            {
                continue;
            }
            
            // cout << "parent[" << y << "] << " << x << endl;
            
            parent[y].push_back(x);
        }
        
        for (int i = 0; i < n; i++)
        {
            f[i] = -1;
        }
        
        int ans2 = 0;
        
        for (int i = 0; i < n; i++)
        {
            int x = i, y = favorite[x];
            
            if (favorite[y] == x && x < y)
            {
                ans2 += get_f(x) + get_f(y);
            }
        }
        
        return max(ans, ans2);
    }
};

Leet Code Weekly Contest 274

1. Check if All A's Appears Before All B's

2. Number of Laser Beams in a Bank

3. Destroying Asteroids

4. Maximum Employees to Be Invited to a Meeting

Case 1 Example (big circle).

Case 2 Example (several sub-graphs with two chains).

COMMAND INTERFACE

:help aguang.xyz