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

输出:

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

预期结果:

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

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

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

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

看了答案的思路,说:每一个括号序列可以用 (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. 接雨水

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

image-20211124131559423

(图 1)

image-20211124131618560

(图 2)

交集:

image-20211124131704783

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

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

即对于图 1,

image-20211124132445431

对于图 2,

image-20211124132457495

交集应当取最小值:

image-20211124132535920

然后还要排除柱子:

image-20211124132610905

最后把有效值相加。

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 批量标记). 再放第二个。

image-20211124140248890

image-20211124140356108

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

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

56. 合并区间

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

image-20211124140859935

我的想法:

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

示意图如下:

image-20211124141104037

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

image-20211124144035195

代码:

#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

可以,前两个都找对了。

image-20211124144128279

image-20211124144203808

改写成循环,并且用同样的方法找 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;
  }
};

59. 螺旋矩阵 II

思路:

image-20211124152329539

观察到可以顺次生成 n-1 个数,第二层 n-3 个,第三层 n-5 个。每层生成 4 次。通过次数可以转换为移动方向。

60. 排列序列

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时,所有排列如下:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

给定 nk,返回第 k 个排列。

要返回指定个排列,这有点难度。排列组合若是不加 cache,性能会非常垃圾。

最原始的想法自然是依序生成,直到抵达所要的那一个,但这样前面的都成了无用功。

我们最好能求出第 k 个排列的各位数字。观察上面的各列,

第一列是 1 1 2 2 3 3,注意到数字连续出现,且每个出现的次数为 23 的排列数 2! = $(n-1)!$

第二列是 2 3 1 3 1 2,可以分为 23 13 12,是 123 分别从 i, i+1, i+2 位置拿走 1, 2, 3 所得

第三列是 3 2 3 1 2 1,可以分为 32 31 21,是 321 分别从 i+2, i+1, i 位置拿走 1, 2, 3 所得

也可以同时看二三列,分别是 23, 13, 12 的排列的第 1、2 个排列。

所以第一列数字就是 $k / (n-1)!$ 向上取整。

第二列数字就是 {1,2,…n} - {k} 的第 k % (n-1)! 个排列

这题有空再做吧,我脑子要烧掉了。

64. 最小路径和

思路:由于 “每次只能向下或者向右移动一步。” 于是可以利用左边和上边的格子进行动态规划。

这种题要避免陷入局部最优解。dp [i][j] 表示从 [0,0] 移动到 [i,j] 的最小路径和。

63. 不同路径 II

无非是某些格变成 0 罢了。

image-20211124174538758