Java题解 | HJ53 #杨辉三角的变形#

杨辉三角的变形

https://www.nowcoder.com/practice/8ef655edf42d4e08b44be4d777edbf43

描述

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

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

数据范围：

输入描述：

输入一个int整数

输出描述：

输出返回的int值

解法

该题转为了，第n行的数字序列是什么？如果求得了第n行的数字序列，那么从这个数字序列里面找第1个偶数就简单了。

那么如何来生成第n行的数字序列？

观察得知，第n行是上一行个数加2，就是说，第n行有(n-1)*2 +1 个数字，上述问题可以转为了n 乘以 (n-1)*2 +1 的矩阵问题。

矩阵为空的赋值0；
计算时先算第1行，再算第2行，因此类推，算到n行为止。
每行的数字序列都是左右对称的，先找到要计算的起止位置。开始位置是上一行的开始位置左移一位；截止位置是上一行的截止位置右移一位

/*
 * Copyright (c) waylau.com, 2022. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.Scanner;

/**
 * HJ53 杨辉三角的变形.
 * 描述
 * 以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，
 * 左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
 * 求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。
 * 输入n(n <= 1000000000)
 * 本题有多组输入数据，输入到文件末尾，请使用while(cin>>)等方式读入
 * 输入描述:输入一个int整数
 * 输出描述:输出返回的int值
 * 示例1
 * 输入
 * 4
 * 输出
 * 3
 *
 * @author <a href="https://waylau.com">Way Lau</a>
 * @since 2022-08-26
 */
public class HJ053DeformationOfYanghuiTriangle {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        // 输出
        System.out.println(getResult(n));

        // 关闭
        in.close();
    }

    private static int getResult(int n) {
        int m = (n - 1) * 2 + 1; // 矩阵的列数。

        // 矩阵为空的赋值0；
        int[][] arr = new int[n][m];

        // 中间索引位置
        int mid = m / 2;

        //计算时先算第1行，
        arr[0][mid] = 1;

        // 起止位置
        int start = mid;
        int end = mid;

        // 再算第2到n行，因此类推，算到n行为止。
        for (int i = 1; i < n; i++) {
            start--;
            end++;
            for (int j = start; j <= end; j++) {
                // 上一行的左、中、右 值
                // 需要考虑边界
                int previousLeft = j - 1 < 0 ? 0 : arr[i - 1][j - 1];
                int previousMid = arr[i - 1][j];
                int previousRight = j + 1 > n ? 0 : arr[i - 1][j + 1];

                // 上一行的左、中、右 值相加
                arr[i][j] = previousLeft + previousMid + previousRight;
            }
        }

        // 取最后一行遍历，找出偶数后返回
        for (int i = 1; i < m; i++) {
            int v = arr[n - 1][i];

            // 判断是偶数
            if (v % 2 == 0) {
                return i + 1;
            }
        }

        return -1;
    }
}

上面的逻辑本身没有问题，但在运行测试用例时候，发生了OOM。这意味着随着规模数的增加，内存的占用到了无法接受的地步。

最后只能是路走偏锋，采用寻找规律法

/*
 * Copyright (c) waylau.com, 2022. All rights reserved.
 */

package com.waylau.nowcoder.exam.oj.huawei;

import java.util.Scanner;

/**
 * HJ53 杨辉三角的变形.
 * 描述
 * 以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，
 * 左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
 * 求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。
 * 输入n(n <= 1000000000)
 * 本题有多组输入数据，输入到文件末尾，请使用while(cin>>)等方式读入
 * 输入描述:输入一个int整数
 * 输出描述:输出返回的int值
 * 示例1
 * 输入
 * 4
 * 输出
 * 3
 *
 * @author <a href="https://waylau.com">Way Lau</a>
 * @since 2022-08-26
 */
public class HJ053DeformationOfYanghuiTriangle2 {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        
        // 观察规律法
        while (in.hasNextInt()) {
            int num = in.nextInt();
            if(num == 1 || num == 2){
                System.out.println(-1);
                continue;
            }
            else if(num % 4 == 1 || num % 4 == 3){
                System.out.println(2);
                continue;
            }
            else if(num % 4 == 0){
                System.out.println(3);
                continue;
            }
            else if(num % 4 == 2){
                System.out.println(4);
                continue;
            }
        }
        // 关闭
        in.close();
    }
}