题解 | #数据分类处理#

数组分组

http://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86

算法渣渣,不会递归、动态规划,突然发现与称砝码那道题思路一样


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            boolean b = test(arr);
            System.out.println(b);
        }
    }


    public static boolean test(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();//存放除了5的倍数和3的倍数之外的数
        int sum1 = 0;//5的倍数总和
        int sum2 = 0;//3的倍数总和(不包括5的倍数)
        int sum = 0;
        for (int j : arr) {
            sum += j;
            if (j % 5 == 0) {
                sum1 += j;
            } else if (j % 3 == 0) {
                sum2 += j;
            } else {
                list.add(j);
            }
        }
        if (sum % 2 != 0) { //总和为奇数,不能分组
            return false;
        } else {
            int mid = sum / 2;
            //在list集合中找出任意个数相加的结果,保存到set集合中(去重)
            //类似于称砝码那道题
            HashSet<Integer> hashSet = new HashSet<>();
            hashSet.add(0);
            for (Integer value : list) {
                ArrayList<Integer> temp = new ArrayList<>(hashSet); //保存上一次累加的结果
                for (Integer integer : temp) {
                    hashSet.add(integer + value);
                }
            }
            //如果有一个数与sum1(或sum2)相加等于总和一半,即可以分组
            for (Integer integer : hashSet) {
                if (integer + sum1 == mid) {
                    return true;
                }
            }
            return false;
        }
    }
}


全部评论
这个不全
点赞 回复 分享
发布于 2022-05-26 11:18

相关推荐

06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务