首页 > 试题广场 >

数组分组

[编程题]数组分组
  • 热度指数：125257 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 n 个整数 a_1, a_2, \dots, a_n，将其分为 a,b 两个数组，满足：
\hspace{23pt}\bullet\,所有 5 的倍数元素均在 a 数组中；
\hspace{23pt}\bullet\,所有 3 的倍数元素（不包括 5 的倍数）均在 b 数组中；
\hspace{23pt}\bullet\,其他元素可以任意分配。
\hspace{15pt}求解是否存在一种分配方案，使得 a 数组中各个元素之和等于 b 数组中各个元素之和。每一个元素要么在 a 数组中，要么在 b 数组中；数组可以为空，此时和为 0。如果存在这样的方案，输出 \rm true，否则输出 \rm false。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 50\right) 代表给定的整数个数。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(-500 \leqq a_i \leqq 500\right)。


输出描述:
\hspace{15pt}如果存在满足条件的分配方案，输出 \rm true，否则输出 \rm false。
示例1

输入

4
1 5 -5 1

输出

true

说明

\hspace{15pt}在这个样例中，a 数组可以为 \{5, -5, 1\}，b 数组可以为 \{1\}，满足条件。
示例2

输入

3
3 5 8

输出

false
算法知识视频讲解
开通博客
头像 我心态贼好
发表于 2020-07-26 20:53:58
JAVA 先把三和五的倍数都挑出来，算好两边的和sum3和sum5，所有数总和为sum，求出target = sum/2 - sum3，把剩余的数放在一起，转化成在一个list中找能不能凑出target。 import java.util.*; public class Main{ publ 展开全文
去ta的博客 赞 (53) 回复(15) 收起
头像 Clench
发表于 2021-08-19 16:55:12
对递归不太熟 执着于自己的方法 写了大半年 终于写出来了 哭了 def add(sm5,sm3,temp): if len(temp)==0: if sm5==sm3: return True else: re 展开全文
去ta的博客 赞 (48) 回复(13) 收起
头像 明刘
发表于 2021-11-06 03:37:45
# 深度优先递归 # 题目要求将数组分为两组，5和3的倍数不能在同一组内，非5或3的倍数随意放在任意一组，要求分配之后两组和相等 # 根据题意将数组中的5和3分别放到两组中，然后递归穷举所有非5或3的倍数的分组情况 def dfs(three, five, other): if not ot 展开全文
去ta的博客 赞 (42) 回复(7) 收起
头像 牛客最小的小白
发表于 2021-08-28 14:52:28
参考别人的题解先把三和五的倍数都挑出来，算好两边的和sum3和sum5，所有数总和为sum，不是3或5倍数的剩余的数放在集合中。求出target = sum/2-sum3或者target=sum/2-sum5作为目标数，看list中找能不能凑出target。在剩余集合中找target是一个dfs过程 展开全文
去ta的博客 赞 (30) 回复(7) 收起
头像 健康快乐最重要
发表于 2020-03-11 11:49:01
这道题和以前做过的求和是一个思路，凑数(求和)题目如下：链接：https://blog.nowcoder.net/n/a6b71a5651874650a65945e9bae8e5bf这个题是一维的，直接把一段数字进行遍历，然后把能构成的都输出出来就行。在遍历解空间过程中，适当剪枝可以增大程序的时间效 展开全文
去ta的博客 赞 (24) 回复(6) 收起
头像 摸鱼学大师
发表于 2021-11-04 11:15:07
题目的主要信息： 对输入的n个数，询问能否被分成两组，且两组的和相等 其中第一组必须包含所有5的倍数，第二组必须包含3的倍数（不含5的倍数） 其他数字任意放 可以分出空数组，因为正负数和可能为0 方法一：集合枚举 具体做法： 在输入的时候直接开始计算5的倍数的和与3的倍数的和，然后剩余的数字再加 展开全文
去ta的博客 赞 (19) 回复(0) 收起
头像 牛客313925129号
发表于 2021-12-09 14:34:08
题意理解 把一个数组分成两部分（part1、part2），要求两部分的数字之和相等。其中，所有5的倍数（包括3和5的公倍数）要放在同一部分，其余3的倍数要放在同一部分。 让两部分之和相等，等价于从数组中找到一些数，使其和等于总和sum的一半。 方法一 深度优先搜索。 对于每一个数，有2种情况：放入p 展开全文
去ta的博客 赞 (11) 回复(3) 收起
头像 牛客834002708号
发表于 2021-08-14 17:22:55
import java.util.*; public class Main {     public static void main(String[] args) { 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 牛客793258981号
发表于 2021-11-17 17:55:54
1.首先计算3,5倍数的差值，如果3的倍数为+，那么5的倍数为-，反之亦然。把结果放入set{}集合中 2.分别取剩余数值，与之前结果计算，每个数值都可以为+或者-，那么把+，-的结果均放入集合中 3.全部计算完成后，如果0值在结果里，则返回true,否则返回false wh 展开全文
去ta的博客 赞 (9) 回复(5) 收起
头像 wkyang
发表于 2022-03-31 11:41:51
假设分配后已经相等（相加后具有相等初值）， 然后依据条件从两个数组中剔除数据，若全部剔除后，两组剩下的数还是相等则认为可以实现 #include<stdio.h> int solu(int N1,int N2,int arr[],in 展开全文
去ta的博客 赞 (9) 回复(0) 收起

问题信息

字符串 递归
难度：
335条回答 42903浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数组分组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号