京东笔试数据分析讨论

第一题股票AC27%就不谈了,第二题简单些,想跟牛友讨论一下,
贴一下原题(第二题):
作者:十四颗糖
来源:牛客网
#一共有n个格子从左到右排成了一行,从1~n编号。第 i 个格子上写着一个正整数a[i]。
#一开始你在1号格子,并且手里有一个数字h0。
#当你在第 i 号格子,手里有数字 h 的时候,你有两个选择:
#(1)跳到第i + h号格子,手中的数字依然是h;
#(2)跳到第i + a[i]号格子,手中的数字变成a[i];
#在跳跃的过程中是不允许超出n号格子的。
#你想知道一共有多少种不同的路径,可以从1号格子跳到n号格子,两条路径是不同的当且仅当它们经过的格子集合是不同的。输出不同路径的条数除以998244353的余数。
#输入
#第一行包含两个整数n和h0;
#第二行包含n个正整数a[i];
#2 <= n <= 1000, 1 <= a[i], h0 <= n - 1

#样例输入
#5 1
#2 3 2 4 3
#样例输出
#4
#
#
#提示
#输入样例2
#3 10
#10 10 10
#
#输出样例2
#0

这个题是个简单的递归,但是只AC了78%,有些case我没考虑到,现在复盘还是没想出来,贴一下Python代码。讨论一下我哪些情况没有考虑。
n, h0 = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = [-1] + a


def jump(idx, h):
    global n, a
    if idx == 0:
        return 
    if idx > n:
        return 0
    elif idx == n:
        return 1
    else:
        if h == a[idx]:
            return jump(idx + h, h)
        return (jump(idx + h, h) + jump(idx + a[idx], a[idx])) 


print(jump(1, h0) % 998244353)



#京东##数据分析工程师##笔经##校招#
全部评论
应该不是取余的问题,我试过无论是最终结果取余还是在每次return的时候取余都是78%
点赞 回复 分享
发布于 2020-04-19 08:43
居然无人讨论此题emmmmmm
点赞 回复 分享
发布于 2020-04-19 17:49
up
点赞 回复 分享
发布于 2020-04-20 14:01
第二题我用的bfs,ac了
点赞 回复 分享
发布于 2020-04-20 17:48
python的递归要记得加一句sys.setrecursionlimit(1000000)
点赞 回复 分享
发布于 2020-08-13 00:49

相关推荐

牛客868257804号:九个中铁八个中建
点赞 评论 收藏
分享
3 23 评论
分享
牛客网
牛客企业服务