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

这是qklbishe.com第13573 篇笔试面试资料
提供答案分析,通过本文《一维数轴,初始位置在原点,每次可以选择向左或者向右移动0或3或7或11个单位 N次询问,每次给出一个坐标arr[i],求从0点走到arr[i]需要的最少次数-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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

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

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

今天 14:46:48 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 一维数轴,初始位置在原点,每次可以选择向左或者向右移动0或3或7或11个单位 N次询问,每次给出一个坐标arr[i],求从0点走到arr[i]需要的最少次数-笔试面试资料

提供最优质的资源集合

立即查看 了解详情