LeetCode 1387. Sort Integers by The Power Value

, , , , ,

Question

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

  • if x is even then x = x / 2
  • if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Solution

题目对于奇数和偶数计算的方式不同，但是可以用递归加上memo实现。但是这里不是动态规划，因为这里没有涉及到求最小最大，保留memo是为了多次调用可能会有相同的数，这样直接返回值即可。计算出个数之后，新建类并且使用自定义排序。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Data {
        int num;
        int count;
        
        public Data(int n, int c) {
            num = n;
            count = c;
        }
    } 
    public int getKth(int lo, int hi, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Data> list = new ArrayList<>(hi - lo + 1);
        for (int i = 0; i < hi - lo + 1; i++) {
            list.add(new Data(lo + i, ways(lo + i, map)));
        }
        Collections.sort(list, (a, b) -> a.count - b.count);
        return list.get(k - 1).num;
    }
    
    public int ways(int num, HashMap<Integer, Integer> map) {
        if (num == 1) return 0;
        if (map.get(num) != null) return map.get(num);
        int res = 0;
        if (num % 2 == 0) {
            res = 1 + ways(num / 2, map);   
        } else {
            res = 1 + ways(3 * num + 1, map);     
        }
        map.put(num, res);
        return res;
    }