- 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
this->inorder = inorder;
return build(0, preorder.size() - 1, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
vector<int> inorder;
TreeNode* build(int l1, int r1, int l2, int r2) {
if (l1 > r1) return nullptr;
TreeNode* root = new TreeNode(preorder[l1]);
// preorder[l1...r1], inorder[l2...r2]
int mid = l2;
while (inorder[mid] != preorder[l1]) mid++;
// preorder[l1...r1], inorder[l2...mid...r2];
root->left = build(l1 + 1, l1 + (mid - l2), l2, mid - 1);
root->right = build(l1 + mid - l2 + 1, r1, mid + 1, r2);
return root;
}
};
- 297. 二叉树的序列化与反序列化 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string ans;
rserialize(root, ans);
return ans;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for (char ch : data) {
if (ch == ',') {
dataArray.push_back(str);
str.clear();
}
else
str += ch;
}
if (!str.empty()) {
dataArray.push_back(str);
str.clear();
}
return rdeserialize(dataArray);
}
private:
void rserialize(TreeNode* root, string& str) {
if (root == nullptr) {
str += "null,";
return;
}
str += to_string(root->val) + ",";
rserialize(root->left, str);
rserialize(root->right, str);
}
TreeNode* rdeserialize(list<string>& dataArray) {
if (dataArray.front() == "null") {
dataArray.erase(dataArray.begin());
return nullptr;
}
TreeNode* root = new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
root->left = rdeserialize(dataArray);
root->right = rdeserialize(dataArray);
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
- 1245. 树的直径 - 力扣（LeetCode）
class Codec {
public:
int treeDiameter(vector<vector<int>>& edges) {
n = 0;
for (vector<int> edge : edges) {
int x = edge[0];
int y = edge[1];
n = max(n, max(x, y));
}
n++;
for (int i = 0; i < n; i++) to.push_back({});
for (vector<int> edge : edges) {
int x = edge[0];
int y = edge[1];
to[x].push_back(y);
to[y].push_back(x);
}
int p = findFarthet(0).first;
return findFarthet(p).second;
}
private:
vector<vector<int>> to;
int n;
// <点，距离>
pair<int, int> findFarthet(int start) {
vector<int> depth(n, -1);
queue<int> q;
q.push(start);
depth[start] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : to[x]) {
if (depth[y] != -1) continue;
depth[y] = depth[x] + 1;
q.push(y);
}
}
int ans = start;
for (int i = 0; i < n; i++)
if (depth[i] > depth[ans]) ans = i;
return {ans, depth[ans]};
}
};
- 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
this->p = p;
this->q = q;
dfs(root);
return ans;
}
private:
TreeNode* p;
TreeNode* q;
TreeNode* ans;
pair<bool, bool> dfs(TreeNode* root) {
if (root == nullptr) return {false, false};
pair<bool, bool> leftRst = dfs(root->left);
pair<bool, bool> rightRst = dfs(root->right);
pair<bool, bool> result;
result.first = leftRst.first || rightRst.first || root->val == p->val;
result.second = leftRst.second || rightRst.second || root->val == q->val;
if (result.first && result.second && ans == nullptr) ans = root;
return result;
}
};
- 684. 冗余连接 - 力扣（LeetCode）
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = 0;
for (vector<int> edge : edges) {
int x = edge[0];
int y = edge[1];
n = max(n, max(x, y));
}
// 出边数组
to = vector<vector<int>>(n + 1);
visited = vector<bool>(n + 1);
for (vector<int> edge : edges) {
int x = edge[0];
int y = edge[1];
to[x].push_back(y);
to[y].push_back(x);
hasCycle = false;
dfs(x, 0);
if (hasCycle) return edge;
}
return {};
}
private:
vector<vector<int>> to;
vector<bool> visited;
bool hasCycle;
void dfs(int x, int fa) {
if (visited[x]) return;
visited[x] = true;
for (int y : to[x]) {
if (y == fa) continue;
if (!visited[y]) dfs(y, x);
else hasCycle = true;
}
// 一般dfs此处无需恢复
// 不过此题需要多次使用visited数组，所以要恢复现场
visited[x] = false;
}
};
- 207. 课程表 - 力扣（LeetCode）
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
to = vector<vector<int>>(numCourses);
inDegree = vector<int>(numCourses, 0);
for (vector<int>& pre : prerequisites) {
int ai = pre[0];
int bi = pre[1];
to[bi].push_back(ai);
inDegree[ai]++;
}
queue<int> q;
// 拓扑排序
// 第一步：从零入度点出发
for (int i = 0; i < numCourses; i++)
if (inDegree[i] == 0) q.push(i);
vector<int> lessons;
while (!q.empty()) {
int x = q.front();
q.pop();
lessons.push_back(x);
// 第二步：扩展一个点，周围的点入度减一
for (int y : to[x]) {
inDegree[y]--;
// 第三步：入度减为0，表示可以入队了
if (inDegree[y] == 0)
q.push(y);
}
}
return lessons.size() == numCourses;
}
private:
vector<vector<int>> to;
vector<int> inDegree;
};
- 210. 课程表 II - 力扣（LeetCode）
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
to = vector<vector<int>>(numCourses);
inDegree = vector<int>(numCourses, 0);
for (vector<int>& pre : prerequisites) {
int ai = pre[0];
int bi = pre[1];
to[bi].push_back(ai);
inDegree[ai]++;
}
queue<int> q;
// 拓扑排序
// 第一步：从零入度点出发
for (int i = 0; i < numCourses; i++)
if (inDegree[i] == 0) q.push(i);
vector<int> lessons;
while (!q.empty()) {
int x = q.front();
q.pop();
lessons.push_back(x);
// 第二步：扩展一个点，周围的点入度减一
for (int y : to[x]) {
inDegree[y]--;
// 第三步：入度减为0，表示可以入队了
if (inDegree[y] == 0)
q.push(y);
}
}
return lessons.size() == numCourses ? lessons : vector<int>();
}
private:
vector<vector<int>> to;
vector<int> inDegree;
};
- 17. 电话号码的字母组合 - 力扣（LeetCode）
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits == "") return {};
alphabet['2'] = "abc";
alphabet['3'] = "def";
alphabet['4'] = "ghi";
alphabet['5'] = "jkl";
alphabet['6'] = "mno";
alphabet['7'] = "pqrs";
alphabet['8'] = "tuv";
alphabet['9'] = "wxyz";
this->digits = digits;
dfs(0);
return ans;
}
private:
vector<string> ans;
string digits;
unordered_map<char, string> alphabet;
string str;
void dfs(int index) {
if (index == digits.length()) {
ans.push_back(str);
return;
}
for (char ch : alphabet[digits[index]]) {
str.push_back(ch);
dfs(index + 1);
str.pop_back();
}
}
};
- 51. N 皇后 - 力扣（LeetCode）
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
this->n = n;
used = vector<bool>(n, false);
dfs(0);
vector<vector<string>> ans;
for (vector<int>& p : result) {
vector<string> pattern(n, string(n, '.'));
for (int row = 0; row < n; row++)
pattern[row][p[row]] = 'Q';
ans.push_back(pattern);
}
return ans;
}
private:
int n;
vector<bool> used;
unordered_map<int, bool> usedPlus;
unordered_map<int, bool> usedMinus;
vector<int> p;
vector<vector<int>> result;
void dfs(int row) {
if (row == n) {
result.push_back(p);
return;
}
for (int col = 0; col < n; col++)
if (!used[col] && !usedPlus[row + col] && !usedMinus[row - col]) {
used[col] = true;
usedPlus[row + col] = true;
usedMinus[row - col] = true;
p.push_back(col);
dfs(row + 1);
p.pop_back();
usedMinus[row - col] = false;
usedPlus[row + col] = false;
used[col] = false;
}
}
};
- 200. 岛屿数量 - 力扣（LeetCode）
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
this->grid = grid;
visited = vector<vector<bool>>(m, vector<bool>(n, false));
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == '1' && !visited[i][j]) {
ans++;
bfs(i, j);
}
return ans;
}
private:
int m, n;
vector<vector<char>> grid;
vector<vector<bool>> visited;
void bfs(int sx, int sy) {
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
queue<pair<int, int>> q;
q.push({sx, sy});
visited[sx][sy] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (visited[nx][ny]) continue;
if (grid[nx][ny] != '1') continue;
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
};
- 433. 最小基因变化 - 力扣（LeetCode）
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
for (string& seq : bank) hashBank.insert(seq);
if (hashBank.find(endGene) == hashBank.end()) return -1;
const char gene[4] = {'A', 'C', 'G', 'T'};
depth[startGene] = 0;
queue<string> q;
q.push(startGene);
while (!q.empty()) {
string s = q.front();
q.pop();
for (int i = 0; i < 8; i++)
for (int j = 0; j < 4; j++)
if (s[i] != gene[j]) {
string ns = s;
ns[i] = gene[j];
if (hashBank.find(ns) == hashBank.end()) continue;
if (depth.find(ns) != depth.end()) continue;
depth[ns] = depth[s] + 1;
q.push(ns);
if (ns == endGene) return depth[ns];
}
}
return -1;
}
private:
unordered_set<string> hashBank;
unordered_map<string, int> depth;
};
