leetcode406. Queue Reconstruction by Height

morgan 發布于2019-08-16 15:42 / 2423人閱讀

摘要：題目要求假設有一組人站成一堆，每個人都記錄下了自己的高度，以及在自己前面有多少個不比自己矮的人?，F在請按照這個信息將這組人放在隊列中正確的位置上并返回。但是這樣解決其實復雜化了問題。即越大，則該同等高度的人一定在另一個同等高度的人后面。

題目要求

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.


Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

假設有一組人站成一堆，每個人都記錄下了自己的高度，以及在自己前面有多少個不比自己矮的人。現在請按照這個信息將這組人放在隊列中正確的位置上并返回。

思路和代碼

剛開始我試圖用分治法來解決，因為每一個小隊列中，高度最矮且站在自己前面的高個最少的人一定位于k位置上。但是這樣解決其實復雜化了問題。

可以從另一個角度來想，首先我們知道，同等高度的人，其相對位置一定是根據k的值從小到大排列的。即k越大，則該同等高度的人一定在另一個同等高度的人后面。如果我們從高到低將人們插入隊列中，可以知道，k的值就該人在當前隊列中的下標，如：

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
首先將其按照h和k排序，得出結果：
[[7,0],[7,1],[6,1],[5,1],[5,0],[5,2],[4,4]]

當前結果隊列為[]
將[7,0]插入下標為0的位置上 結果隊列[[7,0]]
將[7,1]插入下標為1的位置上 結果隊列[[7,0],[7,1]]
將[6,1]插入下標為1的位置上 結果隊列[[7,0],[6,1],[7,1]]
按照這種規則，依次按照順序和k的值將數據插入結果隊列中

代碼如下：

    public int[][] reconstructQueue(int[][] people) {
        int[][] result = new int[people.length][2];
        Arrays.sort(people, new Comparator() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
            
        });
        for(int i = 0 ; i pos; j--) {
                result[j] = result[j - 1];
            }    
            result[pos] = people[i];
        }
        return result;
    }

云服務器 GPU云服務器 Reconstruction 服務器異常406 服務器報406錯誤 Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73653.html

Queue Reconstruction by Height

摘要：題目鏈接的題感覺思路好難寫啊。一直重復到結束。第一遍第二遍第三遍每次最前面的減的是最多的，所以考慮倒過來做這樣減的時候就是碰到之后先減，碰到了，之后是減。又由于減到的時候要倒過來到結果里面，實際上就是把小的查到前面對應位置的過程。 Queue Reconstruction by Height 題目鏈接：https://leetcode.com/problems... greedy的題感...

melody_lql 2019-08-14 17:22 評論0 收藏0
leetcode102. Binary Tree Level Order Traversal

摘要：題目要求對于一棵樹進行序遍歷。水平遍歷即遍歷結束當前行以后再遍歷下一行，并將每行的結果按行填入到數組中返回。利用水平遍歷的話，我們只需要知道當前元素在樹中的高度就可以知道應當插入到那個數組中。題目要求 Given a binary tree, return the level order traversal of its nodes values. (ie, from left to...

Coding01 2019-08-16 12:09 評論0 收藏0
[LeetCode] 490. The Maze (BFS/DFS)

Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...

smartlion 2019-08-16 13:51 評論0 收藏0
[LeetCode] Reconstruct Itinerary

摘要：來自大神的解答，只能膜拜。題目確定了至少有一條的行程不存在分支情況，一定有相同的最終目的地，而且對于多條的行程，要選取字母順序較小的一條。 Problem Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the i...

jubincn 2019-08-14 14:02 評論0 收藏0
[Leetcode] The Skyline Problem 天際線問題

摘要：遍歷時，通過一個堆來得知當前圖形的最高位置。堆頂是所有頂點中最高的點，只要這個點沒被移出堆，說明這個最高的矩形還沒結束。對于左頂點，我們將其加入堆中。 The Skyline Problem A citys skyline is the outer contour of the silhouette formed by all the buildings in that city w...

hidogs 2019-08-14 12:34 評論0 收藏0