杨辉三角的变形

[编程题]杨辉三角的变形

热度指数：150441 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

数据范围： $1 \le n \le 10^9 \$

输入描述:

输入一个int整数

输出描述:

输出返回的int值

示例1

输入

输出

算法知识视频讲解

Javascript_V8

牛客355074576号

没有想到规律

遍历杨辉三角的方法只能通过 22/30

遍历第n行：

25/30 组用例通过

运行时间2001ms

占用内存9720KB


let n = parseInt(readline())

let arr = [0,0,1,0,0]


for(let i = 1;i<n;i++){
    
    let row = new Array(2*i+5).fill(0)
    
    for(let j =2; j<row.length-2;j++){
        
        row[j] = arr[j-2] + arr[j-1] +arr[j]
    }  
     
    arr = row
//     如果arr 是二维数组 row[j] = arr[i-1][j-2] + arr[i-1][j-1] +arr[i-1][j]
//     arr.push(row) 
//     可以打印出杨辉三角
}

let flag = -1


for(let i = 2;i<2*n+1;i++){
     if(arr[i]%2 == 0 ){
        flag = i -1
         break
    }
}

console.log(flag)

发表于 2022-08-05 01:35:47 回复(0)

Javascript_V8

Little-Bird

1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
1,5,10,10,5,1
1,6,15,20,15,6,1
1,7,21,35,35,21,7,1
1,8,28,56,70,56,28,8,1
1,9,36,84,126,126,84,36,9,1
1,10,45,120,210,252,210,120,45,10,1

1,11,55,165,330,462,462,330,165,55,11,1

var line;
while ((line = readline())) {
console.log(fun(parseInt(line)));
}
// 每一行的第一列都是1，可以忽略
// 观察可得从第三行的第二列开始，就成奇偶的
// 那么思路就出现了

function fun(row) {
if (row == 1 || row== 2) {
return -1;
} else if (row % 2 == 1) {
return 2;
} else if (row % 4 == 0) {
return 3;
} else {
return 4;
}
}

发表于 2022-05-25 00:04:53 回复(0)

Javascript_V8

优秀的阿二

//正常解***有内存超限:您的程序使用了超过限制的内存的报错
// let hang = Number(readline());
// let arr = [];
// for(let i = 0;i<hang;i++){
// let len = i*2+1;
// arr.push(Array.from({length:len},()=>1))
// }
// 计算
// for(let i = 2;i<arr.length;i++){
// let str = [].concat(arr[i-1]);
// str.unshift(0);
// str.unshift(0);
// str.push(0);
// str.push(0);
// for(let j = 0;j<arr[i].length;j++){
// arr[i][j] = str.slice(j,j+3).reduce((a,b)=>a+b,0)
// }
// }
// let ks = -1;
// for(let i = 0;i<arr[arr.length-1].length;i++){
// if(arr[arr.length-1][i]%2===0){
// ks = i+1
// break;
// }
// }
// console.log( ks )

//由于题目只需要找某一行的第一个偶数，就可以偷个机

if(hang==1||hang===2){
console.log(-1)
}else{
if(hang%2==0&&(hang/2)%2!==0){
console.log(4)
}
else if(hang%2===0){
console.log(3)
}else{
console.log(2)
}
}

发表于 2022-05-06 21:50:41 回复(0)

Javascript_V8

易婷婷1368883533

let line;

while(line=Number(readline())){
    var newArr = [];
    var oldArr = [1];
    for (var i = 2; i <= line; i++) {
        for (var j = 0; j < 2 * i - 1; j++) {
            if (j == 0 || j == 2 * i - 2) {
                newArr.push(oldArr[0]);
            } else if (j == 1 || j == 2 * i - 3) {
                newArr.push((i === 2 ? 0 : oldArr[1]) + oldArr[0]);
            } else {
                newArr.push(oldArr[j] + oldArr[j - 1] + oldArr[j - 2]);
            }
        }
        oldArr = newArr;
        newArr = [];
    }

    let result = -1;
    for (var i = 0; i < oldArr.length; i++) {
        if (oldArr[i] % 2 === 0) {
            result = i + 1;
            break;
        }
    }
    console.log(result);
}

发表于 2021-07-25 02:30:28 回复(0)