首页 > 试题广场 >

杨辉三角的变形

[编程题]杨辉三角的变形
  • 热度指数：169129 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义变形的杨辉三角规则：
\hspace{23pt}\bullet\,第一行为固定的整数 1；
\hspace{23pt}\bullet\,第二行开始，每行的数字数量均比上一行多两个，且中心对称（也可以看作是在上一行的基础上首尾增加了一个数字）；每个位置上的数字是它正上方、左上角和右上角这三个数之和（如果不存在某个数，认为该数就是 0）。
\hspace{15pt}下方展示了计算的过程：
\begin{bmatrix}<br />1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & 1 & {\color{grey}0} \\<br />1 & 1 & 1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} \\<br />1 & 2 & 3 & 2 & 1<br />\end{bmatrix}<br />\to<br />\begin{bmatrix}<br />{\color{grey}0} & {\color{grey}0} & {\color{grey}0} & 1 & {\color{grey}0} & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & {\color{grey}0} & 1 & 1 & 1 & {\color{grey}0} & {\color{grey}0} \\<br />{\color{grey}0} & 1 & 2 & 3 & 2 & 1 & {\color{grey}0} \\<br />1 & 3 & 6 & 7 & 6 & 3 & 1<br />\end{bmatrix}

\hspace{15pt}现在，你需要输出第 n 行中第一个偶数出现的位置。从 1 开始计数。

输入描述:
\hspace{15pt}输入一个整数 n \left(1 \leqq n \leqq 10^9\right) 代表询问的行数。


输出描述:
\hspace{15pt}输出一个整数，代表第 n 行中第一个偶数出现的位置。特别地如果第 n 行中没有偶数，则输出 -1。
示例1

输入

4

输出

3
示例2

输入

3

输出

2
示例3

输入

1

输出

-1
算法知识视频讲解
添加回答
Java
故事与你love头像 故事与你love 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            //生成变形杨辉三角二维数组
            int row = in.nextInt();
            int column = 2 * row - 1;
            int[][] arrays = new int[row][column];
            arrays[1-1][row-1] = 1;//第一行最中间的元素赋值1
            for (int i = 1;i<row; i++){
                for(int j = 0;j < column; j++){
                    if(j-1 >=0 && j+1<column){ 
                        arrays[i][j] =arrays[i-1][j-1] + arrays[i-1][j] + arrays[i-1][j+1];}
                    if(j-1 < 0){
                        arrays[i][j] = 0 + arrays[i-1][j] + arrays[i-1][j+1];
                    }
                     if(j+1 >= column){
                        arrays[i][j] = arrays[i-1][j-1] + arrays[i-1][j] + 0;
                    }
                }
            }
            //最后一行，计算第一个偶数位置
            int count = 0;
            for(int k = 0; k < (column + 1)/2  ; k++){
                if (arrays[row-1][k] % 2 == 0){
                    System.out.println(k+1);//输出第一个偶数位置
                    break;
                }
                else{
                    count++;//没有找到则记数
                }
            }
            if(count == (column + 1)/2 ){
                System.out.println(-1);
            }
            
     
        }
    }
}
正常逻辑没问题，到10000时耗尽堆内存了，它奶奶的
发表于 2025-02-27 00:03:48 回复(0)
Java
那个渔头像 那个渔

import java.util.Scanner;

//杨辉三角，会超时，用递归，咋整呢
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //row行，col列
        int row = sc.nextInt();
        int col = 2 * row - 1;
        int[][] arr = new int[row][col];
        //对第n行的数进行遍历
        for (int i = 0; i < col; i++) {
            int sum = getSum(arr, row - 1, i);
            if (sum % 2 == 0) {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(-1);
    }

    //求二维数组第几行几列的值 ，递归
    public static int getSum(int[][] arr, int row, int col) {
        if (row == 0 && col == arr.length - 1) {
            return 1;
        }
        //有上一行
        if (row - 1 >= 0) {
            //有左上角
            if ( col - 1 >= 0) {
                //有左上角 有右上角
                if (col + 1 < arr[0].length) {
                    return getSum(arr, row - 1, col - 1) + getSum(arr, row - 1, col) + getSum(arr,
                            row - 1, col + 1);
                }
            } else {
                //没有左上角 有右上角
                if (col + 1 < arr[0].length) {
                    return getSum(arr, row - 1, col) + getSum(arr, row - 1, col + 1);
                }
            }
        } else {
            return 0;
        }
        return getSum(arr, row - 1, col - 1) + getSum(arr, row - 1, col) + getSum(arr,
                row - 1, col + 1);
    }
}

发表于 2025-02-03 17:08:43 回复(0)
Java
Sen_n头像 Sen_n
 n=10000时  二维数组OOM
找规律 
发表于 2025-01-27 22:34:02 回复(0)
Java
认真的芝士在敲键盘头像 认真的芝士在敲键盘
import java.util.Scanner;
//    n 1   2   3   4   5   6   7   8   9   10  11  ……
//index -1  -1  2   3   2   4   2   3   2   4   2   ……

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            if ( a <= 2) {// 1 2
                System.out.println(-1);
            } else if (a % 4 == 0) {// 4 8
                System.out.println(3);
            } else if (a % 4 == 1 || a % 4 == 3) { // 3 5 7 9 11
                System.out.println(2);
            } else if (a % 4 == 2) {// 6 10
                System.out.println(4);
            }
        }
    }
}
发表于 2024-09-12 15:51:13 回复(0)
Java
牛客499848474号头像 牛客499848474号
投机取巧

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        if(a <= 2){
            System.out.println(-1);
        }else if(a % 2 == 1){
            System.out.println(2);
        }else if(a % 4 == 0){
            System.out.println(3);
        }else{
            System.out.println(4);
        }
    }
}

发表于 2024-08-21 11:35:24 回复(0)
Java
爱吃香菜的小确幸在投简历头像 爱吃香菜的小确幸在投简历 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        if (row == 1 || row == 2){
            System.out.println(-1);
        }else if ((row & 1) == 1){//奇数
            System.out.println(2);
        }else if ((row & 2) == 2){//偶数但不是4的倍数
            System.out.println(4);
        }else
            System.out.println(3);//4的倍数
    }
}

发表于 2024-07-07 11:24:59 回复(0)
Java
牛客76365361号头像 牛客76365361号
这可是简单题，都在找规律…… 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a < 3) {
                System.out.println("-1");
                return;
            }
            if((a & 1) == 1) {
                System.out.println("2");
                return;
            }
            if((a & 2) == 2) {
                System.out.println("4");
                return;
            }
            System.out.println("3");
            return;
        }
    }
}


发表于 2024-06-29 12:02:58 回复(0)
Java
牛客625422543号头像 牛客625422543号
尝试过两轮无果：
1、构造n行的二维数组存储，但那个10000行的用例会OOM。
2、递归表达(i,j)位置的数，只求第n行的每个数，找到偶数为止。但因为方法递归到底还是等于在栈空间中构造了一遍完整的三角，要么超时要么栈溢出。
3、换个思路，题目只关心是不是偶数，又没说要求算出来，于是找规律，3分钟找到了... O(1)算法秒杀。
发表于 2024-06-17 11:28:06 回复(0)
Java
fake_lok666头像 fake_lok666
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int length = in.nextInt();
if(length<=2){
System.out.println("-1");
}else if(length%2 == 1){
System.out.println("2");
}else{
if((length/2)%2==0){
System.out.println("3");
}else{
System.out.println("4");
}
}
}
}
发表于 2024-06-04 10:15:15 回复(0)
Java
无梦0头像 无梦0
可以跑通用例，但其实并不符合要求。暴力破解的，虽然没有oom，有个异常值是手动推导的： 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int len = in.nextInt();
        if (len > 2 && len % 2 == 1) {
            System.out.println(2) ;
            return;
        }
        if (len > 500) {
            System.out.println(3) ;
            return;
        }

        int[] old = new int[1];
        int[] ne = new int[1];
        ne[0] = 1;
        //组织树
        for (int i = 2; i <= len; i++) {
            old = ne;
            ne = new int[i * 2 - 1];
            for (int j = 0; j < ne.length; j++) {
                int s1 = j - 2;
                int s2 = j - 1;
                int s3 = j;
                int sum = 0;
                if (s1 >= 0 && s1 <= old.length - 1) {
                    sum = sum + old[s1];
                }
                if (s2 >= 0 && s2 <= old.length - 1) {
                    sum = sum + old[s2];
                }
                if (s3 >= 0 && s3 <= old.length - 1) {
                    sum = sum + old[s3];
                }
                if (i > 0) {
                    // System.out.print(sum + " ") ;
                }

                ne[j] = sum;
            }
            if (i > 0) {
                // System.out.println("") ;
            }

        }

        for (int i = 0; i < ne.length; i++) {
            if (ne[i] % 2 == 0) {
                System.out.println(i + 1) ;
                return;
            }
        }
        System.out.println(-1) ;
    }


}


编辑于 2024-04-08 15:02:58 回复(0)
Java
黑客永不服输头像 黑客永不服输

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int[] wb = function(a);
            boolean find = false;
            for (int i = 0; i < wb.length; i++) {
                if (wb[i] % 2 == 0) {
                    System.out.println(i + 1);
                    find = true;
                    break;
                }
            }
            if (find == false) {
                System.out.println(-1);
            }

        }
    }

    private static int[] function(int a) {
        if (a == 1) {
            return new int[]{1};
        } else if (a == 2) {
            return new int[]{1, 1};
        }
        else if(a==3){
            return new int[]{1,2,3};
        }else {
            int t = (2 * a - 1) / 2 + 1;
            int[] res = new int[t];
            int[] arr = function(a - 1);
            for (int i = 0; i < res.length; i++) {
                if (i == 0) {
                    res[i] = 1;
                } else if (i == 1) {
                    res[i] = arr[0] + arr[1];
                } else if (i == res.length-1) {
                    res[i] = arr[i - 2] * 2 + arr[i - 1];
                } else {
                    res[i] = arr[i - 2] + arr[i - 1] + arr[i];
                }
            }
            return res;
        }
    }
}我本地编译没问题，但是为什么在OJ系统里面说我OutOfMemoryError: Java heap space了

编辑于 2024-03-29 13:56:14 回复(0)
Java
牛客700990974号头像 牛客700990974号
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // 1
            // 1 1 1
            // 1 2 3 2 1
            // 1 3 6 7 6 3 1
            // 1 4 10 16 19 16 10 4 1

            // 会超时
//            int lineNum = in.nextInt();
//            if (lineNum < 3) {
//                System.out.println(-1);
//                continue;
//            }
//            List<Integer> rowList = new ArrayList<Integer>();
//            List<Integer> preRowList = new ArrayList<Integer>();
//            preRowList.add(1);
//            for (int row = 1; row < lineNum; row++) {
//                rowList.add(1);
//                for (int col = 1; col < row * 3 + 1; col++) {
//                    int num = 0;
//                    num += col - 2 >= 0 && col - 2 < preRowList.size() ? preRowList.get(col - 2) :0;
//                    num += col - 1 >= 0 && col - 1 < preRowList.size() ? preRowList.get(col - 1) :0;
//                    num += col >= 0 && col < preRowList.size() ? preRowList.get(col) :0;
//                    rowList.add(col, num);
//                    if (row == lineNum - 1 && (num & 1) == 0) {
//                        System.out.println(col + 1);
//                        break;
//                    }
//                }
//                preRowList = rowList;
//                rowList = new ArrayList<>();
//            }

            // 找规律
            // 1    2   3   4   5   6   7   8   9   10  11  12
            // -1  -1   2   3   2   4   2   3   2   4   2   3
            int lineNum = in.nextInt();
            if (lineNum < 3) {
                System.out.println(-1);
                continue;
            }
            if ((lineNum & 1) == 1) // 奇数
                System.out.println(2);
            else if (lineNum % 4 == 0) // 4的倍数
                System.out.println(3);
            else
                System.out.println(4); // 偶数但不是4的倍数
        }
    }
}
发表于 2023-12-11 14:40:04 回复(0)
Java
徐墨耀头像 徐墨耀
就是一个找规律的题目，如果模仿杨辉三角就是会导致运行时间超出限制。
下面这段代码是模拟杨辉三角，然后去寻找偶数，但是测试用例10000会超时。 
import java.util.ArrayList;
import java.util.Scanner;

public class T53 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n <= 2) {
                System.out.println("-1");
                return;
            }
            if (n % 2 != 0) {
                System.out.println("2");
                return;
            }
            int flag = 3;
            ArrayList<Integer> reference = new ArrayList<>();
            reference.add(1);
            reference.add(2);
            reference.add(3);
            reference.add(2);
            reference.add(1);
            while (true) {
                ArrayList<Integer> current = new ArrayList<>();
                int length = 2 * (flag+1) - 1;
                //对当前行数据生成
                for (int i = 1; i <= length; i++) {
                    if (i == 1 || i == length) {
                        current.add(1);
                        continue;
                    }
                    if (i == 2) {
                        current.add(reference.get(0) + reference.get(1));
                        continue;
                    }
                    if (i == length - 1) {
                        current.add(reference.get(reference.size() - 1) + reference.get(reference.size() - 2));
                        continue;
                    }
                    current.add(reference.get(i - 3) + reference.get(i - 2) + reference.get(i - 1));
                }
                reference = current;
                flag++;
                if (flag == n) {
                    break;
                }
            }
            for (int i = 0; i < reference.size(); i++) {
                if (reference.get(i) % 2 == 0) {
                    System.out.println(i + 1);
                    return;
                }
            }
        }

    }
}


发表于 2023-11-29 14:59:44 回复(0)
Java
Kili_66头像 Kili_66 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int [] m = {2, 3, 2, 4};
        System.out.println(n >= 3 ? m[(n - 3) % 4] : -1);
    }
}

发表于 2023-11-25 15:21:06 回复(1)
Java
Fox_man头像 Fox_man
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //方法1；直接开辟二维数组进行赋值遍历，超内存且超时
    public static int solve(int n){
        int m = 2*n-1;
        int[][] arr = new int[n][m];
        //初始化第一层(因为int型默认值为0，所以为赋值的地方就为0)
        arr[0][m/2] = 1;

        int left=0;
        int right=0;
        int up=0;
        //开始遍历
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(j-1 >= 0){
                    left = arr[i-1][j-1];
                }
                if(j+1<m){
                    right = arr[i-1][j+1];
                }
                up = arr[i-1][j];

                arr[i][j] = left+up+right;
            }
            left = up = right = 0;
        }

        for(int j=0;j<m;j++){
            if(arr[n-1][j]%2==0)
                return j+1;
        }

        return -1;
    }
    //方法2：开辟两个一维数组，交替遍历赋值，不超内存，但超时
    public static int solve2(int n){
        int m = 2*n-1;

        int[] pre = new int[m];
        int[] now = new int[m];
        int[] tmp;

        //初始化第一层
        pre[m/2] = 1;

        int left=0;
        int right=0;
        int up=0;

        //开始循环赋值，
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(j-1>=0){
                    left = pre[j-1];
                }
                if(j+1<m){
                    right = pre[j+1];
                }
                up = pre[j];

                now[j] = left+up+right;
            }
            left = up = right = 0;
           
            //交换上下层
            tmp = now;
            now = pre;
            pre = tmp;
        }

        //最后一层遍历赋值之后，由于交换了引用，最后一层其实在pre上
        for(int j=0;j<m;j++){
            if(pre[j]%2==0)
                return j+1;
        }

        return -1;
    }

    //方法3：寻找规律，可以发现，从第3行开始，偶数出现的位置依次为 2,3,2,4
    //且这个规律呈现周期性，即从第7行开始，偶数出现的位置也依次是：2，3，2，4，故可以直接计算
    public static int solve3(int n){
        if(n==1 || n==2){
            return -1;
        }

        if(n%4==3 || n%4==1){
            return 2;
        }
        if(n%4==0){
            return 3;
        }
        if(n%4==2){
            return 4;
        }

        return -1;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           System.out.println(solve3(n));
        }
    }
}
发表于 2023-03-05 14:33:06 回复(0)
Java
zzloveyou头像 zzloveyou
这种解*** n = 10000时 会导致OOM 如何优化？ 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt();
            int[][] dp = new int[N + 1][2 * N];
            dp[1][1] = 1;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= 2 * N - 1; j++) {
                    for (int k = j - 2; k <= j; k++) {
                        if (k < 1 || k > (2 * (i - 1) - 1)) {
                            continue;
                        }
                        dp[i][j] += dp[i - 1][k]; 
                    }
                }
            }
            int ans = -1;
            for (int m = 1; m <= 2 * N - 1; m++) {
                if (dp[N][m] % 2 == 0) {
                    ans = m;
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}


发表于 2023-02-05 01:53:48 回复(4)
Java
、前头像 、前
oom了，不按出题人想的找规律就不行，感觉构建完整的杨辉三角难度大些 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[][] arrray = new int[n][2*n-1];
        for(int i=0;i<n;i++){
            arrray[i][0] = 1;
        }
        for(int i = 1;i<n;i++){
            for(int j=1;j<(2*(i+1)-1);j++){
                if(j==1){
                    arrray[i][j]=0+1+arrray[i-1][j];
                }else if(j>=2){
                    arrray[i][j]=arrray[i-1][j-2]+arrray[i-1][j-1]+arrray[i-1][j];
                }
                
            }
        }
        int flag = -1;
        for(int i = 0;i<2*n-1;i++){
            if(arrray[n-1][i]%2==0){
                flag=i+1;
                break;
            }
        }
        System.out.print(flag);

    }


}


// 1 
// 1 1 1
// 1 2 3 2 1
// 1 3 6 7 6 3 1


// a[i][j]=a[i-1][j-2]+a[i-1][j-1]+a[i-1][j]
// 2n-1

发表于 2023-01-07 21:14:28 回复(2)
Java
UnYee头像 UnYee
/*其实就是个找规律题*/
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        if(n>=3){
            if((n-1)%2==0){
                System.out.print("2");
            }else{
                if(n%4==0){
                    System.out.print("3");
                }else{
                    System.out.print("4");
                }
            }    
        }else{
            System.out.print("-1");
        }
    }
}

发表于 2022-08-30 16:39:03 回复(0)
Java
牛客200498065号头像 牛客200498065号
被骗惨了，老老实实构造了个杨辉三角，结果内存吵了（OOM） 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        int n = Integer.parseInt(str);
        int[][] arr = new int[n][(2 * n) - 1];
        for(int i = 0; i < n; i++){
            if(i == 0){
                arr[i][n - 1] = 1;
                continue;
            }
            if(i == n - 1){
                arr[i][0] = 1;
                arr[i][2 * i] = 1;
            }
            for(int k = 1; k <= 2 * n  - 3; k++){
                arr[i][k] = arr[i - 1][k - 1] + arr[i - 1][k] + arr[i - 1][k + 1];
            }
        }
        for (int i = 0; i < arr[n - 1].length; i++) {
            if(arr[n - 1][i] % 2 == 0) {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(-1);
    }
}


发表于 2022-08-14 23:38:34 回复(2)
Java
醉饮荷风头像 醉饮荷风
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            int num = in.nextInt();
            if (num == 1 || num == 2) {
                System.out.println(-1);
                return;
            } else if (num % 4 == 1 || num % 4 == 3) {
                System.out.println(2);
                return;
            } else if (num % 4 == 0) {
                System.out.println(3);
                return;
            } else if (num % 4 == 2) {
                System.out.println(4);
                return;
            }
    }
}
发表于 2022-06-11 16:59:32 回复(0)
提交观点

问题信息

基础数学
难度：
50条回答 33703浏览

热门推荐

通过挑战的用户

查看代码

相关试题

杨辉三角的变形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号