[LeetCode] Weekly Contest 282 復習

はじめに

LeetCode Weekly Contest 282 の復習記事です。3 問目までは 30 分以内に割とサクッと解けましたが、4 問目は 1 時間かけても全く解けませんでした。

2185. Counting Words With a Given Prefix

https://leetcode.com/problems/counting-words-with-a-given-prefix/

与えられた文字列群wordsの中に、prefで指定された文字列をプレフィックスとして持つ文字列が何個あるかを求める問題です。

難易度

Easy

アプローチ

1問目ということで特に捻りもなくてやるだけですね。

解答

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int res = 0;

        for (auto& w : words) {
            if (w.find(pref) == 0) {
                res++;
            }
        }
        
        return res;
    }
};

別解として、もしfind関数を使わずに自分で実装するとしたら以下のような感じになります。

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int res = 0;

        for (auto& w : words) {
            int j = 0;
            for (int i = 0; i < min(w.size(), pref.size()); i++) {
                if (pref[j] != w[i]) {
                    break;
                }
                j++;
            }
            
            if (j == pref.size()) {
                res++;
            }
        }
        
        return res;
    }
};

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

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram-ii/

この問題、Mediumですが正直Easyレベルだと思います。

難易度

Medium

アプローチ

結局、sとtのヒストグラムを一致させるための最小操作回数なので、各文字列の文字の出現回数をカウントし、各文字の差分の和を求めればよいです。

解答

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> count(26, 0);
        int res = 0;
        
        for (auto& c : s) {
            count[c - 'a']++;
        }
        
        for (auto& c : t) {
            count[c - 'a']--;
        }
        
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                res += abs(count[i]);
            }
        }
        return res;
    }
};

2187. Minimum Time to Complete Trips

https://leetcode.com/problems/minimum-time-to-complete-trips/

time[i]でi番目のバスが1回の旅行にかかる時間を示し、totalTripsが必要な旅行回数を示します。求めるものは、totalTrips回旅行をするのにかかる最低の時間です。なお、time[i]で与えられる各バスはそれぞれ独立かつ連続して旅行が可能です。

難易度

Medium

アプローチ

totalTrips回旅行をするのにかかる最小の時間と最大の時間は、それぞれtime[i]中の最小値、最大値から求めることが出来ます。この手の問題はバイナリサーチですね。left = 最小時間, right = 最大時間として、条件を満たす最小の時間を求めます。

解答

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        sort(time.begin(), time.end());

        long long l = 0;
        long long r = time.back() * (long)totalTrips;
        long long res = 0;
        while (l <= r) {
            long long m = l + (r - l) / 2;
            if (isOk(time, totalTrips, m)) {
                r = m - 1;
                res = m;
            } else {
                l = m + 1;
            }
        }

        return res;
    }

private:
    bool isOk(vector<int>& time, int& totalTrips, long long& m) {
        long long count = 0;

        for (auto& x : time) {
            count += m / x;
        }
        
        return count >= totalTrips;
    }
};

2188. Minimum Time to Finish the Race

https://leetcode.com/problems/minimum-time-to-finish-the-race/

TBU.

難易度

Hard

アプローチ

解答