[2019ココ冬季実習]Q 05ホテルの部屋を割り当てる(JAVA)

7408 ワード
アルゴリズム#アルゴリズム# コーディングテスト ProblemSolving テキストリンク
質問する
説明:
これは正確性と効率テストでそれぞれ得点する問題です.
スノータウンでホテルを経営しているスカフィーは、ホテルに泊まりたいお客様のために部屋を手配したいと思っています.ホテルにはk部屋があり、1号室からk号室まで番号がついています.最初はすべての部屋が空いていましたが、Skypeは以下のルールでお客様の部屋を手配したいと思っています.
  • 申請ごとに部屋を手配する.
  • 宿泊したい部屋番号をお客様から提出されました.
  • お客様が希望する部屋が空いている場合は、すぐに手配してください.
  • お客様が希望する部屋ができたら、希望する部屋より番号が大きく、空き部屋の中で一番小さい部屋を手配します.
  • 例えば10室あり、お客様が希望する部屋番号が順番[1,3,4,1,3,1,1]であれば、以下のように部屋を割り当てる.
    • ご希望のお部屋番号は113344123516です
    部屋総数kとお客様が希望する部屋番号を順番に並べた部屋番号numberをパラメータとして指定した場合、solution関数を完了し、各お客様に割り当てられた部屋番号を順番に並べて返します.
    せいげんじょうけん
  • kは1以上1012以下の自然水です.
  • room number配列の大きさは1または20万以下である.
  • room number配列の各要素の値はkより大きい自然数である.
  • room number配列は、すべてのお客様が部屋を割り当てることができる場合にのみ入力されます.
  • 例えば、k=5、room number=[5,5]は部屋を割り当てることができないお客様を招くため、入力として使用できません.
    • I/O例
    kroom_numberresult10[1,3,4,1,3,1][1,3,4,2,5,6]
    に答える
    説明:
  • ・room_number順次探索し、部屋を手配し、貯まるanswer
  • 割り当てられた部屋の情報は、HashMap人allocatedエ<현재 방, 다음 방>形態で格納される.
  • 空室であれば割り当てroomNumber
  • 寒い部屋なら次の部屋が空く前に再帰コールallocateRoom()部屋の手配.
    • HashSetだけでは効率的に通れない問題です.そこでこの人の探索を使おうかと悩んだが、解けず、最終的には探索を通じてHashMapを使おうとした.
    コード#コード#
    import java.util.*;

class Solution {

    private static Map<Long, Long> allocated = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        ArrayList<Long> answer = new ArrayList<>();
        for (long roomNumber : room_number) {
            long result = allocateRoom(roomNumber);
            allocated.put(result, result + 1);
            answer.add(result);
        }
        return answer.stream().mapToLong(Long::longValue).toArray();
    }

    private long allocateRoom(long roomNumber) {
        if (allocated.get(roomNumber) == null) return roomNumber;
        allocated.put(roomNumber, allocateRoom(allocated.get(roomNumber)));
        return allocated.get(roomNumber);
    }
}
    リファレンス
    [2019ココア開発者冬季便利]JAVAにホテルの部屋を割り当てる
    Android開発携帯電話(サムスン)写真アプリ写真回転問題解決方法
    アルゴリズム#アルゴリズム#