[编程题]数组分组
- 热度指数：128786 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表给定的整数个数。
个整数
。
输出描述:
，否则输出
。
示例1
输入
4 1 5 -5 1
输出
true
说明
数组可以为
，
数组可以为
，满足条件。
示例2
输入
3 3 5 8
输出
false
我写的一般哈，技术有限，这题应该是先算5和3那个数组的差值，剩下的元素放到第三个集合里面，用01背包问题的解法，找到其中的一部分放入背包，让重量等于（集合三的总重量+前两个集合重量的差值）/2
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int cluba=0,clubb=0;
ArrayList<Integer> an=new ArrayList<>();
for(int i=0;i<n;++i){
int a1=in.nextInt();
if(a1%5==0){
cluba+=a1;
}else if(a1%3==0){
clubb+=a1;
}else{
an.add(a1);
}
}
int diff=cluba-clubb;
int sums=0;
for(int i=0;i<an.size();++i){
sums+=an.get(i);
}
if(((diff+sums)&1)==1){
System.out.println(false);
}else{
if(dfs(an,(diff+sums)/2,new boolean[an.size()],0)){
System.out.println(true);
}else{
System.out.println(false);
}
}
}
private static boolean dfs(ArrayList<Integer>aa,int target,boolean used[],int nowweight){
if(nowweight==target)return true;
for(int i=0;i<aa.size();++i){
if(!used[i]){
used[i]=true;
if(dfs(aa,target,used,nowweight+aa.get(i)))return true;
used[i]=false;
}
}
return false;
}
}
发表于 2025-08-08 17:03:36
回复(0)
把5倍数和3倍数分别放到两个集合中并分别对集合总和求和，把剩余元素放到第三个集合里。
如果在第三个集合存在一个组合，使得sum / 2 - sum3，说明结果为true。
这里我们用回溯遍历第三个集合，找到target值则返回true，否则 返回false
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int[] nums = new int[n];
int sum = 0;
for (int i = 0; i < n; i++){
int num = in.nextInt();
sum += num;
nums[i] = num;
}
List<Integer> leftList = new ArrayList<>();
List<Integer> times3List = new ArrayList<>();
List<Integer> times5List = new ArrayList<>();
int sum5 = 0, sum3 = 0;
for (int num : nums){
if (num % 5 == 0){
times5List.add(num);
sum5 += num;
}else if (num % 3 == 0 && num % 5 != 0){
times3List.add(num);
sum3 += num;
}else leftList.add(num);
}
int target = sum / 2 - sum3;
if (sum % 2 != 0) {
System.out. println("false");
continue;
}
backtracking(leftList, 0, 0, target);
boolean res = backtracking(leftList, 0, 0, target);
System.out.println(res);
}
}
private static boolean backtracking(List<Integer> leftList, int startindex, int res, int target){
if (res == target){
return true;
}
for (int i = startindex; i < leftList.size(); i++){
if (backtracking(leftList, i + 1, res + leftList.get(i), target)){
return true;
}
}
return false;
}
}
发表于 2025-07-28 03:04:35
回复(0)
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)
问题信息
难度：
49条回答
2075收藏
44247浏览
通过挑战的用户
查看代码-
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号
