Google VO

第一题O(N)解：用一个单调增的stack，每来一个数找它在stack里的位置，找到后stack的size就是返回的结果，然后把剩余的数放回stack LogN解：Java里用一个tree map，把新来的数直接加到tree map里，如果已有key的话就counter+1，返回headMap(key).size()

第三题dp怎么做啊？

wuyufei2002 发表于 2021-5-25 05:21
第一题O(N)解：用一个单调增的stack，每来一个数找它在stack里的位置，找到后stack的size就是返回的结果， ...

要是没有treemap库函数，是不是还得自己写一个？那好难啊

第一题可以用Binary Index Tree吧

第一题没有重复的数的话直接上TreeMap解决问题。有的话会复杂，感觉需要上segment tree或者binary index tree。就是要知道数字的取值范围, 建立一个logN高度的树。leaf nodes是每个具体的输入值和count, 所有非leaf nodes就是代表值的范围和所有的counts. [left, right, count]。 segment tree说说还可以, 真写codes就是个坑

第三题感觉也是dp。

1. 
   
2. dp[i][k] -> dp[i+M][k+1] 其中 k + 1 between [1..N], means b counts if we use k a-M-strings and next character to work on is s.charAt(i) (not done yet)
   
3. 如果[i..i+M-1]之间没有任何b, dp[i+M][k] = dp[i][k] (不需要替换, 所以b的数量不减少, 也不用消化任何M长的a串)
   
4.                    如果有b,  dp[i+M][k+1] = dp[i][k] - (b counts between [i..i+M-1]) (需要替换一次,所以k+1)
   
5. 
   
6. dp[0][0] = s里面所有b的count
   
7. 
   

复制代码

[/i]

第三题 dp
dp[i][j] -> 对前i个字符，使用j个string a，最多能覆盖的char b的数量

dp[i][j] = max(dp[i - 1][j], dp[i - M][j - 1] + (countB[i] - countB[i - M]))
i < M时，dp[i][j] = countB[i]

第一题是经典的binary indexed tree(fenwick tree) 和 segmented tree, 面试不多，但是leetcode上这种类型的题目还挺多的，但普遍都是mid - hard

补充内容 (2021-06-07 06:30 +08:00):
segment tree, binary indexed tree 的update 和 query都是log(n), 因为在一开始的时候，建树就是balanced了，不知道题主所说不可取是什么意思

补充内容 (2021-06-07 06:33 +08:00):
在update和insert的时候，也只用沿着root到一个leaf这条path上的node进行update就行了，因为已经是balanced了，所以最大深度就是log(n)

第三题可以用dp[n][k]: 长度为n的string, 用k个长度为m的string来替换，b的最少数量
第一种情况，刚好替换到最后一个字符 此时上一个状态是dp[n - m][k - 1]
第二种情况，除去第一种情况的其他情况(最后一个字符没有被替换）此时上一个状态是dp[n-1][k] + (str[n-1] == ‘b’)
综合两种情况：
dp[n][k] = min(dp[n - m][k - 1], dp[n - 1][k] + str[n - 1] == ‘b’)

第三题 如果是用纯A的字符串来替代，能不能吧所有B的substring找出来 放在一个heap里 然后就按长度去greedy的盖

SimonLevy 发表于 2021-5-26 12:06
第三题 dp
dp[j] -> 对前i个字符，使用j个string a，最多能覆盖的char b的数量

大大能不能详细写一下这个方法，我按照您的思路写出来结果不是1, max会保留最大的b count数，烦劳大大指点