805. 数组的均值分割
困难
相关企业
给定你一个整数数组 nums
我们要将 nums
数组中的每个元素移动到 A
数组 或者 B
数组中,使得 A
数组和 B
数组不为空,并且 average(A) == average(B)
。
如果可以完成则返回true
, 否则返回 false
。
注意:对于数组 arr
, average(arr)
是 arr
的所有元素除以 arr
长度的和。
示例 1:
输入: nums = [1,2,3,4,5,6,7,8] 输出: true 解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
示例 2:
输入: nums = [3,1] 输出: false
提示:
1 <= nums.length <= 30
0 <= nums[i] <= 104
——————————————————————————————————————————————————————————————————————
1 class Solution { 2 public boolean splitArraySameAverage(int[] nums) { 3 if (nums.length == 1) { 4 return false; 5 } 6 int n = nums.length, m = n / 2; 7 int sum = 0; 8 for (int num : nums) { 9 sum += num; 10 } 11 for (int i = 0; i < n; i++) { 12 nums[i] = nums[i] * n - sum; 13 } 14 15 Set<Integer> left = new HashSet<Integer>(); 16 for (int i = 1; i < (1 << m); i++) { 17 int tot = 0; 18 for (int j = 0; j < m; j++) { 19 if ((i & (1 << j)) != 0) { 20 tot += nums[j]; 21 } 22 } 23 if (tot == 0) { 24 return true; 25 } 26 left.add(tot); 27 } 28 int rsum = 0; 29 for (int i = m; i < n; i++) { 30 rsum += nums[i]; 31 } 32 for (int i = 1; i < (1 << (n - m)); i++) { 33 int tot = 0; 34 for (int j = m; j < n; j++) { 35 if ((i & (1 << (j - m))) != 0) { 36 tot += nums[j]; 37 } 38 } 39 if (tot == 0 || (rsum != tot && left.contains(-tot))) { 40 return true; 41 } 42 } 43 return false; 44 } 45 } 46 47 作者:力扣官方题解 48 链接:https://leetcode.cn/problems/split-array-with-same-average/solutions/1966163/shu-zu-de-jun-zhi-fen-ge-by-leetcode-sol-f630/ 49 来源:力扣(LeetCode) 50 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
原文地址:http://www.cnblogs.com/wzxxhlyl/p/16888462.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性