Yanghui triangle in algorithm practice, line k of Yanghui triangle

1. Yanghui triangle

Given a nonnegative integer named numRows, the first numRows of Yanghui triangle are generated.

In Yanghui triangle, each number is the sum of the numbers on the top left and the top right.

Example:
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

java

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> rs = new ArrayList<List<Integer>>();
        List<Integer> prior = null;
        for(int i=1;i<=numRows;i++){
            List<Integer> tmp = new ArrayList<>();
            for(int j=0;j<i;j++){
                if(j==0||j==i-1){
                    tmp.add(1);
                }else{
                    tmp.add(prior.get(j-1)+prior.get(j));
                }
            }
            rs.add(tmp);
            prior = tmp;
        }
        return rs;
    }
}

php

class Solution {

    /**
     * @param Integer $numRows
     * @return Integer[][]
     */
    function generate($numRows) {
        $rs = [];
        for($i=1;$i<=$numRows;$i++){
            $tmp = [];
            for($j=0;$j<$i;$j++){
                if($j==0||$j==$i-1){
                    array_push($tmp,1);
                }else{
                    array_push($tmp,$rs[$i-2][$j-1]+$rs[$i-2][$j]);
                }
            }
            array_push($rs,$tmp);
        }
        return $rs;
    }
}

2. Line k of Yanghui triangle

Given a nonnegative index K, where k < 33, returns the K line of Yang Hui triangle.

Example:
Input: 3
Output: [1,3,3,1]

Use combination formula directly

C(n,i) = n!/(i!*(n-i)!)

Then item (i+1) is the multiple of item I = (n-i)/(i+1);

java

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> rs= new ArrayList<>();
        long  m = 1;
        for(int i=0;i<=rowIndex;i++){
            rs.add((int)m);
            m = m*(rowIndex-i)/(i+1);
        }
        return rs;
    }
}

Note:

m cannot be int, overflow will occur

 

php

class Solution {

    /**
     * @param Integer $rowIndex
     * @return Integer[]
     */
    function getRow($rowIndex) {
        $m = 1;
        $rs = [];
        for($i=0;$i<=$rowIndex;$i++){
            array_push($rs,(int)$m);
            $m = $m*($rowIndex-$i)/($i+1);
        }
        return $rs;
    }
}

Tags: Ruby Java PHP

Posted on Sat, 02 Nov 2019 01:31:34 -0700 by Neomech