题解 | #杨辉三角的变形#

杨辉三角的变形

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

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

求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。数据范围： $1 \le n \le 10^9 \$ 。本题有多组输入数据。

输入描述：

输入一个int整数

输出描述：

输出返回的int值

示例

输入：4
2

输出：3
-1

方法一

思路分析

方法一的思路为暴力求解，直接构造数组求解杨辉三角的数组的元素，然后遍历最后一行求解第一个出现偶数的位置。根据题目要求第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0），因此构造$arr[n,2*n-1]$的二维数组。构造方法如下：

初始化数组元素为0
三角形三个顶点位置的元素均为1
每行的每个数，是恰好是它上面的数，左上角数到右上角的数，3个数之和，如果这个数不存在即为0

按照上面的办法可以构造得到完整的杨辉三角数组。之后遍历数组的最后一行，找到第一个为偶数的元素位置，如果没有输出-1

核心代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int count=0;
    while(cin>>count)
    {
        if(count<=2) 
        {
            cout<<-1<<endl;
            continue;
        }
        vector<vector<int>>arr(count,vector<int>(2*count-1,0));
        arr[0][count-1]=1;//三角形三个顶点的元素为1
        arr[count-1][0]=1;
        arr[count-1][2*count-2]=1;
        for(int i=1;i<count;i++)
        {
            for(int j=1;j<2*count-2;j++)
                arr[i][j]=arr[i-1][j]+arr[i-1][j-1]+arr[i-1][j+1];//三个数之和
        }
        
        for(int i=0;i<2*count-1;i++)
        {
            if(arr[count-1][i]!=0 && (arr[count-1][i]%2==0))
           {
               cout<<i+1<<endl;
               break;
           }
        }
    }
}

复杂度分析

时间复杂度：时间花费在数组的构造，时间复杂度为$O(n^2)$，之后需要在数组最后一行寻找第一个偶数的位置，时间复杂度为$O(n)$，总的时间复杂度为$O(n^2)$
空间复杂度：需要构造额外的存储空间数组，空间复杂度为$O(n^2)$

方法二

思路分析

本题除了使用暴力法构造数组之外，也可以根据规律进行求解，可以看到第一行和第二行是没有偶数出现的，因此直接输出-1。之后的每一行中偶数元素的出现也是带有规律的。在分析的过程中在找偶数行的过程中需要多求解几行才可以找到规律。

图解

核心代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int count=0;
    while(cin>>count)
    {
        if(count<3) cout<<-1<<endl;
        else if(count%2!=0) cout<<2<<endl;//奇数行
        else if(count%2==0&&count%4==0) cout<<3<<endl;//偶数行分为两类
        else cout<<4<<endl;
    }
    return 0;
}