Queue Reconstruction by Height

melody_lql 发布于2019-08-14 17:22 / 1083人阅读

摘要：题目链接的题感觉思路好难写啊。一直重复到结束。第一遍第二遍第三遍每次最前面的减的是最多的，所以考虑倒过来做这样减的时候就是碰到之后先减，碰到了，之后是减。又由于减到的时候要倒过来到结果里面，实际上就是把小的查到前面对应位置的过程。

Queue Reconstruction by Height

题目链接：https://leetcode.com/problems...

greedy的题感觉思路好难写啊。
首先肯定是要排序，首先想到的思路是先按h再按k排序，h从低到高，k从高到低，原因是第一步想先把是0的yi 个一个放进结果里，然后把前面的k都--，第二遍还是找k = 0的。一直重复到结束。

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

第一遍：

result: [[5, 0], [7, 0]]

aux: [[4, 2], [5, 0], [6, 0], [7, 0]]

第二遍:

result: [[5, 0], [7, 0], [5, 2], [6, 1]]

aux: [[4, 0], [7, 0]]

第三遍：

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

aux: []

每次最前面的减的是最多的，所以考虑倒过来做：
[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
这样减的时候就是碰到[7, 0]之后[7, 1], [6, 1]先减1，碰到了[5, 0]，之后[5, 2], [4, 4]是减2。又由于减到0的时候要倒过来append到结果里面，实际上就是把h小的查到前面对应位置的过程。discussion给的解法实在太厉害了，真想不出来。

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if(people.length == 0) return people;
        
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List result = new ArrayList();
        for(int[] person : people) {
            result.add(person[1], person);
        }
        return result.toArray(new int[result.size()][2]);
    }
}

云服务器私有云 Reconstruction height() height queue()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66589.html

leetcode406. Queue Reconstruction by Height

摘要：题目要求假设有一组人站成一堆，每个人都记录下了自己的高度，以及在自己前面有多少个不比自己矮的人。现在请按照这个信息将这组人放在队列中正确的位置上并返回。但是这样解决其实复杂化了问题。即越大，则该同等高度的人一定在另一个同等高度的人后面。题目要求 Suppose you have a random list of people standing in a queue. Each per...

morgan 2019-08-16 15:42 评论0 收藏0
332. Reconstruct Itinerary

摘要：题目解答都是用来解，一个用一个用来实现深度优先搜索，搜索到一个城市只是的时候即没有出度的时候，把这个记入中去，因为它肯定是最后到达的城市，然后依次向前类推的要求在存入的时候就用先存好先进去的说明是出发城市，那么最先出发的城市最后出来题目：Given a list of airline tickets represented by pairs of departure and arri...

greatwhole 2019-08-14 14:17 评论0 收藏0
TensorFlow实战：Neural Style

摘要：作者使用实现了，并将其开源放在了上。在年的两个问题上分别取得了第一名和第二名。的获取方式是第层，形状为，的获取方式是第层，形状为。每个卷积核可以看做是图形的一种特征抽取。相关性的描述使用余弦相似性，而余弦相似性又正比于两种特征的点积。 showImg(https://segmentfault.com/img/bVPmNA?w=1056&h=707); Neural Style是一个非常...

stackfing 2019-07-25 12:01 评论0 收藏0