• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

互联网 diligentman 3个月前 (02-25) 32次浏览










福大大架构师每日一题的个人空间
/
福大大架构师每日一题
/

正文

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

原创
福大大架构师每日一题
福大大架构师每日一题
31分钟前
阅读数 3

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个集合的累加和接近,返回最接近的情况下,较小集合的累加和。

福哥答案2020-02-25:
自然智慧即可。
1.递归。有代码。
2.动态规划。dp是三维数组。有代码。

代码用golang编写,代码如下:

package main

import "fmt"

const INT_MAX = int(^uint(0) >> 1)
const INT_MIN = ^INT_MAX

func main() {
   
    arr := []int{
   1, 2, 3, 4, 100}
    ret := right1(arr)
    fmt.Println("1.递归:", ret)
    ret = right2(arr)
    fmt.Println("2.动态规划:", ret)
}

func right1(arr []int) int {
   
    if len(arr) < 2 {
   
        return 0
    }
    sum := 0
    for _, v := range arr {
   
        sum += v
    }
    if len(arr)&1 == 0 {
   
        return process1(arr, 0, len(arr)/2, sum/2)
    } else {
   
        ret1 := process1(arr, 0, len(arr)/2, sum/2)
        ret2 := process1(arr, 0, len(arr)/2+1, sum/2)
        if ret1 < ret2 {
   
            return ret2
        } else {
   
            return ret1
        }
    }
}
func process1(arr []int, i int, picks int, rest int) int {
   
    if i == len(arr) {
   
        if picks == 0 {
   
            return 0
        } else {
   
            return -1
        }
    } else {
   
        p1 := process1(arr, i+1, picks, rest)
        p2 := -1
        next := -1
        if arr[i] <= rest {
   
            next = process1(arr, i+1, picks-1, rest-arr[i])
        }
        if next != -1 {
   
            p2 = arr[i] + next
        }
        return GetMax(p1, p2)
    }
}

func right2(arr []int) int {
   
    if len(arr) < 2 {
   
        return 0
    }
    sum := 0
    for _, v := range arr {
   
        sum += v
    }
    sum >>= 1
    N := len(arr)
    M := (len(arr) + 1) >> 1
    dp := make([][][]int, N)
    for i := 0; i < N; i++ {
   
        dp[i] = make([][]int, M+1)
        for j := 0; j < M+1; j++ {
   
            dp[i][j] = make([]int, sum+1)
            for k := 0; k < sum+1; k++ {
   
                dp[i][j][k] = INT_MIN
            }
        }
    }
    for i := 0; i < N; i++ {
   
        for k := 0; k <= sum; k++ {
   
            dp[i][0][k] = 0
        }
    }
    for k := 0; k <= sum; k++ {
   
        if arr[0] <= k {
   
            dp[0][1][k] = arr[0]
        } else {
   
            dp[0][1][k] = INT_MIN
        }
    }

    for i := 1; i < N; i++ {
   
        for j := 1; j <= GetMin(i+1, M); j++ {
   
            for k := 0; k <= sum; k++ {
   
                dp[i][j][k] = dp[i-1][j][k]
                if k-arr[i] >= 0 {
   
                    dp[i][j][k] = GetMax(dp[i][j][k], dp[i-1][j-1][k-arr[i]]+arr[i])
                }
            }
        }
    }
    return GetMax(dp[N-1][M][sum], dp[N-1][N-M][sum])
}

func GetMin(a int, b int) int {
   
    if a < b {
   
        return a
    } else {
   
        return b
    }
}
func GetMax(a int, b int) int {
   
    if a > b {
   
        return a
    } else {
   
        return b
    }
}

执行结果如下:
2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个


左神java代码
评论

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

2021-01-06:mysql中,我存十亿个手机号码,考虑存储空间和查询效率,用什么类型的字段去存?
2020-12-12:现场写代码,把CPU打满,java和go都行,并解释为什么。
2021-01-19:mysql中,一张表里有3亿数据,未分表,其中一个字段是企业类型,企业类型是一般企业和个体户,个体户的数据量差不多占50%,根据条件把个体户的行都删掉。请问如何操作?
2020-01-15:用户登录,保存30天的免登,只允许两个设备登录,如果有第三个设备登录,踢掉第一个。改密码的时候,所有设备需要下线。这个逻辑怎么实现呢?

加载中

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

取消
发布

更多评论

其他人还在看

更多精彩内容

再见,MySQL!头条、腾讯、快手都在用的OLAP新秀已成气候!

阿里流传着这样一句话,“一切业务数据化,一切数据业务化”。 作为大数据从业者,你一定明白有数据是一回事,可要想让数据发挥价值、成为生产力是另一回事。手里得有两把刷子,才能成为大数据圈儿的“大拿”! …
0
0

Linux sudo权限提升漏洞复现(CVE-2021-3156)

2021年01月27日,RedHat官方发布了sudo 缓冲区/栈溢出漏洞的风险通告,普通用户可以通过利用此漏洞,而无需进行身份验证,成功获取root权限。 据报道这个漏洞已存在十年了,大部分的linux系统都存在这个sudo漏洞。…
1
0

你不知道的mysql的3W法,内附超好用的报表工具

WHAT? 什么是MySQL? MySQL是一种关系型数据库管理系统,关系数据库将数据保存在不同的表中,而不是将所有数据放在一个大仓库内,这样就增加了速度并提高了灵活性。 WHY?为什么需要MySQL工具? MySQL现已经成为大…
0
0

Thinkphp5截取文章标题超过指定长度的方法

可采用substr和mb_substr两种方法。对于mb_substr我们可以设置其截取编码的方式,尤其是中文字符,可避免出现乱码现象。 if(strlen($title)>10){ $str=$substr($title,0,10,’utf-8); $str=$str.’………
0
0

对二五仔的一次病毒分析

不知道哪个同事收到了邮件并打开 邮件附属两个doc文件 打开邮件 好家伙、看这个邮件就指定不对劲 马上查一波、发现乃是钓鱼邮件!!! SHA256:e3939ac53aed2324a1ece27b41dd49218c8f2726a5afa639656c87ce87a36e0…
0
0

Spring 自定义注解玩法大全,从入门到…

程序员的成长之路 互联网/程序员/技术/资料共享 关注 阅读本文大概需要 5 分钟。 作者:何甜甜在吗 链接:https://juejin.im/post/5cf376e16fb9a07eee5eb6eb 在业务开发过程中我们会遇到形形色色的注解,但是框架…
0
0

冬奥气象保障保的是什么?

点击上方蓝字关注我,阅读本文 明年的这个时候,2022年北京冬奥会已经开幕。第24届冬季奥林匹克运动会将于2022年2月4日至2月20日在北京、张家口两个城市闪亮登场。这几天从早到晚忙的我们是“不亦乐乎”。2月4日,…
0
0

我们搞了一个副业社群!

朋友们,大家好! 熟悉我的小伙伴都知道,最早我的工作是做Python开发,每个月拿着一些固定工资,虽然还算不错,但是只能说勉强过日子。 每个月都等着发工资的时间,还各种贷款,信用卡,花呗等等。 18年底因为要…
0
0

处理JavaScript异常的正确姿势

处理JavaScript异常的正确姿势 参考文章: (1)处理JavaScript异常的正确姿势 (2)https://www.cnblogs.com/fundebug/p/7989066.html 备忘一下。…
0
0

一文一点 | 你认为什么是DDD设计方法的基石

这是【一文一点】的第8篇原创文章,不拘泥于篇幅字数,用一篇文章说清一个知识点。 答案是:通用语言和模型驱动。 1、 所有的软件最终是要解决用户问题的,而软件的落地最终是要靠一行行的代码垒起来的,那么这个…
0
0

没有更多内容
加载失败,请刷新页面

点击加载更多
加载中

下一页

关于作者

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个





2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

福大大架构师每日一题
关注

私信
提问

文章
588
经验值
7.3K

粉丝
78
关注
78

作者的专辑

全部

福大大架构师每日一题(588)

源创计划
立即入驻

自媒体入驻开源社区,

获百万流量,打造个人技术品牌

推荐关注

换一批

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

wotrd
文章 26
访问 12.8W

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

爱编程的浪子
文章 76
访问 3.9W

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

12叔
文章 42
访问 14.3W

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

yokol
文章 41
访问 5.9W

2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个

文振熙
文章 173
访问 63.9W

打赏

0 评论


0 收藏

0

微信
QQ
微博

分享

选择专区和圈子:{{title}}
{{o.name}}


{{m.name}}

取消
确定


2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个
2021-02-25:给定一个正数数组arr,请把arr中所有的数分成两个集合。如果arr长度为偶数,两个集合包含数的个数要一样多;如果arr长度为奇数,两个集合包含数的个数必须只差一个。请尽量让两个



喜欢 (0)