可删除字母，需要多少次构造

第四轮是给两个string，

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

题目看了好久完全不懂怎么会提到binary search
感谢@yangyuzhiguang的代码一看就明白了

顺便贴个Python的两种版本

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

kaipeng21 发表于 2019-4-11 06:02
source = "bcaecbcd"
target = "dcbceacb"

嗯嗯，之前思路不对，改了下:

1. import collections
   
2. 
   
3. 
   
4. def min_str(src, target):
   
5.     dic = collections.defaultdict(list)
   
6.     for i, s in enumerate(src):
   
7.         dic[s].append(i)
   
8. 
   
9.     res = 0
   
10.     i = 0
    
11.     n = len(target)
    
12.     while i < n:
    
13.         j = i
    
14.         tmp_dic = collections.defaultdict(int)
    
15.         prev_idx = None
    
16.         while j < n:
    
17.             a = target[j]
    
18.             if a not in dic:
    
19.                 return -1
    
20.             else:
    
21.                 tmp_dic[a] += 1
    
22.                 if tmp_dic[a] > len(dic[a]):
    
23.                     break
    
24.                 else:
    
25.                     cur_idx = dic[a][tmp_dic[a]-1]
    
26.                     if prev_idx is None:
    
27.                         prev_idx = cur_idx
    
28.                     elif prev_idx > cur_idx:
    
29.                         while tmp_dic[a] <= len(dic[a]) and prev_idx > dic[a][tmp_dic[a]-1]:
    
30.                             tmp_dic[a] += 1
    
31.                         if tmp_dic[a] > len(dic[a]):
    
32.                             break
    
33.                         prev_idx = dic[a][tmp_dic[a]-1]
    
34.                         # Reach the end of src. Need a new src
    
35.                         if prev_idx == len(src)-1:
    
36.                             break
    
37.             j += 1
    
38.         res += 1
    
39.         i = j
    
40.     return res
    
41. 
    
42. src = "bcaecbcd"
    
43. aim = "dcbceacb"
    
44. print(min_str(src, aim))
    
45. 
    
46. src = 'abcdb'
    
47. aim = 'ba'
    
48. print(min_str(src, aim))
    
49. 
    
50. src = 'abcadb'
    
51. aim = 'aaaa'
    
52. print(min_str(src, aim))
    
53. 
    
54. src = "aabaaaaabaaabbbbaaaa"
    
55. aim = "bbaabbbb"
    
56. print(min_str(src, aim))
    
57. 
    
58. 
    

复制代码

写了一个贪心的解法，不确定有没有edge case没cover到。。

1. import collections
   
2. 
   
3. 
   
4. def min_str(src, target):
   
5.     dic = collections.defaultdict(list)
   
6.     for i, s in enumerate(src):
   
7.         dic[s].append(i)
   
8. 
   
9.     res = 0
   
10.     i = 0
    
11.     n = len(target)
    
12.     while i < n:
    
13.         j = i
    
14.         tmp_dic = collections.defaultdict(int)
    
15.         prev = None
    
16.         while j < n:
    
17.             a = target[j]
    
18.             if a not in dic:
    
19.                 return -1
    
20.             else:
    
21.                 tmp_dic[a] += 1
    
22.                 # case1: 若使用过的字符a数量 > dic里记录a的长度，则需要一个新的src, 对应Example 1
    
23.                 # case2: 若当前字符a在src的index小于其前一个字符的index, 则也需要一个新的src，对应Example 2
    
24.                 if tmp_dic[a] > len(dic[a]) or \
    
25.                         (prev is not None and dic[a][tmp_dic[a]-1] < prev):
    
26.                     break
    
27.                 prev = dic[a][tmp_dic[a] - 1]
    
28.             j += 1
    
29.         res += 1
    
30.         i = j
    
31.     return res
    
32. 
    
33. # Example 1
    
34. src = 'abcadb'
    
35. aim = 'aaaa'
    
36. print(min_str(src, aim))
    
37. 
    
38. # Example 2
    
39. src = 'abcdb'
    
40. aim = 'ba'
    
41. print(min_str(src, aim))
    
42. 
    
43. # Example 3
    
44. src = "aabaaaaabaaabbbbaaaa"
    
45. aim = "bbaabbbb"
    
46. print(min_str(src, aim))
    

复制代码

补充内容 (2019-4-6 05:33):
复杂度O(m+n)?

补充内容 (2019-4-6 05:34):
搞错了，复杂度是O(max(m, n))?

步惊云 发表于 2019-3-6 10:23
和 LIS 一个意思, 最坏情况O[mn], m = source string 长度, n = target string 长度

好一点的做法就是你 ...

你这题我应该是做过的。所以第一反应就比较像N+L。

但是我觉得和楼顶那题很像。只不过一个是连续走，而楼顶的题目是跳着走

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，版主@14417335 发的所有帖子，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

用贪心的思想写了一个，我的理解是这里是subsequence，不是substring

1. public class RepeatingWordToTarget {
   
2.         public int findRepeatingTimes(String target, String resource) {
   
3.                 int indexInTarget = 0;
   
4.                 int indexInResource = 0;
   
5.                 int lent = target.length();
   
6.                 int lenr = resource.length();
   
7. 
   
8.                 while(indexInTarget < lent) {
   
9.                         char c = target.charAt(indexInTarget);
   
10.                         if(c == resource.charAt(indexInResource%lenr)) {
    
11.                                 indexInResource++;
    
12.                                 indexInTarget++;
    
13.                         } else {
    
14.                                 indexInResource++;
    
15.                         }
    
16.                 }
    
17.                 if(indexInResource%lenr == 0) return indexInResource/lenr;
    
18.                 else return indexInResource/lenr + 1;
    
19.         }
    
20. 
    
21.         public static void main(String[] args) {
    
22.                 RepeatingWordToTarget rw = new RepeatingWordToTarget();
    
23.                 String target = "aabaaaaabaaabbbbaaaa";
    
24.                 String resource = "bbaabbbb";
    
25.                 System.out.println(rw.findRepeatingTimes(target, resource));
    
26.         }
    
27. 
    
28. }

复制代码

求问，当source中有重复字符，位置怎么存在TreeSet里？

yangyuzhiguang 发表于 2019-3-19 12:40
用贪心的思想写了一个，我的理解是这里是subsequence，不是substring
[mw_shl_code=java,true]public clas ...

indexInResource 也需要一个上界，不然会死循环

这无语了 发表于 2019-3-23 13:26
indexInResource 也需要一个上界，不然会死循环

就是说如果扫了一遍，没有这个字符就直接break，不再重复扫下去

看到好几次了，但高频题區没有啊

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

https://www.1point3acres.com/bbs ... read&tid=491464
是不是一样的？