{"topic":{"id":13245,"title":"leetcode 存在“尽管 submission 通过了，但解法是错误的”的情况","slug":"topic","categoryId":4,"createdAt":"2024-08-12 05:47:47.960787","bumpedAt":"2024-08-12 05:47:48.195495","views":146,"postsCount":1,"highestPostNumber":1,"likeCount":0,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"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: Lis…","deletedAt":null,"isAnonymous":false,"category":{"id":4,"name":"谈笑风生","slug":"general","color":"25AAE2"},"author":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif"},"tags":[]},"posts":[{"id":38610,"postNumber":1,"raw":"https://leetcode.com/problems/ones-and-zeroes\n\n这样做贼 jb 快，但却是错的：\n![Screenshot_20240812_134456|690x73](/uploads/image/71/f4/71f45566ce5945f544647d4420e4b7f73e31176668b694bfebfdbdec63208e88.avif)\nhttps://leetcode.com/problems/ones-and-zeroes/solutions/3924490/accepted-greedy-solution-with-counterexample/\n```python\n\nclass Solution:\n def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n d = []\n for s in strs:\n cnts = [0,0]\n for char in s:\n if char == '0': \n cnts[0] +=1\n else:\n cnts[1] += 1\n if cnts[0] <= m and cnts[1] <= n:\n d.append(cnts)\n sorted_d3 = sorted(d, key=lambda x:(x[0]+x[1], x[0], x[1]))\n m_left, n_left = m, n\n ans3 = 0\n while sorted_d3:\n subset = sorted_d3.pop(0)\n if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:\n ans3 += 1\n m_left = m_left-subset[0]\n n_left = n_left-subset[1]\n sorted_d4 = sorted(d, key=lambda x:(x[0]+x[1], x[1], x[0]))\n m_left, n_left = m, n\n ans4 = 0\n while sorted_d4:\n subset = sorted_d4.pop(0)\n if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:\n ans4 += 1\n m_left = m_left-subset[0]\n n_left = n_left-subset[1]\n m_left, n_left = m, n\n sorted_d1 = sorted(d, key=lambda x:(x[0], x[1]))\n ans1 = 0\n while sorted_d1:\n subset = sorted_d1.pop(0)\n if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:\n ans1 += 1\n m_left = m_left-subset[0]\n n_left = n_left-subset[1]\n m_left, n_left = m, n\n sorted_d2 = sorted(d, key=lambda x:(x[1], x[0]))\n ans2 = 0\n while sorted_d2:\n subset = sorted_d2.pop(0)\n if m_left-subset[0] >= 0 and n_left-subset[1] >= 0:\n ans2 += 1\n m_left = m_left-subset[0]\n n_left = n_left-subset[1]\n return max(ans1, ans2, ans3, ans4)\n```\n\n我写的应该正确的时间空间比较垃圾的 DP：\n\n![Screenshot_20240812_134537|586x82](/uploads/image/49/d5/49d5325bed49fb1d834eca43ef2d718093b28c98ccb042ad6fc40b8ba4848458.avif)\n\n```python\nclass Solution:\n def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n from collections import Counter\n dp2 = [[0] * (m + 1) for _ in range(n + 1)]\n counter = [Counter(s) for s in strs]\n for c in counter:\n num_zeros, num_ones = c.get('0', 0), c.get('1', 0)\n for i_zeros in range(m, num_zeros - 1, -1):\n for i_ones in range(n, num_ones - 1, -1):\n dp2[i_ones][i_zeros] = max(dp2[i_ones][i_zeros], dp2[i_ones - num_ones][i_zeros - num_zeros] + 1)\n return dp2[n][m]\n```\n\n\n看别人提交的有更快的 DP：\n![Screenshot_20240812_134710|542x73](/uploads/image/4b/8e/4b8e79274b2e19ba42781fa4d80c32190a81f1865bd9e0156518dc2b6c8d9201.avif)\n\n```python\nclass Solution:\n def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n count = []\n for i in strs:\n d_temp = {'0': 0, \"1\": 0}\n for j in i: d_temp[j]+=1\n count.append((d_temp['0'], d_temp['1']))\n list_0 = sorted(list(set([i[0] for i in count])))\n d_temp = {}\n for i in range(len(list_0)): d_temp[list_0[i]] = i\n new = [[] for i in list_0] \n for i in count: new[d_temp[i[0]]].append(i)\n for i in new: i.sort(key = lambda x: x[1])\n def dp(loc, m, n):\n if loc == 0:\n start, cnt = 0, 0\n while (m>=0 and n>=0) and start=0 and n>=0: cnt+=1\n start+=1\n return cnt\n start, cnt, res = 0, 0, [0]*(len(new[loc])+1)\n res[0] = dp(loc-1, m, n)\n while (m>=0 and n>=0) and start=0 and n>=0: \n cnt+=1\n res[cnt] = dp(loc-1, m, n)+cnt\n start+=1\n return max(res)\n return dp(len(list_0)-1, m, n)\n```","cooked":"

https://leetcode.com/problems/ones-and-zeroes

这样做贼 jb 快，但却是错的：
\n $\"Screenshot_20240812_134456\"$

https://leetcode.com/problems/ones-and-zeroes/solutions/3924490/accepted-greedy-solution-with-counterexample/

\n```python\n

class Solution:
\ndef findMaxForm(self, strs: List[str], m: int, n: int) -> int:
\nd =
\nfor s in strs:
\ncnts = [0,0]
\nfor char in s:
\nif char == '0':
\ncnts[0] +=1
\nelse:
\ncnts[1] += 1
\nif cnts[0] <= m and cnts[1] <= n:
\nd.append(cnts)
\nsorted_d3 = sorted(d, key=lambda x:(x[0]+x[1], x[0], x[1]))
\nm_left, n_left = m, n
\nans3 = 0
\nwhile sorted_d3:
\nsubset = sorted_d3.pop(0)
\nif m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
\nans3 += 1
\nm_left = m_left-subset[0]
\nn_left = n_left-subset[1]
\nsorted_d4 = sorted(d, key=lambda x:(x[0]+x[1], x[1], x[0]))
\nm_left, n_left = m, n
\nans4 = 0
\nwhile sorted_d4:
\nsubset = sorted_d4.pop(0)
\nif m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
\nans4 += 1
\nm_left = m_left-subset[0]
\nn_left = n_left-subset[1]
\nm_left, n_left = m, n
\nsorted_d1 = sorted(d, key=lambda x:(x[0], x[1]))
\nans1 = 0
\nwhile sorted_d1:
\nsubset = sorted_d1.pop(0)
\nif m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
\nans1 += 1
\nm_left = m_left-subset[0]
\nn_left = n_left-subset[1]
\nm_left, n_left = m, n
\nsorted_d2 = sorted(d, key=lambda x:(x[1], x[0]))
\nans2 = 0
\nwhile sorted_d2:
\nsubset = sorted_d2.pop(0)
\nif m_left-subset[0] >= 0 and n_left-subset[1] >= 0:
\nans2 += 1
\nm_left = m_left-subset[0]
\nn_left = n_left-subset[1]
\nreturn max(ans1, ans2, ans3, ans4)

\n我写的应该正确的时间空间比较垃圾的 DP：\n\n![Screenshot_20240812_134537|586x82](/uploads/image/49/d5/49d5325bed49fb1d834eca43ef2d718093b28c98ccb042ad6fc40b8ba4848458.avif)\n\n```python\nclass Solution:\n    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n        from collections import Counter\n        dp2 = [[0] * (m + 1) for _ in range(n + 1)]\n        counter = [Counter(s) for s in strs]\n        for c in counter:\n            num_zeros, num_ones = c.get('0', 0), c.get('1', 0)\n            for i_zeros in range(m, num_zeros - 1, -1):\n                for i_ones in range(n, num_ones - 1, -1):\n                    dp2[i_ones][i_zeros] = max(dp2[i_ones][i_zeros], dp2[i_ones - num_ones][i_zeros - num_zeros] + 1)\n        return dp2[n][m]\n

看别人提交的有更快的 DP：
\n $\"Screenshot_20240812_134710\"$

class Solution:\n    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:\n        count = []\n        for i in strs:\n            d_temp = {'0': 0, \"1\": 0}\n            for j in i: d_temp[j]+=1\n            count.append((d_temp['0'], d_temp['1']))\n        list_0 = sorted(list(set([i[0] for i in count])))\n        d_temp = {}\n        for i in range(len(list_0)): d_temp[list_0[i]] = i\n        new = [[] for i in list_0] \n        for i in count: new[d_temp[i[0]]].append(i)\n        for i in new: i.sort(key = lambda x: x[1])\n        def dp(loc, m, n):\n            if loc == 0:\n                start, cnt = 0, 0\n                while (m>=0 and n>=0) and start<len(new[loc]):\n                    curr_m, curr_n = new[loc][start]\n                    m = m-curr_m\n                    n = n-curr_n\n                    if m>=0 and n>=0: cnt+=1\n                    start+=1\n                return cnt\n            start, cnt, res = 0, 0, [0]*(len(new[loc])+1)\n            res[0] = dp(loc-1, m, n)\n            while (m>=0 and n>=0) and start<len(new[loc]):\n                curr_m, curr_n = new[loc][start]\n                m = m-curr_m\n                n = n-curr_n\n                if m>=0 and n>=0: \n                    cnt+=1\n                    res[cnt] = dp(loc-1, m, n)+cnt\n                start+=1\n            return max(res)\n        return dp(len(list_0)-1, m, n)\n

\n","createdAt":"2024-08-12 05:47:48.195495","updatedAt":"2024-08-12 05:50:24.496756","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":476,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif","admin":true,"moderator":false,"signatureRaw":"","signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":1,"hasUrlPostNumber":false}