http://community.topcoder.com/stat?c=problem_statement&pm=12790&rd=15708

这道题只有两个操作,一是加一,二是数组所有元素乘以二,求最少操作次数从全0数组变成目标数组。我的方法是从目标数组反推全0数组,如果有奇数就变成偶数,全偶数就除以二。这个方法是可以过的,就是效率拙计:

import java.util.*;
public class IncrementAndDoubling
{
    public int getMin(int[] A)
    {
        int count = 0;
        int len = A.length;
        while (true)
        {
            boolean done = true;
            for (int i = 0; i < len; i++)
            {
                if (A[i] % 2 == 1)
                {
                    A[i]--;
                    count++;
                }
                if (A[i] != 0)
                    done = false;
            }
            if (done) break;
            for (int i = 0; i < len; i++)
            {
                A[i] = A[i] / 2;
            }
            count++;
        }
        return count;
    }
}

但更好的方法如标程里所介绍,观察到除以2就是移位,0和1的转换。那么最后的结果其实是数组里所有二进制1的个数,加上最长的二进制表示长度。

int getMin(vector<int> desiredArray)
{
    int mx = 1;  // '0' has length 1
    int sum = 0;
    for (int x: desiredArray) {
        int c = 0;
        // extract bits from x:
        while (x > 0) {
            c++;
            sum += x % 2; //the last bit
            x /= 2;
        }
        mx = std::max(mx, c);
        // the number c of bits is wrong for '0', but it doesn't matter
        // because mx is initially set to 1.
    }
    return mx - 1 + sum;
}

  

  

转载于:https://www.cnblogs.com/lautsie/p/3440307.html

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐