474 Ones and Zeroes 一和零
2024-09-06 15:55:31
在计算机界中,我们总是追求用有限的资源获取最大的收益。
现在,假设你分别支配着 m 个 0 和 n 个 1。另外,还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ,找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出,即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10",但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
详见:https://leetcode.com/problems/ones-and-zeroes/description/
C++:
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n)
{
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (string str : strs)
{
int zeros = 0, ones = 0;
for (char c : str)
{
(c == '0') ? ++zeros : ++ones;
}
for (int i = m; i >= zeros; --i)
{
for (int j = n; j >= ones; --j)
{
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
};
参考:https://www.cnblogs.com/grandyang/p/6188893.html
最新文章
- Android中的内容提供器
- ORA-01034错误:ORALCE NOT CONNECT
- Python Decorator 和函数式编程
- js的url中传递中文参数乱码,如何获取url中参数问题
- mysql编码详解
- phpMyAdmin导入本地数据库
- Highcharts 基本曲线图
- Oracle的完整练习,纯手工打字,可能有一两点错误。。。
- nginx反向代理与负载均衡
- selenium WebDriver 八种定位方式源码
- 学号20175212 《Java程序设计》第7周学习总结
- 开发vue单页面Demo
- Vim 学习
- L275 Climate Change Is Having a Major Impact on Global Health
- xcode工程编译错误:missing required architecture i386 解决方法
- jquery formValidator 表单验证插件, ajax无法传值到后台问题的解决
- 最新!2016中国城市GDP排名出炉
- MATLAB(2)——小波工具箱使用简介
- 基于jQuery/CSS3实现拼图效果的相册插件
- 如果你不知道这11款常见的Web应用程序框架 就说明你out了
热门文章
- MapReduce算法形式五:TOP—N
- __sizeof__()
- Tomcat启动报:invalid LOC header (bad signature)的问题
- I2S
- js中的逻辑与(&;&;)与逻辑或(||)
- Getting Started with xUnit.net (desktop)
- WAS:修改jsp编译器用JDK5.0
- 第三届蓝桥杯C++B组省赛
- 理解Objective-C Runtime(四)Method Swizzling
- 行内元素变成会计元素block和inline-block的区别