首页 > 其他分享 >2024-03-27:用go语言,多维费用背包。 给你一个二进制字符串数组 strs 和两个整数 m 和 n, 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个

2024-03-27:用go语言,多维费用背包。 给你一个二进制字符串数组 strs 和两个整数 m 和 n, 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个

时间:2024-03-27 21:47:22浏览次数:32  
标签:03 arr return strs len int go dp

2024-03-27:用go语言,多维费用背包。

给你一个二进制字符串数组 strs 和两个整数 m 和 n,

请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集。

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3。

输出:4。

答案2024-03-27:

来自左程云

灵捷3.5

大体步骤如下:

1.findMaxForm1 函数使用递归的方式实现。它遍历字符串数组 strs,将每个字符串中0和1的数量存储在一个二维数组 arr 中。然后通过递归函数 process1 进行计算,不断比较所选字符串是否符合要求,选择放入或不放入子集。该方法的时间复杂度为O(2^n),空间复杂度为O(n)。

2.findMaxForm2 函数使用记忆化搜索的方式实现。它也遍历字符串数组 strs 得到二维数组 arr,但使用三维数组 dp 进行记忆化,记录已经计算过的结果,避免重复计算。该方法的时间复杂度为O(m * n * len(strs)),空间复杂度为O(m * n * len(strs))。

3.findMaxForm3 函数使用动态规划的方式实现。它从后向前遍历字符串数组 strs,得到二维数组 dp 来保存计算结果。通过比较选择当前字符串加入子集还是不加入子集,并更新动态规划数组 dp。该方法的时间复杂度为O(m * n * len(strs)),空间复杂度为O(m * n * len(strs))。

4 findMaxForm4 函数使用动态规划的方式实现。它遍历字符串数组 strs,得到二维数组 dp 来保存计算结果。使用一维数组 dp 进行滚动更新,从后向前遍历,根据当前字符串的0和1的数量,更新动态规划数组 dp。该方法的时间复杂度为O(m * n * len(strs)),空间复杂度为O(m * n)。

总时间复杂度:O(m * n * len(strs))

总额外空间复杂度:O(m * n * len(strs))

Go完整代码如下:

package main

import (
	"fmt"
)

var zeros, ones int

func findMaxForm1(strs []string, m int, n int) int {
	len := len(strs)
	arr := make([][]int, len)
	for i := 0; i < len; i++ {
		zeroAndOne(strs[i])
		arr[i] = []int{zeros, ones}
	}
	return process1(arr, 0, m, n)
}

func process1(arr [][]int, i int, z int, o int) int {
	if i == len(arr) {
		return 0
	}
	p1 := process1(arr, i+1, z, o)
	p2 := 0
	if arr[i][0] <= z && arr[i][1] <= o {
		p2 = 1 + process1(arr, i+1, z-arr[i][0], o-arr[i][1])
	}
	if p1 > p2 {
		return p1
	}
	return p2
}

func findMaxForm2(strs []string, m int, n int) int {
	len := len(strs)
	arr := make([][]int, len)
	for i := 0; i < len; i++ {
		zeroAndOne(strs[i])
		arr[i] = []int{zeros, ones}
	}
	dp := make([][][]int, len)
	for i := 0; i < len; i++ {
		dp[i] = make([][]int, m+1)
		for j := 0; j <= m; j++ {
			dp[i][j] = make([]int, n+1)
			for k := 0; k <= n; k++ {
				dp[i][j][k] = -1
			}
		}
	}
	return process2(arr, 0, m, n, dp)
}

func process2(arr [][]int, i int, z int, o int, dp [][][]int) int {
	if i == len(arr) {
		return 0
	}
	if dp[i][z][o] != -1 {
		return dp[i][z][o]
	}
	p1 := process2(arr, i+1, z, o, dp)
	p2 := 0
	if arr[i][0] <= z && arr[i][1] <= o {
		p2 = 1 + process2(arr, i+1, z-arr[i][0], o-arr[i][1], dp)
	}
	ans := p1
	if p2 > p1 {
		ans = p2
	}
	dp[i][z][o] = ans
	return ans
}
func findMaxForm3(strs []string, m int, n int) int {
	len0 := len(strs)
	dp := make([][][]int, len0+1)
	for i := len0; i >= 0; i-- {
		dp[i] = make([][]int, m+1)
		for z := 0; z <= m; z++ {
			dp[i][z] = make([]int, n+1)
		}
	}
	for i := len0 - 1; i >= 0; i-- {
		zeroAndOne(strs[i])
		for z := 0; z <= m; z++ {
			for o := 0; o <= n; o++ {
				dp[i][z][o] = dp[i+1][z][o]
				if zeros <= z && ones <= o {
					dp[i][z][o] = max(dp[i][z][o], 1+dp[i+1][z-zeros][o-ones])
				}
			}
		}
	}
	return dp[0][m][n]
}

func zeroAndOne(str string) {
	zeros = 0
	ones = 0
	for i := 0; i < len(str); i++ {
		if str[i] == '0' {
			zeros++
		} else {
			ones++
		}
	}
}

func findMaxForm4(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	for _, s := range strs {
		zeroAndOne(s)
		for i := m; i >= zeros; i-- {
			for j := n; j >= ones; j-- {
				dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
			}
		}
	}
	return dp[m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	strs := []string{"10", "0001", "111001", "1", "0"}
	m := 5
	n := 3

	res1 := findMaxForm1(strs, m, n)
	fmt.Println("findMaxForm1:", res1)

	res2 := findMaxForm2(strs, m, n)
	fmt.Println("findMaxForm2:", res2)

	res3 := findMaxForm3(strs, m, n)
	fmt.Println("findMaxForm3:", res3)

	res4 := findMaxForm4(strs, m, n)
	fmt.Println("findMaxForm4:", res4)
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

def zero_and_one(string):
    zeros = 0
    ones = 0
    for char in string:
        if char == '0':
            zeros += 1
        else:
            ones += 1
    return zeros, ones

def find_max_form1(strs, m, n):
    length = len(strs)
    arr = []
    for i in range(length):
        zeros, ones = zero_and_one(strs[i])
        arr.append((zeros, ones))
    return process1(arr, 0, m, n)

def process1(arr, i, z, o):
    if i == len(arr):
        return 0
    p1 = process1(arr, i+1, z, o)
    p2 = 0
    if arr[i][0] <= z and arr[i][1] <= o:
        p2 = 1 + process1(arr, i+1, z-arr[i][0], o-arr[i][1])
    if p1 > p2:
        return p1
    return p2

def find_max_form2(strs, m, n):
    length = len(strs)
    arr = []
    for i in range(length):
        zeros, ones = zero_and_one(strs[i])
        arr.append((zeros, ones))
    dp = [[[-1] * (n+1) for _ in range(m+1)] for _ in range(length)]
    return process2(arr, 0, m, n, dp)

def process2(arr, i, z, o, dp):
    if i == len(arr):
        return 0
    if dp[i][z][o] != -1:
        return dp[i][z][o]
    p1 = process2(arr, i+1, z, o, dp)
    p2 = 0
    if arr[i][0] <= z and arr[i][1] <= o:
        p2 = 1 + process2(arr, i+1, z-arr[i][0], o-arr[i][1], dp)
    ans = p1
    if p2 > p1:
        ans = p2
    dp[i][z][o] = ans
    return ans

def find_max_form3(strs, m, n):
    length = len(strs)
    dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(length+1)]
    for i in range(length-1, -1, -1):
        zeros, ones = zero_and_one(strs[i])
        for z in range(m+1):
            for o in range(n+1):
                dp[i][z][o] = dp[i+1][z][o]
                if zeros <= z and ones <= o:
                    dp[i][z][o] = max(dp[i][z][o], 1 + dp[i+1][z-zeros][o-ones])
    return dp[0][m][n]

def find_max_form4(strs, m, n):
    dp = [[0] * (n+1) for _ in range(m+1)]
    for s in strs:
        zeros, ones = zero_and_one(s)
        for i in range(m, zeros-1, -1):
            for j in range(n, ones-1, -1):
                dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
    return dp[m][n]

strs = ["10", "0001", "111001", "1", "0"]
m = 5
n = 3

res1 = find_max_form1(strs, m, n)
print("findMaxForm1:", res1)

res2 = find_max_form2(strs, m, n)
print("findMaxForm2:", res2)

res3 = find_max_form3(strs, m, n)
print("findMaxForm3:", res3)

res4 = find_max_form4(strs, m, n)
print("findMaxForm4:", res4)

在这里插入图片描述

标签:03,arr,return,strs,len,int,go,dp
From: https://www.cnblogs.com/moonfdd/p/18100298

相关文章

  • .NET周刊【3月第3期 2024-03-24】
    国内文章Garnet:力压Redis的C#高性能分布式存储数据库https://www.cnblogs.com/InCerry/p/18083820/garnet_introduce微软研究院开源了一个名为Garnet的C#项目,实现了Redis协议,允许客户端无需修改直接替换Redis。Garnet基于C#.NET8.0开发,致力于提供极速、可扩展和低延迟的缓存......
  • 20240327打卡
    第五周第一天第二天第三天第四天第五天第六天第七天所花时间20h4h4h代码量(行)877164371博客量(篇)111知识点了解navigation路由配置,jetpackcompose组件运用,容器封装第一次结对作业开始Web搓后端ing~主要完成了用户登录与管......
  • 推荐 10 个非常有用的 Golang Libraries
    推荐10个非常有用的GolangLibraries原创 GoOfficialBlog GoOfficialBlog 2024-03-2518:16 山东 听全文Go语言的标准库非常好用。通常情况下,你不需要任何额外的库来完成任务。但是在某些情况下,可能需要使用一些库。今天将与你分享日常工作中很有用的10个......
  • 20240320-2-线性回归+逻辑回归
    线性回归于逻辑回归面试题1.简单介绍一下线性回归。**线性回归(LinearRegression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。**这种函数是一个或多个称为回归系数的模型参数的线性组合。只有一个自变量的情况称......
  • go: embed
    go:embed​go:embed​是Go语言在其1.16版本中引入的一个新功能,它允许开发者在编译时将文件或文件夹嵌入到Go程序中。这样做可以简化资源文件的分发,因为它们会被编译到可执行文件里,避免了在运行时需要处理文件路径和分发额外文件的问题。要使用go:embed​,你需要做以下几......
  • P1036 [NOIP2002 普及组] 选数
    思路:也算典型的dfs,题目就是要求从n个数中选择k个数,计算这k个数的和,看这个和是否是素数。我们知道在dfs时相当于是进行全排列,而结果要求的是组合后和的情况。根据排列和组合的关系,他们之间差K!倍,所以需要在dfs求得个数cnt后除以k!。题目:AC代码:#include<algorithm>#include<io......
  • Java 发送邮件(2024-03)
    1\2\packageorg.jeecg.common.util.io;importcom.sun.mail.util.MailSSLSocketFactory;importlombok.extern.slf4j.Slf4j;importorg.jeecg.common.util.DateUtils;importjavax.activation.DataHandler;importjavax.activation.DataSource;importjavax.acti......
  • C. Theofanis' Nightmare
    原题链接题解太巧妙了!!层加式?code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lla[100005]={0};intmain(){llt;cin>>t;while(t--){lln;cin>>n;for(inti=1;i<=n;i++)cin>&g......
  • 巴旦木(美国大杏仁)到2030年市场规模将接近708亿元
    一、市场趋势分析作为一种健康且多功能的坚果,巴旦木(又称美国大杏仁)在全球范围内因其营养价值和美味口感而受到消费者的青睐。随着健康食品趋势的兴起,巴旦木的需求持续增长,尤其在零食和烘焙行业中被广泛应用。二、主要竞争者概览市场上的主要竞争来自拥有强大种植和加工能力......
  • Pillow教程03:图像处理的基本步骤+分离split+合并merge+混合blend+composite遮罩
    --------------Pillow教程集合---------------Python项目18:使用Pillow模块,随机生成4位数的图片验证码Python教程93:初识Pillow模块(创建Image对象+查看属性+图片的保存与缩放)Pillow教程02:图片的裁剪+复制粘贴+旋转角度+翻转+降噪滤镜(平滑、锐化、边缘检测)Pillow教程03:图像......