Week 10 - 474. Ones and Zeroes
2024-08-27 19:52:16
474. Ones and Zeroes
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s
and n 1s
respectively. On the other hand, there is an array with strings consisting of only 0s
and 1s
.
Now your task is to find the maximum number of strings that you can form with given m 0s
and n 1s
. Each 0 and 1 can be used at most once.
Note:
- The given numbers of 0s and 1s will both not exceed 100
- The size of given string array won't exceed 600.
Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2:
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
my solution:
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> list;
bool flag = true;
for (vector<string>::iterator i = strs.begin(); i != strs.end(); i++) {
int count0 = 0, count1 = 0;
for (auto p : *i) { if (p == '0') count0++; else count1++; }
if ((m >= count0 && n >= count1)) {
flag = false;
vector<string> strs_cp = strs;
strs_cp.erase(strs_cp.begin() + (i - strs.begin()));
list.push_back(1 + findMaxForm(strs_cp, m - count0, n - ((*i).length() - count0)));
}
}
if (!flag) return *max_element(list.begin(), list.end()); else return 0;
}
};
在自己做这道题的过程中我使用的是递归的想法,能做出正确的答案,但是提交到leetcode显示Time limit exceeded。递归的做法虽然能做但是并没有利用到相同的子结构来降低复杂度。于是改出了一个非递归的做法。
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> memory(m + 1, vector<int>(n + 1, 0));
for (auto &s : strs) {
int count0 = 0, count1 = 0;
for (auto p : s) { if (p == '0') count0++; else count1++; }
for (int i = m; i >= count0; i--) {
for (int j = n; j >= count1; j--) {
memory[i][j] = max(memory[i][j], memory[i - count0][j - count1] + 1);
}
}
}
return memory[m][n];
}
};
用一个表来记录每组成一个字符串之后的状态。
最新文章
- [ASP.NET MVC 小牛之路]15 - Model Binding
- AngularJS的$watch用法
- jQuery疑惑记录
- Android Studio导入System Library步骤
- Vijos1053 Easy sssp[spfa 负环]
- paip.文件目录操作uAPI php python java对照
- 【转】mac os x系统上Android开发环境的搭建
- thinkphp模板中foreach循环没数据的错误解决
- C语言文法 改
- OpenGL图形管线和坐标变换[转]
- HDNOIP201206施工方案
- ASP.NET-FineUI开发实践-1
- css3 在线编辑工具 连兼容都写好了
- js基本框架
- Linux服务器杀马(转)
- javaMelody监控javaWeb程序性能
- sql2008升级到r2提示:检查当前是否正确配置了报表服务器、数据库服务器是否正在运行以及您是否有权访问
- 使用nexus 管理pip 私有包
- fastdfs远程服务器java连接失败的问题
- DBCO
热门文章
- maven联通网络下中央仓库不能访问的解决办法
- 在java中读取文件中的内容
- Java组合算法
- Error response from daemon: Container ************** is not running
- 个人智能家居系统 - MQTT服务器搭建(centOS7.3)
- 牛客练习赛33 C	tokitsukaze and Number Game (结论+字符串处理)
- 网络流 最大流SAPkuangbin模板
- case_match
- JVM内存结构之本地方法栈
- canvas合并两张图片