プログラマーベストアルバム

11925 ワード
プログラマ テキストリンク

ベストアルバム


これはプログラマハッシュカテゴリの3つの問題です.
レベル2を全部解いて3を解くという考えで、この間はレベル3を解いていませんでしたが、思ったほど難しくなくて驚きました.難易度分類の基準は目に見える.😅
mapデータ構造を使用すると、キー:値ペアを生成できます.初めてこの問題を解いたとき、mapもベクトルのように2次元に宣言できることを知らなかった.したがって、各曲はvectorに含まれ、タイプ区分はデータベースを使用するようにcategoryテーブルを作成します.

その後、mapは2次元として使用され、category mapは必要ありません.

に答える


複数の曲を再生するタイプ順を探すためにpriorityqueueを使用した.
  • total timesマップを発表し、各タイプの再生回数を求め、優先キューを作成する.
  • PQのルート値に対応するタイプの最初の2つのインデックスを探します.(あるジャンルの曲があれば1曲)

    • 最終コード

    #include <bits/stdc++.h>
using namespace std;

struct Song{
    int id;
    int playTime;
    Song(int idx,int pt){
        id=idx;
        playTime=pt;
    }
    bool operator<(const Song &s) const {
        if(playTime!=s.playTime) return playTime>s.playTime;
        else return id<s.id;
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    priority_queue<pair<int,string>> PQ;
    map <string,int> total_times;
    map <string,int> ::iterator it;
    map <string,vector<Song>> playList;
    map <string,vector<Song>> :: iterator pit;
    
    for(int i=0;i<genres.size();i++){
       total_times[genres[i]]+=plays[i];
        playList[genres[i]].push_back(Song(i,plays[i]));
    }
    
      for(it=total_times.begin();it!=total_times.end();it++){
        PQ.push(make_pair(it->second,it->first));
    }
    
    
    for(pit=playList.begin();pit!=playList.end();pit++){
        sort(playList[pit->first].begin(),playList[pit->first].end());
    }
   
  
     while(!PQ.empty()){
        string gen = PQ.top().second;
        answer.push_back(playList[gen][0].id);
         if(playList[gen].size()>1) {
            answer.push_back(playList[gen][1].id);
            } 
        PQ.pop();
    }
    return answer;
}
    [トップに戻る](Back Top)ボタンの効果
    AngularJS(7)-表