在牛牛面前放着nnn个数,这些数字既有奇数也有偶数,只不过牛牛对奇数情有独钟,他特别想让这些数都变成奇数。 现在牛牛获得了一种能力,他可以执行一种操作:每次选中一个偶数,然后把这些数中与该数相等的数都除以2,例如现在有一个数组为[2,2,3][2,2,3][2,2,3],那么牛牛可以执行一次操作,使得这个数组变为[1,1,3][1,1,3][1,1,3]。 牛牛现在想知道,对于任意的n个数,他最少需要操作多少次,使得这些数都变成奇数?
贪心即可
用<set>去重,将n个数中的偶数存入set,每次取出set中的最大的偶数,取半,判断是否为偶数,是偶数就加入set,set自动去重,直到set为kong</set>
class Solution {
public:
/**
* 返回一个数,代表让这些数都变成奇数的最少的操作次数
* @param n int整型 代表一共有多少数
* @param a int整型vector 代表n个数字的值
* @return int整型
*/
int solve(int n, vector<int>& a) {
// write code here
set<int> s;
for(int i=0;i<n;i++){
if(a[i]%2==0){
s.insert(a[i]);
}
}
int l=0;
while(s.size()){
auto cc = s.end();
--cc;
int pp=*cc;
s.erase(*cc);
l++;
int temp=pp/2;
if(temp%2==0){
s.insert(temp);
}
}
return l;
}
};
京公网安备 11010502036488号