LeetCode第182試合(Weekly Contest 182)解題報告

11062 ワード
LeetCodeブラシ問題記録と問題解 同前 LeetCodeコンテスト アナログ DP KMP map
わあ、大声で泣いて、最后の问题も难しすぎて、KMP+DP、私のKMPはすべて木が学んで、心を刺しました.
第1題:ソート+暴力シミュレーションまたはカウント統計.
第二題:暴力シミュレーションまたは最適化.
第三題:シミュレーション+mapの使用.
第四題:KMP+DP.
詳細は以下の通りです.
1.配列内の幸運数を見つける(Find Lucky Integer In An Array)
ACコード(方法一、ソート+暴力列挙C++)
ACコード(方法二、計数統計C++)
2.作戦単位数の統計(Count Number of Teams)
ACコード(方法一、暴力列挙C++)
ACコード(方法二、暴力最適化C++)
3.地下鉄システムの設計(Design Underground System)
ACコード(C++)
4.すべての良い文字列を見つける(Find All Good Strings)
ACコード(C++)
LeetCode第182試合の週間試合の住所:
https://leetcode-cn.com/contest/weekly-contest-182/
1.配列内の幸運数を見つける(Find Lucky Integer In An Array)
タイトルリンク
https://leetcode-cn.com/problems/find-lucky-integer-in-an-array/
に言及
整数配列では,1つの整数の出現頻度がその数値サイズと等しい場合,この整数を「幸運数」と呼ぶ.
整数配列arrをあげます.そこから幸運の数を見つけて返してください.
配列に複数のラッキー数がある場合は、最大のラッキー数を返すだけです.配列に幸運数が含まれていない場合は、-1を返します.
例1:
  ：arr = [2,2,3,4]
  ：2
  ：           2 ，     2         2 。

ヒント:
  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500

    • 問題を解く構想.
     
    方法一、並べ替え+暴力列挙
    問題に基づいて,まずソートを行い,各数(大きいから小さいまで)についてその出現回数を計算することができ,出現回数==数値であれば答えである.
    時間的複雑度はO(N＊logN)＋O(N＊N),空間的複雑度はO(1)である.データ範囲によってはタイムアウトしません.
     
    方法二、計数統計
    データの範囲に応じて,ある数が出現した回数,すなわちcnt[i]はiという数を表し,cnt[i]回が出現した501の配列で格納できる.
    ではiは大きいから小さいまで判断し、i==cnt[i]?はい、それでは答えです.
    時間的複雑度はO(max(N,M))であり,ここでMはarr[i] 。空間的複雑度はO(M)である.
     
    ACコード(方法一、ソート+暴力列挙C++)
    class Solution {
public:
    int findLucky(vector& arr) {
        sort(arr.begin(), arr.end());
        reverse(arr.begin(), arr.end());
        int n = arr.size();
        for(int i = 0;i < n; ++i)
        {
            int cnt = 1;
            for(int j = 0;j < n; ++j)
            {
                if(j == i) continue;
                if(arr[j] == arr[i]) ++cnt;
            }
            if(cnt == arr[i]) return arr[i];
        }
        return -1;
    }
};

     
    ACコード(方法二、計数統計C++)
    const int MAXM = 510;

class Solution {
public:
    int cnt[MAXM];
    int findLucky(vector& arr) {
        memset(cnt, 0, sizeof(cnt));
        for(auto a : arr) ++cnt[a];

        for(int i = 500; i >= 1; --i)
        {
            if(i == cnt[i]) return i;
        }
        return -1;
    }
};

    2.作戦単位数の統計(Count Number of Teams)
    タイトルリンク
    https://leetcode-cn.com/problems/count-number-of-teams/
    に言及
    n名士兵が一列に並んでいる.兵士一人一人にユニークな採点ratingがある.
    3人の兵士ごとに作戦単位を構成することができ、グループ分けのルールは以下の通りである.
    チームからi、j、kの3人の兵士を選出し、彼らの採点はrating[i]、rating[j]、rating[k]作戦単位が満たす必要がある:rating[i]rating[j]>rating[k]であり、そのうち0<=iは上記の項目で構成できる作戦単位数に戻ってください.各兵士は複数の作戦単位の一部であってもよい.
    例1:
      ：rating = [2,5,3,4,1]
  ：3
  ：             (2,3,4)、(5,4,1)、(5,3,1) 。

    例2:
      ：rating = [2,1,3]
  ：0
  ：      ，          。

    ヒント:
  • n == rating.length
  • 1 <= n <= 200
  • 1 <= rating[i] <= 10^5

    • 問題を解く構想.
     
    方法一、暴力列挙
    最初、テーマを見て、そう考えて、可能なすべてのi j kを列挙して、それから条件を満たしていないと判断します.それでは時間の複雑さはO(N^3)で、データの範囲によって、やはり木が問題になるので、タイムアウトしないので、直接解決すればいいです.
     
    方法二、暴力の最適化
    ある兵士jを中間とする兵士が、その左/右スコアがrating[j]より小さい兵士数をそれぞれ統計すると、兵士jを中間とする兵士が構成できる作戦単位数は、両者の兵士数の積となる.
    値<値<値<値、そして値>値>の値ですが、これも似ています.
    このとき,我々jは遍歴し,残りは,jは左と右を遍歴するので,時間複雑度はO(N^2)で最適化した.
     
    ACコード(方法一、暴力列挙C++)
    class Solution {
public:
    int numTeams(vector& rating) {
        int n = rating.size();
        if(n <= 2) return 0;
        
        int ans = 0;
        for(int i = 0;i < n; ++i)
        {
            for(int j = i + 1;j < n; ++j)
            {
                for(int k = j + 1;k < n; ++k)
                {
                    if(rating[i] < rating[j] && rating[j] < rating[k])
                        ++ans;
                        
                    if(rating[i] > rating[j] && rating[j] > rating[k])
                        ++ans;
                }
            }
        }
        return ans;
        
    }
};

     
    ACコード(方法二、暴力最適化C++)
    class Solution {
public:
    int numTeams(vector& rating) {
        int n = rating.size();
        if(n < 3) return 0;
        int ans = 0;

        //     rating[i] < rating[j] < rating[k]
        for(int j = 1;j < n - 1; ++j)
        {
            int miCnt = 0, mxCnt = 0;
            for(int i = j - 1;i >= 0; --i)
            {
                if(rating[i] < rating[j]) ++miCnt;
            }
            for(int k = j + 1;k < n; ++k)
            {
                if(rating[j] < rating[k]) ++mxCnt;
            }
            ans += miCnt * mxCnt;
        }

        //   ，rating[i] > rating[j] > rating[k]
        for(int j = 1;j < n - 1; ++j)
        {
            int miCnt = 0, mxCnt = 0;
            for(int i = j - 1;i >= 0; --i)
            {
                if(rating[i] > rating[j]) ++mxCnt;
            }
            for(int k = j + 1;k < n; ++k)
            {
                if(rating[j] > rating[k]) ++miCnt;
            }
            ans += miCnt * mxCnt;
        }
        return ans;
    }
};

     
    3.地下鉄システムの設計(Design Underground System)
    タイトルリンク
    https://leetcode-cn.com/problems/design-underground-system/
    に言及
    テーマと例が長すぎて、具体的にテーマのリンクを見ます
    ヒント:
  •  20000  。
  • 1 <= id, t <= 10^6
  • ， 。
  • 1 <= stationName.length <= 10
  •  10^-5  。

    •  
     
    解題分析
    テーマを手に入れるには、テーマに基づいてシミュレーションすればいいはずです.
    では、どのような過程を考えていますか.まず、IDという人は、ある時間、ある駅に入ります.そして同じようにこの人は、ある時間、ある地下鉄の駅を離れます.
    では、2つの地下鉄の駅を指定して、平均時間(複数のIDがある場合、または1つのIDが何度も歩いている場合、この2つの地下鉄の駅であれば、時間/数回かかる)を求めるように要求します.
    だから上のものによって、私たちは、最初、IDという人を記録して、駅に入って、場所と時間を記録して、そんなに速く探したいなら、unordered_mapとunordered_mapは一番速いです.
    そして誰かが駅を出ると、私たちはすぐにこの人を見つけることができて、駅に入る時間と駅に入る場所があります.
    しかし、私达の后ろで、判断しなければならないのは、2つの地下鉄の駅で、それでは、私达はある人によって駅を出ることができて、私达は急速にこの人を探し当てることができて、駅に入る时间と駅に入る场所、私达はこの时具体的にIDに関心を持っていませんて、具体的な関心は:2つの地下鉄の駅、时间、同じ1、2つの地下鉄の駅が现れた回数です.では、2つの地下鉄の駅名をつなぎ、unordered_を使います.mapとunordered_map.
    では、最後に出力するときは、入力した2つの地下鉄の駅に基づいて、mapの中で探して、その総消費時間/この時です.
    (2つの地下鉄駅の接続は、start+"#"+end)です.
    だからこの問題は、主にmap+シミュレーションでいいです.
     
    ACコード(C++)
    class UndergroundSystem {
public:
    unordered_map enter;
    unordered_map time;
    unordered_map cost;
    unordered_map cnt;

    UndergroundSystem() {
        enter.clear();
        time.clear();
        cost.clear();
        cnt.clear();
    }
    
    void checkIn(int id, string stationName, int t) {
        enter[id] = stationName;
        time[id] = t;
    }
    
    void checkOut(int id, string stationName, int t) {
        string all = enter[id] + "#" + stationName;
        long long c = t - time[id];
        cost[all] += c;
        ++cnt[all];
    }
    
    double getAverageTime(string startStation, string endStation) {
        string all = startStation + "#" + endStation;
        return 1.0 * cost[all] / cnt[all];
    }
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem* obj = new UndergroundSystem();
 * obj->checkIn(id,stationName,t);
 * obj->checkOut(id,stationName,t);
 * double param_3 = obj->getAverageTime(startStation,endStation);
 */

    4.すべての良い文字列を見つける(Find All Good Strings)
    タイトルリンク
    https://leetcode-cn.com/problems/find-all-good-strings/
    に言及
    長さnの文字列s 1とs 2と、文字列evilを2つあげます.良い文字列の数を返してください.
    良い文字列の定義は、その長さはnであり、辞書順はs 1以上であり、辞書順はs 2以下であり、evilをサブ文字列として含まない.
    答えが大きいかもしれませんので、10^9+7の残りの結果を返してください.
    例1:
      ：n = 2, s1 = "aa", s2 = "da", evil = "b"
  ：51 
  ：    25    'a'        ："aa"，"ac"，"ad"，...，"az"。   25    'c'        ："ca"，"cc"，"cd"，...，"cz"。  ，      'd'        ："da"。

    例2:
      ：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
  ：0 
  ：          s1       s2        evil     "leet"   。        。

    ヒント:
  • s1.length == n
  • s2.length == n
  • 1 <= n <= 500
  • 1 <= evil.length <= 50
  • 。

    •  
    解題分析
    難しいですね.この問題こそ、本当に「難しい」です.KMP+DPを組み合わせた.
    この問題の最大の難点は、あるサブストリングを「含まない」文字列がどれだけあるかを計算することです.このサブストリング自体は繰り返し可能であり,これは繰り返しカウントの問題をもたらす.すなわち,すべてのsaからsbまでの文字列がどれだけあるかを計算し,条件に合わない文字列をすべて減算することを考えると,減算の過程で「いくつかのevil列を含む」という状況を考慮しなければならない.
    例えば、含まないサブストリングが「abaab」である場合、「abaab」という文字列には2つの「abaab」が含まれ、2回「減」され、反発原理に基づいて1回返却される必要がある.では、文字列にevil列がいくつあるか/あるかどうかをどのように判断しますか?これがKMPアルゴリズムの範疇です.
    そのためKMPが必要です.
    しかし、従来の文字列アルゴリズムでは、元の文字列を1つのマッチング列でマッチングしていましたが、現在は「1つの」ソース文字列ではなく、多くの文字列があります.一つ一つ列挙すれば、この複雑さは想像しにくいに違いない.
    だからDPを使います.
     
    具体的なコードは中国ランキング4位のhuangyuyang大男のコードです.
     
    ACコード(C++)
    class Solution {
public:
    int nxt[1005];
    void get(string s)
    {
        int i, j, len = s.size();
        nxt[0]=-1;
        for(i=0,j=-1;i s1[i]) {
                                    newk = 1;
                                }
                            }
                            if (l == 0) {
                                if (c > s2[i]) {
                                    continue;
                                } else if (c < s2[i]) {
                                    newl = 1;
                                }
                            }
                            int pos = get(e, j, c);
                            if (pos == e.size()) {
                                continue;
                            }
                            //printf("%c %d %d %d %d
    ", c, i + 1, pos, newk, newl);
                            (f[i + 1][pos][newk][newl] += f[i][j][k][l]) %= MO;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n && j <= e.size() - 1; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 2; l++) {
                    (ans += f[n][j][k][l]) %= MO;
                }
            }
        }
        return ans;
    }
};

    Built-in Shrinkerを使ってデバッグビルドで64k問題を回避する
    Templateテンプレート入門