[Swift]LeetCode62.不同路径|UniquePaths

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9921029.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

8ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         if m == 0 || n == 0 {
 4             return 0
 5         }
 6         var columns: [Int] = Array(repeating: 1, count: m)
 7         for _ in 1..<n { // 逐行遍历
 8             for i in 1..<m { // 第一位, 始终只有1种(+0)
 9                 columns[i] += columns[i-1]
10             }
11         }
12         return columns.last!
13     }
14 }

8ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         var pathNums = Array(repeating: Array(repeating:0,count: n),count: m)
 4         return _helper(&pathNums, m - 1, n - 1)
 5     }
 6     private func _helper(_ pathNums: inout [[Int]], _ m: Int, _ n: Int) -> Int {
 7         if m < 0 || n < 0 {
 8             return 0
 9         }
10         if m == 0 || n == 0 {
11             return 1
12         }
13         
14         if pathNums[m][n] != 0 {
15             return pathNums[m][n]
16         }
17         pathNums[m][n] = _helper(&pathNums, m - 1, n) + _helper(&pathNums, m, n - 1)
18         
19         return pathNums[m][n]
20     }
21 }

12ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         if m == 0 || n == 0 { return 0 }
 4         var count = Array(repeating: Array(repeating: 0, count: n), count: m)
 5         var col = n-1
 6         while col >= 0 {
 7             var row = m-1
 8             while row >= 0 {
 9                 if row == m-1 && col == n-1 {
10                     count[row][col] = 1
11                 } else {
12                     count[row][col] = (col < n-1 ? count[row][col+1] : 0) + (row < m-1 ? count[row+1][col] : 0)                   
13                 }
14                 row -= 1
15             }
16             col -= 1
17         }
18         return count[0][0]
19     }
20 }

16ms

 1 class Solution {
 2     
 3     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 4         guard m > 0 else {
 5             return 0
 6         }
 7         
 8         var steps = Array(repeating: Array(repeating: 1, count: n), count: m)
 9         for row in 1..<m {
10             for column in 1..<n {
11                 steps[row][column] = steps[row - 1][column] + steps[row][column - 1]
12             }
13         }
14         
15         return steps[m - 1][n - 1]
16     }
17     
18 }

20ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         if m == 0 || n == 0 {
 4             return 0
 5         }
 6         var map = Array(repeating: Array(repeating:0,count: n),count: m)
 7         for i in 1 ..< m {
 8             for j in 1 ..< n {
 9                 var num1 = map[i - 1][j]
10                 var num2 = map[i][j - 1]
11                  if i - 1 == 0 || j == 0 {
12                     num1 = 1
13                 }
14                 if i == 0 || j - 1 == 0 {
15                     num2 = 1
16                 }
17                 map[i][j] = num1 + num2
18             }
19         }
20          if m - 1 == 0 || n - 1 == 0 {
21             return 1
22         } else {
23             let result = map[m - 1][n - 1]
24             return result
25         }
26     }
27 }

24ms

 1 class Solution {
 2     
 3     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 4         var arrs: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: m)
 5         for i in 0..<m{
 6             for j in 0..<n{
 7                 if i == 0 && j == 0{
 8                     arrs[i][j] = 1
 9                 }else if i == 0 {
10                     arrs[i][j] = arrs[i][j-1]
11                 }else if j == 0{
12                     arrs[i][j] = arrs[i-1][j]
13                 }else{
14                     arrs[i][j] = arrs[i-1][j] + arrs[i][j-1]
15                 }
16             }
17         }
18         return arrs[m-1][n-1]
19     }
20 }

32ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         guard m > 1 else {
 4             return m == 0 ? 0 : 1
 5         }
 6         guard n > 1 else {
 7             return n == 0 ? 0 : 1
 8         }
 9         
10         var path = [Int].init(repeating: 1, count: m+1)
11         path[0] = 0
12         for _ in 2...n {
13             for j in 1...m {
14                 path[j] = path[j] + path[j-1]
15             }
16         }
17         print(path)
18         return path[m]
19     }
20 }

40ms

 1 class Solution {
 2     func uniquePaths(_ m: Int, _ n: Int) -> Int {
 3         let l = max(m,n)
 4         let s = min(m,n)
 5         if s==1 {
 6             return 1
 7         }
 8         // c l,s 组合
 9         var ji1 = 1
10         var ji2 = 1
11         for i in 1...s-1 {
12             ji1*=i
13             ji2*=l+s-i-1
14         }
15         return ji2/ji1
16     }
17 }