狗家新鲜五轮昂塞

做了下第二题，欢迎指正。求米

1. # coding: utf-8
   
2. 
   
3. """
   
4. Given an array containing only 0 and 1s, find the best subarray to perform a single flip operation.
   
5. The goal is that: after the flip, number of 1s should  be the maximum.
   
6. Flip operation means that you will convert all 0 to 1, and all 1 to 0 in that array.
   
7. You can skip flipping if you think it is not worth doing the flip.
   
8. Return the maximum number of 1s after you do the flip.
   
9. 
   
10. 队友还是用的prefix sum再找区间最大的差值，面试官说可以O(1)空间，作为homework。
    
11. 
    
12. Follow-up: what if it is a 2D array?</div>
    
13. """
    
14. 
    
15. 
    
16. class Solution:
    
17.     def max_flip(self, bits):
    
18.         dp = [0] * len(bits)
    
19.         for i, b in enumerate(bits):
    
20.             val = 1 if b == '1' else -1
    
21.             prev = dp[i - 1] if i > 0 else 0
    
22.             dp[i] = min(prev + val, val)
    
23.         orig_one_count = sum(1 for b in bits if b == '1')
    
24.         res = orig_one_count + max(-min(dp), 0)
    
25.         return res
    
26. 
    
27.     def max_flip_follow_up(self, bits):
    
28.         # O(1) space. rolling array. dp[i] only relies on the prev one.
    
29.         dp = [0] * 2
    
30.         min_dp = 0
    
31.         for i, b in enumerate(bits):
    
32.             val = 1 if b == '1' else -1
    
33.             prev = dp[(i - 1) % 2] if i > 0 else 0
    
34.             dp[i % 2] = min(prev + val, val)
    
35.             min_dp = min(min_dp, dp[i % 2])
    
36.         orig_one_count = sum(1 for b in bits if b == '1')
    
37.         res = orig_one_count + max(-min_dp, 0)
    
38.         return res
    
39.    
    
40. 
    
41. import unittest
    
42. class Tests(unittest.TestCase):
    
43.     def test1(self):
    
44.         bits = '0001000'
    
45.         sol = Solution()
    
46.         actual = sol.max_flip(bits)
    
47.         self.assertEqual(actual, 6)
    
48.         actual2 = sol.max_flip_follow_up(bits)
    
49.         self.assertEqual(actual2, 6)
    
50. 
    
51.     def test2(self):
    
52.         bits = '1001001'
    
53.         sol = Solution()
    
54.         actual = sol.max_flip(bits)
    
55.         self.assertEqual(actual, 6)
    
56.         actual2 = sol.max_flip_follow_up(bits)
    
57.         self.assertEqual(actual2, 6)
    
58. 
    
59.     def test3(self):
    
60.         bits = '1111111'
    
61.         sol = Solution()
    
62.         actual = sol.max_flip(bits)
    
63.         self.assertEqual(actual, 7)
    
64.         actual2 = sol.max_flip_follow_up(bits)
    
65.         self.assertEqual(actual2, 7)
    
66. 
    
67.     def test4(self):
    
68.         bits = '1010101'
    
69.         sol = Solution()
    
70.         actual = sol.max_flip(bits)
    
71.         self.assertEqual(actual, 5)
    
72.         actual2 = sol.max_flip_follow_up(bits)
    
73.         self.assertEqual(actual2, 5)
    
74. 
    
75. unittest.main(verbosity=2)

复制代码

sqsigc 发表于 2020-11-22 03:59
第二轮，考虑flip 0的收益是1，flip 1的收益是-1，问题转化为【求一个element是1或者-1的array的max subarr ...

同意！follow up 2d array请问有啥思路么？

huntingzhu 发表于 2020-12-29 15:48
还是没理解第一题什么意思。如果给定
[1‘abc’][2‘54321’][1‘abcdef’][1‘re’]
max_size_over_aa ...

我猜应该是max_size_overall是对字符数而言，而不是message数量

sqsigc 发表于 2020-11-22 03:59
第二轮，考虑flip 0的收益是1，flip 1的收益是-1，问题转化为【求一个element是1或者-1的array的max subarr ...

真的牛逼！

第三题可以转化成 trie tree? then bfs??

第二题不是义领领思吗