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;
}
};
思路來源
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135486.html
標籤：其他