Leet Code Weekly Contest 266

1. Count Vowel Substrings of a String

Brute-force, time complexity: $O(n^2)$

c++

class Solution {
public:
    
    bool valid(string s)
    {
        bool has[5];
        
        memset(has, false, sizeof(bool) * 5);
        
        for (auto c : s)
        {
            if (c == 'a')
            {
                has[0] = true;
            }
            
            else if (c == 'e')
            {
                has[1] = true;
            }
            
            else if (c == 'i')
            {
                has[2] = true;
            }
            
            else if (c == 'o')
            {
                has[3] = true;
            }
            
            else if (c == 'u')
            {
                has[4] = true;
            }
            else return false;
        }
        
        for (int i = 0; i < 5; i++)
        {
            if (!has[i])
            {
                return false;
            }
        }
        
        return true;
    }
    
    int countVowelSubstrings(string word)
    {
        int ans = 0;
        
        for (int i = 0; i < word.length(); i++)
        {
            for (int j = 1; i + j <= word.length(); j++)
            {
                string s = word.substr(i, j);
                
                if (valid(s))
                {
                    ans++;
                }
            }
        }
        
        return ans;
    }
};

2. Vowels of All Substrings

A char at position $i$ will be contained by $(i + 1) * (n - i)$ substrings. So we just scan and count all vowels in the given string.

Time complexity: $O(n)$

c++

class Solution {
public:
    bool valid(char c)
    {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
    
    long long countVowels(string word)
    {
        long long ans = 0;
        long long n = word.length();
        
        for (long long i = 0; i < n; i++)
        {
            if (valid(word[i]))
            {
                ans += (i + 1) * (n - i);
            }
        }
        
        return ans;
    }
};

3. Minimized Maximum of Products Distributed to Any Store

Let's assume we have a function $F(x)$ which means the number of products we need when we decide the maximum number of products that are given to any store is $x$ .

Obviously, for any $x \leq y$ , $f(x) \geq f(y)$ .

Then the problem can be seen as a binary search to find the minimum $x$ where $f(x) >= n$ .

Time complexity: $O(n * lg(n))$

c++

class Solution {
public:
    
    int calc(int t, vector<int> &quantities)
    {
        int ans = 0;
        
        for (auto x : quantities)
        {
            ans += (x - 1) / t + 1;
        }
        
        return ans;
    }
    
    int minimizedMaximum(int n, vector<int>& quantities)
    {
        int left = 1, right = 100000;
        
        while (left < right)
        {
            int mid = (left + right) / 2;
            
            if (calc(mid, quantities) <= n)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        
        return right;
    }
};

4. Maximum Path Quality of a Graph

When you find the description "Note: There are at most four edges connected to each node.", it is probably misleading you to a Tree-DP. But if find the constraint "10 <= timej, maxTime <= 100", we know there will be at most 10 edges of the path. And based only that, if we pre-compute the shortest path from $0$ to each node, we can futher prune some branches.

So the solution is DFS + SPFA.

c++

class Solution
{
public:
    
    // (target, time)
    vector<pair<int, int>> targets[1000];
    
    int min_dist[1000];
    
    void spfa(int n)
    {
        for (int i = 0; i < n; i++)
        {
            min_dist[i] = INT_MAX;
        }
        
        bool visited[1000];
        memset(visited, false, sizeof(bool) * n);
        
        min_dist[0] = 0;
        visited[0] = true;
        queue<int> q({ 0 });
        
        while (!q.empty())
        {
            int x = q.front(); q.pop();
            visited[x] = false;
            
            for (auto e : targets[x])
            {
                int y = e.first, d = e.second;
                
                if (min_dist[x] + d < min_dist[y])
                {
                    min_dist[y] = min_dist[x] + d;
                    
                    if (!visited[y])
                    {
                        q.push(y);
                        visited[y] = true;
                    }
                }
            }
        }
    }
    
    int ans = 0, allowed_time;
    
    int visit_count[10000];
    
    vector<int> scores;
    
    // visiting node x, used time d, got score before visit
    void dfs(int x, int d, int score)
    {
        if (visit_count[x]++ == 0)
        {
            score += scores[x];
        }
        
        if (d + min_dist[x] <= allowed_time)
        {
            ans = max(ans, score);
            
            for (auto e : targets[x])
            {
                dfs(e.first, d + e.second, score);
            }
        }
        
        visit_count[x]--;
    }
    
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime)
    {
        int n = values.size();
        
        for (auto e : edges)
        {
            int x = e[0], y = e[1], time = e[2];
            targets[x].push_back(make_pair(y, time));
            targets[y].push_back(make_pair(x, time));
        }
        
        spfa(n);
        
        allowed_time = maxTime;
        
        memset(visit_count, 0, sizeof(int) * 1000);
        
        scores = vector<int>(values.begin(), values.end());
        
        dfs(0, 0, 0);
        
        return ans;
    }
};

Leet Code Weekly Contest 266

1. Count Vowel Substrings of a String

2. Vowels of All Substrings

3. Minimized Maximum of Products Distributed to Any Store

4. Maximum Path Quality of a Graph

COMMAND INTERFACE

:help aguang.xyz