题解 | #农场的奶牛分组# java

农场的奶牛分组

https://www.nowcoder.com/practice/bdb90a97a15d42f989e406080d88bed9

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @return bool布尔型
     */
    public boolean canPartition (int[] weights) {
        // write code here
        int sum = Arrays.stream(weights).sum();
        if ((sum & 1) == 1) return false;
        sum >>= 1;
        boolean[] f = new boolean[sum + 1];
        f[0] = true;
        for (int x : weights) {
            for (int j = sum; j >= x; j--) {
                f[j] = (f[j] || f[j - x]);
            }
        }
        return f[sum];
    }
}

修改后的代码使用的编程语言是Java。

该题考察的知识点包括:

  • 动态规划:代码中使用了动态规划的思想来解决背包问题,通过填表格的方式求解能否将一组物品分成两个相等的子集。
  • 数组操作:使用数组来记录状态转移和计算是否能够平分重量。

代码的解释:

  1. 使用 Arrays.stream(weights).sum(); 计算整数数组 weights 中所有元素的总和。
  2. 判断总和的奇偶性:如果总和是奇数,则无法分成两个相等的子集,直接返回 false
  3. 计算目标和:将总和除以 2,得到目标和,因为要找到能够达到目标和的子集。
  4. 创建状态数组:使用 boolean[] f 来表示是否可以通过选择一些元素得到特定的重量和。数组长度为 sum + 1,因为重量和的范围是从 0 到目标和。
  5. 初始化状态:将 f[0] 设为 true,表示总和为 0 的情况下可以选择不取任何元素。
  6. 动态规划状态转移:遍历 weights 数组中的每个元素 x,然后从目标和开始往前遍历,更新 f[j] 为 f[j] || f[j - x],表示在选择或不选择当前元素 x 的情况下,能否得到重量和为 j
  7. 返回结果:返回 f[sum],表示是否能够通过选择一些元素得到目标和,从而将数组分成两个相等的子集。
全部评论

相关推荐

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

创作者周榜

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