首页 > 试题广场 >

牛牛摇骰子

[编程题]牛牛摇骰子
  • 热度指数: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%的数据

对于50%的数据

对于100%的数据

1. 用动态规划,结果内存爆了
def solve_2(self, arr):
    # dp_init = self.__solve_table(100)
    dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3]
    max_num = max(arr)
    dp = [0 for i in range(max_num + 1)]

    # 初始化
    for i in range(1, 12):
        dp[i] = dp_init[i]

    # 动态转移方程
    # dp[i] = min(dp[i-11], dp[i-7], dp[i-3]) + 1
    for i in range(12, max_num + 1):
        dp[i] = min(dp[i - 11], dp[i - 7], dp[i - 3]) + 1

    rnt = list()
    for i in arr:
        rnt.append(dp[i])
    return rnt

2. 改成循环数组,还是动态规划,结果超时了。。
def solve_3(self, arr):
    # dp_init = self.__solve_table(100)
    dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3]
    max_num = max(arr)
    dp = [0 for i in range(15)]

    # 初始化
    middle = dict()
    for i in range(1, 12):
        dp[i] = dp_init[i]
        if i in arr:
            middle[i] = dp[int(i % 12)]

    # 动态转移方程 + 循环数组
    # dp[i] = min(dp[i-11], dp[i-7], dp[i-3]) + 1
    j, a, b, c = 0, 1, 5, 9
    arr_set = set(arr)
    for i in range(12, max_num + 1):
        # j = int(i % 12)
        # dp[j] = min(dp[j - 11], dp[j - 7], dp[j - 3]) + 1
        # dp[j] = min(dp[int((i - 11) % 12)], dp[int((i - 7) % 12)], dp[int((i - 3) % 12)]) + 1
        dp[j] = min(dp[a], dp[b], dp[c]) + 1
        if i in arr_set:
            middle[i] = dp[j]
        j, a, b, c = int((j + 1) % 12), int((a + 1) % 12), int((b + 1) % 12), int((c + 1) % 12)

    rnt = list()
    for i in arr:
        rnt.append(middle[i])
    return rnt

3. 最后把前100个答案都打印出来,找规律,结果就过了。。
def solve_4(self, arr):
    """
     找规律
     0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1,
        4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2,
        5, 4, 3, 4, 5, 4, 3, 4, 5, 4, 3,
        6, 5, 4, 5, 6, 5, 4, 5, 6, 5, 4,
        7, 6, 5, 6, 7, 6, 5, 6, 7, 6, 5,
        8, 7, 6, 7, 8, 7, 6, 7, 8, 7, 6,
        9, 8, 7, 8, 9, 8, 7, 8, 9, 8, 7
    """
    # dp_init = self.__solve_table(100)
    dp_init = [0, 3, 4, 1, 2, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2, 5, 4, 3]
    rnt = list()
    for num in arr:
        if num < len(dp_init):
            rnt.append(dp_init[num])
            continue
        tmp = int(num % 11)
        if tmp == 0:
            rnt.append(num // 11)
            continue

        if tmp in [3, 7]:
            rnt.append(num // 11 + 1)
            continue

        if tmp < 3:
            rnt.append(num // 11 + 4 - tmp)
        elif tmp == 4:
            rnt.append(num // 11 + 2)
        elif tmp == 5:
            rnt.append(num // 11 + 3)
        elif tmp == 6:
            rnt.append(num // 11 + 2)
        elif tmp == 8:
            rnt.append(num // 11 + 2)
        elif tmp == 9:
            rnt.append(num // 11 + 3)
        elif tmp == 10:
            rnt.append(num // 11 + 2)
    return rnt




发表于 2021-07-22 14:46:48 回复(0)