题解 | #牛牛摇骰子#
牛牛摇骰子
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记录最终答案。