474. Ones and Zeroes
题目文本会按所选界面语言从俄语翻译；代码保持不变。
Дан 数组 двоичных строк strs и два целых числа m и n.
return размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все elementы множества x также являются elementами множества y.
示例:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
C# 解法
匹配/原始public class Solution {
public int FindMaxForm(string[] strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.Length); i++) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0) {
int[] count = CountZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
len++;
}
}
if (zeroes <= m && ones <= n)
maxlen = Math.Max(maxlen, len);
}
return maxlen;
}
public int[] CountZeroesOnes(string s) {
int[] c = new int[2];
foreach (char ch in s) {
c[ch - '0']++;
}
return c;
}
}C++ 解法
自动草稿，提交前请检查#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int FindMaxForm(vector<string> strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.size()); i++) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0) {
vector<int>& count = CountZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
len++;
}
}
if (zeroes <= m && ones <= n)
maxlen = max(maxlen, len);
}
return maxlen;
}
public vector<int>& CountZeroesOnes(string s) {
vector<int>& c = new int[2];
foreach (char ch in s) {
c[ch - '0']++;
}
return c;
}
}Java 解法
匹配/原始public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.length); i++) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0) {
int[] count = countzeroesones(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
len++;
}
}
if (zeroes <= m && ones <= n)
maxlen = Math.max(maxlen, len);
}
return maxlen;
}
public int[] countzeroesones(String s) {
int[] c = new int[2];
for (int i = 0; i < s.length(); i++) {
c[s.charAt(i) - '0']++;
}
return c;
}
}JavaScript 解法
匹配/原始class Solution {
findMaxForm(strs, m, n) {
let maxlen = 0;
for (let i = 0; i < (1 << strs.length); i++) {
let zeroes = 0, ones = 0, length = 0;
for (let j = 0; j < 32; j++) {
if ((i & (1 << j)) !== 0) {
const count = this.countZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n) break;
length++;
}
}
if (zeroes <= m && ones <= n) {
maxlen = Math.max(maxlen, length);
}
}
return maxlen;
}
countZeroesOnes(s) {
const count = [0, 0];
for (const char of s) {
count[char - '0']++;
}
return count;
}
}Python 解法
匹配/原始class Solution:
def findMaxForm(self, strs, m, n):
maxlen = 0
for i in range(1 << len(strs)):
zeroes, ones, length = 0, 0, 0
for j in range(32):
if i & (1 << j):
count = self.count_zeroes_ones(strs[j])
zeroes += count[0]
ones += count[1]
if zeroes > m or ones > n:
break
length += 1
if zeroes <= m and ones <= n:
maxlen = max(maxlen, length)
return maxlen
def count_zeroes_ones(self, s):
count = [0, 0]
for char in s:
count[int(char)] += 1
return countGo 解法
匹配/原始package main
import (
"fmt"
)
type Solution struct{}
func (s *Solution) findMaxForm(strs []string, m int, n int) int {
maxlen := 0
for i := 0; i < (1 << len(strs)); i++ {
zeroes, ones, length := 0, 0, 0
for j := 0; j < len(strs); j++ {
if (i & (1 << j)) != 0 {
count := s.countZeroesOnes(strs[j])
zeroes += count[0]
ones += count[1]
if zeroes > m || ones > n {
break
}
length++
}
}
if zeroes <= m && ones <= n {
maxlen = max(maxlen, length)
}
}
return maxlen
}
func (s *Solution) countZeroesOnes(str string) [2]int {
count := [2]int{}
for _, char := range str {
count[char-'0']++
}
return count
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
sol := Solution{}
fmt.Println(sol.findMaxForm([]string{"10", "0001", "111001", "1", "0"}, 5, 3))
}Algorithm
Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
Считаем количество нулей и единиц в каждом подмножестве.
Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.
目前还没有活跃职位。