题解 | #数组分组#

数组分组

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

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();
            List<Integer> list = new ArrayList();
            while (in.hasNextInt()) {
                list.add(in.nextInt());
            }
            List<Integer> left = new ArrayList();
            List<Integer> right = new ArrayList();
            int leftSum = 0, rightSum = 0, total = 0;
            for (Integer item : list) {
                if (item % 5 == 0) {
                    left.add(item);
                    leftSum += item;
                }
                if (item % 3 == 0) {
                    right.add(item);
                    rightSum += item;
                }
                total += item;
            };
            // 左右高度差
            int sum = Math.abs(rightSum) - Math.abs(leftSum) > 0 ? rightSum-leftSum: leftSum-rightSum;

            list.removeAll(left);
            list.removeAll(right);
            // 剩余列表中空的,则提前结束
            if (sum == 0 && list.size() == 0) {
                System.out.println(true);
                return;
            }
           // 奇数不满足条件
            if (total % 2 != 0) {
                System.out.println(false);
                return;    
            }
             // 求t,  leftSum+t+rightSum+t+sum = total
            int t = (total - leftSum - rightSum - sum) / 2;
            int remainSum = list.stream().mapToInt(i->i).sum();
            // 是否存在 前i个元素内子集和为t
            System.out.println(search(list, t, list.size() - 1));

        }
    }
    //是否存在 前i个元素内的子集和为t
    protected static boolean search(List<Integer> list, int target, int i) {
        if (target == 0) {
            return true;
        }
        if (i == 0) {
            return target == list.get(0) ;
        }
        // 不选择 第i个元素 或 选择
        return search(list, target, i - 1) || search(list, target - list.get(i), i - 1);

    }


}

全部评论

相关推荐

争当牛马还争不上
码农索隆:1.把简历改哈 2.猛投,狠投 3.把基础打牢 这样你在有机会的时候,才能抓住
点赞 评论 收藏
分享
_mos_:我以为手抄报简历就已经很顶了,没想到还有表格简历
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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