logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
LinkedIn onsite一道题
avatar
LinkedIn onsite一道题# JobHunting - 待字闺中
j*r
1 楼
给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
if (s.charAt(i) == s.charAt(j)){
Set subSet = getAllPalidrome(s, i + 1, j - 1);
ret.addAll(subSet);
for (String str : subSet) ret.add(s.charAt(i) + str + s.charAt(i));
}
}
}
allSubSet.put(ind, ret);
return ret;
}
avatar
l*s
2 楼
如果s不是空的话，感觉这步永远走不到
if (s == null || s.size() == 0) { ret.add(""); return ret;}
avatar
f*b
3 楼
谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
f*y
4 楼
要求所有可能，不是总数。这个必须dfs，怎么去重应该有些优化的地方

谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
j*r
5 楼
这个吗？
266 Palindrome Permutation
收费题。。。没钱做

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
l*s
6 楼
Tested on Coderpad. Looks good.
private static ISet getPal(string s){
IDictionary> dict = new Dictionary>();
for(int i = 0; i < s.Length; i++){
if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
dict[s[i]].Add(i);
}
ISet result = new HashSet();
dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
dict);
return result;
}
private static void dfs(ISet result, StringBuilder sLeft,
StringBuilder sRight, string s, int left, int right, IDictionary> dict){
for(int i = left; i <= right; i++){
result.Add(sLeft.ToString() + s[i] + sRight.ToString());
for(int j = 0; j < dict[s[i]].Count; j++)
if(dict[s[i]][j] <= i) continue;
else if (dict[s[i]][j] > right) break;
else{
sLeft.Append(s[i]);
sRight.Insert(0, s[i]);
result.Add(sLeft.ToString() + sRight.ToString());
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
sLeft.Length -= 1;
sRight.Remove(0, 1);
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
}
}
}
avatar
j*r
7 楼
这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
重的

,

【在 l******s 的大作中提到】
: Tested on Coderpad. Looks good.
: private static ISet getPal(string s){
: IDictionary> dict = new Dictionary>();
: for(int i = 0; i < s.Length; i++){
: if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
: dict[s[i]].Add(i);
: }
: ISet result = new HashSet();
: dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
: dict);
avatar
l*s
8 楼
好像很难。比如说这个例子abcbabcba，当找到前面一段abcba后，后面的abcba怎么也无
法预料，我无法从现有的字符串中找出这两段的关联的必然联系，所以也必须走到
Substring from index 3 to 7才能确定是不是重复，而找到那一步后的HashSet.Add
却是O(1)的，加不加没有时间上的区别。
期待更好的答案。

【在 j********r 的大作中提到】
: 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
: 重的
:
: ,
avatar
l*s
9 楼
我也没钱做，不过应该跟266和267也不同。
如果是说DP，我只想到Palindrome Patition，那就更差得远了。

【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
avatar
l*a
10 楼
求出所有可能的回文子序列，为什么会是动态规划呢？比如aaaaaaaaaa，我看符合条件
的子序列有指数级别个

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
w*k
11 楼
不大可能，那两道收费的分别是Easy和Medium，成功率很高，这题应该不是这个级别的。

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
d*v
12 楼
现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
两次馆子就出来了。

【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
avatar
j*r
13 楼
说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
细节没考虑到，想要查错，手动过test case，简直就是自虐
现在onsite好多时候，难度不在思路，在于细节了

【在 d******v 的大作中提到】
: 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
: 两次馆子就出来了。
avatar
E*g
14 楼
楼主好人，请问面的什么职位啊？
avatar
w*g
15 楼
just printing the results takes exponential time in worst case. how can it
be quadratic time.
I agree that dynamic programming is the approach
find results for size 2,4,6,... is sufficient

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
b*e
16 楼
/*
Find all substring palindomes. No dupe.
Vanilla JS. Run it with node.js or in browser console.
*/
function reverse(s) {
var o = '';
for (var i = s.length - 1; i >= 0; i--)
o += s[i];
return o;
};
var p = function(s) {
var prevLookup = {};
var nextLookup = {};

for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (!prevLookup[c]) {
prevLookup[c] = [];
nextLookup[c] = [];
}
}
for (var i = 0; i < s.length; i++) {
for(var c in prevLookup) {
var lookup = prevLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == 0) {
lookup[i] = null;
} else {
lookup[i] = lookup[i-1];
}
}
}
}
for (var i = s.length-1; i >= 0; i--) {
for(var c in nextLookup) {
var lookup = nextLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == s.length-1) {
lookup[i] = null;
} else {
lookup[i] = lookup[i+1];
}
}
}
}
console.log(prevLookup);
console.log(nextLookup);
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
_rec(0, s.length-1, "");
};
var s = "abcbabcba";
var s2 = "aaaaaaaa";
p(s2);

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
l*n
17 楼
re这个，题确实不在多而在精。碰到原题要能从细节上防御好，不是原题也要践行自己
练题时的全方位考虑。

【在 j********r 的大作中提到】
: 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
: 也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
: 另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
: 都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
: 问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
: 细节没考虑到，想要查错，手动过test case，简直就是自虐
: 现在onsite好多时候，难度不在思路，在于细节了
avatar
l*n
18 楼
假设"可以删除任意字符"是能删除任意位置、任意多个，那么复杂度肯定是至少O(2^n)
。既然已经指数级别了，也不少一个O(n)，索性就直接枚举然后O(n)判断是否符合
palidrome好了。

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
j*r
19 楼
谢谢，不过js看不太懂，能说一下思路和复杂度吗？

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
b*e
20 楼
看这段就够了：
// start code
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
// end code
nextLookup[c][i] = min(j, where j >= i and s[j] = c)
prevLookup[c][i] = max(k, where k <= i and s[k] = c)

【在 j********r 的大作中提到】
: 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
avatar
j*r
21 楼
感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
j*g
22 楼
可以删除任意字符，那不是等价于 找所有可能序列

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
b*e
23 楼
Did you even bother to run the code? It's simple: copy and paste the code to
chrome console.

【在 j********r 的大作中提到】
: 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
avatar
s*x
24 楼
这个很找最长回文子序列差不多吧？从任意位置往两边扩。O(N^2）
avatar
j*r
25 楼
不好意思，确实不熟悉js。
刚才跑了一下，几种情况都解决的很好，很赞。

to

【在 b***e 的大作中提到】
: Did you even bother to run the code? It's simple: copy and paste the code to
: chrome console.
avatar
b*e
26 楼
其实不必纠结于JS。这种纯算法的题用什么都一样。这也是为什么一般interview都让
你随便挑语言。这个JS program其实跟Java program也没有什么本质区别，除了一些
language primitives不完全一样。
我的解法，如果你看懂了，是完美解法。无重复的逐一完全遍历所有的substring
palindrome。复杂度就是O(the number of palindrome substrings).

【在 j********r 的大作中提到】
: 不好意思，确实不熟悉js。
: 刚才跑了一下，几种情况都解决的很好，很赞。
:
: to
avatar
O*A
27 楼
本题应该不是dp。Otherwise， what's the sub-optimal structure and overlapping?
blaze 的解法很巧妙。关键是建立两个不同方向的lookup table,每个entry分别是字符
以及一个数组，数组中的 i 元素 是从 i 位置往左（右）看能看到的该字符的最近位
置。然后从两边向中间扫描。
关于leetcode 266， 267 参考：
http://buttercola.blogspot.com/2015/08/leetcode-palindrome-perm
avatar
a*u
28 楼
看了半小时才看懂，这方法太帅了！

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
r*g
29 楼
very nice solution
关键是对每个可能的char，维护了一维数组，数组中的i意思是从这个i看过去下一个
same char出现的位置，这样DFS就是对char来做遍历。
收藏了，准备有时间谢谢。
thanks

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
r*g
30 楼
而且这个解法很巧妙的解决了奇数长和偶数长的问题。
avatar
r*g
31 楼
而且这个解法很巧妙的解决了奇数长和偶数长的问题。
avatar
j*r
32 楼
给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
if (s.charAt(i) == s.charAt(j)){
Set subSet = getAllPalidrome(s, i + 1, j - 1);
ret.addAll(subSet);
for (String str : subSet) ret.add(s.charAt(i) + str + s.charAt(i));
}
}
}
allSubSet.put(ind, ret);
return ret;
}
avatar
l*s
33 楼
如果s不是空的话，感觉这步永远走不到
if (s == null || s.size() == 0) { ret.add(""); return ret;}
avatar
f*b
34 楼
谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
f*y
35 楼
要求所有可能，不是总数。这个必须dfs，怎么去重应该有些优化的地方

谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
j*r
36 楼
这个吗？
266 Palindrome Permutation
收费题。。。没钱做

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
l*s
37 楼
Tested on Coderpad. Looks good.
private static ISet getPal(string s){
IDictionary> dict = new Dictionary>();
for(int i = 0; i < s.Length; i++){
if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
dict[s[i]].Add(i);
}
ISet result = new HashSet();
dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
dict);
return result;
}
private static void dfs(ISet result, StringBuilder sLeft,
StringBuilder sRight, string s, int left, int right, IDictionary> dict){
for(int i = left; i <= right; i++){
result.Add(sLeft.ToString() + s[i] + sRight.ToString());
for(int j = 0; j < dict[s[i]].Count; j++)
if(dict[s[i]][j] <= i) continue;
else if (dict[s[i]][j] > right) break;
else{
sLeft.Append(s[i]);
sRight.Insert(0, s[i]);
result.Add(sLeft.ToString() + sRight.ToString());
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
sLeft.Length -= 1;
sRight.Remove(0, 1);
dfs(result, sLeft, sRight, s, i + 1, dict[s[i]][j] - 1, dict);
}
}
}
avatar
j*r
38 楼
这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
重的

,

【在 l******s 的大作中提到】
: Tested on Coderpad. Looks good.
: private static ISet getPal(string s){
: IDictionary> dict = new Dictionary>();
: for(int i = 0; i < s.Length; i++){
: if(!dict.ContainsKey(s[i])) dict[s[i]] = new List();
: dict[s[i]].Add(i);
: }
: ISet result = new HashSet();
: dfs(result, new StringBuilder(), new StringBuilder(), s, 0, s.Length - 1,
: dict);
avatar
l*s
39 楼
好像很难。比如说这个例子abcbabcba，当找到前面一段abcba后，后面的abcba怎么也无
法预料，我无法从现有的字符串中找出这两段的关联的必然联系，所以也必须走到
Substring from index 3 to 7才能确定是不是重复，而找到那一步后的HashSet.Add
却是O(1)的，加不加没有时间上的区别。
期待更好的答案。

【在 j********r 的大作中提到】
: 这个复杂度多少？worst case好像也有o(2^n), 而且也没有很好的去重，都是用set去
: 重的
:
: ,
avatar
l*s
40 楼
我也没钱做，不过应该跟266和267也不同。
如果是说DP，我只想到Palindrome Patition，那就更差得远了。

【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
avatar
l*a
41 楼
求出所有可能的回文子序列，为什么会是动态规划呢？比如aaaaaaaaaa，我看符合条件
的子序列有指数级别个

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
w*k
42 楼
不大可能，那两道收费的分别是Easy和Medium，成功率很高，这题应该不是这个级别的。

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
d*v
43 楼
现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
两次馆子就出来了。

【在 j********r 的大作中提到】
: 这个吗？
: 266 Palindrome Permutation
: 收费题。。。没钱做
avatar
j*r
44 楼
说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
细节没考虑到，想要查错，手动过test case，简直就是自虐
现在onsite好多时候，难度不在思路，在于细节了

【在 d******v 的大作中提到】
: 现在是刷题去找一份几十万美刀的工作啊，这百八十块的前期投资还是要舍得的，少去
: 两次馆子就出来了。
avatar
E*g
45 楼
楼主好人，请问面的什么职位啊？
avatar
w*g
46 楼
just printing the results takes exponential time in worst case. how can it
be quadratic time.
I agree that dynamic programming is the approach
find results for size 2,4,6,... is sufficient

【在 f*******b 的大作中提到】
: 谢谢分享，这是leetcode原题啊哥们，用dp做，时间O(n^2) 空间O(n^2)
avatar
b*e
47 楼
/*
Find all substring palindomes. No dupe.
Vanilla JS. Run it with node.js or in browser console.
*/
function reverse(s) {
var o = '';
for (var i = s.length - 1; i >= 0; i--)
o += s[i];
return o;
};
var p = function(s) {
var prevLookup = {};
var nextLookup = {};

for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (!prevLookup[c]) {
prevLookup[c] = [];
nextLookup[c] = [];
}
}
for (var i = 0; i < s.length; i++) {
for(var c in prevLookup) {
var lookup = prevLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == 0) {
lookup[i] = null;
} else {
lookup[i] = lookup[i-1];
}
}
}
}
for (var i = s.length-1; i >= 0; i--) {
for(var c in nextLookup) {
var lookup = nextLookup[c];
if (c == s.charAt(i)) {
lookup[i] = i;
} else {
if (i == s.length-1) {
lookup[i] = null;
} else {
lookup[i] = lookup[i+1];
}
}
}
}
console.log(prevLookup);
console.log(nextLookup);
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
_rec(0, s.length-1, "");
};
var s = "abcbabcba";
var s2 = "aaaaaaaa";
p(s2);

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
l*n
48 楼
re这个，题确实不在多而在精。碰到原题要能从细节上防御好，不是原题也要践行自己
练题时的全方位考虑。

【在 j********r 的大作中提到】
: 说的对，不过最近leetcode狂加了50道题，做不过来，而且收费的题目做的人少，答案
: 也少，所以我就没看。做完lintcode可以考虑再来做做这些题目。
: 另外我感觉题目不一定做很多，但一定要做精，做通，leetcode现在那些题，我也不能
: 都保证20分钟bug free用两种以上方法写出来，好几次onsite都是原题，但是因为细节
: 问题，都是坑坑巴巴弄了好长时间，根本没机会做follow up. 白板的时候，如果一点
: 细节没考虑到，想要查错，手动过test case，简直就是自虐
: 现在onsite好多时候，难度不在思路，在于细节了
avatar
l*n
49 楼
假设"可以删除任意字符"是能删除任意位置、任意多个，那么复杂度肯定是至少O(2^n)
。既然已经指数级别了，也不少一个O(n)，索性就直接枚举然后O(n)判断是否符合
palidrome好了。

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
j*r
50 楼
谢谢，不过js看不太懂，能说一下思路和复杂度吗？

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
b*e
51 楼
看这段就够了：
// start code
var _rec = function(left, right, accum) {
console.log(accum + reverse(accum));
if (left > right) return;
for (var c in prevLookup) {
var leftMostPos = nextLookup[c][left];
var rightMostPos = prevLookup[c][right];
if (leftMostPos != null && leftMostPos <= right) {
console.log(accum + c + reverse(accum));
if (rightMostPos > leftMostPos) {
_rec(leftMostPos + 1, rightMostPos -1, accum + c);
}
}
}
};
// end code
nextLookup[c][i] = min(j, where j >= i and s[j] = c)
prevLookup[c][i] = max(k, where k <= i and s[k] = c)

【在 j********r 的大作中提到】
: 谢谢，不过js看不太懂，能说一下思路和复杂度吗？
avatar
j*r
52 楼
感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
j*g
53 楼
可以删除任意字符，那不是等价于 找所有可能序列

【在 j********r 的大作中提到】
: 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
: 我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
: Map> allSubSet = new HashMap();
: Set getAllPalidrome(String s, int x, int y){
: int ind = x * s.length() + y;
: if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
: Set ret = new HashSet();
: if (s == null || s.size() == 0) { ret.add(""); return ret;}
: if (s.size() == 1) { ret.add(s); return ret;}
: for(int i = x; i <= y; i++){
avatar
b*e
54 楼
Did you even bother to run the code? It's simple: copy and paste the code to
chrome console.

【在 j********r 的大作中提到】
: 感觉还是O(2^n)级别的，特别是bbbbbb, 这个要输出2^6个结果
avatar
s*x
55 楼
这个很找最长回文子序列差不多吧？从任意位置往两边扩。O(N^2）
avatar
j*r
56 楼
不好意思，确实不熟悉js。
刚才跑了一下，几种情况都解决的很好，很赞。

to

【在 b***e 的大作中提到】
: Did you even bother to run the code? It's simple: copy and paste the code to
: chrome console.
avatar
b*e
57 楼
其实不必纠结于JS。这种纯算法的题用什么都一样。这也是为什么一般interview都让
你随便挑语言。这个JS program其实跟Java program也没有什么本质区别，除了一些
language primitives不完全一样。
我的解法，如果你看懂了，是完美解法。无重复的逐一完全遍历所有的substring
palindrome。复杂度就是O(the number of palindrome substrings).

【在 j********r 的大作中提到】
: 不好意思，确实不熟悉js。
: 刚才跑了一下，几种情况都解决的很好，很赞。
:
: to
avatar
O*A
58 楼
本题应该不是dp。Otherwise， what's the sub-optimal structure and overlapping?
blaze 的解法很巧妙。关键是建立两个不同方向的lookup table,每个entry分别是字符
以及一个数组，数组中的 i 元素 是从 i 位置往左（右）看能看到的该字符的最近位
置。然后从两边向中间扫描。
关于leetcode 266， 267 参考：
http://buttercola.blogspot.com/2015/08/leetcode-palindrome-perm
avatar
a*u
59 楼
看了半小时才看懂，这方法太帅了！

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
r*g
60 楼
very nice solution
关键是对每个可能的char，维护了一维数组，数组中的i意思是从这个i看过去下一个
same char出现的位置，这样DFS就是对char来做遍历。
收藏了，准备有时间谢谢。
thanks

【在 b***e 的大作中提到】
: /*
: Find all substring palindomes. No dupe.
: Vanilla JS. Run it with node.js or in browser console.
: */
: function reverse(s) {
: var o = '';
: for (var i = s.length - 1; i >= 0; i--)
: o += s[i];
: return o;
: };
avatar
r*g
61 楼
而且这个解法很巧妙的解决了奇数长和偶数长的问题。
avatar
r*g
62 楼
而且这个解法很巧妙的解决了奇数长和偶数长的问题。
avatar
k*r
63 楼
anyone who can share a java/c++ code? Thank you and Blaze!
avatar
I*c
64 楼
我的java实现，参考了Blaze的思路，不过不知道真正理解了他的思路没有，因为我不
太看得懂javascript.下面是几个点：
1. 这个题目用的是backtracking而不是dp，因为dp不可能给你产生排列组合。dp通常
就是给你一个最值。
2. 时间复杂度是指数级。
3. 题目的本质是产生排列。
4. 一般的backtracking来形成字符串的话,从现有字母集中每次任意挑一个字母,然后
从剩下的字母里继续挑。把所有字母都加到字符串里面去了，这轮程序也就完了。这个
题目因为有个顺序的限制条件，决定程序怎样进行下去并不能用剩下多少字符来决定，
而应该是用已经加入字符串的字母的位置来决定。
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
public class Example5 {
public static void main(String [] args){
Example5 o = new Example5();
List results = o.setUp("abcbabcba");
for(String str: results){
System.out.println(str);
}
}
public List setUp(String palidrome){
HashMap > map = new HashMap List>();
HashMap locations = new HashMap Pointers>();
char [] chs = palidrome.toCharArray();
int i = 0;
for(i=0;iif(map.containsKey(chs[i])){
map.get(chs[i]).add(i);
}
else{
List tmp = new ArrayList ();
tmp.add(i);
map.put(chs[i],tmp);
}
}
Set keySet = map.keySet();
Iterator iter = keySet.iterator();
List results = new ArrayList ();
while(iter.hasNext()){
Character ch=iter.next();
//results.add(ch.toString());
int size = map.get(ch).size();
locations.put(ch, new Pointers(0,size-1));
}
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
dfs(results,0,chs.length-1,sb1,sb2,keySet,map,locations);
return results;
}

private class Pointers {
int left;
int right;
public Pointers(int left, int right){
this.left = left;
this.right = right;
}
}

public void dfs (List results, int left, int right,
StringBuilder sb1, StringBuilder sb2, Set keySet, HashMap <
Character, List> map, HashMap locations) {
Iterator iter = keySet.iterator();
while(iter.hasNext()){
Character ch=iter.next();
//System.out.println("ch="+ch+" left="+left+" right="+right);
Pointers p=locations.get(ch);
//System.out.println("left1="+p.left+" right1="+p.right);
List nums = map.get(ch);
int oldLeft = p.left;
int oldRight = p.right;
while((p.left<=p.right)&&(nums.get(p.left)p.left++;
}
while((p.left<=p.right)&&(nums.get(p.right)>right)){
p.right--;
}
if(p.left<=p.right){
results.add(sb1.toString()+ch+sb2.toString());
//System.out.println(sb1.toString()+ch+sb2.toString());
}
if(p.leftsb1.append(ch);
sb2.insert(0,ch);
int tmp1 = p.left;
int tmp2 = p.right;
p.left++;
p.right--;
//System.out.println(sb1.toString()+sb2.toString());
results.add(sb1.toString()+sb2.toString());
dfs(results,nums.get(tmp1)+1,nums.get(tmp2)-1,sb1,sb2,keySet
,map,locations);
sb1.deleteCharAt(sb1.length()-1);
sb2.deleteCharAt(0);
}
p.left = oldLeft;
p.right = oldRight;
}
}
}
相关阅读
谁有跳马题的原题？EMC 面试 求指教这个timeline是啥意思一个基本的复杂度问题10分钟前的G家电面面经有人做projecteuler吗？急问：学校postdoc能随时走人吗？有谁是跳槽去微软的，求助一个问题facebook hackercup里的一道题三星德州最近cs招工市场？recruiter邮件中的一个问题要了ssn,背景调查会查些什么?码农的优势和劣势拿到G家口头offer，想问一下它家sign on bonus大概可以有多少？iterator 实现 如何 peek()，pop()?M 家 只要C/C++吗？ 只熟悉java的要不要啊？请问如果onsite被拒了还能发信问原因么？我的悲惨经历告诉你碰上很熟的题怎么办太郁闷了！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。