Java实现杨辉三角高效查找目标值算法（蓝桥杯省赛备战）

问题描述

在杨辉三角中查找给定目标值的位置，并输出其所在的行数和列数。如果目标值不存在于杨辉三角中，则输出提示信息。

初始解法

package 蓝桥杯.省赛;
import java.util.Scanner;

public class 杨辉三角 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        int row = -1;
        int col = -1;
        int[][] arr = new int[100][21];


        for (int i = 0; i < 100; i++) {
            // 每次循环创建一个一维数组
            arr[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    arr[i][j] = 1;
                } else {
                    // 杨辉三角中的值等于它的左上角的值+右上角的值。
                    arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
                }

                if (arr[i][j] == target) {
                    // 索引一般从index从0开始，但是行数，列数从1开始
                    row = i + 1;
                    col = j + 1;
                    break;
                }
            }
            // 它检查在整个外循环中是否找到了目标值。
            // 如果 row 不等于1，意味着在内循环中找到了目标值，那么外循循环也不再继续，
            if (row != -1) {
                break;
            }
        }

        if (row != -1) {
            System.out.print((int) ((row - 1) * row * 0.5 + col));

        }

    }
}

算法优化

上述代码可以解决问题，但存在一些可以优化的地方：

1. 减少内存使用: 不需要创建固定大小的二维数组，可以使用两个一维数组滚动存储当前行和上一行的值。
2. 避免不必要的计算: 不需要遍历整个杨辉三角，在计算过程中判断当前值是否等于目标值即可。
3. 提前终止: 如果目标值大于杨辉三角的最大值，可以提前终止循环。

优化后的代码

import java.util.Scanner;

public class 杨辉三角 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();

        int row = 1;
        int col = 1;
        int prev = 1;
        int current = 1;

        while (current < target) {
            if (col == 1 || col == row) {
                current = 1;
            } else {
                current = prev + current;
            }

            prev = current;
            col++;

            if (col > row) {
                row++;
                col = 1;
            }

            if (current == target) {
                break;
            }

            // 如果当前值超过目标值，则提前终止循环
            if (current > target) {
                row = -1;
                col = -1;
                break;
            }
        }

        if (row != -1) {
            System.out.println((int) ((row - 1) * row * 0.5 + col));
        } else {
            System.out.println('目标值不在杨辉三角中');
        }
    }
}

总结

通过上述优化，可以减少内存的使用，并且能够更快地找到目标值所在的位置，提升程序运行效率，更有效地应对蓝桥杯省赛这类算法竞赛。