Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)
2023-09-14 08:58:01 时间
805. 数组的均值分割
给定的整数数组 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].
PS:
这个题是求能不能进行平均分组,我们可以把题目转换成模拟一个组所有的值得和
因为要求是俩个组得平均值相等,也就是所有人得平均值都要相等
DFS寻找每一次得可能,知道找到
class Solution {
//两组的平均值相等的话,证明我所有的和的平均值是相等的
public boolean splitArraySameAverage(int[] A) {
int sum = 0;
for (int num : A) {
sum += num;
}
//Asum / len = Bsum / i = Csum / len - i
int len = A.length;
Arrays.sort(A);
for (int i = 1; i <= len / 2; i++) {
if (sum * i % len == 0) {
//是否存在长度为i 的 sum和为 sum * i / len B arr
if (dfs(A, i, sum * i / len, 0)){
return true;
}
}
}
return false;
}
private boolean dfs(int[] A, int n, int targetSum, int startIndex) {
if (targetSum == 0 && n == 0) {
return true;
}
if (n != 0) {
for (int i = startIndex; i < A.length; i++) {
if (i > startIndex && A[i] == A[i - 1]) {
continue;
}
if (dfs(A, n - 1, targetSum - A[i], i + 1)) {
return true;
}
}
}
return false;
}
}
相关文章
- java卸载dll,如何在java中卸载Dll?[通俗易懂]
- Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装
- java线程池的面试题_献给准备面试的你,Java线程and线程池面试题小结「建议收藏」
- idea2019开发第一个java程序HelloWorld「建议收藏」
- java注解拦截_轻松实现java拦截器+自定义注解
- java中打印数组的方法_Java数组方法–如何在Java中打印数组
- java 链表长度_Java实现单向链表[通俗易懂]
- java数组排序去重_JAVA数组去重排序
- 做了三年Java,java注释的三种形式
- java启动器_JAVA基础:Java 启动器如何查找类
- java控制台输入数组_Java控制台输入数组并逆序输出的方法实例
- 【说站】java如何定义变量
- JAVA遍历数组的三种方法_java遍历object数组
- java 事务嵌套_Java事务以及嵌套事务[通俗易懂]
- 经验总结Java在ACM算法竞赛编程中易错点详解编程语言
- java线程同步方法详解编程语言
- 使用Java在Linux系统上开发:一步步安装全部组件(java环境linux)
- Linux重装Java:给你的操作系统新的灵魂(linux重装java)
- 操作Redis Java中自动处理过期数据(redisjava过期)
- 使用Redis Java实现过期时间管理(redisjava过期)
- 策略Java利用Redis实现缓存数据过期策略(redisjava过期)
- 机制Redis Java的过期机制实现方法(redisjava过期)
- 在什么情况下,Java比C++慢很多?