1387. 将整数按权重排序（递归 +记忆化+排序）

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

如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

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

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

文章目录

• 思路
• 解题方法
• Code

思路

计算每个数的权重，递归记忆化，然后按照权重排序，相同时按照数本身排.

解题方法

数据范围不大，递归+记忆化就可以

Code

class Solution {
private : 
struct node {
    int x ; 
    int weight;
} ; 
public:

    unordered_map<int,int> memo ; 
    static bool cmp(const node &x , const  node &y){
        if(x.weight != y.weight) {
            return x.weight < y.weight ; 
        }else{
            return x.x < y.x ; 
        }
    }
    int dfs(int x ) {
        if(x <=1 ) return 0 ; 
        if(x ==2 ) return 1 ; 
        if(memo.count(x)) {
            return memo[x] ; 
        }
        // 偶数
        if( x%2 == 0) {
            return memo[x] = dfs(x/2) +1  ;
        }else{
            return memo[x] = dfs(3*x+1) +1 ; 
        }
    }
    int getKth(int lo, int hi, int k) {
        vector<node> r ; 
        for(int i = lo ; i<=hi ; i++) {
            int w = dfs(i) ; 
            r.push_back( {i,w}) ; 
        }  
        sort(r.begin() ,r.end(),cmp) ; 


        return r[k-1].x  ;   

    }
};