python3 非取巧找规律 完整获取杨辉三角变形详解

杨辉三角的变形

http://www.nowcoder.com/questionTerminal/8ef655edf42d4e08b44be4d777edbf43

看来看去大多是找规律的,如果找不到规律就凉凉了,这边完整用二维矩阵构建出杨辉三角变形,然后取最后一行遍历获得结果

while True:
    try:
        n = int(input())
        res = - 1    #初始化结果为-1
        l = [[0]*(2*n+1) for _ in range(n)]    #以n行的长度创建二维矩阵,每行开头插入2个0
        l[0][2] = 1    #第一行起始值为1(因开头插入了两个0,所以第三位为1)
        for x in range(1,n):    #构造完整的杨辉三角矩阵
            for j in range(2,2*(x+2)-1):
                l[x][j] = l[x-1][j-2]+l[x-1][j-1]+l[x-1][j]
        for i in range(len(l[n-1][2:])):    #遍历杨辉三角矩阵最后一行,去掉开始插入的两个0
            if int(l[n-1][2:][i])%2 == 0:    #如果发现偶数,输入下标,并把答案res置为!=-1的值
                print(i+1)
                res = 0
                break
        if res == -1:    #如果前面没有找到偶数,那么res还是初始值,输出即可满足题意
            print(-1)
    except:
        break
全部评论
注意条件`n <= 1000000000`,你这直接卡死了。
2 回复 分享
发布于 2021-08-05 14:53
别用二维数组 直接整两个list就行,一个pre,一个cur
1 回复 分享
发布于 2021-08-29 22:31
我是老实的,一上来老老实实用 nodejs 构建数组,思路通了,oom不通。。。
点赞 回复 分享
发布于 01-16 09:31 广东
暴力破解,卡死+2 from functools import cache @cache def triangle(n:int)->list[int]: res=[] if n==1: return [1] if n==2: return [1,1,1] prev=triangle(n-1) res.append(prev[0]) res.append(sum(prev[0:2])) for i in range(len(prev)-2): res.append(sum(prev[i:i+3])) res.append(sum(prev[-2:])) res.append(prev[-1]) return res while True: try: n=int(input()) for i,e in enumerate(triangle(n)): if e%2==0: print(i+1) break else: print(-1) except: break
点赞 回复 分享
发布于 2024-10-06 16:13 上海
如果强行求的话,可以只求每一行的前四个元素即可,这里定有偶
点赞 回复 分享
发布于 2024-06-27 16:15 河南
但是构造杨辉三角的思路还是很好的!
点赞 回复 分享
发布于 2024-02-28 18:35 广东
看时间复杂度O(N**2)就知道要超时的,做题前肯定要看的,不要浪费那个时间去试。
点赞 回复 分享
发布于 2023-08-25 17:58 北京
二维数组和一维数组的都试过了,结果二维的超内存,一维的超时间
点赞 回复 分享
发布于 2022-08-16 20:02
只用了当前矩阵和copy当前矩阵作为上一个矩阵,并且只取了一边,防止爆内存和加快运算,然鹅在n=10000时还是超时了。最后老老实实看解析找规律
点赞 回复 分享
发布于 2022-08-07 11:07
超时
点赞 回复 分享
发布于 2022-05-21 10:46
构建完整的会超内存的
点赞 回复 分享
发布于 2022-05-18 11:46
java 的二维矩阵尝试过,11个用例中有一个边界用例(极大值)通不过,报内存溢出。或许改用List存储可行,毕竟List不需要物理上连续的内存空间
点赞 回复 分享
发布于 2022-03-05 16:23
内存超标了
点赞 回复 分享
发布于 2022-02-28 22:32
这样性能太低了,而且当n很大时会爆内存,非常卡
点赞 回复 分享
发布于 2022-02-17 14:48

相关推荐

点赞 评论 收藏
分享
10-13 16:58
门头沟学院 Java
点赞 评论 收藏
分享
评论
30
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务