企業(yè)logo設計規(guī)范廣州百度快速優(yōu)化排名
1. 題目鏈接:740. 刪除并獲得點數(shù)
2. 題目描述:
給你一個整數(shù)數(shù)組
nums
,你可以對它進行一些操作。每次操作中,選擇任意一個
nums[i]
,刪除它并獲得nums[i]
的點數(shù)。之后,你必須刪除 所有 等于nums[i] - 1
和nums[i] + 1
的元素。開始你擁有
0
個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。示例 1:
輸入:nums = [3,4,2] 輸出:6 解釋: 刪除 4 獲得 4 個點數(shù),因此 3 也被刪除。 之后,刪除 2 獲得 2 個點數(shù)??偣搏@得 6 個點數(shù)。
示例 2:
輸入:nums = [2,2,3,3,3,4] 輸出:9 解釋: 刪除 3 獲得 3 個點數(shù),接著要刪除兩個 2 和 4 。 之后,再次刪除 3 獲得 3 個點數(shù),再次刪除 3 獲得 3 個點數(shù)。 總共獲得 9 個點數(shù)。
提示:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
3. 解法(動態(tài)規(guī)劃):
3.1 算法思路:
- 定義一個常量
N
,表示數(shù)組的最大值加1
。這里假設輸入數(shù)組nums
中的元素都是非負整數(shù),并且小于等于N-1
。 - 創(chuàng)建一個長度為N的整數(shù)數(shù)組
arr
,并初始化為0
。這個數(shù)組用于存儲每個元素出現(xiàn)的次數(shù)。 - 遍歷輸入數(shù)組
nums
,將每個元素的值累加到對應的arr
數(shù)組位置上。這樣可以統(tǒng)計每個元素出現(xiàn)的次數(shù)。 - 創(chuàng)建一個長度為N的整數(shù)向量
f
,用于存儲動態(tài)規(guī)劃的狀態(tài)。這個向量f[i]
表示在考慮前i個元素時可以獲得的最大收益。 - 創(chuàng)建一個引用
g
,指向向量f
,以便在后續(xù)計算中使用。 - 使用循環(huán)迭代計算狀態(tài)轉(zhuǎn)移方程。從i=1開始,依次計算f[i]和g[i]的值。
f[i] = g[i - 1] + arr[i]
:表示在考慮前i個元素時,可以選擇當前元素或者不選擇當前元素。g[i] = max(f[i - 1], g[i - 1])
:表示在考慮前i個元素時,可以選擇當前元素或者不選擇當前元素。
- 返回最終結(jié)果,即最大收益??梢酝ㄟ^比較
f[N - 1]
和g[N - 1]
的值來得到最大收益。
3.2 C++算法代碼:
class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001; // 定義一個常量N,表示數(shù)組的最大值加1int arr[N] = {0}; // 創(chuàng)建一個長度為N的整數(shù)數(shù)組arr,并初始化為0for (auto x : nums) arr[x] += x; // 遍歷輸入數(shù)組nums,將每個元素的值累加到對應的arr數(shù)組位置上vector<int> f(N); // 創(chuàng)建一個長度為N的整數(shù)向量f,用于存儲動態(tài)規(guī)劃的狀態(tài)auto g = f; // 創(chuàng)建一個引用g,指向向量f,以便在后續(xù)計算中使用for (int i = 1; i < N; i++) {f[i] = g[i - 1] + arr[i]; // 更新狀態(tài)轉(zhuǎn)移方程,計算當前位置的最大收益g[i] = max(f[i - 1], g[i - 1]); // 更新狀態(tài)轉(zhuǎn)移方程,計算當前位置的最大收益(不選擇當前元素)}return max(f[N - 1], g[N - 1]); // 返回最終結(jié)果,即最大收益}
};