在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0.
Example: Input: 3 Output: [1,3,3,1] 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。 在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 1 class Solution { 2 func getRow(_ rowIndex: Int) -> [Int] { 3 //滚动数组 4 var arr:Array = Array(repeating: 1, count: (rowIndex+1)) 5 for i in 0..<rowIndex 6 { 7 // 第一个元素 不需要计算 所以j从 1 开始 8 // i+1 代表最后一个元素: < (i+1) 表示最后一个元素不用计算 9 for j in (1 ..< (i+1)).reversed() 10 { 11 // 从后往前计算, 防止覆盖 12 arr[j] = arr[j] + arr[j - 1] 13 } 14 } 15 return arr 16 } 17 } 8ms 1 class Solution { 2 func getRow(_ rowIndex: Int) -> [Int] { 3 var memo: [[Int]] = [[1], [1, 1]] 4 if rowIndex <= 1 { return memo[rowIndex] } 5 return calculateRows(memo, rowIndex) 6 } 7 8 func calculateRows (_ memo: [[Int]], _ rowIndex: Int) -> [Int] { 9 if memo.count-1 == rowIndex { return memo[rowIndex] } 10 var dp = memo 11 var prevArr = dp[dp.count-1] 12 var arr = Array(repeating: 0, count: prevArr.count+1) 13 arr[0] = 1 14 arr[arr.count-1] = 1 15 16 for i in 1..<arr.count-1 { 17 arr[i] = prevArr[i-1]+prevArr[i] 18 } 19 20 dp.append(arr) 21 return calculateRows(dp, rowIndex) 22 } 23 } 8ms 1 class Solution { 2 func getRow(_ rowIndex: Int) -> [Int] { 3 if rowIndex == 0 { 4 return [1] 5 } 6 var result = [Int](repeatElement(0, count: rowIndex + 1)) 7 result[0] = 1 8 for i in 1...rowIndex { 9 var j = i 10 while j >= 1 { 11 result[j] += result[j - 1] 12 j -= 1 13 } 14 } 15 return result 16 } 17 }
|
请发表评论