在牛牛面前放着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; } };