如何对 vector 初始化

• 大小为size的一维向量，二位向量

1
2

vector<what-type> var-name(what-size);
vector<vector<what-type>> var-name(rowSize, vector<what-type>(colSize));

• 数组转 vector

1
2
3
4
5
6
7
8
9
10
11
12

int rowSize = ?;
int colSize = ?;
what-type A_[rowSize][colSize] = {
  {element1, elment2, ..., element},
  {},
  ...
  {}
};
vector<vector<what-type>> A(rowSize, vector<what-type>(colSize));
for(int row=0; row<rowSize; row++) {
  A[row].assign(A_[row], A_[row] + colSize);
}

对 vector 等 STL 标准容器进行排序操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#inlcude <algorithm>	/* sort */
 
bool compareFunc(int before, int after) {
  return (before < after);
}
 
struct compareClass {
  bool operator() (int before, int after) {
    return (before < after);
  }
} compareObj;
 
// using default comparison(operator <)
sort(vector.begin(), vector.end());
sort(vector.begin(), vector.begin() + length);
 
// using comparison function
sort(vector.begin(), vector.end(), compareFunc);
 
 // using comparison object
sort(vector.begin(), vector.end(), compareObj);

• 上述的 sort(begin, end, comparison) 函数，其中[before]元素与[after]元素满足comparison关系
• 一些自带的 comparison 函数

1
2
3
4
5
6
7
8
9

// 相等
equal_to<>()
not_equal_to<>()
less<>() 
greater<>()
// ≤
less_equal<>()
// ≥
greater_equal<>()

使用二维 vector 维护邻接列表

1
2
3
4
5
6

vector<vector<int>> graph;
graph.resize(vertex-number);
// vector<pair<int, int>> edges;
for(int edgeIdx=0; edgeIdx<edges.size(); edgeIdx++) {
  graph[edges[edgeIdx].first].push_back(edges[edgeIdx].second);
}

STL 常见容器关键操作

• vector $\begin{cases} push\_back \cr pop\_back \end{cases}$　　list $\begin{cases} push\_back \cr pop\_back \cr push\_front \cr pop\_front \end{cases}$
• stack $\begin{cases} push \cr pop \cr top \end{cases}$　　queue $\begin{cases} push \cr pop \cr front \cr back \end{cases}$
• map, set $\begin{cases} insert \cr erase \cr \color{red}{find} \end{cases}$

DFS&BFS 的快速实现

• DFS 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void dfs() {
  for 节点 ? :
    if(!visited[?]) {
      dfs(?, visited);
    }
}
 
void dfs(startIdx, visited[]) {
  visited[startIdx] = true;
  for 节点 startIdx 的邻接边 startIdx->?:
    if(!visited[?]) {
      dfs(?, visited);
    }
}

• DFS 堆栈

1
2
3
4
5
6
7
8
9
10
11
12
13

void dfs(root) {
  nodeStack.push(root);
  visited[root] = true;
  while(!nodeStack.empty()) {
    curNode = nodeStack.top();
    nodeStack.pop();
    for curNode 的邻接边 curNode->?:
      if(!visited[?]) {
        nodeStack.push(?);
        visited[?] = true;
      }
  }
}

• BFS 队列

1
2
3
4
5
6
7
8
9
10
11
12
13

void bfs(root) {
  nodeQueue.push(root);
  visited[root] = true;
  while(!nodeQueue.empty()) {
    curNode = nodeQueue.front();
    nodeStack.pop();
    for curNode 的邻接边 curNode->?:
      if(!visited[?]) {
        nodeQueue.push(?);
        visited[?] = true;
      }
  }
}

最短路径问题

• 带正权（不可带负权）的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

void Dijkstra(source) {
  visited[] = false;
  prevs[] = NULL;
  dists[] = INT_MAX;
 
  dists[source] = 0;
 
  for 完成所有节点挑选:
    curMinDist = INT_MAX;
    pickNode = NULL;
    for 所有节点?:
      if(!visited[?] && dists[?] < curMinDist) {
        curMinDist = dists[?];
        pickNode = ?;
      }
 
    if(pickNode == NULL) {
      // 存在节点不可达
      return;
    }
 
    visited[pickNode] = true;
    for pickNode 所有邻接边 pickNode->?:
      if(!visited[?] 
        && dists[?] > (dists[pickNode] + 边权)) {
        dists[?] = dists[pickNode] + 边权;
        prevs[?] = pickNode;
      }
}

• 可带负权的图 $\longrightarrow$ 可以检测是否有负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

bool BellmanFord(source) {
  visited[] = false;
  prevs[] = NULL;
  dists[] = INT_MAX;
 
  dists[source] = 0;
 
  for 完成所有节点[0-N-1]挑选:
    updated = false;
    // 更新所有节点
    for 所有节点?:
      for ?的所有邻接边?->△:
        if(dists[△] != INT_MAX 
          && dists[△] > (dists[?] + 边权)) {
          dists[△] = dists[?] + 边权;
          prevs[△] = ?;
        }
 
    if(!updated) {
      // 完成最短路径搜索
      return true;
    }
 
    if(已经挑选了所有节点 && updated) {
      // 存在负环
      return false;
    }
}

最小生成树问题

• Prim 算法，与 Dijkstra 类似，只不过代价是到当前生成树的，而不是到源的代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void Prim(root = 0) {
  visited[] = false;
  prevs[] = NULL;
  costs[] = INT_MAX;
 
  costs[root] = 0;
 
  for 完成所有节点挑选:
    curMinCost = INT_MAX;
    pickNode = NULL;
    for 所有节点?:
      if(!visited[?] && costs[?] < curMinCost) {
        curMinCost = costs[?];
        pickNode = ?;
      }
 
    if(pickNode == NULL) {
      // 节点不可达
      return;
    }
 
    visited[pickNode] = true;
    // 更新 cost
    for pickNode 所有邻接边 pickNode->?:
      if(!visited[?] 
        && costs[?] > (dists[pickNode] + 边权)) {
        costs[?] = costs[pickNode] + 边权;
        prevs[?] = pickNode;
      }
}

关于子串、子序列的动态规划问题

• dp[i]：转化到以 [i] 结尾或者 [0, …, i] 这样的子串/子序列的子问题
• dp[i][j]：转化到 [i, …, j] 这样的子串/子序列的子问题
  • 以长度递增为填表方向
    • 长度为 1，需作为基单独计算
    • 长度为 2，可能需要作为基单独计算

动态规划：编辑距离（Edit distance）

• 设需要计算编辑距离的两个字符串分别为 x[1…m] 和 y[1…n]
• $E(i, j)$：x[1…i] 和 y[1…j] 的编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

for i = 0, 1, 2, ..., m
  // y 插入操作
  j=0: // x 为空
    E(i, j) = i;
 
for j = 1, 2, ..., n
  // y 删除操作
  i=0: // y 为空
    E(i, j) = j;
 
for i = 1, 2, ..., m
  for j = 1, 2, ..., n
    E(i, j) = min{
      1 + E(i-1, j),	// y 删除操作
      1 + E(i, j-1),	// y 插入操作
      diff(i, j) + E(i-1, j-1),	// y 替换操作
    }
 
return E(m, n)

• 其中，$diff(i, j) = \begin{cases} 0, x[i]=y[j] \cr 1, else \end{cases}$

动态规划：最长路

• 保证在计算dist(v)时，v的前驱节点u的最短/长路已经算出来 $\Longrightarrow$ 按照拓扑排序的顺序来计算每个点v的最长/短路dist(v)

1
2
3
4

initialize all dist(·) value to ∞
dists[source] = 0
for v∈V\{source}, in topological order:
  dist(v) = max/min \_{(u, v) ∈ E} {dist(u) + weight(u, v)}

• 有点复杂的动态规划思路
  • $ans[j][i]$：以 j 点为起点，经过点集 i 中的点恰好一次而不经过其他点的路径长度的最大值，不存在则为-∞

1
2
3
4
5

A. i 只包含一个点，ans[j][i] = 0
B. 否则，ans[j][i] = max(graph[j][k] + ans[k][s])
  S 表示 i 集合中去掉了 j 点的集合
  k 遍历集合 S 中的点，点 j 到点 k 有边存在，权值为 graph[j][k]
C. 所有 ans[j][i] 的最大值即为最长路

动态规划：最短可靠路径

• 从 s 到 t 的不超过 k 条边的最短路
• dist(v, i)：从起点 s 到 v 点恰好经过 i 条边的最短路

1
2
3

i = 0, dist(s, i) = 0, 其他为∞
for 所有顶点 v
  dist(v, i) = min{(u, v) \in E} {dist(u, i-1) + weight(u, v)}

动态规划：最长递增序列

• 转化为最长路径问题（容易提取）

1
2
3
4
5
6
7

for(fromIdx=0; fromIdx<n; fromIdx++) {
  for(toIdx=fromIdx+1; toIdx<n; toIdx++) {
    if(num[toIdx] > num[fromIdx]) {
      graph[fromIdx].push_back(toIdx);
    }
  }
}

• 动态规划（$O(N^2)$）
  • $L(j)$：以第 j 个数结尾的最长递增子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14

L(0) = 1;
prevs[] = -1;
for j = 1...n-1:
  // 最长递增序列只有 num[j]
  int localMax = 0;
  
  for i = 0...j:
    // 以比 num[j] 小的数结尾的最长递增子序列长度+1
    if(num[i] < num[j] && L(i) > localMax) {
      localMax = L(i);
      prevs[j] = i;
    }
 
  L(j) = localMax + 1;

动态规划：矩阵连乘

• 给定 n 个矩阵构成的一个链 <A1, A2, ..., An>，其中矩阵Ai的大小为 $P_{i-1} * P_{i}, i=1,…n$，找一个计算顺序，使得计算乘积A1A2...An的乘法次数最少。
• $m[i, j]$：表示计算 Ai...Aj的最小乘法次数
  • $min_{i \leq k \leq j} {m[i, k] + m[k+1, j] + P_{i-1}P_{k}P_{j}}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

n = length[p] - 1
 
for i = 1...n:
  m[i, i] = 0
 
for l = 2...n:
  for i = 1...(n-l+1):
    j = i + l - 1
    m[i, j] = ∞
    for k = i...j-1:
      q = m[i, k] + m[k+1, j] + P[i-1]*P[k]*P[j]
      if(q < m[i, j]) {
        m[i, j] = q;
        s[i, j] = k;
      }
 
return m[1, n], s[1, n]

• m[1, n]为最终需要的最小乘法次数，通过s[1, n]可以回溯得到对应的计算顺序

期末机考错误题目反思

• 617. Merge Two Binary Trees

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { // t1==NULL or t1!=NULL if(t2 == NULL) { return t1; } // t2!=NULL t1==NULL else if(t1 == NULL) { t1 = new TreeNode(t2->val); mergeTrees(t1->left, t2->left); mergeTrees(t1->right, t2->right); } // t2!=NULL t1!=NULL else { t1->val += t2->val; mergeTrees(t1->left, t2->left); mergeTrees(t1->right, t2->right); } return t1; } };

  • 反思：t1 = new TreeNode(t2->val); 之后，损失了该节点与 t1 树的连接关系；需要通过单独开一棵树的方式来解决这个问题。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if(t1 == NULL) { return t2; } if(t2 == NULL) { return t1; } TreeNode* result = new TreeNode(t1->val + t2->val); result->left = mergeTrees(t1->left, t2->left); result->right = mergeTrees(t1->right, t2->right); return result; } };

• 542. 01 Matrix

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  class Solution { private: int BFS(vector<vector<int>>& matrix, int startRowIdx, int startColIdx) { queue<int> queue_; // 这里已经很难处理，似乎没办法记录当前层（广度优先搜索的深度）层数，即步数 } public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int rowSize = matrix.size(); int colSize = matrix[0].size(); vector<vector<int>> stepMatrix(rowSize, vector<int>(colSize)); for(int row=0; row<rowSize; row++) { for(int col=0; col<colSize; col++) { if(matrix[row][col] == 0) { stepMatrix[row][col] = 0; } else { stepMatrix[row][col] = BFS(matrix, row, col); } } } return stepMatrix; } };

  • 反思：原先的想法是对于那些 1 的位置，进行DFS（现在想想应该BFS），寻找其到达最近的 0 需要的步数；会存在的一个问题（如上）就是，如何得到这些 1 到 0 的步数呢？而且无论是 DFS 还是 BFS，显然都存在重复的搜索操作。那假如换种思路，从那些 0 出发，一层一层向外扩张去更新那些 1 所在位置的步数呢？每一层的扩张显然可以利用上一层扩张的结果去更新，不存在重复的搜索操作。因此，一开始将那些 1 所在位置的到最近 0 所在位置的步数初始化为INT_MAX，然后从那些 0 所在位置开始通过 BFS 一层一层进行扩张，用更小的步数去更新 1 所在位置的值，最终，那些原先为 1 所在位置的值便是其到达最近 0 所在位置需要的步数了。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  class Solution { public: vector<vector<int> > updateMatrix(vector<vector<int> >& matrix) { int rowSize = matrix.size(); int colSize = matrix[0].size(); vector<vector<int> > stepMatrix(rowSize, vector<int>(colSize)); queue<pair<int, int> > queue_; for(int row=0; row<rowSize; row++) { for(int col=0; col<colSize; col++) { if(matrix[row][col] == 0) { stepMatrix[row][col] = 0; queue_.push(pair<int, int>(row, col)); } else { stepMatrix[row][col] = INT_MAX; } } } // up; down; left; right int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while(!queue_.empty()) { pair<int, int> curPos = queue_.front(); queue_.pop(); for(int i=0; i<4; i++) { int rowIdx = curPos.first + dirs[i][0]; int colIdx = curPos.second + dirs[i][1]; if(rowIdx<0 || colIdx<0 || rowIdx>=rowSize || colIdx>=colSize) { continue; } if(stepMatrix[curPos.first][curPos.second]+1 < stepMatrix[rowIdx][colIdx]) { stepMatrix[rowIdx][colIdx] = stepMatrix[curPos.first][curPos.second]+1; queue_.push(pair<int, int>(rowIdx, colIdx)); } } } return stepMatrix; } };

• Longest Common Substring

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

  class Solution { public: /** * @param A, B: Two string. * @return: the length of the longest common substring. */ int longestCommonSubstring(string &A, string &B) { int lenA = A.length(); int lenB = B.length(); if(lenA==0 || lenB==0) { return 0; } // L[idxA][idxB]: the largest length of LCS ending with A[idxA] and B[idxB] int L[lenA][lenB]; for(int idxB=0; idxB<lenB; idxB++) { L[0][idxB] = B[idxB]==A[0]? 1 : 0; } for(int idxA=0; idxA<lenA; idxA++) { L[idxA][0] = A[idxA]==B[0]? 1 : 0; } for(int idxA=1; idxA<lenA; idxA++){ for(int idxB=1; idxB<lenB; idxB++){ L[idxA][idxB] = A[idxA]==B[idxB]? L[idxA-1][idxB-1]+1 : 0; } } int maxLen = 0; for(int idxA=0; idxA<lenA; idxA++){ for(int idxB=0; idxB<lenB; idxB++){ if(L[idxA][idxB] > maxLen) { maxLen = L[idxA][idxB]; } } } return maxLen; } };

  • 反思：子问题定义的时候出现问题，应该是L[idxA][idxB]：the largest length of LCS ending with A[idxA] and B[idxB]，而不是A[0…idxA]和B[0…idxB]的最长公共子串。
• 198. House Robber
  • 机考时是求数列：A[0], A[1], …, A[n-1] 的最小和，要求A[i]和A[i+1]至少选取一个；打家劫舍这道题类似，相当于在数列中取出一个或多个不相邻数，使其和最大。
  • 打家劫舍要求确保不出现连续相邻的两个数，下面两个子问题都能够保证这样的一个前提条件。
    • ①money[i]：抢劫完房间 house[i] 后，能够获得的最大金钱数目。
    • ②money[i]：在房间 house[0], …, house[i] 中进行抢劫能够获得的最大金钱数目。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

  #define max(a,b) (a>b?a:b) class Solution { public: int rob(vector<int>& nums) { // money[i]: max money after robbing house[i] int numSize = nums.size(); if(numSize == 0) { return 0; } vector<int> money(nums.size()); money[0] = nums[0]; if(numSize > 1) { money[1] = nums[1]; } if(numSize > 2) { money[2] = nums[0] + nums[2]; } for(int i=3; i<numSize; i++) { money[i] = max(money[i-3], money[i-2]); money[i] += nums[i]; } int largestMoney = money[0]; for(int i=1; i<numSize; i++) { if(money[i] > largestMoney) { largestMoney = money[i]; } } return largestMoney; } };

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  #define max(a,b) (a>b?a:b) class Solution { public: int rob(vector<int>& nums) { // money[i]: max money after reaching house[i], may robbed house[i] int numSize = nums.size(); if(numSize == 0) { return 0; } vector<int> money(nums.size()); money[0] = nums[0]; if(numSize > 1) { money[1] = max(nums[0], nums[1]); } for(int i=2; i<numSize; i++) { money[i] = max(money[i-2]+nums[i], money[i-1]); } return money[numSize-1]; } };

  • 然而，机考时的最小和问题必须满足：不存在相邻两个数不选的情况；显然对于转化为子问题②很难保证这个前提条件。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  #define min(a,b) (a<b?a:b) class Solution { public: int minSum(vector<int>& nums) { // sums[i]: minimum sum ending with nums[i] int numSize = nums.size(); if(numSize == 0) { return 0; } vector<int> sums(nums.size()); sums[0] = nums[0]; if(numSize > 1) { sums[1] = nums[1]; } for(int i=2; i<numSize; i++) { sums[i] = min(sums[i-2], sums[i-1]); sums[i] += nums[i]; } return min(sums[numSize-2], sums[numSize-1]); } };