杨辉三角的变形

题目来源

牛客网：杨辉三角的变形

题目描述

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

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

数据范围：1≤n≤10 ^9

输入描述

输入一个int整数

输出描述

输出返回的int值

示例1

输入

4

输出

3

思路分析

解法一

构造数阵，将题目描述的数阵用动态二维数组构造出来，找到对应行进行遍历，查找第一个偶数，但是这种方式占用内存过大，所以当数字比较大时，会超出内存限制。

解法二

找规律：

除了一二行之外，后面偶数出现的规律都为：2、3、2、4……

代码展示

解法一

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

int main(){
    int n=0;
    while(cin>>n)
    {
        vector<vector<int>> vv(n);
        for(int i=0;i<n;i++)
        {
            vv[i].resize(2*i+1,1);
        }
        //构造数阵
        for(int i=2;i<n;i++)
        {
            for(int j=1;j<vv[i].size()-1;j++)
            {
                vv[i][j]=vv[i-1][j-1];
                if(j-2>=0)
                {
                    vv[i][j]+=vv[i-1][j-2];
                }
                if(j<vv[i-1].size())
                {
                    vv[i][j]+=vv[i-1][j];
                }
            }
        }
        int ret=-1;
        for(int i=0;i<vv[n-1].size();i++)
        {
            if(!(vv[n-1][i]&0x01))
               {
                   ret=i+1;
                   break;
               }
        }
        cout<<ret<<endl;
    }
    return 0;
}

解法二

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

int main(){
    int n=0;
    while(cin>>n)
    {
        int ret=-1;
        if(n>2)
        {
            if(n%4==3||n%4==1)
            {
                ret=2;
            }
            if(n%4==0)
            {
                ret=3;
            }
            if(n%4==2)
            {
                ret=4;
            }
        }
        cout<<ret<<endl;
    }
    return 0;
}

解法二代码优化：

将出现位置结果按取模的下标保存在数组中，可以直接通过取模的结果按下标找到对应出现位置。

int n = 0;
int table[] = { 4,2,3,2 };
while (cin >> n)
{
    int ret = -1;
    if (n > 2)
    {
        ret = table[(n - 2) % 4];
    }
    cout << ret << endl;
}