每日一题 LeetCode 474. 一和零 java题解
2021/6/6 14:23:06
本文主要是介绍每日一题 LeetCode 474. 一和零 java题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
https://leetcode-cn.com/problems/ones-and-zeroes/
1.未优化的动态规划
思路
动态规划。
用dp[i][j][k]表示前i个字符串中 j个0、k个1的最大子集大小 。下标均从1开始计数。
当i=0时,没有字符串,所以dp[i][j][k]=0。
转移方程
这个字符串的0和1个数分别为zeros,ones.
1.j>=zeros&&k>=ones
(1)向子集中加入这个字符串
dp[i][j][k]=dp[i-1][j-zeros][k-ones]+1
(2)不向子集中加入
dp[i][j][k]=dp[i-1][j][k]
综上,dp[i][j][k]=min(dp[i-1][j-zeros][k-ones]+1,dp[i][j][k]=dp[i-1][j][k]);
2.else
dp[i][j][k]=dp[i-1][j][k]
代码
class Solution { public int findMaxForm(String[] strs, int m, int n) { int len=strs.length; if(len==0) return 0; int[][][] dp=new int[len+1][m+1][n+1]; /* for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ dp[0][j][k]=0; } } */ for(int i=1;i<=len;i++){ int zeros=count(strs[i-1]); int ones=strs[i-1].length()-zeros; for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ dp[i][j][k]=dp[i-1][j][k]; if(j>=zeros&&k>=ones){ dp[i][j][k]=Math.max(dp[i-1][j-zeros][k-ones]+1,dp[i][j][k]); } } } } return dp[len][m][n]; } //统计0的个数 public int count(String s){ int count=0; for(char c:s.toCharArray()){ if(c=='0'){ count++; } } return count; } }
复杂度
时间复杂度:O(lmn+L),其中 l 是数组 strs 的长度,m 和 n 分别是 0 和 1 的容量,L 是数组 strs 中的所有字符串的长度之和。
空间复杂度 O(lmn)
2.空间优化
复杂度
空间复杂度:O(mn),其中 m 和 n 分别是 0 和 1 的容量。使用空间优化的实现,需要创建 m+1 行 n+1 列的二维数组dp。
代码
由于dp[i][][] 的每个元素值的计算只和dp[i−1][][] 的元素值有关,因此可以使用滚动数组的方式,去掉 dp 的第一个维度,将空间复杂度优化到 O(mn)。
实现时,内层循环需采用倒序遍历的方式,这种方式保证转移来的是dp[i−1][][] 中的元素值。
public int findMaxForm(String[] strs, int m, int n) { int[][] dp = new int[m + 1][n + 1]; int length = strs.length; for (int i = 0; i < length; i++) { int[] zerosOnes = getZerosOnes(strs[i]); int zeros = zerosOnes[0], ones = zerosOnes[1]; for (int j = m; j >= zeros; j--) { for (int k = n; k >= ones; k--) { dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1); } } } return dp[m][n]; }
这篇关于每日一题 LeetCode 474. 一和零 java题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现