18

杨辉三角算法 | zhangman523

 4 years ago
source link: https://www.zhangman523.cn/420.html?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

杨辉三角 的算法实现

杨辉三角形是排列成三角形的一系列数字。 在杨辉三角形中，每一行的最左边和最右边的数字总是 1。 对于其余的每个数字都是前一行中直接位于它上面的两个数字之和。

下面给出一个5行的杨辉三角：

yanghuiTrangle

可以看到，每行的最左边和最右边的数字是基本情况，在这个问题中，它总是等于 1。
因此，我们可以将基本情况定义如下:

f(i,j) = 1 where j=1 or j=i

让我们从杨辉三角形内的递推关系开始。
首先，我们定义一个函数 f(i, j)它将会返回杨辉三角形第 i 行、第 j 列的数字。

我们可以用下面的公式来表示这一递推关系：

f(i,j)=f(i−1,j−1)+f(i−1,j)

java 实现

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

    [1,1],
   [1,2,1],
  [1,3,3,1],
[1,4,6,4,1]

方法一 迭代实现

public List<List<Integer> generateTrangle(int numRows){
    List<List<Integer>> list = new ArrayList<>();
    for(int i=0;i<numRows;i++){
        List<Integer> subList = new ArrayList<>();
        list.add(subList);
        for(int j=0;j<i+1;j++){
            f(j==i||j==0){//每行的最左边和最右边的数字都是1
                subList.add(1);
            }else{
                //递推关系
                subList.add((list.get(i-1).get(j-1)+list.get(i-1).get(j)));
    return list;

方法二 递归实现

public List<List<Integer>> generateTriangleByRecursive(int numRow) {
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0; i < numRow; i++) {
      List<Integer> subList = new ArrayList<>();
      for (int j = 0; j < i + 1; j++) {
        subList.add(generate_Triangle_by_recursive(i, j));
      list.add(subList);
    return list;
private int generate_Triangle_by_recursive(int i, int j) {
    int result;
    if (j == 0 || j == i) {
      result = 1;
    } else {
      result =
          (generate_Triangle_by_recursive(i - 1, j - 1) + generate_Triangle_by_recursive(
              i - 1, j));
    return result;

在上面的例子中，您可能已经注意到递归解决方案可能会导致一些重复的计算，例如，我们重复计算相同的中间数以获得最后一行中的数字。 举例说明，为了得到 f(5, 3) 的结果，我们在 f(4, 2) 和 f(4, 3) 的调用中计算了 f(3, 2) 两次。下面我们优化递归算法

方法三 递归+记忆化

public List<List<Integer>> generateTriangleByRecursive(int numRow) {
    List<List<Integer>> list = new ArrayList<>();
    Map<Integer, Map<Integer, Integer>> cacheMap = new HashMap<>();
    for (int i = 0; i < numRow; i++) {
      List<Integer> subList = new ArrayList<>();
      for (int j = 0; j < i + 1; j++) {
        subList.add(generate_Triangle_by_recursive(i, j, cacheMap));
      list.add(subList);
    return list;
  private int generate_Triangle_by_recursive(int i, int j,
      Map<Integer, Map<Integer, Integer>> cacheMap) {
    if (cacheMap.containsKey(i) && cacheMap.get(i).containsKey(j)) {
      return cacheMap.get(i).get(j);
    int result;
    if (j == 0 || j == i) {
      result = 1;
    } else {
      result =
          (generate_Triangle_by_recursive(i - 1, j - 1, cacheMap) + generate_Triangle_by_recursive(
              i - 1, j, cacheMap));
    if (!cacheMap.containsKey(i)) {
      Map<Integer, Integer> map = new HashMap<>();
      cacheMap.put(i, map);
    cacheMap.get(i).put(j, result);
    return result;

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

输出: [1,3,3,1]
public List<Integer> getRow(int rowIndex) {
    List<List<Integer>> list = new ArrayList<>();
        for(int i=0;i<rowIndex+1;i++){
            List<Integer> subList = new ArrayList<>();
            list.add(subList);
            for(int j=0;j<i+1;j++){
                if(j==i||j==0){//first and end
                    subList.add(1);
                }else{
                   subList.add((list.get(i-1).get(j-1)+list.get(i-1).get(j)));
    return list.get(rowIndex);

转载请注明：zhangman523 » 杨辉三角 的算法实现


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK