Leetcode 1387:将整数按权重排序(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1387:将整数按权重排序(超详细的解法!!!)

in leetcode with 0 comment

我们将整数 x权重 定义为按照下述规则将 x 变成 1 所需要的步数:

比方说,x=3 的权重为 7 。因为 3 需要 7 步变成 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)。

给你三个整数 lohik 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ,如果大于等于 2 个整数有 相同 的权重,那么按照数字自身的数值 升序排序

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意,题目保证对于任意整数 x (lo <= x <= hi) ,它变成 1 所需要的步数是一个 32 位有符号整数。

示例 1:

输入:lo = 12, hi = 15, k = 2
输出:13
解释:12 的权重为 9(12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ,答案是第二个整数也就是 13 。
注意,12 和 13 有相同的权重,所以我们按照它们本身升序排序。14 和 15 同理。

示例 2:

输入:lo = 1, hi = 1, k = 1
输出:1

示例 3:

输入:lo = 7, hi = 11, k = 4
输出:7
解释:区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。

示例 4:

输入:lo = 10, hi = 20, k = 5
输出:13

示例 5:

输入:lo = 1, hi = 1000, k = 777
输出:570

提示:

解题思路

首先不难想到暴力解法,也就是对于每个数字分别计算需要多少步,然后排序取出权重第k大的数即可。

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def cal(x):
            res = 0
            while x != 1:
                if x & 1: x = x * 3 + 1
                else: x //= 2
                res += 1
            return res
            
        return sorted(list(range(lo, hi + 1)), key=lambda x: cal(x))[k - 1]

这个问题由于lohi[1, 1000]内,所以我们完全可以将所有数都算出来,然后查表即可。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses