题解 | #数组分组#

数组分组

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.IOException;
/**
 * 传入一个int型数组,返回该数组能否分成两组,使得两组中各元素加起来的和相等,
 * 并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数)
 * @author chronos
 *
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        String input;
        while ((input = read.readLine()) != null){
            int n = Integer.parseInt(input);
            
            int[] array = new int[n];
            String[] strs = read.readLine().split(" ");
            for(int i = 0; i < n; i++) {
            	array[i] = Integer.parseInt(strs[i]);
            }
            System.out.println(solution(array));
        }     
	}
	public static boolean solution(int[] array) {
		if(array.length < 2)
			return false;
		
		int sum = 0, sum3 = 0;
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 0; i < array.length; i++) {
        	sum += array[i];
        	if(array[i] % 3 == 0 && array[i] != 0) 
        		sum3 += array[i];
        	else if(array[i] % 5 == 0 && array[i] != 0)
        		continue;
        	else
        		list.add(array[i]);
        }
		if(sum % 2 != 0)
			return false;
		
		int num1 = sum / 2 - sum3;   //第一个数组差的数
		
		return dfs(list, num1, 0);
//		int len = list.size();
//		int[] remainder = new int[len];
//		for(int i = 0; i < len; i++) {
//			remainder[i] = list.get(i);
//		}
//		Arrays.sort(remainder);

		//在剩下的数字中找到和为num1的,如果没有返回false
		
		 
	}
	private static boolean dfs(List<Integer> bag, int target, int i) {
		if (i == bag.size()) 
        	return target == 0;
        // dfs搜索,对每个元素,选择或者放弃
        return dfs(bag, target, i + 1) || dfs(bag, target - bag.get(i), i + 1);
    }
}

全部评论

相关推荐

真tmd的恶心,1.面试开始先说我讲简历讲得不好,要怎样讲怎样讲,先讲背景,再讲技术,然后再讲提升多少多少,一顿说教。2.接着讲项目,我先把背景讲完,开始讲重点,面试官立即打断说讲一下重点,无语。3.接着聊到了项目的对比学习的正样本采样,说我正样本采样是错的,我解释了十几分钟,还是说我错的,我在上一家实习用这个方法能work,并经过市场的检验,并且是顶会论文的复现,再怎么不对也不可能是错的。4.面试官,说都没说面试结束就退出会议,把面试者晾在会议里面,丝毫不尊重面试者难受的点:1.一开始是讲得不好是欣然接受的,毕竟是学习。2.我按照面试官的要求,先讲背景,再讲技术。当我讲完背景再讲技术的时候(甚至已经开始蹦出了几个技术名词),凭什么打断我说讲重点,是不能听出人家重点开始了?这也能理解,每个人都有犯错,我也没放心上。3.我自己做过的项目,我了解得肯定比他多,他这样贬低我做过的项目,说我的工作是错误的,作为一个技术人员,我是完全不能接受的,因此我就和他解释,但无论怎么解释都说我错。凭什么,作为面试官自己不了解相关技术,别人用这个方式work,凭什么还认为这个方法是错的,不接受面试者的解释。4.这个无可厚非,作为面试官,不打招呼就退出会议,把面试者晾着,本身就是有问题。综上所述,我现在不觉得第一第二点也是我的问题,面试官有很大的问题,就是专门恶心人的,总结面试官说教,不尊重面试者,打击面试者,不接受好的面试者,技术一般的守旧固执分子。有这种人部门有这种人怎么发展啊。最后去查了一下,岗位关闭了。也有可能是招到人了来恶心人的,但是也很cs
牛客20646354...:招黑奴啊,算法工程师一天200?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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