[Swift]LeetCode1066.校园自行车分配II|CampusBikesII

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

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

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

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

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

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

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All worker and bike locations are distinct.
1 <= workers.length <= bikes.length <= 10

在由 2D 网格表示的校园里有 n 位工人（worker）和 m 辆自行车（bike），n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。

我们为每一位工人分配一辆专属自行车，使每个工人与其分配到的自行车之间的曼哈顿距离最小化。

p1 和 p2 之间的曼哈顿距离为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

返回每个工人与分配到的自行车之间的曼哈顿距离的最小可能总和。

示例 1：

输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：6
解释：
自行车 0 分配给工人 0，自行车 1 分配给工人 1 。分配得到的曼哈顿距离都是 3, 所以输出为 6 。

示例 2：

输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：4
解释：
先将自行车 0 分配给工人 0，再将自行车 1 分配给工人 1（或工人 2），自行车 2 给工人 2（或工人 1）。如此分配使得曼哈顿距离的总和为 4。

提示：

0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
所有工人和自行车的位置都不相同。
1 <= workers.length <= bikes.length <= 10

Runtime: 36 ms

Memory Usage: 20.9 MB

 1 class Solution {
 2     var dp:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:11),count:1 << 11)
 3     func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
 4         var workers = workers
 5         var bikes = bikes
 6         return F(&workers, &bikes, 0, 0)
 7     }
 8     
 9     func getCost(_ a:[Int],_ b:[Int]) -> Int
10     {
11         var ret:Int = 0
12         for i in 0..<a.count
13         {
14             ret += abs(a[i] - b[i])
15         }
16         return ret
17     }
18     
19     func F(_ w:inout [[Int]], _ b:inout [[Int]],_ bikesTaken:Int,_ workerId:Int) -> Int
20     {
21         var x:Int = b.count
22         if workerId == w.count {return 0}
23         else if bikesTaken + 1 == (1 << x) {return 0}
24         else if dp[bikesTaken][workerId] != -1 {return dp[bikesTaken][workerId]}
25         
26         var curr:Int = 1000000000
27         for i in 0..<x
28         {
29             if (bikesTaken & (1 << i)) != 0 {continue}
30             curr = min(curr, F(&w, &b, bikesTaken | (1 << i), workerId + 1) + getCost(b[i], w[workerId]))
31         }
32         dp[bikesTaken][workerId] = curr
33         return curr
34     }
35 }

回溯法：Time Limit Exceeded

 1 class Solution {
 2     var ans:Int = -1
 3     var vis:[Bool] = [Bool](repeating:false,count:20)
 4     func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
 5         var list1:[Position] = [Position]()
 6         var list2:[Position] = [Position]()
 7         for pos in workers
 8         {
 9             list1.append(Position(pos[0] , pos[1]))
10         }
11         for pos in bikes
12         {
13             list2.append(Position(pos[0] , pos[1]))
14         }
15         backtracking(list1 , 0 , list2 , 0)
16         return ans
17     }
18     
19     func getDist(_ pos1:Position ,_ pos2:Position) -> Int
20     {
21         return abs(pos1.x - pos2.x) + abs(pos1.y - pos2.y)
22     }
23     
24     func backtracking(_ list1:[Position],_ current:Int,_ list2:[Position],_ dist:Int)
25     {
26         if current == list1.count
27         {
28             if dist < ans || ans < 0 {ans = dist}
29         }
30         else
31         {
32             for i in 0..<list2.count
33             {
34                 if !vis[i]
35                 {
36                     vis[i] = true
37                     backtracking(list1 , current + 1 , list2 , dist + getDist(list1[current] , list2[i]))
38                     vis[i] = false
39                 }
40             }
41         }
42     }
43 }
44 
45 class Position
46 {
47     var x:Int
48     var y:Int
49     init(_ x:Int,_ y:Int)
50     {
51         self.x = x
52         self.y = y
53     }
54 }

DFS：Time Limit Exceeded

 1 class Solution {
 2     var minNum:Int = Int.max
 3     func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
 4         var arrBool:[Bool] = [Bool](repeating:false,count:bikes.count)   
 5         dfs(workers, 0, bikes,&arrBool, 0)
 6         return minNum
 7     }
 8     
 9     func dfs(_ workers: [[Int]],_ i:Int,_ bikes: [[Int]],_ used:inout [Bool],_ sum:Int)
10     {
11         if i == workers.count
12         {
13             minNum = min(minNum, sum);
14             return
15         }
16         
17         for j in 0..<bikes.count
18         {
19             if used[j] {continue}
20             used[j] = true
21             dfs(workers, i+1, bikes, &used, sum + getDistance(workers[i], bikes[j]))
22             used[j] = false
23         }
24     }
25     
26     func getDistance(_ p1:[Int],_ p2:[Int]) -> Int
27     {
28         return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
29     }
30 }