1387. Sort Integers by The Power Value

题目信息

题号:

1387

难度:

Medium

主题:

动态规划、记忆化、排序

原题:

LeetCode 1387

重点:

幂值是按 Collatz 规则变到 1 的步数;先按幂值升序,再按整数升序,返回第 k 个

题目重述

对正整数 x 反复执行:若为偶数则除以 2,若为奇数则变为 3x+1,直到得到 1。所需步数称为 x 的幂值。

把闭区间 [lo,hi] 内所有整数按幂值升序排序,幂值相同时按整数值升序排序。返回排序后的第 k 个整数,k 从一开始计数。

1 <= lo <= hi <= 1000,1 <= k <= hi-lo+1。

自建示例

幂值相同时使用数值作为次序:

输入:lo = 1, hi = 4, k = 3
输出:4
解释:1、2、3、4 的幂值分别为 0、1、7、2,排序为 [1,2,4,3]。

区间只有一个整数:

输入:lo = 7, hi = 7, k = 1
输出:7
解释:唯一候选直接返回。