算法题求助

HJ93

描述

输入int型数组,询问该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),不是5的倍数也不是3的倍数能放在任意一组,可以将数组分为空数组,能满足以上条件,输出true;不满足时输出false。

数据范围:每个数组大小满足 1 \le n \le 50 \1n50  ,输入的数据大小满足 |val| \le 500 \val500 

输入描述:

第一行是数据个数,第二行是输入的数据

输出描述:

返回true或者false

// 先把三和五的倍数都挑出来,算好两边的和sum3和sum5,所有数总和为sum,不是3或5倍数的剩余的数放在集合中。
// 求出target = sum/2-sum3或者target=sum/2-sum5作为目标数,看list中找能不能凑出target。
// 在剩余集合中找target是一个dfs过程

// 终止条件,用完集合数,返回target==0

// 两种递归情况

// --选择start位置,递归找新目标数target-list.get(start)

// --不选择start位置,在start+1和以后位置找target
// 特例:sum不是2的倍数,不可等分成两份,直接输出false

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
            //根据输入计算sum3,sum5和所有数总和sum,同时把不是5和3倍数的剩余数放入集合
            List<Integer> list = new LinkedList<>();
            int n = in.nextInt();
            int sum5=0, sum3=0, sum = 0;
            for (int i = 0; i < n; i++){
                int cur = in.nextInt();//输入
                if (cur % 5 == 0){//5倍数和
                    sum5 += cur;
                }else if (cur % 3 == 0){//3倍数和
                    sum3 += cur;
                }else{//剩余加入集合
                    list.add(cur);
                }
                sum += cur;//总和
            }

            //特例,总和不是2的倍数,不可分2份和相等的数字
            if(sum%2!=0) System.out.println("false");
            else{//否则,在剩余数中找目标数字
                int target = sum/2 - sum3;//也可以是sum/2-sum5
                System.out.println(helper(list, target, 0));
            }
        
    }

    private static boolean helper(
            List<Integer> list, int target, int start){
        if (start == list.size())
            return target == 0;//终止条件

        //选择start位置,递归找新目标数target-list.get(start), 或者不选择start位置,在后面位置找target
        return helper(list, target-list.get(start),
                start+1) || helper(list, target, start+1);
    }
}
为什么程序运行到以下地方还会继续运行呢?遇到rerurn不应该退出吗?(倒数第六行)我的测试数据是5(总共五个数),5,3,1,  1,  2
return target == 0

#java实习##笔试题目##Java#
全部评论
这种数字比较多(50个)一般就不能dfs枚举了,所有数的和的值范围小(50×500=25000)所以可以考虑背包。
1 回复 分享
发布于 2022-05-08 03:52
递归结束的条件不对吧,你这样写找到target后还会继续往后找,target会减成负数。我理解结束条件,一个是找到了 target==list. get(i); return true; 一个是没找到 start==list. size()-1 && target !=list. get(i); return flse;
点赞 回复 分享
发布于 2022-05-26 12:43

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

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