乐趣区

关于golang:Leetcode专题数组119杨辉三角II

力扣链接:https://leetcode-cn.com/probl…
解题思路:

  1. 解法一:应用杨辉三角的解法,返回固定下标的一位数组,该解法须要二维数组
func getRow(rowIndex int) []int {res := make([][]int, rowIndex + 1)
    for i := range res {res[i] = make([]int, i + 1)
        res[i][0] = 1
        res[i][i] = 1
        for j := 1; j < i; j++ {res[i][j] = res[i-1][j-1] + res[i-1][j]
        }
    }
    return res[rowIndex]
}

2. 优化一:其实咱们在计算 row+ 1 行时,只应用了第 row 行的数据,所以能够用 滚动数组 来进行空间上的优化

func getRow(rowIndex int) []int {pre, cur := []int, []int
    for i := range rowIndex {cur[i] = make([]int, i + 1)
        cur[i][0] = 1
        cur[i][i] = 1
        for j := 1; j < i; j++ {cur[j] = pre[j-1] + pre[j]
        }
        pre = cur
    }
    return pre
}
退出移动版