题目详情
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
以上三角形的数阵,第一行只有一个数1, 以下每行的每个数,是恰好是它上面的数,左上的数和右上数等3个数之和(如果不存在某个数,认为该数就是0)。
求第n行第一个偶数出现的位置。如果没有偶数,则输出-1。例如输入3,则输出2,输入4则输出3。
输入n(n <= 1000000000)
函数头部:
C/C++:
int run(int n);
java:
public solution {
public static int run(int n);
}
分析
首先想到的是最简单直接的方法硬算,考虑到三角形的对称性,可以只计算一半得出结果。
将数据存放在按照如下图所示的数组中:
第n行只需要第n-1行的计算结果,且,k<n时,有arr[n][k] =
arr[n-1][k] + arr[n-1][k - 1] + arr[n][k - 2],当k==n时,有arr[n][k] = arr[n-1][k - 1] + 2 * arr[n][k - 2]。由于问题只需要计算出第一个偶数的位置,所以可以将上式中的加法,换为异或可以加快速度。
arr[n-1][k] + arr[n-1][k - 1] + arr[n][k - 2],当k==n时,有arr[n][k] = arr[n-1][k - 1] + 2 * arr[n][k - 2]。由于问题只需要计算出第一个偶数的位置,所以可以将上式中的加法,换为异或可以加快速度。
#define N 6 //int arr[1000000005]; unsigned char arr1[N + 5]; unsigned char arr2[N + 5]; int run(int n) { if(n == 1 || n == 2)//当n为1,2时,都是-1 return -1; //利用两个指针,交替保存计算结果,这样可以避免使用N*N的数组 unsigned char *parr_old = arr1; unsigned char *parr_cur = arr2; unsigned char *ptmp; int index; arr1[1] = 1; arr2[1] = 1; for(int i = 2; i < n; ++i)//计算从2到n-1的三角内值 { index = i > N ? N : i; for(int j = 2; j < index; ++j) { //由于只要得出奇偶结果,只利用每个数的最后一位即可,可以利用异或运算更快 //每个数只与其上一层中的第j个和第j-1,第j-2个数有关 parr_cur[j] = parr_old[j] ^ parr_old[j - 1] ^ parr_old[j - 2]; } if(i < N)//三角形的中线上的数,与j-1,j-2和j有关,但是j-2与j是一样的,异或为0,所以只需要j-1 parr_cur[i] = parr_old[i - 1]; ptmp = parr_old; parr_old = parr_cur; parr_cur = ptmp; } for(int j = 2; j <= index; ++j)//找到第一个偶数 { parr_cur[j] = parr_old[j] ^ parr_old[j - 1] ^ parr_old[j - 2]; if((parr_cur[j] & 0x01) == 0) { return j; } } return -1; }
但是仔细读题后发现n <= 1000000000的,上面的算法时间复杂度是O(n^2),一定会超时。
不过可以利用上面的方法分析结果,找出规律。
n为3-50内的数时计算结果为:
可以看出,结果只有2,3,4三种数字,当n为奇数时,都是3,n为偶数时结果只与n的第二位有关,即(n>>1&0x01) +3.所以可以得到代码:
int run(int n) { if(n < 3) { return -1; } if(n & 0x01 == 1) { return 2; } return ((n >> 1) & 0x01) + 3; }
这个时间复杂度为O(1)。