Google VO

yueyingjuesha 发表于 2021-5-26 14:57
第三题可以用dp[n][k]: 长度为n的string, 用k个长度为m的string来替换，b的最少数量
第一种情况，刚好替换 ...

大大要是用min的比较话会一直返回0，能不能写个详细些的方法，感谢大大了

第一题 我感觉刷题网这个post很好
https://leetcode.com/problems/co ... nts-and-explanation

markbs123 发表于 2021-5-28 12:54
大大能不能详细写一下这个方法，我按照您的思路写出来结果不是1, max会保留最大的b count数，烦劳大大指 ...

1. /**
   
2.      * @param str target string contains only 'a' and 'b'
   
3.      * @param n number of mask string contains only 'a'
   
4.      * @param m length of mask string
   
5.      * [url=home.php?mod=space&uid=160137]@return[/url] number of char 'a' after applying mask strings
   
6.      */
   
7.     public int findNumberOfBAfterReplace(String str, int n, int m) {
   
8.         int l = str.length();
   
9.         int[][] dp = new int[l][n];
   
10.         int[] countB = new int[l];
    
11.         for (int i = 0; i < l; i++) {
    
12.             countB[i] = (i == 0 ? 0 : countB[i - 1])
    
13.                     + (str.charAt(i) == 'b' ? 1 : 0);
    
14.         }
    
15. 
    
16.         for (int i = 0; i < l; i++) {
    
17.             for (int j = 0; j < n; j++) {
    
18.                 if (i < m) {
    
19.                     dp[i][j] = countB[i];
    
20.                 } else {
    
21.                     dp[i][j] = Math.max(dp[i - 1][j],
    
22.                             (j == 0 ? 0 : dp[i - m][j - 1]) + countB[i] - countB[i - m]);
    
23.                 }
    
24.             }
    
25.         }
    
26. 
    
27.         return countB[l - 1] - dp[l - 1][n - 1];
    
28.     }

复制代码

cxw111 发表于 2021-5-29 00:02
第一题 我感觉刷题网这个post很好
https://leetcode.com/problems/count-of-smaller ...

我觉得能写出BST的解就好了吧？

hz2019 发表于 2021-5-26 00:57
第一题可以用Binary Index Tree吧

可以先问清楚输入的num的范围，比如说是0-100, 那么用100个bucket计数，直接上BIT(Fenwick tree),可以实现log(100).

aniu123 发表于 2021-6-9 18:36
可以先问清楚输入的num的范围，比如说是0-100, 那么用100个bucket计数，直接上BIT(Fenwick tree),可以实 ...

soga..厉害了老哥，完美转化成range sum的问题，主要是不用担心新增node了。如果不给定num的范围，就不太好用BIT了，毕竟是data stream。

djmiss 发表于 2021-6-2 08:03
我觉得能写出BST的解就好了吧？

最差是O(N2) 看面试官叼不叼难了.....非要实现logn 只能手写红黑树了lol

请问后续怎么样？过hc了吗？

SimonLevy 发表于 2021-5-31 14:18
[mw_shl_code=java,true]/**
     * @param str target string contains only 'a' and 'b'
     * @par ...

探讨一下，个人感觉这个状态转移方程：
dp[i][i][j] = Math.max(dp[i - 1][j], dp[i - m][j - 1]) + countB[i] - countB[i - m])
中的dp[i - 1][j] 不太对，这个情况代表了前面 i - 1 个字符串用j个a替换字符串，最大能覆盖多少b。这个最大能覆盖多少b的值跟dp[i][i][i][j] 不一定是等同的。如果字符i - 1本身是b，然后恰好前面的第j个替换字符串能多出来一个替换到它，那值应该要加1。 但问题是不知道能不能替换到它。所以我觉得用dp有点儿复杂这道题。而且相比最简单的greedy，用dp也没有优势。直接sliding window找覆盖b最多的M子字符串并且替换，重复N次就可以了。或者找出以b开头的M子字符串，以数量排个序，从大到小往下拿，也可以。[/i][/i][/i][/i]

第一题 叁易吴