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 的大作中提到】
: std::string needs resize, char* does not
| s**x
发帖数: 405 | | W********e
发帖数: 45 | 5
哦，我是想不明白，不是resize本身，二是为什么要做这个动作，说白了是不理解这里
的DFS啊！
【在 s**x 的大作中提到】
: 拜托您好好阅读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 的大作中提到】
: 题目是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 的大作中提到】
: 难看是难看了点，但是避免字符串复制
: 如果不传引用就可以直接传 sample+"("
| o****d
发帖数: 2835 | 10 恩 用引用 避免复制是对的
我想说的意思是 用resize比起pop_back难看懂 理解上不是那么直接
【在 s**x 的大作中提到】
: 难看是难看了点，但是避免字符串复制
: 如果不传引用就可以直接传 sample+"("
|
|
