LeetCode Weekly Contest 282

1. Counting Words With a Given Prefix

Brute-force.

c++

class Solution
{
public:
    
    bool valid(string &word, string &ref)
    {
        if (ref.length() > word.length())
        {
            return false;
        }
        
        for (int i = 0; i < ref.length(); i++)
        {
            if (ref[i] != word[i])
            {
                return false;
            }
        }
        
        return true;
    }
    
    int prefixCount(vector<string>& words, string pref)
    {
        int ans = 0;
        
        for (auto &w : words)
        {
            if (valid(w, pref))
            {
                ans++;
            }
        }
        
        return ans;
    }
};

2. Minimum Number of Steps to Make Two Strings Anagram II

Use a hash-map to count the frequency of each character.
For each character c, let's say the frequency of c in s is x and the frequency of c in t is y, we need abs(x - y) steps.

c++

class Solution
{
public:
    int minSteps(string s, string t)
    {
        unordered_map<char, int> cnt1, cnt2;
        
        for (auto &c : s)
        {
            cnt1[c]++;
        }
        
        for (auto &c : t)
        {
            cnt2[c]++;
        }
        
        int ans = 0;
        
        for (char c = 'a'; c <= 'z'; c++)
        {
            int x = cnt1[c], y = cnt2[c];
            ans += max(x, y) - min(x, y);
        }
        
        return ans;
    }
};

3. Minimum Time to Complete Trips

Binary-search.

c++

typedef long long ll;

class Solution {
public:
    
    ll trips(vector<int> &time, ll totalTime)
    {
        ll ret = 0;
        
        for (auto &t : time)
        {
            ret += totalTime / t;
        }
        
        return ret;
    }
    
    ll minimumTime(vector<int>& time, int totalTrips)
    {
        ll low = 1, high = 1, ans;
        
        for (auto &t : time)
        {
            high = max(high, ((ll) t) * totalTrips);
        }
        
        while (low <= high)
        {
            ll mid = (low + high) / 2;
            
            if (trips(time, mid) >= totalTrips)
            {
                ans = mid;
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        
        return ans;
    }
};

4. Minimum Time to Finish the Race

Let's say $G_i$ indicates the minimum time to run $i$ laps using only one tire. We can easily calculate that in $O(n)$ time.
Let's say $H_i$ indicates the minimum time to run $i$ laps using possibly multiple tires.
$H_i = \text{min}(H_j + G_{i - j} + \text{changeTime})$ where $j \lt i$ .
Since we counted one more changeTime, so the answer should be $H_{\text{numLaps}} - \text{changeTime}$ .

c++

typedef long long ll;

class Solution
{
public:
    
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps)
    {
        vector<ll> g(1001, INT_MAX);
        
        g[0] = 0;
        
        for (auto trie : tires)
        {
            ll f = trie[0], r = trie[1], time = 0, ri = 1;
            
            for (int i = 1; i <= numLaps; i++)
            {
                time += f * ri;
                ri = ri * r;
                
                if (time >= INT_MAX)
                {
                    break;
                }
                
                g[i] = min(g[i], time);
            }
        }
        
        vector<ll> h(1001, INT_MAX);
        
        h[0] = 0;
        
        for (int i = 1; i <= numLaps; i++)
        {
            for (int j = 0; j < i; j++)
            {
                h[i] = min(h[i], h[j] + g[i - j] + changeTime);
            }
        }
        
        return h[numLaps] - changeTime;
    }
};

LeetCode Weekly Contest 282

1. Counting Words With a Given Prefix

2. Minimum Number of Steps to Make Two Strings Anagram II

3. Minimum Time to Complete Trips

4. Minimum Time to Finish the Race

COMMAND INTERFACE

:help aguang.xyz