我在解決這個動態規劃問題的方法中缺少什么？（Leetcode740.洗掉并賺取）

我正在嘗試了解如何解決Leetcode 問題 #740：洗掉和賺取

我最近在面試前評估中遇到了這個問題，但無法在規定的時間內完成。我今天一直在研究它，試圖將我的頭環繞在它周圍，但此刻我有點繞圈子。我查看了大量資源、視頻、教程等，但我使用的是 vanilla JS，很多指南都是我目前不知道的 C 、Python 或 Typescript。（我計劃至少學習 Python 和 Typescript，但我目前正在使用我目前的知識集）。這導致了困惑和沮喪，因為示例 python/c 代碼等的準確翻譯仍然讓我感到困惑。

問題如下：

給定一個整數陣列 nums。您希望通過多次執行以下操作來最大化獲得的分數：

選擇任何nums[i]并洗掉它以獲得nums[i]積分。之后，您必須洗掉每個等于 的nums[i] - 1元素和每個等于 的元素nums[i] 1。

通過多次應用上述操作，回傳您可以獲得的最大積分數。

示例 1

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

示例 2

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

到目前為止我所擁有的：

const deleteAndEarn = (nums) => {
  if(!nums || nums.length === 0) return 0;
  if(nums.length === 1) return nums[0];
  if(nums.length === 2) return nums[1];
  
  const freq = makeDict(nums);
  let prevNum
  let [keep, avoid] = [0, 0];
  for(const num of [...Object.keys(freq)].sort()){
    let max = Math.max(keep, avoid)
    if(parseInt(num) - 1 !== prevNum){
      [keep, avoid] = [
        (freq[num] * parseInt(num))   max,
        max
      ]
    }else{
      [keep, avoid] = [
        parseInt(num) * freq[num]   avoid,
        max
      ]
    }
    prevNum = parseInt(num)
  }
  
  return Math.max(keep, avoid)
};

const makeDict = (nums) => {
  const dict = {}
  for(const num of nums){
    dict[num] = !!dict[num] ? dict[num]   : 1
  }
    return dict
}

提供 Python 解決方案

這就是我試圖對我的代碼進行建模的原因，但我實際上并不了解 Python 語法，所以我確定我遺漏了一些東西。

class Solution(object):
    def deleteAndEarn(self, nums):
        count = collections.Counter(nums)
        prev = None
        avoid = using = 0
        for k in sorted(count):
            if k - 1 != prev:
                avoid, using = max(avoid, using), k * count[k]   max(avoid, using)
            else:
                avoid, using = max(avoid, using), k * count[k]   avoid
            prev = k
        return max(avoid, using)

我真的不明白為什么這段代碼不起作用，我什至一步一步地運行示例案例。請幫助我了解如何執行此操作，以便我可以找到作業！

非常感謝

uj5u.com熱心網友回復：

我想到了！問題是雙重的。

錯誤一號

首先，感謝David Eisenstat 發現了我makeDict()函式中的錯誤。

不正確的代碼行如下：

dict[num] = !!dict[num] ? dict[num]   : 1

而正確的語法如下：

dict[num] = !!dict[num] ?   dict[num] : 1

或者

dict[num] = !!dict[num] ? dict[num]   1 : 1

問題來自后綴與前綴增量運算子在 Javascript 中的作業方式。

來自 MDN 檔案：

如果使用后綴，在運算元之后使用運算子（例如，x ），則遞增運算子遞增并回傳遞增前的值。

如果使用前綴，在運算元之前帶有運算子（例如， x），則遞增運算子遞增并回傳遞增后的值。

錯誤二

第二個問題來自我最初的保護條款。

if(nums.length === 2) return nums[1];

我認為這是我一開始對提供的陣列進行排序時的殘余，但即使這樣自動選擇最后一個元素也沒有任何意義。我洗掉了這一行，結合對之前makeDict()功能的調整，代碼通過了所有提供的測驗。

下面提供了我的作業解決方案。對有關如何改進代碼的可讀性或效率的任何建議持開放態度。

感謝幫助！

const deleteAndEarn = (nums) => {
  if(!nums || nums.length === 0) return 0;
  if(nums.length === 1) return nums[0];
  
  const freq = makeDict(nums);
  let prevNum
  let [keep, avoid] = [0, 0];
  
  for(const num of Object.keys(freq)){
    let max = Math.max(keep, avoid)
    if(parseInt(num) - 1 !== prevNum){
      [keep, avoid] = [
        (freq[num] * parseInt(num))   max,
        max
      ]
    }else{
      [keep, avoid] = [
        parseInt(num) * freq[num]   avoid,
        max
      ]
    }
    prevNum = parseInt(num)
  }
  
  return Math.max(keep, avoid)
};

const makeDict = (nums) => {
  const dict = {}
  for(const num of nums){
    dict[num] = !!dict[num] ?   dict[num] : 1
  }
    return dict
}

uj5u.com熱心網友回復：

您現有代碼中的一個錯誤是

[...Object.keys(freq)].sort()

不會按順序對數字進行排序 - 請參閱此處。

另一個錯誤是您的演算法沒有任何回溯 - 您不想在給定時貪婪地選擇 3 [3, 4, 4, 4]。

我認為解決這個問題的最好方法是理解輸入中只需要考慮連續數字的字串。例如，給定

[1, 2, 3, 6, 7, 8]

將其分成所有連續的整數字串：

[1, 2, 3]
[6, 7, 8]

然后為每個序列決定最佳選擇。

您不能只選擇序列中的所有奇數或所有偶數，因為這將無法選擇，例如 1 和 4 [1, 1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4]。我能看到的最好方法是使用遞回函式：檢查序列時getBestSequenceSum，以 N 開頭，回傳最大值：

• N 加總和getBestSequenceSum(seq.slice(2))（跳過序列中的下一項），或
• 總和getBestSequenceSum(seq.slice(1))（使用序列中的下一項）

充分覆寫所有可能性。

可能有更高效的演算法，但這個相對簡單直觀。

const getBestSequenceSum = (seq) => {
  if (seq.length === 0) return 0;
  // Include the lowest value in the sequence, or not?
  const sumOfLowestVal = seq[0].num * seq[0].count;
  
  return Math.max(
    sumOfLowestVal   getBestSequenceSum(seq.slice(2)),
    getBestSequenceSum(seq.slice(1))
  );
};
const deleteAndEarn = (nums) => {
  nums.sort((a, b) => a - b);
  let lastNum;
  const sequences = [];
  for (const num of nums) {
    if (num !== lastNum && num !== lastNum   1) {
      // New sequence
      sequences.push([]);
    }
    const thisSequence = sequences[sequences.length - 1];
    if (num !== lastNum) {
      thisSequence.push({ num, count: 0 });
    }
    thisSequence[thisSequence.length - 1].count  ;
    lastNum = num;
  }
  return sequences.reduce((a, seq) => a   getBestSequenceSum(seq), 0);
};

console.log(deleteAndEarn([10,8,4,2,1,3,4,8,2,9,10,4,8,5,9,1,5,1,6,8,1,1,6,7,8,9,1,7,6,8,4,5,4,1,5,9,8,6,10,6,4,3,8,4,10,8,8,10,6,4,4,4,9,6,9,10,7,1,5,3,4,4,8,1,1,2,1,4,1,1,4,9,4,7,1,5,1,10,3,5,10,3,10,2,1,10,4,1,1,4,1,2,10,9,7,10,1,2,7,5]));

The number of calculations could be reduced somewhat by changing the { num, count: 0 } objects to a single number instead, but that would be more difficult to understand when reading the code.

You could also reduce the number of calculations by caching already-optimized sequences so as not to recalculate them multiple times, but that'd make the code significantly longer.

標籤：javascript 算法 动态规划

上一篇：在C 類中使用遞回-傳遞自己的資料成員

下一篇：給定字串表示確定矩陣維數的演算法