[编程题]数组分组
- 热度指数：125257 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表给定的整数个数。
个整数
。
输出描述:
，否则输出
。
示例1
输入
4 1 5 -5 1
输出
true
说明
数组可以为
，
数组可以为
，满足条件。
示例2
输入
3 3 5 8
输出
false
Java版本
import java.util.*;
public class Main {
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int n = Integer.parseInt(in.nextLine());
if (n == 0) {
System.out.println("true");
return;
}
// sub为5的倍数的数组元素和与3的倍数的数组元素和之差,初始为0
int sub = 0, sumOfOther = 0;
List<Integer> list = new ArrayList<>();
while (n-- > 0) {
int num = in.nextInt();
if (num % 5 == 0) sub += num;
else if (num % 3 == 0) sub -= num;
else {
sumOfOther += num;
list.add(num);
}
}
sumOfOther = sumOfOther + sub;
if (sumOfOther % 2 != 0) {
System.out.println("false");
return;
}
list.add(sub);
// 至此问题等价于：在list中选出一堆数，使它们的和sum等于sumOfOther/2
// 从0号位置开始选
System.out.println(getTargetSumFromList(list, 0, sumOfOther / 2));
}
}
// list：目标数组，i:待选元素的位置，targetSum：目标和
private static boolean getTargetSumFromList(List<Integer> list, int i,
int targetSum) {
if (targetSum == 0) return true;
if (i == list.size()) return false;
return getTargetSumFromList(list, i + 1, targetSum - list.get(i)) ||
getTargetSumFromList(list, i + 1, targetSum);
}
}
发表于 2025-04-07 16:25:34
回复(0)
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int count=(int)in.nval;
int[] array=new int[count];
int sum=0;
int index1=0;
int index2=0;
for(int i=0;i<count;i++){
in.nextToken();
array[i]=(int)in.nval;
sum+=array[i];
if(array[i]%5==0){
index1=1;
}else if(array[i]%3==0&&array[i]%5!=0){
index2=1;
}
}
if(sum<0){
sum=Math.abs(sum);
for(int i=0;i<count;i++){
array[i]=Math.abs(array[i]);
}
}
if(sum%2==1){
System.out.println(false);
}else if(sum==0){
if(index1==1&&index2==1){ //5的倍数和3的倍数同时存在
System.out.println(false);
}else{
System.out.println(true);
}
}
else{
int target=sum/2;
boolean[] dp=new boolean[1001]; //这里选用j-array[i]可能的最大值来作为背包容量，因为array[i]存在负数
dp[0]=true;
for(int i=0;i<array.length;i++){
for(int j=target;j>=0;j--){
if(array[i]%5!=0){
if(j-array[i]>=0&&dp[j-array[i]]){
dp[j]=true;
}
}
}
}
System.out.println(dp[target]);
}
}
}
} 用背包问题的思想写出来的，需要另外讨论sum==0的情况
发表于 2025-04-03 00:52:41
回复(0)
用例有病，这几个数能得出true?
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// sum5、sum3、list分别存5倍数、3倍数、其他
int sum5 = 0, sum3 = 0;
List<Integer> list = new ArrayList<>();
while (n-- > 0) {
int a = in.nextInt();
if (a % 5 == 0) sum5 += a;
else if (a % 3 == 0) sum3 += a;
else list.add(a);
}
// 调用
System.out.println(fun(sum5, sum3, list, 0));
}
// dfs
public static boolean fun(int sum5, int sum3, List<Integer> list, int k) {
for (int i = k; i < list.size(); i++) {
// list每个数就2种情况：加到sum5或sum3
return fun(sum5 + list.get(i), sum3, list, k + 1) ||
fun(sum5, sum3 + list.get(i), list, k + 1);
}
return sum5 == sum3; // 递归出口：list处理完了
}
}
发表于 2025-03-13 16:32:32
回复(0)
动态规划，勉强过了
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//jichu用来存储即时分割的数据
static Stack<Integer> jinchu = new Stack<>();
//list用来存储任意分配的数值
static ArrayList<Integer> list = new ArrayList<>();
//result用来存储判定结果
static boolean result = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//存储a,b集合的初级处理和
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {
int temp = sc.nextInt();
if (temp % 5 == 0) {
a = a + temp;
} else if (temp % 3 == 0 && temp % 5 != 0) {
b = b + temp;
} else {
list.add(temp);
}
}
int sum=0;
for(int x:list){
sum=sum+x;
}
Panding(a, b, 0, sum, 0);
System.out.print(result);
}
private static void Panding(int a, int b, int aj, int bj, int count) {
if (a + aj == b + bj) {
result = true;
}
if (count < list.size()) {
jinchu.push(list.get(count));
Panding(a, b, aj + list.get(count), bj- list.get(count), count+1);
jinchu.pop();
}
if (!jinchu.isEmpty()) {
int pop = jinchu.pop();
Panding(a, b, aj - pop, bj + pop, count);
jinchu.push(pop);
}
}
} import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//jichu用来存储即时分割的数据
static Stack<Integer> jinchu = new Stack<>();
//list用来存储任意分配的数值
static ArrayList<Integer> list = new ArrayList<>();
//result用来存储判定结果
static boolean result = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//存储a,b集合的初级处理和
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {
int temp = sc.nextInt();
if (temp % 5 == 0) {
a = a + temp;
} else if (temp % 3 == 0 && temp % 5 != 0) {
b = b + temp;
} else {
list.add(temp);
}
}
int sum=0;
for(int x:list){
sum=sum+x;
}
Panding(a, b, 0, sum, 0);
System.out.print(result);
}
private static void Panding(int a, int b, int aj, int bj, int count) {
if (a + aj == b + bj) {
result = true;
}
if (count < list.size()) {
jinchu.push(list.get(count));
Panding(a, b, aj + list.get(count), bj- list.get(count), count+1);
jinchu.pop();
}
if (!jinchu.isEmpty()) {
int pop = jinchu.pop();
Panding(a, b, aj - pop, bj + pop, count);
jinchu.push(pop);
}
}
}
发表于 2025-02-26 02:51:12
回复(0)
import java.util.ArrayList;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int sum_a = 0;
int sum_b = 0;
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < num; i++) {
int n = in.nextInt();
if(n%5==0){
sum_a+=n;
} else if (n%3==0) {
sum_b+=n;
}else {
list.add(n);
}
}
System.out.println(dfs(list,0,sum_a,sum_b));
}
public static boolean dfs(ArrayList<Integer> list,int num,int sumA,int sumB){
if(num>=list.size()) {
if(sumA==sumB)
return true;
else
return false;
}
if(dfs(list,num+1,sumA+list.get(num),sumB))
return true;
if(dfs(list,num+1,sumA,sumB+ list.get(num)))
return true;
return false;
}
}
发表于 2025-02-13 17:26:49
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
// 用递归很方便，但要注意一个坑：如果用remove方法每次都把传入的数组弹出，最终会导致无法恢复现场
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
ArrayList<Integer> normal = new ArrayList<>();
int fivesum = 0, threesum = 0;
for (int i = 0; i < n; i++) {
if (nums[i] % 5 == 0) {;
fivesum += nums[i];
} else if (nums[i] % 3 == 0) {
threesum += nums[i];
} else {
normal.add(nums[i]);
}
}
System.out.println(canEqual(threesum, fivesum, normal, 0));
}
public static boolean canEqual(int three, int five, ArrayList<Integer> normal, int index) {
if (index == normal.size()) {
if (three == five) {
return true;
}
return false;
} else {
int curr = normal.get(index);
return canEqual(three + curr, five, normal, index+1) || canEqual(three, five + curr, normal, index+1);
}
}
}
发表于 2024-10-03 09:35:59
回复(0)
题目分析
3和5在两个数组，求两个数组的差值dis。假设数组A - B = dis;
那么剩余数组项划分成两个数组中 B‘ - A' = dis；B' + A' = sum(剩余项总和)；
B‘ = （sum+dis）/2;
所以问题转换成 剩余数组项中是否存在某些项的和 = target?
问题一：由于剩余项可能为负，target可能为负，不能使用动态规划；
问题二：不要求连续子集，不能使用前缀和；
暴力解决，将当前遍历的所有可能的集和存入set
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 输入
int count = in.nextInt();
int[] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = in.nextInt();
}
// 5 3数组的差值绝对值，剩余项，以及剩余总和
int dis = 0, sum = 0;
List<Integer> rest = new ArrayList<>();
for (int num : arr) {
if (num % 5 == 0) dis += num;
else if (num % 3 == 0) dis -= num;
else {
sum += num;
rest.add(num);
}
}
dis = Math.abs(dis);
// 判断是否剩余rest中某些项的和 = target
boolean f = false;
if (rest.size() == 0 && dis == 0) {
f = true;
} else {
if ((sum + dis) % 2 != 0) {
f = false;
} else {
int target = (sum + dis) / 2;
// 判断一个数组中是否存在某些项的和 = target
Set<Integer> sums = new HashSet<>();
for(int num : rest){
Set<Integer> newSums = new HashSet<>();
for(int s : sums){
int newsum = s + num;
if(newsum == target){
f = true;
break;
}
newSums.add(newsum);
}
if(f) break;
if(num == target){
f = true;
break;
}else{
newSums.add(num);
}
sums.addAll(newSums);
}
}
}
// 打印结果
if (f) {
System.out.println("true");
} else {
System.out.println("false");
}
}
}
发表于 2024-08-29 10:29:05
回复(0)
import java.util.ArrayList;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int count = in.nextInt();
ArrayList ao = new ArrayList();
int sum5 = 0;
int sum3 = 0;
int sumo = 0;
while(in.hasNextInt()){
int a = in.nextInt();
if(a%5 == 0){
sum5 += a;
} else if(a%3 == 0){
sum3 += a;
} else {
ao.add(a);
sumo += a;
}
}
if((sum5 + sum3 + sumo)%2 != 0){
System.out.print(false);
} else {
int sum = (sum3 + sum5 + sumo)/2 -sum5;
if(cansum(ao, ao.size() - 1, sum)){
System.out.print(true);
} else {
System.out.print(false);
}
}
}
private static boolean cansum(ArrayList a, int i, int sum){
if(a.size() == 0 || i < 0){
return sum == 0;
}
return cansum(a, i - 1 , sum) || cansum(a, i - 1, sum - a.get(i));
}
}
发表于 2024-05-23 10:18:03
回复(0)
普通递归就好
import java.util.stream.*;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int total= in.nextInt();
List<Integer> arr5 = new ArrayList(total);
List<Integer> arr3 = new ArrayList(total);
otherArr = new ArrayList(total);
for (int i = 0; i < total; i++) {
int item = in.nextInt();
if (0 == item % 5) {
arr5.add(item);
} else if (0 == item % 3) {
arr3.add(item);
} else {
otherArr.add(item);
}
}
absOf5And3 = Math.abs(arr5.stream().mapToInt(i -> i).sum() -
arr3.stream().mapToInt(i -> i).sum());
otherArrSize = otherArr.size();
if (0 == otherArrSize) {
if (0 == absOf5And3) {
System.out.println("true");
return;
} else {
System.out.println("false");
return;
}
}
signArr = new int[otherArrSize];
IntStream.range(0, otherArrSize).forEach(i -> signArr[i] = -1);
sumAndCheckEqual();
calc(otherArrSize - 1);
}
private static int absOf5And3;
private static List<Integer> otherArr;
private static int otherArrSize;
private static int[] signArr;
private static void sumAndCheckEqual() {
if (absOf5And3 == Math.abs(IntStream.range(0, otherArrSize).map(i -> otherArr.get(i) * signArr[i]).sum())) {
System.out.println("true");
System.exit(0);
}
}
private static void calc(int plusSignSwitchIndex) {
if (0 > plusSignSwitchIndex) {
System.out.println("false");
System.exit(0);
}
if (-1 == signArr[plusSignSwitchIndex]) {
signArr[plusSignSwitchIndex] = 1;
for (int i = 1 + plusSignSwitchIndex; i < otherArrSize; i++) {
signArr[i] = -1;
}
sumAndCheckEqual();
calc(otherArrSize - 1);
} else {
calc(plusSignSwitchIndex - 1);
}
}
}
编辑于 2023-12-07 15:56:27
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static Stack<Integer> stack = new Stack();
public static boolean flag = false;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine());
int[] a = new int[n];
int sum3 = 0;
int sum5 = 0;
for(int i = 0; i < n; i++){
a[i] = in.nextInt();
if(a[i]%3 == 0){
sum3 += a[i];
}else if(a[i] % 5 == 0){
sum5 += a[i];
}else{
stack.push(a[i]);
}
}
dfs(sum3, sum5);
System.out.println(flag);
}
public static void dfs(int sum3, int sum5) {
if (stack.empty() && sum3 == sum5) {
flag = true;
}
if (!stack.empty()) {
int n = stack.pop();
dfs(sum3+n, sum5);
dfs(sum3, sum5+n);
stack.push(n);
}
}
}
发表于 2023-11-28 17:45:46
回复(0)
// 用的递归，很方便，不知道正确性，欢迎大家指正
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
boolean result = canPartition(nums, 0, 0, 0);
System.out.println(result ? "true" : "false");
}
in.close();
}
// 递归的方式解决，index表示当前的数字在数组中的位置，sum1表示第一组数的和，sum2表示第二组数的和
private static boolean canPartition(int[] nums, int index, int sum1, int sum2) {
// 递归的终止条件，当遍历到最后一位时，检查sum1是否等于sum2，如相等，则返回true
if (index == nums.length) {
return Math.abs(sum1 - sum2) == 0;
}
// 将5放进第一组数，sum1加上该数，index + 1表示遍历到下一组数
if (nums[index] % 5 == 0) {
return canPartition(nums, index + 1, sum1 + nums[index], sum2);
} else if (nums[index] % 3 == 0) { //将3放进第二组数
return canPartition(nums, index + 1, sum1, sum2 + nums[index]);
} else {
// 尝试把非3非5的数放进第一组
if (canPartition(nums, index + 1, sum1 + nums[index], sum2)) {
return true;
}
// 尝试把非3非5的数放进第二组
if (canPartition(nums, index + 1, sum1, sum2 + nums[index])) {
return true;
}
}
// 所有的方法都没法分，返回false
return false;
}
}
发表于 2023-07-23 03:10:26
回复(0)
import java.io.*;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
int n = Integer.parseInt(str);
String[] strArr = br.readLine().split(" ");
ArrayList<Integer> list = new ArrayList<>();
int sum3=0,sum5=0,sum=0;
for (String s : strArr){
int num=Integer.parseInt(s);
// 3的倍数则加到sum3
if(num%3==0) sum3 += num;
// 5的倍数则加到sum5
else if(num%5==0) sum5 += num;
// 不是3、5的倍数则加到集合中
else list.add(num);
// 所有数之和
sum+=num;
}
// 两个相等的数之和为偶数，如果sum不为偶数，说明两个数组的和不相等
if(sum%2!=0) System.out.println(false);
else{
// target代表能与sum3相加得到sum/2的值，即判断list是否存在和或值为target的元素，
// 即用list的元素凑出target
// 假设存在满足条件的元素，则得：sum=sum3+sum5+c（list的元素和）和sum/2=sum3+a
// 由此可得sum/2=sum5+（c-a），即若能凑出a使得sum/2=sum3+a，则list剩余元素和+sum5
// 必等于sum/2，所以target可以为sum/2-sum3或者sum/2-sum5
int target=sum/2-sum3;
System.out.println(solution(list,target,0));
}
}
}
private static boolean solution(List<Integer>list, int target, int index) {
// 递归终止条件
if (index == list.size()) return target==0;
// 核心在target-list.get(index)，在solution(list,target-list.get(index),index+1)中
// 由于index+1，所以它会依次减去list中的元素，直到index == list.size()（即减完最后一个元素），
// 而solution(list,target,index+1)则表示跳过第index个元素进入递归，即target不减第index个元素，
// 所以每次递归都会出现减或者不减第index个元素的情况，因此递归终止时，完成了对list中元素所有可能类型
// 的拼凑。当index == list.size()递归终止时，如果 target==0，说明能在list元素中凑出sum/2-sum3。
// 可对list={1,2,5,7}进行纸上递归计算演示
return solution(list,target-list.get(index),index+1)||solution(list,target,index+1);
}
}
发表于 2023-07-12 16:33:40
回复(0)
问题信息
难度：
47条回答
2017收藏
42902浏览
通过挑战的用户
查看代码-
2022-09-16 11:42:25 -
2022-09-16 10:19:55 -
2022-09-16 09:40:07 -
2022-09-15 23:57:39
-
2022-09-15 23:44:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
