题解 | #牛牛摇骰子#

牛牛摇骰子

http://www.nowcoder.com/practice/f9e26ad67525493bab009c66c5ad36fe

题意理解

对于一维数轴上的一个数,下一步可以加3、7、11,也可以减3、7、11,经过一系列的加减操作后得到目标数值arr[i],我们要使做的加减操作的次数尽可能少。

方法一

用time[i]记录得到i需要最少的加减操作的次数。
我们要得到数值i,可以先得到数值j,再加上i-j就可以了。此时,得到i的操作数time[i],就等于time[j]加上time[i-j]。示意图如下:
图片说明

对于j的范围,考虑到对称性,只要在1~i/2之间即可。在求time[i]的时候,要求time[1]~time[i-1]已知,这是一个动态规划的过程。

再看题目中的数值要求范围,当目标数值i较大时,time数组会过大并报错,所以考虑将所有目标数值尽可能减小。当i较大时,肯定是先不断地加11所需的操作次数最少,这里用到了贪心的思想,得到目标数值i需要的操作数time[i]就等于加11的次数k再加上time[i-11*k]。我们这里设定加11的次数为max(0,i/11-1)。

最后的任务就是设定初始值,从time[1]~time[11]。

具体代码如下:

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        int len = arr.size(), maxm = 0;
        int time[101];//记录得到目标数值需要的操作数
        vector<int> ans;//记录最终答案
        //设定初始值
        time[1] = 3; time[2] = 4; time[3] = 1;
        time[4] = 2; time[5] = 3; time[6] = 2;
        time[7] = 1; time[8] = 2; time[9] = 3;
        time[10] = 2; time[11] = 1; 

        for (int i=0;i<len;i++)
        {
            //把较大的arr[i]缩小。
            ans.push_back(max(0,arr[i]/11 - 1));//先记录下加11的操作次数
            arr[i] = arr[i] - ans[i]*11;
            if (arr[i] > maxm) maxm = arr[i];
        }
        //一次性求解所有的time,避免重复计算。
        for (int i=12;i<=maxm;i++)
        {
            time[i] = 1000;
            for (int j=1;j<=i/2;j++)
            {
                if (time[j]+time[i-j]<time[i]) time[i] = time[j] + time[i-j];
            }
        }
        //用加11的次数+得到缩小后目标数值的操作次数
        for (int i=0;i<len;i++)
        {
            ans[i] += time[arr[i]];
        }
        return ans;
    }
};

时间复杂度:。该方法使用了一次二重循环,但是内循环的maxm已被缩小至常数。
空间复杂度:。创建了一个数组ans记录最终答案。

方法二

既然当目标数值较大时,我们总是优先使用加11操作,那么可以考虑解中是否存在一定的周期性规律。通过方法一的输出,我们可以发现从12开始,每11个数字它们对应的输出为一个周期,其中每个目标数值i对应的输出为i/11加上一个固定值,该固定值根据i%11的不同而不同。

具体代码如下;

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        int len = arr.size(), maxm = 0;
        int time[12];
        vector<int> ans;//记录最终答案
        //设定初始值
        time[1] = 3; time[2] = 4; time[3] = 1;
        time[4] = 2; time[5] = 3; time[6] = 2;
        time[7] = 1; time[8] = 2; time[9] = 3;
        time[10] = 2; time[11] = 1; 

        for (int i=0;i<len;i++)
        {
            if (arr[i]<12) ans.push_back(time[arr[i]]);
            else
            {
                //把较大的arr[i]缩小。
                ans.push_back(max(0,arr[i]/11));
                arr[i] = arr[i] - ans[i]*11;
                int l = arr[i] % 11;
                //根据取余结果加上固定值
                if (l==1 || l==5 || l==9) ans[i] += 3;
                else if (l==2 || l==4 || l==6 || l==8 || l==10) ans[i] += 2;
                else if (l==3 || l==7) ans[i]++;
            }
        }
        //用加11的次数+得到缩小后目标数值的操作次数
        return ans;
    }
};

时间复杂度:。该方法只使用了一层for循环。
空间复杂度:。创建了一个数组ans记录最终答案。

全部评论

相关推荐

勇敢的联想人前程似锦:如果我是你,身体素质好我会去参军,然后走士兵计划考研211只需要200多分。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务