Java解算法之：杨辉三角的变形

Dear 丶 2024-03-24 14:06 69阅读 0赞

题目：

> 描述：
> 
>     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
>     
>     以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
>     
>     求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。
>     
>     数据范围： 1≤n≤10^9
>     
>     
>     输入描述：
>     输入一个int整数
>     
>     输出描述：
>     输出返回的int值
>     
>     示例1
>     输入：
>     4
>     输出：
>     3

代码题解：

import java.util.Scanner;
    
    /**
     * @ClassName 杨辉三角的变形
     * @Description
     * @Author liulvhua
     * @Date 2023/4/3
     **/
    public class HJ53 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                int n = sc.nextInt();//二维数组第n行
                int m = 2 * n - 1;//第n行非零元素个数
                long[][] nums = initialYang(n, m);
                printYang(nums, n, m);
                int res = result(nums, n, m);
                System.out.println("第 " + n + " 行第一个偶数的位置：" + res);
            }
        }
    
        /**
         * 初始化杨辉三角并赋值非零数
         * @param n
         * @param m
         * @return
         */
        public static long[][] initialYang(int n, int m) {
            long[][] nums = new long[n][m];
            // 左上角数upLeft，右上角数upRight
            long upLeft = 0, upRight = 0;
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    nums[0][n - 1] = 1;//第一行初始化
                    continue;
                }
                //从第二行(i>=1)开始，第i行每行非零元素有m个，即从下标[n-i-1]至[m-1]
                for (int j = n - i - 1; j <= m - 1; j++) {
                    if (j >= 1) {//第2列开始存在左上角数，下标j>=1
                        upLeft = nums[i - 1][j - 1];
                    }
                    if (j <= m - 2) {//第i行第m-1列(即倒数第2列），右上角为0，下标为[m-2]最后一个右上角非零的元素
                        upRight = nums[i - 1][j + 1];
                    }
                    //上面的数、左上角数和右上角的数，3个数之和
                    nums[i][j] = nums[i - 1][j] + upLeft + upRight;
                }
            }
            return nums;
        }
    
        /**
         * 打印杨辉三角
         * @param nums 二维数组
         * @param n 行数
         * @param m 第 n 行非零元素个数
         */
        public static void printYang(long[][] nums, int n, int m) {
            long max = nums[n-1][n-1];//三角矩阵最大数
            int maxLength = String.valueOf(max).length() + 1;
            int distance = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    distance = maxLength - String.valueOf(nums[i][j]).length() + 1;//与下一个数空格数量
                    if (nums[i][j] > 0) {
                        System.out.print(nums[i][j]);
                        for (int p = 0; p < distance; p++) {
                            System.out.print(" ");
                        }
                    } else {
                        for (int y = 0; y < distance + 1; y++) {
                            System.out.print(" ");
                        }
                    }
                }
                System.out.println();
            }
            for (int z = 0; z < (distance + 1) * (n - 1) + 1; z++) {
                System.out.print("--");
            }
            System.out.println();
        }
    
        public static int result (long[][] nums, int n, int m) {
            int res = -1;
            for (int t = 0; t < m; t++) {
                if (nums[n-1][t] % 2 == 0) {
                    res = t + 1;
                    break;
                }
            }
            return res;
        }
    }

测试结果：(输入->打印杨辉三角->输出第n行第一个偶数位置)

![8f35e4b6972d4c8e938f21d905139075.png][]

![709c2fd0a769478e81318aec4c606f7a.png][]

![85eb535f1cc0408592eaa9a3700503db.png][]

其中发现题目所给的n范围在1~10^9，这会导致最后一行的值超出int存储范围，甚至即使是long类型也不一定够。经测试这个程序在大概50左右打印矩阵就会出现问题，应该就是超出了long的范围。

于是便有了下面这种解法：

既然打印矩阵有问题，那就不打印好了。。。

> 1  
> 第 1 行第一个偶数的位置：-1  
> 2  
> 第 2 行第一个偶数的位置：-1  
> 3  
> 第 3 行第一个偶数的位置：2  
> 4  
> 第 4 行第一个偶数的位置：3  
> 5  
> 第 5 行第一个偶数的位置：2  
> 6  
> 第 6 行第一个偶数的位置：4  
> 7  
> 第 7 行第一个偶数的位置：2  
> 8  
> 第 8 行第一个偶数的位置：3  
> 9  
> 第 9 行第一个偶数的位置：2  
> 10  
> 第 10 行第一个偶数的位置：4  
> 11  
> 第 11 行第一个偶数的位置：2  
> 12  
> 第 12 行第一个偶数的位置：3  
> 13  
> 第 13 行第一个偶数的位置：2  
> 14  
> 第 14 行第一个偶数的位置：4

发现规律：

*  第一行和第二行所有数都是1，不存在偶数，所以返回-1，
 *  从第2行开始，每连续4行出现第一个偶数的位置都是2,3,2,4

于是直接对n-2取4的模数，不需要构建杨辉三角，避免了内存不足的问题。

[8f35e4b6972d4c8e938f21d905139075.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/056312d4e3b94163a5f195ae555e64fa.png
[709c2fd0a769478e81318aec4c606f7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4593d7bad590466f8ac65937f263103d.png
[85eb535f1cc0408592eaa9a3700503db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/744ef12c3bc64c20bab018fa504ff21f.png