W********e 发帖数: 45 | 1 题目是leetcode上的Generate Parentheses。
不理解为什么有时候用DFS需要resize,有时候不需要。下面这第一种是resize了,
resize的意义是什么?:
void CombinationPar(vector& result, string& sample, int deep,
2: int n, int leftNum, int rightNum)
3: {
4: if(deep == 2*n)
5: {
6: result.push_back(sample);
7: return;
8: }
9: if(leftNum
10: {
11: sample.push_back('(');
12: CombinationPar(result, sample, deep+1, n, leftNum+1, rightNum
);
13: sample.resize(sample.size()-1); //?????????????
?
14: }
15: if(rightNum
16: {
17: sample.push_back(')');
18: CombinationPar(result, sample, deep+1, n, leftNum, rightNum+1
);
19: sample.resize(sample.size()-1); //?????????????
?
20: }
但是看另一个人的code,没有这个动作:
class Solution {
public:
void printPar(int l, int r, vector& result, char* str, int idx)
{
if (l < 0 || r < l) return;
if (l == 0 && r == 0)
{
str[idx] = '\0';
result.push_back(string(str));
}
else
{
if (l > 0)
{
str[idx] = '(';
printPar(l-1, r, result, str, idx+1);
//不需要做什么pop或者resize的动作??????????????
??
}
if (r > l)
{
str[idx] = ')';
printPar(l, r-1, result, str, idx+1);
//不需要做什么pop或者resize的动作??????????????
??
}
}
}
vector generateParenthesis(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector result;
char* str = new char[2*n+1];
printPar(n, n, result, str, 0);
delete []str;
return result;
}
};
一是不太理解为什么这么样叫做DFS,二是不理解为什么resize,刚入门,请各位指教
!! | s**x 发帖数: 405 | 2 std::string needs resize, char* does not | W********e 发帖数: 45 | 3
resize的意义是什么?
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : std::string needs resize, char* does not
| s**x 发帖数: 405 | | W********e 发帖数: 45 | 5
哦,我是想不明白,不是resize本身,二是为什么要做这个动作,说白了是不理解这里
的DFS啊!
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 拜托您好好阅读STL文档 : http://www.cplusplus.com/reference/string/string/resize/
| s**x 发帖数: 405 | 6 resize cancels the push_back.
You can also use pop_back() instead of resize(size()-1), it is the same. | o****d 发帖数: 2835 | 7 他的目的是把sample的最后一个entry去掉
其实他想做的就是 sample.pop_back(),把之前sample.push_back('(')的清掉
(说实话,感觉他这么写有点难看)
另外 如果CombinationPar的第二个参数 不是引用(string& sample)的话
就不用额外做这个处理了
sample.push_back('(');
CombinationPar(result, sample, deep+1, n, leftNum+1, rightNum);
sample.resize(sample.size()-1);
【在 W********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目是leetcode上的Generate Parentheses。 : 不理解为什么有时候用DFS需要resize,有时候不需要。下面这第一种是resize了, : resize的意义是什么?: : void CombinationPar(vector& result, string& sample, int deep, : 2: int n, int leftNum, int rightNum) : 3: { : 4: if(deep == 2*n) : 5: { : 6: result.push_back(sample); : 7: return;
| s**x 发帖数: 405 | 8 难看是难看了点,但是避免字符串复制
如果不传引用就可以直接传 sample+"(" | W********e 发帖数: 45 | 9
都是高手!
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难看是难看了点,但是避免字符串复制 : 如果不传引用就可以直接传 sample+"("
| o****d 发帖数: 2835 | 10 恩 用引用 避免复制是对的
我想说的意思是 用resize比起pop_back难看懂 理解上不是那么直接
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难看是难看了点,但是避免字符串复制 : 如果不传引用就可以直接传 sample+"("
|
|