白嫖oa一道题求解

ND0406 发表于 2020-09-01 20:04:38
可惜了。。。 python代码我看不懂呀。。。。
有JAVA大神可以说一下具体思路吗？

我的思路是先preprocess，建立array存起来每个index往左往右第一个不同char的位置，还有左右截止到那个char的最佳压缩长度，这步是O(n)
比如aabbbaaaac, idx=2, 3, 4的时候l = 1, r = 5, l_len = 2, r_len=3
接下来用一个长度为k的sliding window扫一遍，每次拿到window左右的两个index，暂记为i和j。然后按s[i]跟s[j]是不是相等分类讨论，求出整体最佳压缩长度
比如刚才的s，k=3, 那么当sliding window扫到bbb的时候i = 1, j = 5. 左边第一个不同char的idx在-1，右边在9，左长为0，右长为1. s[i]==s[j]，中间部分可以用长度为2压缩起来，所以这步sliding window把ans update成0+2+1=3.
对于每一组i，j都可以用O(1)求出最佳长度，这步整体也是O(n)
index边界处理得有点繁琐，可能有更简单的做法

北十字星 发表于 2020-9-2 23:56
哦哦我直接点到lz给的leetcode页面去看了……那个题和这个题条件不一样，你说得对。

那个LC原题我也看了，只是没有“去掉连续k个字符“这样的条件而已？那顺序问题还是存在？

韦小崽 发表于 2020-9-3 00:21
那个LC原题我也看了，只是没有“去掉连续k个字符“这样的条件而已？那顺序问题还是存在？

对 那样用dict就可以啦 只要最后给出长度就可以了的（不过那个lc原题最后是要求modify原来的list然后给那个list最后的坐标。。这个要求有点迷）

北十字星 发表于 2020-9-3 01:14
对 那样用dict就可以啦 只要最后给出长度就可以了的（不过那个lc原题最后是要求modify原来的list然后给那 ...

真的吗……我看那个题的描述，aaabbbaaa出来的结果难道不应该是a3b3a3么？不像是a6b3吧

想到一个方法不知道可不可行。先用两个数组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）吧？

one pass 不行吗？