Leet Code Weekly Contest 264

1. Number of Valid Words in a Sentence

Naive, simple string processing.

c++

inline vector<string> split(string s, char delimiter = ' ')
{
    auto words = vector<string>({ "" });

    for (auto &c : s)
    {
        if (c == delimiter)
        {
            words.push_back("");
        }
        else
        {
            words.back().push_back(c);
        }
    }

    return words;
}

inline bool not_empty(string &s)
{
    return s.length() > 0;
}

template<class T, class UnaryPredicate>
vector<T> where(vector<T> elements, UnaryPredicate pred)
{
    auto ret = vector<T>();
    copy_if(elements.begin(), elements.end(), back_inserter(ret), pred);
    return ret;
}

class Solution
{
public:
    bool isValid(string &w)
    {
        if (w.length() == 0)
        {
            return true;
        }
        
        if (w[w.length() - 1] == '.' || w[w.length() - 1] == '!' || w[w.length() - 1] == ',')
        {
            w = w.substr(0, w.length() - 1);
        }
        
        if (w.length() == 0)
        {
            return true;
        }
        
        int cnt = 0;
        
        for (auto &c : w)
        {
            if (c >= '0' && c <= '9')
            {
                return false;
            }
            
            if (c == '.' || c == '!' || c == ',')
            {
                return false;
            }
            
            if (c == '-')
            {
                cnt++;
            }
        }
        
        if (cnt > 1)
        {
            return false;
        }
        
        if (w[0] == '-' || w[w.length() - 1] == '-')
        {
            return false;
        }
        
        return true;
    }
    
    int countValidWords(string sentence)
    {
        vector<string> words = where(split(sentence), not_empty);
        
        int ans = 0;
        for (auto &w : words)
        {
            if (isValid(w))
            {
                ans++;
            }
        }
        
        return ans;
    }
};

2. Next Greater Numerically Balanced Number

Simple brute force. One small trap is that the upper bound of $n$ is not the uppper bound of the answer.

c++

class Solution
{
public:
    bool isValid(int x)
    {
        int cnt[10];
        
        memset(cnt, 0, sizeof(int) * 10);
        
        for (auto c : to_string(x))
        {
            cnt[c - '0']++;
        }
        
        for (int i = 0; i < 10; i++)
        {
            if (cnt[i] > 0 && cnt[i] != i)
            {
                return false;
            }
        }
        
        return true;
    }
    
    int nextBeautifulNumber(int n)
    {
        for (int i = n + 1; true; i++)
        {
            if (isValid(i))
            {
                return i;
            }
        }
        
        return 0;
    }
};

3. Count Nodes With the Highest Score

We can do a simple DFS to pre-compute the sizes of all subtrees in $O(n)$ time complexity.

For each node $x$ , if we remote this node, the tree will be splitted into three subtrees:

The whole tree cut the current subtree (size: $Size_{0} - Size_{x}$ ).
Left sub tree (size: $Size_{l_x}$ )
Right sub tree (size: $Size_{r_x}$ )

So we can calculate the score of each node $x$ in $O(1)$ time complexity.

Be careful about the types since the product can be larger than $2^{31}$ .

c++

class Solution
{
public:
    
    long long size[100000];
    vector<int> children[100000];
    
    void dfs(int x)
    {
        size[x] = 1;
        
        for (auto c : children[x])
        {
            dfs(c);
            size[x] += size[c];
        }
    }
    
    int countHighestScoreNodes(vector<int>& parents)
    {
        for (int i = 1; i < parents.size(); i++)
        {
            children[parents[i]].push_back(i);
        }
        
        dfs(0);
        
        long long ans = 0;
        
        vector<long long> scores;
        
        for (int i = 0; i < parents.size(); i++)
        {
            long long product = 1;
            
            if (i != 0)
            {
                product *= size[0] - size[i];
            }
            
            for (auto c : children[i])
            {
                product *= size[c];
            }
            
            scores.push_back(product);
            
            ans = max(ans, product);
        }
        
        int cnt = 0;
        
        for (auto x : scores)
        {
            if (x == ans)
            {
                cnt++;
            }
        }
        
        return cnt;
    }
};

4. Parallel Courses III

It can be seen as a DP problem.

Let's say $F_x$ is the minimum time to finish course $x$ and all dependencies of $x$ , we have:

$F_x = \text{Time}_x + \max{F_y}$ where $y$ is a dependency of $x$ .

The overall time complexity is $O(n)$ .

c++

class Solution
{
public:
    vector<int> targets[100000];
    int total_time[100000];
    
    int dfs(int x, vector<int> &time)
    {
        if (total_time[x] == -1)
        {
            int m = 0;
            
            for (auto t : targets[x])
            {
                m = max(m, dfs(t, time));
            }
            
            total_time[x] = m + time[x];
        }
        
        return total_time[x];
    }
    
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time)
    {
        for (auto r : relations)
        {
            targets[r[0] - 1].push_back(r[1] - 1);
        }
        
        for (int i = 0; i < n; i++)
        {
            total_time[i] = -1;
        }
        
        int ans = 0;
        
        for (int i = 0; i < n; i++)
        {
            ans = max(ans, dfs(i, time));
        }
        
        return ans;
    }
};

Leet Code Weekly Contest 264

1. Number of Valid Words in a Sentence

2. Next Greater Numerically Balanced Number

3. Count Nodes With the Highest Score

4. Parallel Courses III

COMMAND INTERFACE

:help aguang.xyz