[Swift]LeetCode805.数组的均值分割|SplitArrayWithSameAverage

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

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

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

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

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

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

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

给定的整数数组 A ，我们要将 A数组中的每个元素移动到 B数组或者 C数组中。（B数组和C数组在开始的时候都为空）

返回true ，当且仅当在我们的完成这样的移动后，可使得B数组的平均值和C数组的平均值相等，并且B数组和C数组都不为空。

示例:
输入: 
[1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

注意:

A 数组的长度范围为 [1, 30].
A[i] 的数据范围为 [0, 10000].

20ms

 1 class Solution {
 2     func splitArraySameAverage(_ nums: [Int]) -> Bool {
 3         let sum = nums.reduce(0, +)
 4         let nums = nums.sorted()
 5         let n = nums.count
 6         if n < 2 { return false }
 7         for i in 1...n / 2 where (sum * i) % n == 0 && dfs(nums, i, 0, sum * i / n) { return true }
 8         return false
 9     }
10     
11     func dfs(_ nums: [Int], _ len: Int, _ idx: Int, _ sum: Int) -> Bool {
12         if sum == 0, len == 0 { return true }
13         if idx >= nums.count || len < 0 || sum < 0 { return false }
14         for i in idx..<nums.count {
15             if i > idx && nums[i] == nums[i - 1] { continue }
16             if dfs(nums, len - 1, i + 1, sum - nums[i]) { return true }
17         }
18         return false
19     }
20 }

Runtime: 604 ms

Memory Usage: 24.9 MB

 1 class Solution {
 2     func splitArraySameAverage(_ A: [Int]) -> Bool {
 3         if A.count < 2 {return false}
 4         var sum:Int = A.reduce(0,+)
 5         var n:Int = A.count
 6         var m:Int = n / 2
 7         var possible:Bool = false
 8         var i:Int = 0
 9         while(i <= m && !possible)
10         {
11             if sum * i % n == 0 {possible = true}
12             i += 1
13         }
14         if !possible {return false}
15         var dp:[Set<Int>] = [Set<Int>](repeating:Set<Int>(),count:m + 1)
16         dp[0].insert(0)
17         for num in A
18         {
19             for i in stride(from:m,through:1,by:-1)
20             {
21                 for a in dp[i - 1]
22                 {
23                     dp[i].insert(a + num)
24                 }
25             }
26         }
27         for i in 1...m
28         {
29             if sum * i % n == 0 && dp[i].contains(sum * i / n)
30             {
31                 return true            
32             }
33         }
34         return false
35     }
36 }