列表

详情


NC207299. 牛牛摇骰子

描述

一维数轴,初始位置在原点,每次可以选择向左或者向右移动0或3或7或11个单位
N次询问,每次给出一个坐标arr[i],求从0点走到arr[i]需要的最少次数

输入描述

对于20%的数据

对于50%的数据

对于100%的数据

示例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)

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

Python3(3.5.2) 解法, 执行用时: 1582ms, 内存消耗: 16344K, 提交时间: 2020-08-08 13:47:27

#
# 把所有询问的答案按询问顺序放入vector里
# @param arr int整型一维数组 要查询坐标的数组
# @return int整型一维数组
#
class Solution:
    def MinimumTimes(self , arr ):
        step = [3, 7, 11]
        v=[0,3,2,1,2,3,2,1,2,3,2]
        ans = []
        for i in arr:
            if i==2:ans.append(4)
            else:
                cnt=0
                cnt+=i//11
                ans.append(cnt+v[i%11])
        return ans

C++11(clang++ 3.9) 解法, 执行用时: 43ms, 内存消耗: 5636K, 提交时间: 2020-08-09 18:59:27

class Solution
{
	public:
		vector<int> MinimumTimes(vector<int> &arr)
		{
			int a[]={0,3,2,1,2,3,2,1,2,3,2,1};
			vector<int>ans;
			for(int e:arr)
			{
				if(e==2)
				ans.push_back(4);
				else 
				ans.push_back(a[e%11]+e/11);
			}
			return ans;
		}
};

上一题