[プログラマー]デュアル・ユーティリティ・プリアンブル・キューJava

11759 ワード
Problem Solving テキストリンク
[Algo Rhythm🕺💃]
難易度:レベル3

1.質問


質問リンク

|問題の説明


デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.

パラメータとして2つの優先順位キューで実行する演算操作を指定した場合、すべての演算を処理した後、キューが空の場合[0,0]空でない場合、「最値、最上昇値」を返すソルバを実装します.
*挿入された数字のアルファベットIは、大文字I(i)を表します.

|制限

  • 操作は、100000より長い文字列配列である.
  • 操作の要素は、キューが実行する操作を表す.
    -要素はコマンドデータ形式で与えられます.
    -最上位/最上位を削除する操作で複数の最上位/最上位が存在する場合は、1つだけ削除します.
  • 空のキューでデータの削除が要求された場合、この操作は無視されます.

    • |I/O例



    |I/O例説明


    16を挿入すると、最大値が削除されます.[0,0]を返します.空ですから.
    7、5、および-5を挿入して、最大値を削除します.最大値7、最小値5を返します.

    2.アルゴリズムby Yoon


    PriorityQueueで解くこともできますソート、remove、addなど便利な問題をArrayListで解いた.
    ArrayListでも私服の名前を列に並べます

  • ArrayListタイプのキュー変数の作成

  • operation配列でfor文の値を1つずつ検索する
    1.1単行動基準では,インデックスが0のところに文字,1のところに数字が含まれているのでsplitで区別する.

  • 1)文字がIの場合
    indexが1の値をint型に変換しqueueを入れます.

  • 2)文字がDの場合
    queueのsizeが0の場合、計算可能な値がないため続行されます.

  • i)数字が1の場合
    queueのsize-1の値を削除します.
    (ソートキューの最後の値が最大)

  • ii)数字が-1の場合、キュー0の値が削除される.(ソートキューの最初の値が最小値であるため)
    • 1.2キューのサイズが0でない場合は、昇順でキューをソートします.

  • queueのsizeが0の場合、回答[0]と回答[1]に0を入力します.

  • そうでなければ、キューの最大値と最小値をそれぞれ入力します.

  • 答えを返す.

    • 3.ソースコード

    import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        ArrayList<Integer> opQueue = new ArrayList<>();
    
        for(int i = 0; i < operations.length; i++){
            String[] op = operations[i].split(" ");
            
            if(op[0].trim().equals("I")){              // input the number
                opQueue.add(Integer.parseInt(op[1]));
            } else { // only D
                if(opQueue.size() == 0) continue;
                
                if(op[1].trim().equals("1")){          // output the max
                    opQueue.remove(opQueue.size()-1);
                } else if(op[1].trim().equals("-1")){  // output the min
                    opQueue.remove(0);
                }
            }
            if(opQueue.size() != 0) Collections.sort(opQueue);
        }
        
        if(opQueue.size() == 0){
            answer[0] = 0;
            answer[1] = 0;
        }else{
            answer[0] = opQueue.get(opQueue.size()-1);
            answer[1] = opQueue.get(0);
        }
        
        
        
        return answer;
    }
}
    尚シリコンバレー2020マイクロサービス分布式電子商取引プロジェクト「穀粒商城」
    RealtSVGにアニメーションを入れる