【HJ53 杨辉三角的变形】

描述

 

以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。

求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。

数据范围： 1 \le n \le 10^9 \1≤n≤109 

输入描述：

输入一个int整数

输出描述：

输出返回的int值

示例1

输入：

4

复制输出：

3

思路一，硬编码，但是内存超过要求限制

def f():
    n = int(input())
    if n == 1 or n == 2:
        print(-1)
        return
    if n >= 3:
        dp = [[1]*(2*i-1) for i in range(1,n+1)]
        dp.insert(0,0)
        # print(dp)
        for i in range(3, n + 1):
            dp[i][0] = 1
            dp[i][1] = i - 1
            for j in range(2, i):
                dp[i][j] = sum(dp[i - 1][j - 2:j + 1])
            dp[i][i:] = sorted(dp[i][:i-1],reverse=True)
        for x in dp[n]:
            if x%2 == 0:
                print(dp[n].index(x) + 1)
                return
        print(-1)

f()

思路二：优化，经过观察发现每4行偶数出现的位置就会循环一次（位置分别是[2, 3, 2, 4])

这种问题适合中找规律

n = int(input())

if n == 1 or n == 2:

    print(-1)

if n >= 3:

    if (n + 1) % 2 == 0 and (n - 1) % 2 == 0:

        print(2)

    elif n % 4 == 0:

        print(3)

    elif n % 2 == 0:

        print(4)

    else:

        print(-1)