牛牛摇骰子

[编程题]牛牛摇骰子

热度指数：172 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一维数轴，初始位置在原点，每次可以选择向左或者向右移动0或3或7或11个单位

N次询问，每次给出一个坐标arr[i]，求从0点走到arr[i]需要的最少次数

示例1

输入

[1,4,14]

输出

[3,2,2]

说明

从0到1最少需要3次(0->7->4->1)（走法不唯一，比如0->11->4->1也只需要3次）
从0到4最少需要2次(0->7->4)
从0到14最少需要2次(0->7->14)

示例2

输入

[6,25]

输出

[2,3]

说明

从0到6最少需要2次(0->3->6)
从0到25最少需要3次(0->7->18->25)

备注:

对于20%的数据 $1\leq N\leq 5,1\leq arr[i]\leq 1e5$

对于50%的数据 $1\leq N\leq 1e5,1\leq arr[i]\leq 5e5$

对于100%的数据 $1\leq N\leq 1e5,1\leq arr[i]\leq 1e9$

算法知识视频讲解

QSheng

发表于 2021-07-22 14:50:22

class Solution: def MinimumTimes(self , arr ): """ 找规律 0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3 展开全文

牛客313925129号

发表于 2021-09-13 16:59:32

题意理解对于一维数轴上的一个数，下一步可以加3、7、11，也可以减3、7、11，经过一系列的加减操作后得到目标数值arr[i]，我们要使做的加减操作的次数尽可能少。方法一用time[i]记录得到i需要最少的加减操作的次数。我们要得到数值i，可以先得到数值j，再加上i-j就可以了。此时，得到i的展开全文