1387. 将整数按权重排序

Powered by:NEFU AB-IN

Link

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 个数。
  注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。

• 思路

  • 正常DFS，之后排序即可
  • 优化:
    • 可以观察到奇数x需变成3x+1，也就是肯定是偶数，那么偶数肯定就需要除以2，那么就可以融合成一步完成
    • 另外，当生成了某数的权重后，可以利用之前的结果，也就是进行记忆化搜索
    • 不懂为什么优化了之后慢了。。

• 代码

  无剪枝

  // ---------------------
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  static int IOS = []() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      return 0;
  }();
  
  class Solution
  {
    public:
      int dfs(int x)
      {
          if (x == 1)
              return 0;
          if (x & 1)
              return 1 + dfs(3 * x + 1);
          else
              return 1 + dfs(x / 2);
      }
  
      int getKth(int lo, int hi, int k)
      {
          vector<PII> ans;
          for (int i = lo; i <= hi; ++i)
          {
              ans.push_back({dfs(i), i});
          }
          sort(ans.begin(), ans.end());
          return ans[k - 1].second;
      }
  };
  
  #undef int
  // ---------------------
  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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44

  ---

  优化

  // ---------------------
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  static int IOS = []() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      return 0;
  }();
  
  class Solution
  {
  public:
      unordered_map<int, int> mp;
      int dfs(int x)
      {
          if(mp.count(x)) return mp[x];
          if (x == 1)
              return 0;
          if (x & 1)
              return mp[x] = 2 + dfs((3 * x + 1) / 2);
          else
              return mp[x] = 1 + dfs(x / 2);
      }
  
      int getKth(int lo, int hi, int k)
      {
          vector<PII> ans;
          for (int i = lo; i <= hi; ++i)
          {
              ans.push_back({dfs(i), i});
          }
          sort(ans.begin(), ans.end());
          return ans[k - 1].second;
      }
  };
  
  #undef int
  // ---------------------
  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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46