白嫖oa一道题求解

北十字星 发表于 2020-9-2 06:03
纯问。。我也不是很确定哈。。刚开始刷题。。。能不能用一个dict()存储每个char出现的频率然后再走一遍dict ...

不太理解同学说的走第二遍dict的过程，可以具体说一下吗？

ND0406 发表于 2020-9-2 06:52
如果k是1， 这个方法是n平方吧？

还是n...确切的来说是2n

写了个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))
   

复制代码

ND0406 发表于 2020-9-2 06:52
如果k是1， 这个方法是n平方吧？

还是n...确切的来说是2n

advpetc 发表于 2020-9-2 06:48
看了一下1531，貌似还是有点区别？这道题要求连续的k个字母，1531貌似没这个要求。比如: aaabcccd,k=2那 ...

ahh刚看到要求连续，写了一份新的另外回复了

advpetc 发表于 2020-9-2 06:52
不太理解同学说的走第二遍dict的过程，可以具体说一下吗？

就是如果我们有AABBCD, dict里面会存{A:2,B:2,C:1,D:1}, 然后如果大于1的话count+1+对应的数字的位数（写个helper用mod10），等于1就count+1就行了

北十字星 发表于 2020-9-2 10:05
就是如果我们有AABBCD, dict里面会存{A:2,B:2,C:1,D:1}, 然后如果大于1的话count+1+对应的数字的位数（写 ...

嗯嗯，compress的步骤应该可以这样

可惜了。。。 python代码我看不懂呀。。。。
有JAVA大神可以说一下具体思路吗？

北十字星 发表于 2020-9-2 10:05
就是如果我们有AABBCD, dict里面会存{A:2,B:2,C:1,D:1}, 然后如果大于1的话count+1+对应的数字的位数（写 ...

用dict会出现一个问题就是

aaabcdefgaaaaaa, k < 6。比如等于5把，那这题最优解就应该是a3ba6或者a3ga6

你要是用dict的话你a怎么存，3还是6还是9？（你不可能存两次）

韦小崽 发表于 2020-9-2 23:02
用dict会出现一个问题就是

aaabcdefgaaaaaa, k < 6。比如等于5把，那这题最优解就应该是a3ba6或者a3ga ...

哦哦我直接点到lz给的leetcode页面去看了……那个题和这个题条件不一样，你说得对。