1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110  // @Title: 根据身高重建队列 (Queue Reconstruction by Height) // @Author: 15816537946@163.com // @Date: 2019-11-17 17:18:37 // @Runtime: 16 ms // @Memory: 5.9 MB /* * @lc app=leetcode.cn id=406 lang=golang * * [406] 根据身高重建队列 * * https://leetcode-cn.com/problems/queue-reconstruction-by-height/description/ * * algorithms * Medium (62.35%) * Likes: 144 * Dislikes: 0 * Total Accepted: 6.3K * Total Submissions: 10.1K * Testcase Example: '[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]' * * 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 * 编写一个算法来重建这个队列。 * * 注意： * 总人数少于1100人。 * * 示例 * * * 输入: * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] * * 输出: * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] * * */ /* func reconstructQueue(people [][]int) [][]int { if len(people) <=1 { return people } fmt.Println("before ->", people) sort.Sort(persons(people)) fmt.Println("after ->", people) res := make([][]int, 0, len(people)) // 插入函数，把person插入到res[idx]上 insert := func(idx int, person []int) { res = append(res, []int{}) copy(res[idx+1:], res[idx:]) res[idx] = person } for _, v := range people { insert(v[1], v) } fmt.Println(res) return res } type persons [][]int func (p persons) Len() int { return len(p)} // h降序，k升序 func (p persons) Less(i,j int) bool { if p[i][0] == p[j][0] { return p[i][1] < p[j][1] } return p[i][0] > p[j][0] } func (p persons) Swap(i, j int) { p[i], p[j] = p[j], p[i]} */ func reconstructQueue(people [][]int) [][]int { if len(people) <= 1 { return people } sort.Sort((persons(people))) ret := make([][]int, 0) insert := func(idx int, person []int) { ret = append(ret, []int{}) copy(ret[idx+1:], ret[idx:]) ret[idx] = person } for _, v := range people { insert(v[1], v) } return ret } type persons [][]int func (p persons) Len() int { return len(p) } func (p persons) Less(i, j int) bool { if p[i][0] == p[j][0] { return p[i][1] < p[j][1] } return p[i][0] > p[j][0] } func (p persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }