角形"/>
[蓝桥杯Java]:杨辉三角形
题目链接
杨辉三角形
题目描述
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯
给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数?
输入描述:
输入一个整数 N。
输出描述:
输出一个整数代表答案。
输入输出样例:
示例 1:
输入
6
输出
13
评测用例规模与约定:
对于 20的评测用例,1 ≤ N ≤ 10;对于所有评测用例1 ≤ N ≤ 1000000000。
运行限制:
最大运行时间:1s
最大运行内存: 256M
分析
如图为杨辉三角形的数组形式,第i行第j列元素nums[i][j] = nums[i - 1][j] + nums[i - 1[j - 1],考虑到问题规模较大,我们可以将二维数组转化成一维滚动数组,对于某一行的第j个元素,有nums[j] = nums[j] + nums[j - 1](nums[j]是上一行与它对应的元素,nums[j - 1]是上一行与它对应的前一个元素,因为要用到它的上一个元素,所以我们遍历的时候是倒序遍历的)。
但是我们要知道一件事:数组应该定义多大呢?即数组的哪一行出现10亿这个数字,考虑第三列也很容易得到递推公式,第n行第三列的值为(n + 1) * n / 2 > 10亿,得到n = 44722。
接下来我们只需要对前44722行进行dp计算,即可找到N。考虑到杨辉三角的递增性质,如果找不到,N一定N+1行的第二个数。
代码
import java.util.Scanner;public class Main {public static void main(String[] args) {long[] nums = new long[44730];Scanner sc = new Scanner(System.in);long n = sc.nextLong();if (n == 1) {System.out.println(1);return;}nums[1] = 1L;for (int i = 2; i <= 44722; ++i) {//倒序遍历for (int j = i; j >= 1; --j) {nums[j] += nums[j - 1];if (nums[j] == n) {/***因为每一行是对称的 而且遍历顺序是倒序* 所以当我们遇到nums[i] == n时 其实第一次出现的位置时此时j下标的对称位置* 即第 i - j + 1 个元素处*/System.out.println(((long)(i) * (long)(i - 1)) / 2 + i - j + 1);return;}}}//此时,N一定是 第N+1行的第二个数System.out.println(((n * (n + 1)) / 2) + 2);}
}
更多推荐
[蓝桥杯Java]:杨辉三角形
发布评论