java - 通过删除数字来计算最大点的算法

Question

我正在研究这个leetcode 算法，我试图通过 2 天以来多次阅读解释来理解它，但我无法理解程序是如何解决的。

这是问题陈述：

给定一个整数数组 nums，您可以对数组执行操作。

在每个操作中，您选择任何 nums[i] 并将其删除以获得 nums[i] 积分。之后，您必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

你从 0 分开始。返回通过应用此类操作可以获得的最大积分数。

示例 1： 输入：nums = [3, 4, 2] 输出：6 解释：删除 4 获得 4 分，因此 3 也被删除。然后，删除 2 即可获得 2 分。共获得 6 分。

以下是关于如何解决的解释：

算法

对于 nums 的每个唯一值 k 按递增顺序，让我们保持正确的 Avoid 和 using 值，分别代表我们不取或取 k 时的答案。

如果新值 k 与之前的最大值 prev 相邻，那么必须取 k 的答案是（k 的点值）+avoid，而不能取 k 的答案是 max(avoid, using)。同样，如果k与prev不相邻，则必须取k的答案是(k的点值)+max(avoid, using)，不取k的答案是max(avoid, using)。

最后，最佳答案可能会或可能不会使用 nums 中的最大值，因此我们返回 max(avoid, using)。

和相应的Java程序：

public int deleteAndEarn(int[] nums) {
        int[] count = new int[10001];
        for (int x: nums) count[x]++;
        int avoid = 0, using = 0, prev = -1;

        for (int k = 0; k <= 10000; ++k) if (count[k] > 0) {
            int m = Math.max(avoid, using);
            if (k - 1 != prev) {
                using = k * count[k] + m;
                avoid = m;
            } else {
                using = k * count[k] + avoid;
                avoid = m;
            }
            prev = k;
        }
        return Math.max(avoid, using);
    }

我无法理解这里如何使用变量以及它如何解决问题陈述avoid。using

你能帮我理解这一点吗？

标签： javaalgorithm

Answer 1

我在那个页面上解决了这个问题。该算法基于一个非常好的技巧。在应用算法之前先处理输入，很容易解决这个问题。输入被重新组织成桶。

假设您有输入：1 1 2 3 3 2 2 4 4 4

您可以将其重组为

(Two 1s), (Three 2s), ( Two 3s), (Three 4s)

现在根据问题，如果您选择任何存储桶，您应该放弃包含 (bucket-element-value - 1 ) 和 (bucket-element-value + 1 ) 的存储桶，它们实际上是与该存储桶相邻的存储桶。

现在的问题归结为在您无法获得相邻存储桶值的约束条件下，您将如何选择存储桶以获得最大总和？

这很简单 - 当您浏览存储桶时，您可以使用存储桶做两件事。要么避免它，要么使用它。

如果你避免它，你可以达到的最大数量是多少 - 这取决于你对前一个做了什么。

amountWhenAvoided[i] = Math.max( amountWhenAvoided[i-1], amountWhenTaken[i-1] );

如果你使用它，你能达到的最大量是多少？你得到那个桶的价值+当你离开/避开前一个桶时你得到的任何东西。

amountWhenTaken[i] = amountWhenAvoided[i-1] + valueOfBucket[i]

一旦你到达桶的尽头，答案将是：

Math.max( amountWhenTaken[n], amountWhenAvoided[n] )

你可以这样编码：

public int deleteAndEarn( int[] nums ) {
  //reorganize.
  int[] valueOfBucket= new int[10001] //This is the maximum size of the buckets.

  for ( int num : nums ) {
     valueOfBucket[num] += num; //Populate each bucket.
  }

  //Now go through each bucket - remember - a bucket could be empty that's fine.
  int[] amountWhenTaken = new int[n];
  int[] amountWhenAvoided = new int[n];
  amountWhenTaken[0] = 0; //Because there are no buckets to start with - buckets start from 1
  amountWhenAvoided[0] = 0;
  for ( int i = 1; i <= n; i++ ) {
     amountWhenAvoided[i] = Math.max( amountWhenAvoided[i-1], amountWhenTaken[i-1] );
     amountWhenTaken[i] = amountWhenAvoided[i-1] + valueOfBucket[i];
  }
  return Math.max( amountWhenTaken[n], amountWhenAvoided[n] );
}

如果你观察上面的代码，真的不需要用数组来做。因为数组中的当前元素依赖于它的前一个元素，所以我们可以只用两个变量来调用它们avoiding, using 然后第二个 for 循环可以写成：

public int deleteAndEarn( int[] nums ) {
      //reorganize.
      int[] valueOfBucket= new int[10001] //This is the maximum size of the buckets.

      for ( int num : nums ) {
         valueOfBucket[num] += num; //Populate each bucket.
      }

      //Now go through each bucket - remember - a bucket could be empty that's fine.
      int using_prev = 0;
      int avoiding_prev = 0;
      int avoiding_curr = 0;
      int using_curr = 0;
      for ( int i = 1; i <= n; i++ ) {
         avoiding_curr = Math.max( avoiding_prev, using_prev);
         using_curr = avoiding_prev + valueOfBucket[i];
         avoiding_prev = avoiding_curr;
         using_prev = using_curr;
      }
      return Math.max( avoiding_curr, using_curr );
 }