../ Competitive Programming

-rw-r--r--aguang4.5 KiB2022-01-093 min read

Leet Code Weekly Contest 275

1. Check if Every Row and Column Contains All Numbers

Naive

c++

class Solution
{
public:
    bool valid(set<int> &s, int n)
    {
        for (int i = 1; i <= n; i++)
        {
            if (s.find(i) == s.end())
            {
                return false;
            }
        }
        
        return true;
    }
    
    bool checkValid(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        
        for (int i = 0; i < n; i++)
        {
            set<int> s;
            
            for (int j = 0; j < n; j++)
            {
                s.insert(matrix[i][j]);
            }
            
            if (!valid(s, n))
            {
                return false;
            }
        }
        
        for (int i = 0; i < n; i++)
        {
            set<int> s;
            
            for (int j = 0; j < n; j++)
            {
                s.insert(matrix[j][i]);
            }
            
            if (!valid(s, n))
            {
                return false;
            }
        }
        
        return true;
    }
};

2. Minimum Swaps to Group All 1's Together II

Preffix-sum.
Since it's circular array, simply double it.

c++

class Solution
{
public:
    int minSwaps(vector<int>& nums)
    {
        int n = nums.size(), m = 0;
        
        for (auto &x : nums)
        {
            if (x == 1)
            {
                m++;
            }
        }
        
        if (m == 0)
        {
            return 0;
        }
        
        vector<int> s = { 0 };
        
        for (auto &x : nums)
        {
            s.push_back(s.back() + x);
        }
        
        for (auto &x : nums)
        {
            s.push_back(s.back() + x);
        }
        
        int ans = INT_MAX;
        
        for (int i = 0; i + m < s.size(); i++)
        {
            ans = min(ans, m - (s[i + m] - s[i]));
        }
        
        return ans;
    }
};

3. Count Words Obtained After Adding a Letter

Sort the letters within each word to construct the hash key.
Enumerate the missing letter from each target word.

c++

class Solution
{
public:   
    int wordCount(vector<string>& startWords, vector<string>& targetWords)
    {
        unordered_set<string> s;
        
        for (auto w : startWords)
        {
            sort(w.begin(), w.end());
            s.insert(w);
        }
        
        int ans = 0;
        
        for (auto w : targetWords)
        {
            sort(w.begin(), w.end());
            
            bool found = false;
            
            for (int i = 0; i < w.length(); i++)
            {
                string t = "";
                
                for (int j = 0; j < w.length(); j++)
                {
                    if (j != i)
                    {
                        t += w[j];
                    }
                }
                
                if (s.find(t) != s.end())
                {
                    found = true;
                    break;
                }
            }
            
            if (found)
            {
                ans++;
            }
        }
        
        return ans;
    }
};

4. Earliest Possible Day of Full Bloom

Considering the constraints, there must be some kind of greedy algorithm and the time complexity should be $O(n \log n)$ .
Seems plant with longer grow time should be done earlier since the total plant time is constant.
I can't really prove it but it just works :)

c++

class Solution {
public:

    struct node
    {
        int id, plantTime, growTime;
        
        int totalTime()
        {
            return this->plantTime + this->growTime;
        }
        
        node(int id, int p, int g)
        {
            this->id = id;
            this->plantTime = p;
            this->growTime = g;
        }
    };
    
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime)
    {
        auto cmp = [](node left, node right)
        {
            return left.growTime < right.growTime;
        };
        
        priority_queue<node, std::vector<node>, decltype(cmp)> q(cmp);
        
        int n = plantTime.size();
        
        for (int i = 0; i < n; i++)
        {
            q.push(node(i, plantTime[i], growTime[i]));
        }
        
        int now = 0, ans = 0;
        
        while (!q.empty())
        {
            auto x = q.top(); q.pop();
            
            now += x.plantTime;
            ans = max(ans, now + x.growTime);
        }
        
        return ans;
    }
};

press any key / click to skip