17 天算法挑战（17）

Pluveto

Nov 24, 2021 发布

? 次浏览

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;
  }
};

然而说我解答错误。

输入：

输出：

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

预期结果：

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

我排序了一下，发现一样的呀。

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

仔细一看，确实少了一个 (())(())。这个是怎么来的呢？()(()) 往中间插入括号。这我还真没考虑到。

看了答案的思路，说：每一个括号序列可以用 (a) b 来表示。之后就是穷举 a, b 了。

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;
  }
};

23. 合并 K 个升序链表

两个链表用双指针，K 的链表用 K 指针？

或者递推一下，先两两合并。

29. 两数相除

记得除法是通过移位实现的。相当于模拟一个移位相减法的除法器电路。

42. 接雨水

思路：可以通过两次遍历然后求交集。

（图 1）

（图 2）

交集：

只要记忆每一层的蓝色方块的起始坐标和结束坐标，然后两图求公共区间长度。

问题在于每一层可能有多个区间。当然也可以看作一个区间，那么需要减去公共区间中的实体方块。

即对于图 1，

对于图 2，

交集应当取最小值：

然后还要排除柱子：

最后把有效值相加。

49. 字母异位词分组

我的思路是排序，并保留原坐标。这么做是可以的，不过看了题解，他的方法更好：

排序，然后以排序后的值为索引，添加到 map [key] 对应的向量中。相当于散列表 + 值拉链。

50. Pow(x, n)

求 $x^n ; n\in \Z$。

思路 0：直接 return pow (x,n) ~~你搁这搁这呢？~~

思路 1：对 $n$ 分类讨论，然后暴力算。

思路 2：

考虑计算 $3^4$，相当于 $3^2 \cdot 3^2$，那么我们就可以减少大约一半的计算量。如果是奇数，$3^5 = 3^2 \cdot 3^2 \cdot 3$. 这比暴算好点。

考虑一般情况：$x^n = x^{n/2} \cdot x^{n/2} \cdot x^{(n\mod2)==0?0:1}$

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;
  }
};

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00%的用户

原来这就是快速幂？

51. N 皇后

皇后走米字形攻击。如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。要求返回所有解法。

想法：暴力法。尝试放置一个，然后把不能放的地方都标 1（或者用 map 批量标记）. 再放第二个。

但是容易看出，这种解法的复杂度太高了。

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

56. 合并区间

这题让我想起了操作系统的进程调度……

我的想法：

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

示意图如下：

问题就转化成实现 nextTailIv 函数。最暴力的方法就是遍历各个区间。但每个区间头尾都要判断，效率太低了。

代码：

#include <debug.h>

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

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

    nextTailIdx = nextTailIv(head, tail, curTail);
    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

可以，前两个都找对了。

改写成循环，并且用同样的方法找 nextHead：


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

    int n = iv.size();
    vector<int> head(n);
    vector<int> tail(n);
    for (int i = 0; i < n; i++) {
      head[i] = iv[i][0];
      tail[i] = iv[i][1];
    }
    // 从最前面的开始
    int startPos = INT_MAX;
    for (int i = 0; i < n; i++) {
      startPos = min(startPos, head[i]);
    }
    while (true) {
      int curTail = startPos, nextTailIdx, nextTailPos;
      while (true) {
        // 指向 start 往后第一个区间的尾巴
        nextTailIdx = nextTailIntervalIdx(head, tail, curTail);
        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;
      }
      auto startIdx = nextHeadIntervalIdx(head, tail, curTail);
      if (startIdx == -1) {
        printf("program done");
        break;
      }
      startPos = head[startIdx];
      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;
  }
  int nextHeadIntervalIdx(vector<int>& head, vector<int>& tail, int start) {
    // 最远的
    int nearestHeadValue = INT_MAX;
    int nearestHeadIvIdx = -1;
    for (int i = 0; i < tail.size(); i++) {
      if (head[i] > start) {
        if (head[i] < nearestHeadValue) {
          nearestHeadValue = head[i];
          nearestHeadIvIdx = i;
        }
      }
    }
    printf("from %d, nextHead is at %d\n", start, nearestHeadValue);
    return nearestHeadIvIdx;
  }
};
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;
}

输出：

pluveto@devhost1:~/leet/2021-11-24$ cr p56.cpp
from 0, nextTail is at 3
curTail = 0
from 3, nextTail is at 4
curTail = 3
from 4, nextTail is at 4
found interval [0,4]
from 4, nextHead is at 6
start = 6
Press Enter to continue...
from 6, nextTail is at 6
found interval [6,6]
from 6, nextHead is at 8
start = 8
Press Enter to continue...
from 8, nextTail is at 18
curTail = 8
from 18, nextTail is at 19
curTail = 18
from 19, nextTail is at 19
found interval [8,19]
from 19, nextHead is at 2147483647
program done■
 ┌──End of program──
 │ Finished in 4615 ms.

简化一下代码：

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& iv) {
    vector<vector<int>> merged;
    int n = iv.size();
    int startPos = INT_MAX;
    for (int i = 0; i < n; i++) {
      startPos = min(startPos, iv[i][0]);
    }
    while (true) {
      int curTail = startPos, nextTailIdx, nextTailPos;
      while (true) {
        nextTailIdx = nextTailIntervalIdx(iv, curTail);
        nextTailPos = iv[nextTailIdx][1];
        if (curTail == nextTailPos) {
          merged.push_back({startPos, curTail});
          break;
        }
        nextTailPos = iv[nextTailIdx][1];
        curTail = nextTailPos;
      }
      auto startIdx = nextHeadIntervalIdx(iv, curTail);
      if (startIdx == -1) {
        break;
      }
      startPos = iv[startIdx][0];
    }

    return merged;
  }
  int nextTailIntervalIdx(vector<vector<int>>& iv, int start) {
    // 最远的
    int farthestTailValue = -1;
    int farthestTailIvIdx = -1;
    for (int i = 0; i < iv.size(); i++) {
      if (iv[i][0] <= start && start <= iv[i][1]) {
        if (iv[i][1] > farthestTailValue) {
          farthestTailValue = iv[i][1];
          farthestTailIvIdx = i;
        }
      }
    }
    return farthestTailIvIdx;
  }
  int nextHeadIntervalIdx(vector<vector<int>>& iv, int start) {
    int nearestHeadValue = INT_MAX;
    int nearestHeadIvIdx = -1;
    for (int i = 0; i < iv.size(); i++) {
      if (iv[i][0] > start) {
        if (iv[i][0] < nearestHeadValue) {
          nearestHeadValue = iv[i][0];
          nearestHeadIvIdx = i;
        }
      }
    }
    return nearestHeadIvIdx;
  }
};

上面的代码可以提交通过，不过只击败了 85.88%

下面看看题解的办法，比我的好多了。

主要利用了排序后的有序性。如果下个区间头小于本区间尾部，则与之合并。

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // 排序
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> ans;
    // 对于每个区间
    for (int i = 0; i < intervals.size();) {
      int tailPos = intervals[i][1];
      int nextIvIdx = i + 1;
      // 如果下个区间头小于本区间尾部，则与之合并
      while (nextIvIdx < intervals.size() && intervals[nextIvIdx][0] <= tailPos) {
        tailPos = max(tailPos, intervals[nextIvIdx][1]);
        nextIvIdx++;
      }
      ans.push_back({intervals[i][0], tailPos});
      i = nextIvIdx;
    }
    return ans;
  }

57. 插入区间

我的思路：找到和插入区间冲突的区间，若有则与之合并。最多只要合并两次。

58. 最后一个单词的长度

我的思路：写个 DFA

class Solution {
 public:
  int lengthOfLastWord(string s) {
    // 0: 等待读入下一个 work
    // 1： 处于字符串中
    const int WAITING = 0;
    const int READING = 1;
    int state = WAITING;
    int length = 0;
    int prevLength = 0;
    for (int i = 0; i < s.size(); i++) {
      if (state == WAITING) {
        if (s[i] == ' ') {
          continue;
        } else {
          state = READING;
          length++;
        }
      } else if (state == READING) {
        if (s[i] == ' ') {
          state = 0;
          prevLength = length;
          length = 0;
          continue;
        } else {
          length++;
        }
      }
    }
    return length > 0 ? length : prevLength;
  }
};