原题链接:
https://leetcode.cn/problems/sort-integers-by-the-power-value/

法1 暴搜

基础暴搜的方式 就是按照题意模拟的即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        ans = []
        for x in range(lo,hi + 1):
            w = 0
            t = x
            while x!=1: 
                w = w + 1
                if x%2 == 0:
                    x//=2
                else:
                    x = x * 3 + 1
            ans.append([w,t])
        
        res = sorted(ans,key=lambda x:x[0])

        return res[k-1][1]

法2: 记忆化搜索

注意到每次搜索时其实存在了很多次重复计算
每次f(x)的权值可由下列情况推得

  1. x==1 f(x) = 0
  2. x为偶数时 f(x) = f(x/2) + 1
  3. x为奇数时 f(x) = 3 * f(x) + 1
    可知 f(x)可以直接上
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
        def getKth(self, lo: int, hi: int, k: int) -> int:
            ans = []
            for x in range(lo,hi + 1):
                w = 0
                t = x
                while x!=1: 
                    w = w + 1
                    if x%2 == 0:
                        x//=2
                    else:
                        x = x * 3 + 1
                ans.append([w,t])
            
            res = sorted(ans,key=lambda x:x[0])
            # 一个f(x/2) 或 3 * f(x) 的状态直接+1 得来不需要再进行重复进行 这种方式即为记忆化搜索
            return res[k-1][1]