386. 字典序排数
题目链接：386.exicographical-numbers
解法：
解法1：DFS，也就是回溯。第一层从1开始，遍历到9，而后面层的循环，也就是递归，从0遍历到9。如果当前节点的数大于n了，那就回溯。但是DFS递归的空间复杂度大于O(1)。
参考【宫水三叶】的题解：DFS(回溯)
解法2：迭代法。对于一个整数 number=1，按照一定的规则去找他的下一个字典序整数，并不断加入结果集中。由于只是不断更新number，所以额外空间为O(1)。更新规则如下：
迭代看了这个规则也不太好理解，把代码模拟运行一下就理解了。
比如第二个条件，n=234时，如果number=199了，那么199 / 10 = 19, 19 / 10 = 1, 1+1=2，也是后面的字典序整数就是：2, 20, 200,..., 21,...。
如果number=234了，那么234 / 10 = 23, 23+1 = 24，那么后面的字典序整数就是：24, 25, ..., 29
参考题解：leetcode官网迭代法
边界条件：无
时间复杂度：O(n)
空间复杂度：回溯O(n)，迭代O(1)
// 回溯
class Solution {
vector<int> result;
public:
vector<int> lexicalOrder(int n) {
// 第一层遍历从1到9，因为0不能作为开头
for (int i=1; i<=9; i++) {
traversal(i, n);
}
return result;
}
private:
void traversal(int cur, int limit) {
if (cur > limit) return;
result.push_back(cur);
for (int i=0; i<=9; i++) {
cur = cur * 10 + i;
// 横向剪枝
if (cur > limit) break;
traversal(cur, limit);
// 为了清晰地展示回溯撤销的操作，没有合并
cur = (cur - i) / 10;
}
}
};// 迭代法
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> result(n);
int cur = 1;
for (int i=0; i<n; i++) {
result[i] = cur;
if (cur * 10 <= n) {
cur *= 10;
} else {
// 比如n=234，cur=199，那么需要回撤到1，再从2开始
while (cur % 10 == 9 || cur + 1 > n) {
cur /= 10;
}
cur++;
}
}
return result;
}
};785.判断二分图
题目链接：785.is-graph-bipartite
解法：
这个题有两种解法：染色法和并查集。并查集本身就是一个很大的内容，所以这里只用染色法。
任选一个节点开始，给它染成红色。随后我们对整个图进行遍历，将该节点直接相连的所有节点染成绿色，表示这些节点不能与起始节点属于同一个集合。我们再将这些绿色节点直接相连的所有节点染成红色，以此类推，直到无向图中的每个节点均被染色。
而如果在过程中，节点直接相邻的节点存在颜色和该节点相同（之前已经被染过），那么染色失败。
解题思路参考：leetcode官网染色法
官网的思路很清晰，但代码实现不简洁，具体代码实现还参考了：知乎染色法
边界条件：
时间复杂度：O(n+m)，其中 n 和 m分别是无向图中的点数和边数。
空间复杂度：O(n)，存储节点颜色的数组需要 O(n) 的空间，并且在深度优先搜索的过程中，栈的深度最大为 n，需要 O(n)的空间。
// DFS染色法
class Solution {
static constexpr int UNCOLORED = 0;
static constexpr int RED = 1;
static constexpr int GREEN = 2;
vector<int> colors;
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
colors.assign(n, UNCOLORED);
for (int i=0; i<n; i++) {
if (colors[i] == UNCOLORED) {
if (!dfs(i, RED, graph)) return false;
}
}
return true;
}
bool dfs(int cur, int color, vector<vector<int>>& graph) {
// 参数color是cur应该染的颜色
// 如果cur已经被染色，但已经染的颜色不是color，表明染色失败
if (colors[cur] != UNCOLORED) {
return colors[cur] == color;
}
colors[cur] = color;
// 这是邻接点应该染的颜色，和cur的不同
int colorNext = color == RED? GREEN: RED;
for (int next: graph[cur]) {
// 遍历所有邻接点，如果该染的颜色和已经染的不同，则失败
if (!dfs(next, colorNext, graph)) return false;
}
return true;
}
};886.可能的二分法
题目链接：886.possible-bipartition
解法：
这个题是上一个题的加强版，也是用染色法或者并查集解决，所以在做此题之前，先把上一个题干掉了。这个tag题的出题频率更高。
这个题其实就比785改动了两个地方：（1）需要自己构建邻接表；（2）点的起始值是1而不是0。
也就是说，只要我们构建好邻接表，然后把起始值从1改为0，那就可以完全复用785的代码了。
参考题解：LeetCode 886 - 可能的二分法 (Python3|Go)[递归/DFS] Possible Bipartition - 知乎
边界条件：无
时间复杂度：O(n+m)
空间复杂度：O(n)
//染色法
class Solution {
static constexpr int UNCOLORED = 0;
static constexpr int RED = 1;
static constexpr int GREEN = 2;
vector<int> colors;
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
// 构建邻接表
vector<vector<int>> graph(n);
for (const auto& dis: dislikes) {
int a = dis[0] - 1;
int b = dis[1] - 1;
graph[a].push_back(b);
graph[b].push_back(a);
}
return isBipartite(graph);
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
colors.assign(n, UNCOLORED);
for (int i=0; i<n; i++) {
if (colors[i] == UNCOLORED) {
if (!dfs(i, RED, graph)) return false;
}
}
return true;
}
bool dfs(int cur, int color, vector<vector<int>>& graph) {
// 参数color是cur应该染的颜色
// 如果cur已经被染色，但已经染的颜色不是color，表明染色失败
if (colors[cur] != UNCOLORED) {
return colors[cur] == color;
}
colors[cur] = color;
// 这是邻接点应该染的颜色，和cur的不同
int colorNext = color == RED? GREEN: RED;
for (int next: graph[cur]) {
// 遍历所有邻接点，如果该染的颜色和已经染的不同，则失败
if (!dfs(next, colorNext, graph)) return false;
}
return true;
}
};
