e***s
发帖数: 799 | 1 最近做题和看板上的帖子，个人觉得hash这个东西用来删除或避免重复是不是不靠谱。
因为有conflict。
比如一道leetcode的题
Generate Parentheses
//Given n pairs of parentheses, write a function to generate all
combinations of well-formed parentheses.
//For example, given n = 3, a solution set is:
//"((()))", "(()())", "(())()", "()(())", "()()()"
我想用DP，每次在前一个结果基础上 左边加"()"，右边加"()，再把整个"(" + result
+ ")".
用HashSet来存放结果，每次加的时候自动排除重复。
我想问HashSet是不是不能保证100%正确？ 正确的做法应该是怎么样了？ | f*******n
发帖数: 12623 | 2 hash collision影响performance。不影响是否正确。
就算你有很烂的hash function，所有东西的hashCode都是一样。这样hash table就变
成linked list。加东西要O(n)。但是还是正确。 | e***s
发帖数: 799 | 3 非常感谢，学艺不精，惭愧。。。
【在 f*******n 的大作中提到】
: hash collision影响performance。不影响是否正确。
: 就算你有很烂的hash function，所有东西的hashCode都是一样。这样hash table就变
: 成linked list。加东西要O(n)。但是还是正确。
| f*******t
发帖数: 7549 | 4 而且这题明显不需要hashset
【在 e***s 的大作中提到】
: 非常感谢，学艺不精，惭愧。。。
| a*******y
发帖数: 1040 | 5 这个recursion吧,随便写了下，可能有bug
void GenerateParenthesis(int left,int right, int level, string str, vector<
string> &result)
{
if(left ==0 && right ==0)
{
result.push_back(str)
return;
}
if (left > 0)
{
str[level] = ')';
GenerateParenthesis(left -1, right + 1,level+1, str, result);
}
if (right > 0)
{
str[level] = '(';
GenerateParenthesis(left, right -1,level+1, str, result);
}
return;
}
call this function with
string str(2*n,'\0');
vector result;
GenerateParentesis(n,0,0,str,result); | h****e
发帖数: 928 | 6 一般这些生成各种组合之类的题目都不应该用hash之类的数据结构来避免
重复，一用就不可能最优。通解应该是生成各种组合的自身过程中就能够
保证不重复。 |
|
