https://leetcode.com/problems/ones-and-zeroes
这样做贼 jb 快，但却是错的：
https://leetcode.com/problems/ones-and-zeroes/solutions/3924490/accepted-greedy-solution-with-counterexample/
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
d = []
for s in strs:
cnts = [0,0]
for char in s:
if char == '0':
cnts[0] +=1
else:
cnts[1] += 1
if cnts[0] <= m and cnts[1] <= n:
d.append(cnts)
sorted_d3 = sorted(d, key=lambda x:(x[0]+x[1], x[0], x[1]))
m_left, n_left = m, n
ans3 = 0
while sorted_d3:
subset = sorted_d3.pop(0)
if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
ans3 += 1
m_left = m_left-subset[0]
n_left = n_left-subset[1]
sorted_d4 = sorted(d, key=lambda x:(x[0]+x[1], x[1], x[0]))
m_left, n_left = m, n
ans4 = 0
while sorted_d4:
subset = sorted_d4.pop(0)
if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
ans4 += 1
m_left = m_left-subset[0]
n_left = n_left-subset[1]
m_left, n_left = m, n
sorted_d1 = sorted(d, key=lambda x:(x[0], x[1]))
ans1 = 0
while sorted_d1:
subset = sorted_d1.pop(0)
if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
ans1 += 1
m_left = m_left-subset[0]
n_left = n_left-subset[1]
m_left, n_left = m, n
sorted_d2 = sorted(d, key=lambda x:(x[1], x[0]))
ans2 = 0
while sorted_d2:
subset = sorted_d2.pop(0)
if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
ans2 += 1
m_left = m_left-subset[0]
n_left = n_left-subset[1]
return max(ans1, ans2, ans3, ans4)
我写的应该正确的时间空间比较垃圾的 DP：
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
from collections import Counter
dp2 = [[0] * (m + 1) for _ in range(n + 1)]
counter = [Counter(s) for s in strs]
for c in counter:
num_zeros, num_ones = c.get('0', 0), c.get('1', 0)
for i_zeros in range(m, num_zeros - 1, -1):
for i_ones in range(n, num_ones - 1, -1):
dp2[i_ones][i_zeros] = max(dp2[i_ones][i_zeros], dp2[i_ones - num_ones][i_zeros - num_zeros] + 1)
return dp2[n][m]
看别人提交的有更快的 DP：
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
count = []
for i in strs:
d_temp = {'0': 0, "1": 0}
for j in i: d_temp[j]+=1
count.append((d_temp['0'], d_temp['1']))
list_0 = sorted(list(set([i[0] for i in count])))
d_temp = {}
for i in range(len(list_0)): d_temp[list_0[i]] = i
new = [[] for i in list_0]
for i in count: new[d_temp[i[0]]].append(i)
for i in new: i.sort(key = lambda x: x[1])
def dp(loc, m, n):
if loc == 0:
start, cnt = 0, 0
while (m>=0 and n>=0) and start<len(new[loc]):
curr_m, curr_n = new[loc][start]
m = m-curr_m
n = n-curr_n
if m>=0 and n>=0: cnt+=1
start+=1
return cnt
start, cnt, res = 0, 0, [0]*(len(new[loc])+1)
res[0] = dp(loc-1, m, n)
while (m>=0 and n>=0) and start<len(new[loc]):
curr_m, curr_n = new[loc][start]
m = m-curr_m
n = n-curr_n
if m>=0 and n>=0:
cnt+=1
res[cnt] = dp(loc-1, m, n)+cnt
start+=1
return max(res)
return dp(len(list_0)-1, m, n)