LeetCode118 杨辉三角形

本文主要是介绍LeetCode118 杨辉三角形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

   给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
   在「杨辉三角」中，每个数是它左上方和右上方的数的和。

2. 示例

   示例 1:
   输入: numRows = 5
   输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
   输入: numRows = 1
   输出: [[1]]

3. 解题思路
   1. 方法一：暴力算法
      1. 根据杨辉三角形定义，每一个元素都是其左上方和右上方之和。为了满足其左上方右上方数值加和，那么可以将整个二维数组填满，这样就可以直接使用获取方两个值加和计算目标元素值。
         
      2. 那么可以按照规律初始化一个二维数组，默认值=0，第一行中间位置是1，遍历数组依次算出每一个元素的值。
      3. 其中每一行的第  总行数numRows - 第i行  个元素即每一行的起始有效值位置(非0位置)，第 每一行总元素个数 - 总行数 + 第i行  个元素即每一行的终止有效位置。
   2. 方法二：暴力算法优化
      1. 优化方法一，不必创建多余0值元素，减少内存、遍历次数。
      2. 根据规律，每一行的起始值和终止值都是1，中间段内按照规律，上方量元素值之和。即每一行元素即numRows个，下标=0或下标=numRows - 1时，值为1。
      3. 原始杨辉三角习惯是按照元素依次错开计算下一个值，那么将每一行每一列按照从左到右对其，可以发现，目标元素的值就是其左上方的值+上方的值。
   3. 方法三：数学公式推到(参考官方题解-方法二)
      1. 依次计算第i行的排列结果。
         
         
4. 代码(Java)

   // 方法一
   class Solution {public List<List<Integer>> generate(int numRows) {if (numRows == 0) {return new ArrayList();}List<List<Integer>> result = new ArrayList<>();List<Integer> temp = new ArrayList<>();int[][] res = new int[numRows][2 * numRows + 1];res[0][numRows] = 1;temp.add(res[0][numRows]);result.add(temp);for (int i = 1; i < numRows; i++) {temp = new ArrayList<>();for (int j = numRows - i; j < res[i].length - numRows + i; j++) {res[i][j] = res[i - 1][j + 1] + res[i - 1][j - 1];if (res[i][j] != 0) {temp.add(res[i][j]);}}result.add(temp);}return result;}
   }

   // 方法二 
   class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<List<Integer>>();for (int i = 0; i < numRows; ++i) {List<Integer> row = new ArrayList<Integer>();for (int j = 0; j <= i; ++j) {if (j == 0 || j == i) {row.add(1);} else {row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));}}ret.add(row);}return ret;}}

   // 方法三
   class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<List<Integer>>();for (int i = numRows - 1; i >= 0; i--) {List<Integer> ans = new ArrayList<>();ans.add(1);int n = 0;long r = 1;while (n < i) {r = r * (i - n) / (n + 1);ans.add((int) r);n++;}ret.add(0, ans);}return ret;}
   }

这篇关于LeetCode118 杨辉三角形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---