【LeetCode】406 and 744

406.根据身高重建队列

解法：排序+插入
题目描述：整数对 (h, k) 表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。
套路：一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。
在本题目中，我首先对数对进行排序，按照数对的元素 1 降序排序，按照数对的元素 2 升序排序。原因是，按照元素 1 进行降序排序，对于每个元素，在其之前的元素的个数，就是大于等于他的元素的数量，而按照第二个元素正向排序，我们希望 k 大的尽量在后面，减少插入操作的次数。
参考题解

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        res = []
        people = sorted(people, key = lambda x: (-x[0], x[1]))
        for p in people:
            if len(res) <= p[1]:
                res.append(p)
            elif len(res) > p[1]:
                res.insert(p[1], p)
        return res

重要方法：
List.insert(position, list)
sorted函数多关键词排序

744.寻找比目标字母大的最小字母

解法：记录存在的字母/扫描
利用集合记录存在的字母，再判断是否存在target大的字母
扫描是同样的思想。
解法2：二分查找

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        length = len(letters)
        l, h = 0, length - 1
        while l <= h:
            m = l + (h - l)//2
            if letters[m] > target:
                h = m - 1
            else:
                l = m + 1
        return letters[l % length]

最后

以上就是陶醉芹菜为你收集整理的【LeetCode】406 and 744的全部内容，希望文章能够帮你解决【LeetCode】406 and 744所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。