x******8
发帖数: 48 | 1 A, B两个String
//example
A = XYZ;
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;
B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
A^2 是B的subsequence, 所以
return k = 2;
A可能有重复的char, B可能有其他字符, 求k. |
I**********a
发帖数: 1183 | 2 subsequence不管顺序吗？ 那就hashmap统计A中字符的频率，然后统计B中对应字符的
频率，然后频率相除ratio中最小的就是k. O(n) time + O(n) space
【在 x******8 的大作中提到】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.
|
b***e
发帖数: 1419 | 3 可以对k进行二分。复杂度O(n*log(n))。
【在 x******8 的大作中提到】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.
|
k****r
发帖数: 807 | 4 String A = "XXZ";
String B = "
XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh";
这样有重复的例子是return 2吗。
|
j**********3
发帖数: 3211 | |
j**********3
发帖数: 3211 | 6 这个怎么算啊？
adhflakjhelXXzzqqkkpoYYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh也是k=2么？
我在中间多加了一个Y |
l******s
发帖数: 3045 | 7 抠字符，抠到抠不出为止。O(n*k)
【在 x******8 的大作中提到】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.
|
s*a
发帖数: 267 | 8 二分不行吧。二分以后朝哪个方向走呢？
【在 b***e 的大作中提到】
: 可以对k进行二分。复杂度O(n*log(n))。
|
x******8
发帖数: 48 | 9 是的
【在 k****r 的大作中提到】
: String A = "XXZ";
: String B = "
: XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh";
: 这样有重复的例子是return 2吗。
:
|
b***e
发帖数: 1419 | 10 你理解错了。我的意思是对于某一个特定的k，判断B中有没有A^k是一个线性O(n)的问
题。并且k有解则对于所有的i
有乜解，然后看k = 2, 4, 8, ...一直找到最终的k. O(n*log(k))。
【在 s*a 的大作中提到】
: 二分不行吧。二分以后朝哪个方向走呢？
|
|
|
l*********u
发帖数: 19053 | 11 先找A^3，找到return 3
再找A^2，找到return 2
最后找A，找到return 1?
【在 x******8 的大作中提到】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.
|
x******8
发帖数: 48 | 12 就是这个意思
【在 l*********u 的大作中提到】
: 先找A^3，找到return 3
: 再找A^2，找到return 2
: 最后找A，找到return 1?
|
l*********u
发帖数: 19053 | 13 A是已知的?还是要自己从B里找?
【在 x******8 的大作中提到】
: 就是这个意思
|
k****r
发帖数: 807 | 14 我的思路：
建立一个一维dp table，大小为A的size；
开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
都完事了dp［n － 1］就是结果。
【在 l*********u 的大作中提到】
: 先找A^3，找到return 3
: 再找A^2，找到return 2
: 最后找A，找到return 1?
|
n*******s
发帖数: 17267 | |
n*******s
发帖数: 17267 | 16 0
么？
【在 j**********3 的大作中提到】
: 这个怎么算啊？
: adhflakjhelXXzzqqkkpoYYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh也是k=2么？
: 我在中间多加了一个Y
|
x******8
发帖数: 48 | 17 能具体说说思路吗？
【在 k****r 的大作中提到】
: 我的思路：
: 建立一个一维dp table，大小为A的size；
: 开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
: 如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
: 都完事了dp［n － 1］就是结果。
|
l*********u
发帖数: 19053 | 18 brilliant
【在 k****r 的大作中提到】
: 我的思路：
: 建立一个一维dp table，大小为A的size；
: 开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
: 如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
: 都完事了dp［n － 1］就是结果。
|
l*********u
发帖数: 19053 | 19 俺那种要扫3次，这位网友的是1次
【在 x******8 的大作中提到】
: 能具体说说思路吗？
|
m***2
发帖数: 595 | 20 看起来有戏，xyzxyz这种算k=2还是1
【在 k****r 的大作中提到】
: 我的思路：
: 建立一个一维dp table，大小为A的size；
: 开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
: 如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
: 都完事了dp［n － 1］就是结果。
|
|
|
m***2
发帖数: 595 | 21 有一个笨办法，不知道对不对，其实就是统计：
1. Y出现以前X的个数 xcount
2. Y的个数 ycount
3. Y出现以后的Z的个数 zcount
再算三者的最小值
因为第一个Y出现以后的X都没有意义，最后一个Y之前的Z也没有意义
int xcount = 0;
int ycount = 0;
int zcount = 0;
boolean ystarted = false;
for (int i = 0; i < n; i++) {
switch(A[i]) {
case 'X': {
if (ystarted == false) {
xcount++;
}
break;
}
case 'Y': {
ycount++;
ystarted = true;
zcount = 0;
break;
}
caes 'Z': {
zcount++;
break;
}
}
return min(xcount,ycount,zcount);
} |
k****r
发帖数: 807 | 22 按lz要求应该是1，按我之前的描述结果是2.
解决办法：增加另一个p［a］，纪录每个元素新开始数数时候的dp［i － 1］，
这样的话，每次想加dp［i］的时候需要增加个判断，看p［a］是不是大于dp［i］。
yes才能加。但什么时候update p［a］我没太想清楚。。。。
【在 m***2 的大作中提到】
: 看起来有戏，xyzxyz这种算k=2还是1
|
k****r
发帖数: 807 | 23 明显不行：XYXXYYZZ。
按您的思路似乎算不出2了，且算法不是ad hoc
【在 m***2 的大作中提到】
: 有一个笨办法，不知道对不对，其实就是统计：
: 1. Y出现以前X的个数 xcount
: 2. Y的个数 ycount
: 3. Y出现以后的Z的个数 zcount
: 再算三者的最小值
: 因为第一个Y出现以后的X都没有意义，最后一个Y之前的Z也没有意义
: int xcount = 0;
: int ycount = 0;
: int zcount = 0;
: boolean ystarted = false;
|
m***2
发帖数: 595 | 24 也是
【在 k****r 的大作中提到】
: 明显不行：XYXXYYZZ。
: 按您的思路似乎算不出2了，且算法不是ad hoc
|
w*******u
发帖数: 267 | 25 显然这是错的。
参见 s = "xyxy" a = "xy"
你这个结果是2，实际应该是1.
【在 k****r 的大作中提到】
: 我的思路：
: 建立一个一维dp table，大小为A的size；
: 开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
: 如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
: 都完事了dp［n － 1］就是结果。
|
w*******u
发帖数: 267 | |
k****r
发帖数: 807 | 27 meme同学，你咋总是写3个的呢？A的size不是3咋办：）
max[
【在 m***2 的大作中提到】
: 也是
|
m***2
发帖数: 595 | 28 先按3来嘛，要是对了我再扩展到m
【在 k****r 的大作中提到】
: meme同学，你咋总是写3个的呢？A的size不是3咋办：）
:
: max[
|
m***2
发帖数: 595 | 29 总的来说就是一轮一轮的扫描，一旦发现顺序不是XYZ这种，就开始重新一轮
每一轮用count[]来记当前轮，用max[]来记录历史上最多的
具体如下：
比如XXYY XYYZ YYZ XYY XXYYZ就是5轮:
1. XXYY
2. XYYZ
3. YYZ
4. XYY
5. XXYYZ
每次发现ch[i] < ch[i - 1]就表示顺序不对了，开始新的一轮，count全部清空
max[0]表示历史上X^的最大次数
max[1]表示历史上XY^的最大次数
max[2]表示历史上XYZ^的最大次数
public class Solution {
public int getK(String B) {
char[] ch = B.toCharArray();
int n = B.length();
int[] count = new int[3];
int[] max = new int[3];
for (int i = 0; i < n; i++) {
if (i == 0 || ch[i - 1] > ch[i]) { //顺序不对就清空重新计数
count[0] = 0;
count[1] = 0;
count[2] = 0;
}
switch(ch[i]) {
case 'X': {
count[0]++;
max[0] = Math.max(max[0],count[0]);
break;
}
case 'Y': {
if (count[1] < max[0]) { //X够了才计Y
count[1]++;
max[1] = Math.max(max[1],count[1]);
break;
}
}
case 'Z': {
if (count[2] < max[1]) {//XY够了才计Z
count[2]++;
max[2] = Math.max(max[2],count[2]);
break;
}
}
}
}
return max[2];
}
}
谁来帮忙想个妖孽的测试集吧！
XYXXYZXXYXZYZZZYXX
自己跑出不对了，应该返回3才对，跪了
啊啊，突然被这句话打败了：
A可能有重复的char |
b***e
发帖数: 1419 | 30 不用拿个dp的锤子到处找钉子。这个题直接搞就好了。
Test if A^k is in B takes simple O(n), as follows:
var test = function(A, k, B) {
var i = 0;
var next = A[i];
var quota = k;
for(j = 0; j < B.length; j++) {
if (B[j] == next) {
quota--;
}
if (quota == 0) {
i++;
if (i >= A.length) {
return true;
} else {
next = A[i];
quota = k;
}
}
}
return false;
};
Then apply binary search to find the largest k, as follows:
var searchK = function(A, B) {
var bot = 1;
var top = Math.floor(B.length / A.length);
while (bot < top) {
var mid = (bot + top) / 2;
if (test(A, mid, B)) {
bot = mid;
} else {
top = mid;
}
}
return test(A, top, B);
};
This take O(n*log(k)), overall.
【在 w*******u 的大作中提到】
: 这题目好难，用动态规划也解不出。
|
|
|
m***2
发帖数: 595 | 31 就酱，挺好
【在 b***e 的大作中提到】
: 不用拿个dp的锤子到处找钉子。这个题直接搞就好了。
: Test if A^k is in B takes simple O(n), as follows:
: var test = function(A, k, B) {
: var i = 0;
: var next = A[i];
: var quota = k;
: for(j = 0; j < B.length; j++) {
: if (B[j] == next) {
: quota--;
: }
|
p*********g
发帖数: 911 | 32 请教一下 A 是ab, B是ababab 那么K是多少呢？谢谢。
【在 b***e 的大作中提到】
: 不用拿个dp的锤子到处找钉子。这个题直接搞就好了。
: Test if A^k is in B takes simple O(n), as follows:
: var test = function(A, k, B) {
: var i = 0;
: var next = A[i];
: var quota = k;
: for(j = 0; j < B.length; j++) {
: if (B[j] == next) {
: quota--;
: }
|
b***e
发帖数: 1419 | 33 1
【在 p*********g 的大作中提到】
: 请教一下 A 是ab, B是ababab 那么K是多少呢？谢谢。
|
p*********g
发帖数: 911 | 34 能解析一下你的程序，在ababab去8情况下是输出几吗？不好意思，在外面，没有电脑。
【在 b***e 的大作中提到】
: 1
|
k****r
发帖数: 807 | 35 是2吧大牛
【在 b***e 的大作中提到】
: 1
|
w*****1
发帖数: 6807 | 36 我也觉的肯定是2，不然一点难度都没有
【在 k****r 的大作中提到】
: 是2吧大牛
|
n*******s
发帖数: 17267 | 37 你看到aabb了？
【在 w*****1 的大作中提到】
: 我也觉的肯定是2，不然一点难度都没有
|
b***e
发帖数: 1419 | 38 看花眼了，是2。
【在 k****r 的大作中提到】
: 是2吧大牛
|
l*******i
发帖数: 25 | 39 @blaze: wrong solution, the variable "i" never resets. try "aabaabbcc". |
b***e
发帖数: 1419 | 40 Come on, did you even seriously read my post?
【在 l*******i 的大作中提到】
: @blaze: wrong solution, the variable "i" never resets. try "aabaabbcc".
|
|
|
l*******i
发帖数: 25 | 41 @Blaze. Sorry. I jumped the gun a bit. Ur solution should work. |
l*********u
发帖数: 19053 | 42 应该是2，B里有aabb
【在 b***e 的大作中提到】
: 1
|
l*n
发帖数: 529 | 43 逻辑有问题，quote到头之后直接检查下一个char in A了，这不对。比如test("xyx",
2, "aaxxyyyxxaa")，检查每个char都符合quota，但其实应该fail。
if (quota == 0) {
i++;
if (i >= A.length) {
return true;
} else {
next = A[i];
quota = k;
}
}
【在 b***e 的大作中提到】
: 不用拿个dp的锤子到处找钉子。这个题直接搞就好了。
: Test if A^k is in B takes simple O(n), as follows:
: var test = function(A, k, B) {
: var i = 0;
: var next = A[i];
: var quota = k;
: for(j = 0; j < B.length; j++) {
: if (B[j] == next) {
: quota--;
: }
|
f********y
发帖数: 156 | 44 他解法没错吧。 subsequence 就是按顺序，但是可以不连续
对了，复杂度应该是 o(n* log(n/k)) = o(n*logn - n*logk) 吧，要是k很小，实际接
近o(n*logn)
逻辑有问题，quote到头之后直接检查下一个char in A了，这不对。比如test("xyx",
2, "aaxxyyyxxaa")，检查每个char都符合quota，但其........
【在 l*n 的大作中提到】
: 逻辑有问题，quote到头之后直接检查下一个char in A了，这不对。比如test("xyx",
: 2, "aaxxyyyxxaa")，检查每个char都符合quota，但其实应该fail。
: if (quota == 0) {
: i++;
: if (i >= A.length) {
: return true;
: } else {
: next = A[i];
: quota = k;
: }
|
l*n
发帖数: 529 | 45 哦，我看成substring了。subsequence的话是没问题了。
,
【在 f********y 的大作中提到】
: 他解法没错吧。 subsequence 就是按顺序，但是可以不连续
: 对了，复杂度应该是 o(n* log(n/k)) = o(n*logn - n*logk) 吧，要是k很小，实际接
: 近o(n*logn)
:
: 逻辑有问题，quote到头之后直接检查下一个char in A了，这不对。比如test("xyx",
: 2, "aaxxyyyxxaa")，检查每个char都符合quota，但其........
|
I*******g
发帖数: 7600 | 46 ZENEFITS问这么傻逼的问题，关键它能够给多少的package?
【在 x******8 的大作中提到】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.
|
b***e
发帖数: 1419 | 47 substring的话就太容易了。
【在 l*n 的大作中提到】
: 哦，我看成substring了。subsequence的话是没问题了。
:
: ,
|
b***e
发帖数: 1419 | 48 还是送佛送到西：其实我前面的一个帖子说了，k要从小向大试探，比如k=1,2,4,8,...
，一直到k过大。这以后二分。严格的log(k)个pass。我的程序里做了简化。
,
【在 f********y 的大作中提到】
: 他解法没错吧。 subsequence 就是按顺序，但是可以不连续
: 对了，复杂度应该是 o(n* log(n/k)) = o(n*logn - n*logk) 吧，要是k很小，实际接
: 近o(n*logn)
:
: 逻辑有问题，quote到头之后直接检查下一个char in A了，这不对。比如test("xyx",
: 2, "aaxxyyyxxaa")，检查每个char都符合quota，但其........
|
