#### 22. 括号生成

()
()()	(())
((()))	(()())	(())() ()(()) ()()()


()()	(())
-> (()()) ((()))


()()	(())
-> ()()() ()()() ()(()) (())()


class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) {
return {};
}
if (n == 1) {
return {"()"};
}
vector<string> ret;
auto prevCase = generateParenthesis(n - 1);
ret.push_back("()" + prevCase[0]);
ret.push_back("(" + prevCase[0] + ")");
for (int i = 1; i < prevCase.size(); i++) {
ret.push_back("()" + prevCase[i]);
ret.push_back(prevCase[i] + "()");
ret.push_back("(" + prevCase[i] + ")");
}
return ret;
}
};



4

["()()()()","(()()())","()(()())","(()())()","((()()))","()()(())","()(())()","(()(()))","()(())()","(())()()","((())())","()((()))","((()))()","(((())))"]


["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]


['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())()()', '()((()))', '()(()())', '()(())()', '()(())()', '()()(())', '()()()()']
['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']


class Solution {
public:
vector<string> rec(int n) {
if (n == 0) {
return {""};
}
if (n == 1) {
return {"()"};
}
vector<string> ret;
for (int i = 0; i < n; i++) {
auto a = rec(i);
auto b = rec(n - i - 1);
for (int j = 0; j < a.size(); j++) {
for (int k = 0; k < b.size(); k++) {
ret.push_back("(" + a[j] + ")" + b[k]);
}
}
}

return ret;
}
vector<string> generateParenthesis(int n) {
auto ret = rec(n);
return ret;
}
};



（图 1）

（图 2）

#### 50. Pow(x, n)

class Solution {
public:
double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if (n == -1) {
return 1 / x;
}
double h = myPow(x, n / 2);
auto ret = h * h *  myPow(x, (n % 2));
return ret;
}
};


#### 51. N 皇后

emm 看了题解，还真是用了这种 $O (n!)$ 的解法。看来目前尚未找到更好的。

#### 56. 合并区间

1. 先建索引，记录每条蛇的头尾位置。
2. 从头部开始遍历，当某个位置中断后（没有任何集合的头尾属于某个位置）则断开。
1. 判断中断：nextTailIv (i) > i（其实就是希望能通过位置反查区间。）

#include <debug.h>

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& iv) {
vector<vector<int>> merged;

int n = iv.size();
vector<int> tail(n);
for (int i = 0; i < n; i++) {
tail[i] = iv[i][1];
}
// 从最前面的开始
int start = INT_MAX;
for (int i = 0; i < n; i++) {
}
int curTail = start, nextTailIdx, nextTailVal;
// 指向 start 往后第一个区间的尾巴
nextTailVal = tail[nextTailIdx];
printf("nextTail = %d\n", nextTailVal);
curTail = nextTailVal;

nextTailVal = tail[nextTailIdx];
printf("nextTail = %d\n", nextTailVal);
curTail = nextTailVal;
return {};
}
int nextTailIv(vector<int>& head, vector<int>& tail, int start) {
// 最远的
int farthestTailValue = -1;
int farthestTailIvIdx = -1;
for (int i = 0; i < tail.size(); i++) {
if (head[i] <= start && start <= tail[i]) {
if (tail[i] > farthestTailValue) {
farthestTailValue = tail[i];
farthestTailIvIdx = i;
}
}
}
return farthestTailIvIdx;
}
};
int main(int argc, char const* argv[]) {
Solution s;
vector<vector<int>> iv = {{0, 3},   {1, 4},  {6, 6},   {10, 12},
{15, 19}, {9, 11}, {14, 15}, {8, 18}};
s.merge(iv);
return 0;
}


nextTail = 3
nextTail = 4



class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& iv) {
vector<vector<int>> merged;

int n = iv.size();
vector<int> tail(n);
for (int i = 0; i < n; i++) {
tail[i] = iv[i][1];
}
// 从最前面的开始
int startPos = INT_MAX;
for (int i = 0; i < n; i++) {
}
while (true) {
int curTail = startPos, nextTailIdx, nextTailPos;
while (true) {
// 指向 start 往后第一个区间的尾巴
nextTailPos = tail[nextTailIdx];
if (curTail == nextTailPos) {
printf("found interval [%d,%d]\n", startPos, curTail);
break;
}
printf("curTail = %d\n", curTail);
nextTailPos = tail[nextTailIdx];
curTail = nextTailPos;
}
if (startIdx == -1) {
printf("program done");
break;
}
printf("start = %d\n", startPos);
system("read -p 'Press Enter to continue...' var");
}

return {};
}
int nextTailIntervalIdx(vector<int>& head, vector<int>& tail, int start) {
// 最远的
int farthestTailValue = -1;
int farthestTailIvIdx = -1;
for (int i = 0; i < tail.size(); i++) {
if (head[i] <= start && start <= tail[i]) {
if (tail[i] > farthestTailValue) {
farthestTailValue = tail[i];
farthestTailIvIdx = i;
}
}
}
printf("from %d, nextTail is at %d\n", start, farthestTailValue);
return farthestTailIvIdx;
}
// 最远的
for (int i = 0; i < tail.size(); i++) {
}
}
}
}
};
int main(int argc, char const* argv[]) {
Solution s;
vector<vector<int>> iv = {{0, 3},   {1, 4},  {6, 6},   {10, 12},
{15, 19}, {9, 11}, {14, 15}, {8, 18}};
s.merge(iv);
return 0;
}