leetcode1558題解【貪心】
- 2020 年 9 月 27 日
- 筆記
- +CodeForces, +貪心
leetcode1558.得到目標數組的最少函數調用次數
演算法
貪心
時間複雜度O(nlogN)，N為數組中最大的那個數。
1.題意就是給定一個函數，該函數有兩種功能，一種就是將數組中的所有數同乘以2，另一種就是將數組中的某個數加1。給定一個數組nums，讓你將初始值全為0的數組arr通過調用給定的函數來變成nums。問最少調用次數。
2.剛開始模擬了一番，但因為考慮的方法不對(至於哪裡不對呢，就是一開始我就把數組的值都加1了一遍，然後再同乘以2，最後再一個個補1，這麼做顯然不利於減少次數。至於當時為啥這麼想，估計是腦子抽了)，最終無果。
3.接下來步入正題，我們可以這麼想。當初始值都為0時，我們可以使部分值首先加1(即最終要變成的較大的值)，讓它們首先乘以2，不斷乘，乘到一定程度再處理。但這麼做有個問題，讓哪部分值先變成1呢？還有就是乘到哪種程度呢？
這個地方的確是個難點，不太容易想。如果直接模擬的話不太容易。
數組中誰乘2的次數最多，當然是目標值最大的那個數乘的次數最多，其他目標值較小的就相對來說乘的次數較少。我們可以貪心地讓那些乘的次數較少的包含在乘的次數最多裡面，至於它具體是怎麼乘的，我們不用考慮太多，這就是貪心演算法的好處。
如何計算每個數最終乘的次數，我們可以分情況討論：
為了方便，我們可以從目標值向初始值變化。
-
對於奇數，可以先讓其變為偶數(變為偶數這個過程即減1，這個需要單獨記錄)，然後再除2，每除一次就記錄一次。
-
對於偶數，就除2，每除一次就記錄一次。可能除著除著就變成奇數了，比如250，這時候就執行上一步。
最終，數組中的值就都變成0了。
4.總之，這道題的基本思路就是求出目標數組中最大值變成0需要除2的次數，以及該數組中每個數需要減1的次數(什麼時候減，就是為奇數的時候減)，二者相加即為答案。
C++程式碼
class Solution {
public:
int minOperations(vector<int>& nums) {
int len = nums.size();
int res = 0;
int mx = 0; //記錄乘以2的最大次數
for(int i = 0; i < len; i++){
int cnt = 0;
while(nums[i]){
if(nums[i] % 2 == 1){
nums[i] -= 1; //把它變成偶數
res++;
}
if(nums[i] > 0){
nums[i] /= 2;
++cnt;
}
}
mx = max(mx, cnt);
}
res += mx;
return res;
}
};
