LeetCode.22 合法括号对的总排列

leetcode

题目

给定括号的对数。要求写出程序。把所有可能的，符合运算括号排列的都输出出来。

总的结果数目

比如当给定括号 的对数为n的时候。总的字符数是n*2。那么总的结果可能是:

相当于有2*n个箱子。每个箱子可以选择’(‘或者’)’。那么总的数目有2^(n<<1)个。

size_t total_size = (1<<(n<<1)) + 1;
char **ret = (char**) malloc(sizeof(char*) * total_size);
memset(ret, 0, sizeof(char*) * total_size);

第pos个字符应该放什么?

由于所有的结果都已经放到了ret中。并且有一个ret_tail记录ret中接下来的空箱子的位置。

for i = 0 : ret {
    字符串 = ret[i]
    根据  字符串 里面的(/)符号数
        决定在后面追加的内容
}

循环体可以写成

ret[0] = "(";
for (pos = 1; pos < (n<<1); pos++) {
    // 当前字符串的数目
    cnt = ret_tail;
    for (i = 0; i < cnt; i++) {
        string = ret[i];
        如果不生成新的字符串，直接在ret[i]上追加字符
        如果需要生成新的字符串，ret_tail申请空间，复制ret[i],然后追加字符到ret[ret_tail];
            ret_tail++;
    }
}

加速判断

为了加速判断，每个字符串申请的空间是:

  1. 先与4 bytes对齐
  2. 再多申请4个int的空间
|........string......|...|used|left|

也就是前面都是正常的C字符串。只不过在这个字符串后面，多申请了一段空间用来存放used/left。

  • used表示(用了多少？
  • left表示)抵消的(还留下多少？比如(()这里的used=2, left = 1。

把这两个int与字符串一起放的原因是容易申请内存。也跟随字符串一起，容易定位与操作。
所以这里生成了两个宏，专门用来取used/left。

#define LEFT_COUNT(p, l) ((int*)(p + l - sizeof(int)))
#define USED_COUNT(p, l) ((int*)(p + l - 2*sizeof(int)))

有了used/left之后。生成新的字符串的时候，used/left的值，就直接在原有的字符串上累加就可以了。

void set_char(char **ret, const size_t i, const size_t pos, const size_t str_len, char c) {
    assert(!ret[i][pos]);
    ret[i][pos] = c;
    int *left = LEFT_COUNT(ret[i], str_len);
    int *used = USED_COUNT(ret[i], str_len);
    if (c == '(') {
        *left += 1;
        *used += 1;
    } else {        
        *left -= 1;
    }
}

代码

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define ROUND_UP(x) ((((x) + 3) >> 2) << 2)
#define LEFT_COUNT(p, l) ((int*)(p + l - sizeof(int)))
#define USED_COUNT(p, l) ((int*)(p + l - 2*sizeof(int)))
void set_char(char **ret, const size_t i, const size_t pos, const size_t str_len, char c) {
    assert(!ret[i][pos]);
    ret[i][pos] = c;
    int *left = LEFT_COUNT(ret[i], str_len);
    int *used = USED_COUNT(ret[i], str_len);
    if (c == '(') {
        *left += 1;
        *used += 1;
    } else {        
        *left -= 1;
    }
}
void dup_string(char **ret, const size_t from, const size_t to, const size_t str_len, int* returnSize) {
    assert(!ret[to]);
    ret[to] = (char*) malloc(sizeof(char) * str_len);
    memcpy(ret[to], ret[from], sizeof(char) * str_len);
    *returnSize += 1; // ERROR: *returnSize + 1 -> *returnSize += 1
}
char** generateParenthesis(int n, int* returnSize) {
    if (0 == n) {
        *returnSize = 0;
        return NULL;
    }
    
    size_t total_size = (1<<(n<<1)) + 1;
    char **ret = (char**) malloc(sizeof(char*) * total_size);
    memset(ret, 0, sizeof(char*) * total_size);
    
    size_t str_len = ROUND_UP(n<<1) + (sizeof(int)<<2);
    ret[0] = (char*) malloc(sizeof(char) * str_len);
    *returnSize = 1; // ERROR: 这里也需要初始化为1
    memset(ret[0], 0, sizeof(char) * str_len);
    /*需要填充的字符串的位置，其中第一个位置能只填(*/
    set_char(ret, 0, 0, str_len, '(');
    /*指向需要填充的尾巴, ret_tail中还没有字符串生成*/
    size_t ret_tail = 1;
    /*其他位置*/
    for (size_t pos = 1; pos < (n<<1); pos++) {
        /*遍历里面的每个字符串*/
        const size_t cnt = ret_tail;
        for (size_t i = 0; i < cnt; i++) {
            assert(ret[i]);
            //assert(ret_tail <= (1<<n));
            char *p = ret[i];
            int *left = LEFT_COUNT(p, str_len);
            int *used = USED_COUNT(p, str_len);
            /*如果(已经用光, 且left为0*/
            if (*used == n && 0 == *left) continue;
            
            /*如果(用光，但是left还有，只能补)*/
            if (*used == n && *left > 0) {
                set_char(ret, i, pos, str_len, ')');
                continue;
            }
            assert(*used < n);
            /*还有(没有用光，那么有两种情况:注意先复制!!可以省掉处理旧字符的情况*/
            if (*left > 0) {
                // b. 放(
                dup_string(ret, i, ret_tail, str_len, returnSize);
                set_char(ret, ret_tail, pos, str_len, '(');
                ret_tail++;
                // a. 放)
                set_char(ret, i, pos, str_len, ')');
                continue;
            }
            /*left == 0, 只能放(*/
            assert(*left == 0);
            set_char(ret, i, pos, str_len, '(');
        }
    }
    return ret;
}