Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)

摘要:
805.数组的均值分割给定的整数数组A,我们要将A数组中的每个元素移动到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。

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实现 LeetCode 805 数组的均值分割 (DFS+分析题)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇oracle19c 数据库备份还原[原]SQLite的学习系列之获取数据库版本下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

VB的学习及使用总结

 引言         在最近的一个需求当中,因为要用到VB的缘故,所以有机会了解了一下VB, 老实讲,我不喜欢这样的学习,本人是在一家银行从事外包工作的,主要从事Java 开发, 工作中就是负责好几个项目的运维,因为这些项目做的时间久了一点,再加上客户这边IT也不是很规范,每个系统、项目用到的技术和架构都是不一样的,可以说是百花齐放,所以有时候在一个项目中...

json数据处理技巧(字段带空格、增加字段)

1、json数据的正常取值:json[i].fieldName 2、json数据的字段带空格:eval('json[' + i + ']["' + field + '"]') 3、json数据的赋值:eval('json[' + i + ']["' + field + '"]=' + jsonFilter.length); 4、json数据增加字段:循环...

Numpy---4.数组的存储和加载

一、二进制 1.numpy.save() numpy.save(file, arr, allow_pickle=True, fix_imports=True) 功能:将数组以二进制的形式存储到文件中 参数: file:文件名或者文件对象。如果是个文件名,则会自动添加后缀.npy如果没有该后缀的话 arr:被存储的数组 allow_pickle:一个...

L3-002 特殊堆栈 (30分) vector容器的模拟、vector容器的一些用法

vector容器的简单应用,我们可以用vector维护一个有序数组,每次对要插入的数用upper_bound或者lower_bound来 为这个数找一个应该插入到vector的位置。另外再找一个数组来维护插入数的顺序,来面对pop操作 在从小到大的排序数组中, lower_bound( begin,end,num):从数组的begin位置到end-1位置...

YAML快速入门

docker -compose中使用yaml格式的配置文件,所以准备学习一下这方面的知识,正好网上有一篇写的不错,直接抄了过来,原文连接: https://www.jianshu.com/p/97222440cd08 YAML快速入门 下面立刻展示YAML最基本,最常用的一些使用格式:首先YAML中允许表示三种格式,分别是常量值,对象和数组例如: #即表示...

confirmit平台问题汇总

Html Styles下任意一个复制样式系统命名的问题:  当某个题中某个元素需要单独设置CSS样式时,复制一份全局样式后,引用复制的那个样式scale (2)会失效。原因:系统默认生成的这个class名称其实是两个class名称( )  , 所以我们引用这个样式会失效。解决方案:自己手动改个合适的单独的class名称。 手机端不能直接给input设置...