题目的主要信息：

• 杨辉三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0）
• 求数阵中第n行第一个偶数出现的位置
• 如果没有偶数，则输出-1

方法一：数组模拟（超出空间）

具体做法：

可以用一个矩阵模拟杨辉三角形构建过程，因为第$nn$n行的数字有$2\ast n-12*n-1$2∗n−1个，因此用一个全部初始化为0的$n\ast (2\ast n-1)n*(2*n-1)$n∗(2∗n−1)的矩阵就可以构建。

首先将三角形三个角的1全部构建好，其余都是0，然后从上到下从左到右遍历矩阵，每次将其顶上三个数相加得到该数组。

遍历最后一行，找到第一个非0偶数出现的位置，因为是对称的，如果过半了且遇到了1还没有找到意味着找不到了。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<vector<int> > matrix(n, vector<int>(2 * n - 1, 0)); //一共n行，最下面一行最多有2*n-1个元素
        matrix[0][n - 1] = 1; //顶角
        matrix[n - 1][0] = matrix[n - 1][2 * n - 2] = 1; //两个底角
        for(int i = 1; i < n; i++)
            for(int j = 1; j < 2 * n - 2; j++)
                matrix[i][j] = matrix[i - 1][j - 1] + matrix[i - 1][j] + matrix[i - 1][j + 1];
        for(int i = 0; i < 2 * n - 1; i++){
            if(matrix[n - 1][i] != 0 && matrix[n - 1][i] % 2 == 0){ //非0偶数
                cout << i + 1 << endl; //输出下标加1;
                break;
            }
            if(i >= n - 1 && matrix[n - 1][i] == 1){ //过一半还没有找到偶数且遇到了1代表永远找不到了
                cout << -1 << endl;
                break;
            }
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，遍历矩阵一共花费$n\ast (2\ast n-1)n*(2*n-1)$n∗(2∗n−1)次
• 空间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，矩阵的大小为$n\ast (2\ast n-1)n*(2*n-1)$n∗(2∗n−1)

方法二：数学规律

具体做法：

我们多画几行出来，如下所示：

我们发现除了前两行外都是有偶数的，奇数行的偶数就在第二个，偶数行的偶数要么在第4个要么在第3个，关键看能不能整除4.

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        if(n <= 2) //小于等于2的行没有偶数
            cout << -1 << endl;
        else{
            if(n % 2) //奇数行偶数在第2个
                cout << 2 << endl;
            else if(n % 4 == 2) //偶数除4余2的在第4个
                cout << 4 << endl;
            else if(n % 4 == 0) //整除4的在第3个
                cout << 3 << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(1\right)O(1)$O(1)，直接找，常数时间
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间