白嫖oa一道题求解

加强版的compress string: https://leetcode.com/problems/string-compression/
现在给定一个str，一个k，要求返回去掉k个连续字符之后compress最短的长度（只需要返回长度即可），例子：

str = ABBBCCDDCCC , k = 3 return 5 by removing DDC from str (ABBBCCCC => A3B4C: length is 5)

我只想到了暴力做，但是感觉一定有更好的解法，因为数据规模是1e5，所有至少n log n才可以pass


求启发

ABBBCCCC => A3B4C: length is 5 等一下这个的表现难道不是ab3c4?
如果我的理解没错的话，python代码在此（空间复杂度可以进一步优化，不过会牺牲可读性我就不做了）

1. def compression(string, k):
   
2.     uncompressed = list()
   
3.     compressed = list()
   
4.     for i in range(len(string)):
   
5.         if i == 0:
   
6.             uncompressed.append(append_character_to_compressed_string(CompressedString(), string[i]))
   
7.         else:
   
8.             uncompressed.append(append_character_to_compressed_string(uncompressed[i - 1], string[i]))
   
9. 
   
10.         if i < k:
    
11.             compressed.append(None)
    
12.         elif i == k:
    
13.             compressed.append(append_character_to_compressed_string(CompressedString(), string[i]))
    
14.         else:
    
15.             choice1 = append_character_to_compressed_string(compressed
    
16.     [i - 1], string[i])
    
17.             choice2 = append_character_to_compressed_string(uncompressed[i - k - 1], string[i])
    
18.             compressed.append(choice1 if len(choice1.full_string) < len(choice2.full_string) else choice2)
    
19.     return compressed[-1].full_string
    
20. 
    
21. class CompressedString:
    
22.     full_string = ''
    
23.     last_char = ''
    
24.     last_count = 0
    
25. 
    
26. def append_character_to_compressed_string(compressed_string, char):
    
27.     output = CompressedString()
    
28.     output.last_char = char
    
29.     if (char != compressed_string.last_char):
    
30.         output.full_string = compressed_string.full_string + char
    
31.         output.last_count = 1
    
32.     else:
    
33.         parts = compressed_string.full_string.rpartition(compressed_string.last_char)
    
34.         output.full_string = parts[0] + char + str(compressed_string.last_count + 1)
    
35.         output.last_count = compressed_string.last_count + 1
    
36.     return output
    
37. 
    
38. 
    
39. print(compression('ABBBCCDDCCC', 3))
    
40. #AB3C4

复制代码

哦我才发现原题只用返回长度就行了，那CompressedString里面不用存full_string，一直计算/更新full string的长度就行了。last_char和last_count应该留着。

写了个O(n) / O(n)的，有的地方能优化，不过不影响复杂度就没再改了

1. 
   
2. class Solution:
   
3.     def get_comp_len(self, s, k):
   
4. 
   
5.         ans = n = len(s)
   
6. 
   
7.         def get_comp_arr(s):
   
8.             i, j, ch, pre = -1, 0, s[0], (-1, 0)
   
9.             arr = [0] * n
   
10.             while i < n and j < n:
    
11.                 while j < n and s[j] == ch:
    
12.                     arr[j] = pre
    
13.                     j += 1
    
14.                 pre = (j - 1, pre[1] + len(str(j - i - 1)) + (j - 2 > i))
    
15.                 i = j - 1
    
16.                 if j >= n:
    
17.                     break
    
18.                 ch = s[j]
    
19.             return arr
    
20. 
    
21.         l_comp = get_comp_arr(s)
    
22.         r_comp = [(n - i - 1, l) for i, l in get_comp_arr(s[::-1])][::-1]
    
23. 
    
24.         for r in range(k - 1, n):
    
25.             l = r - k + 1
    
26.             l_idx, l_len = l_comp[l - 1] if l > 0 else (-1, 0)
    
27.             r_idx, r_len = r_comp[r + 1] if r < n - 1 else (n, 0)
    
28.             if l == 0 or r == n - 1 or s[l - 1] != s[r + 1]:
    
29.                 ans = min(ans, l_len + r_len + (l - l_idx - 1) + (r_idx - r - 1))
    
30.             else:
    
31.                 ans = min(ans, l_len + r_len + len(str(r_idx - l_idx - r + l - 2)) + 1)
    
32.         return ans
    
33. 
    

复制代码

试了下面几个test cases，不知道有没有edge case没考虑到

1. 
   
2. if __name__ == '__main__':
   
3.     s = Solution()
   
4.     print(s.get_comp_len('ABBBCCDDCCC', 3))
   
5.     print(s.get_comp_len('AABBCBBAA', 1))
   
6.     print(s.get_comp_len('A'*50 + 'B' + 'A'*50, 1))
   

复制代码

想到一个方法不知道可不可行。先用两个数组arr1 和arr2[j] 分别记录下标s[0:i+1]和下标s[j:n]的压缩后的字符串长度。
以aa bc aa 为例：  
arr1 = [2(a1），2(a2), 4(a2b1), 6(a2b1c1), ...... 8]  
arr2 = [ 8(a2b1c1a2), 8(a1b1c1a2), ..... 2]   
搞一个长度为k的滑动窗口。如果窗口左边的下标是left, 右边的下标是right 的话， 如果窗口两边的字符不相同，那新的长度就是 arr1[left-1] +arr2[right+1] 的长度；假如arr[left-1] 和arr[right+1] 是同一个字符的话，再做特殊处理。  

特殊处理的方法是：再用两个数组，arr3 和arr4[j] 来记录以i为结尾的连续相同字符长度，和以j为开头的连续相同字符长度。
arr3 = [1, 2, 1, 1, 1, 2]
arr4 = [2, 1, 1, 1, 2 , 1]


窗口两边合并起来之后的就是(arr3[left - 1] + arr4[right+1] ) 变成string之后的长度，再加上窗口前后不相同的字母的字符长度。

数字变成string 的复杂度应该是O(9) 左右。

记录arr1,2,3,4 的复杂度应该是 O(4n) = O(n), 然后一个数字变成string的复杂度大概是O(log10(Integer.MAX))。  
复杂度应该是O(N* log10(Integer.MAX))把。。因为log10（integer.max)大概等于9， 所以其实也能算是O(N）吧？

我没用代码实现过所以不确定这个思路对不对，不过用DP做，复杂度O(n)，应该会需要一个2 x len(string)的存储来存数据。每次算第n个数的时候，算算把n连到n-1的解和已经去掉了k个数的最优解，总之就是每次多存一个数。我试试看能不能把代码写出来

韦小崽 发表于 2020-9-2 03:12
ABBBCCCC => A3B4C: length is 5 等一下这个的表现难道不是ab3c4?
如果我的理解没错的话，python代码在此 ...

感谢回复！ab3c4和a3b4c都是可以的，不需要返回具体的compress的结果，只需要返回长度即可。另外有个小问题，关于33行rpartition这里会不会产生额外的时间复杂度？

advpetc 发表于 2020-9-2 03:28
感谢回复！ab3c4和a3b4c都是可以的，不需要返回具体的compress的结果，只需要返回长度即可。另外有个小问 ...

是个常量，所以我觉得可以忽略不计了。另外，如果不需要整个的结果只需要数字的话，根本用不着partition。代码我就不改了，反正逻辑在那……

韦小崽 发表于 2020-9-2 03:38
是个常量，所以我觉得可以忽略不计了。另外，如果不需要整个的结果只需要数字的话，根本用不着partition ...

好的，谢谢！加米了！

纯问。。我也不是很确定哈。。刚开始刷题。。。能不能用一个dict()存储每个char出现的频率然后再走一遍dict然后把最后字符串长度算出来啊。。。
我觉得是O(2n)属于O(n)，只是空间也要O(n)?

如果有错欢迎指正 谢谢谢谢

LC1531，几周以前的一道周赛题

Actuant 发表于 2020-9-2 06:19
LC1531，几周以前的一道周赛题

看了一下1531，貌似还是有点区别？这道题要求连续的k个字母，1531貌似没这个要求。比如: aaabcccd,k=2那么最后的最好情况是a2c3d OR a3c2d OR a3c2d OR a3bc3 ==> length 5，但是1531可以删除b和d所以最后是a3c3 ==> length 4

韦小崽 发表于 2020-09-01 11:18:26
我没用代码实现过所以不确定这个思路对不对，不过用DP做，复杂度O(n)，应该会需要一个2 x len(string)的存储来存数据。每次算第n个数的时候，算算把n连到n-1的解和已经去掉了k个数的最优

如果k是1， 这个方法是n平方吧？