给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
这道题，最最简洁的方法应该就是使用递归了。主要思路是，每两个一组，进行交换，然后递归执行。
星河拾贝录
class Solution {
public:
LinkedList* swapPairs(LinkedList* head) {
if (!head || !head->next) return head;
// 当前组下的新的head
LinkedList* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明： 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
堆栈的特性是 LIFO，而队列则是 FIFO，因此想要用堆栈实现队列，需要用两个堆栈的 LIFO 叠加效果，来实现 FIFO。
class MyQueue {
public:
MyQueue() = default;
void push(int x) {
while (!output_.empty()) {
input_.push(output_.top());
output_.pop();
}
input_.push(x);
}
int pop() {
while (!input_.empty()) {
output_.push(input_.top());
input_.pop();
}
int ret = output_.top();
output_.pop();
return ret;
}
int peek() {
while (!input_.empty()) {
output_.push(input_.top());
input_.pop();
}
return output_.top();
}
bool empty() {
return input_.empty() && output_.empty();
}
private:
std::stack<int> input_;
std::stack<int> output_;
};请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
队列是 FIFO 的，而堆栈是 LIFO，要想用队列模拟堆栈，就需要在取出元素的时候，将一个队列中的除了最后一个元素的其他移动到另一个队列中，然后返回最后一个元素即可。
class MyStack {
public:
MyStack() = default;
int push(int x) {
auto& q = q1_.size() > 0 : q1_ ? q2_;
q.push(x);
}
int pop() {
std::queue<int>& i = q1_.size() > 0 ? q1_ : q2_;
std::queue<int>& o = q1_.size() > 0 ? q2_ : q1_;
while (i.size() > 1) {
o.push(i.front());
i.pop();
}
int ret = i.front();
i.pop();
return ret;
}
int top() {
std::queue<int>& i = q1_.size() > 0 ? q1_ : q2_;
std::queue<int>& o = q1_.size() > 0 ? q2_ : q1_;
while (i.size() > 1) {
o.push(i.front());
i.pop();
}
int ret = i.front();
i.pop();
o.push(ret);
return ret;
}
bool empty() {
return q1_.empty() && q2_.empty();
}
private:
std::queue<int> q1_;
std::queue<int> q2_;
};给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
迭代法应该是我们最容易想到的常规方法，也比较符合人的思维逻辑。其核心思想就是通过两个指针移动，来 一个一个的修改链表的指向方向。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
};第二个方法就是使用递归，递归这种方法虽然不太容易能够想到，但是代码却很简洁。
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
这道题目是典型的堆栈数据结构的应用，虽然思路很清晰，代码也很简单，但是要注意逻辑的严谨性。尤其是在判断 栈顶元素是否匹配之前，要先判断栈是否为空。
class Solution {
public:
bool isValid(const std::string& s) {
std::stack<char> st;
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
if (c == '}' && st.top() != '{') return false;
if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}
};给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
hash 法是我们在判断重复元素类问题中最常用的方法。针对链表是否有环来说，我们可以遍历链表，并用std::set
存放遍历过的元素，判断是否存在重复元素，如果存在则表示有环，如果遍历结束且不存在重复，则没有环。
class Solution {
public:
bool hasCycle(ListNode* head) {
std::set<ListNode*> set;
ListNode* cur = head;
while (cur) {
if (set.count(cur) > 0) return true;
set.insert(cur);
cur = cur->next;
}
return false;
}
};快慢指针就是用两个指针，一个一次移动一个位置，另一个一次移动两个位置，如果链表存在环，那么快的指针一定会 在某个地方和慢的指针重合，这个思路虽然很简单，但是具体的编码还是要多练习，不然也容易出错。
Ref: https://www.tangramvision.com/blog/c-rust-generics-and-specialization
C++和 Rust 中的泛型都是一种将其他类型作为其定义的一部分的类型。泛型是通过在类型定义中指定占位符的一种方式，然后可以 使用更具体的类型来替换，例如在 C++中可以这定义一个泛型类型：
template<typename T>
struct MyArray {
T* raw_array;
std::size_t size;
};对于这个泛型结构而言，MyArray<int>和MyArray<std::string>是不同的类型。我们可以通过指定具体的T类型，来复用MyArray这个泛型结构体。这里的MyArray<T>就像一个“模板”一样。
泛型不仅仅局限于结构体，我们同样也能写出泛型函数：
给你一个
m x n的矩阵board，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
这道题通常会用DFS来解，但是也可以用并查集解：首先我们将四条边上的’O’合并成一个连通分量，然后再将圈内的所有相邻的 ‘O’连接起来，最后遍历整个表，将所有为’O’且不与四条边上的’O’所在的连通分量相连的节点设置为’X’即可。
#include <vector>
#include <unordered_map>
class UnionFind {
public:
UnionFind(int num) {
for (int i = 0; i < num; ++i) {
parent_.push_back(i);
}
}
void unite(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent_[pRoot] = qRoot;
}
bool connected(int p, int q) {
return find(p) == find(q);
}
int find(int p) {
if (p != parent_[p]) {
parent_[p] = find(parent_[p]);
}
return parent_[p];
}
private:
std::vector<int> parent_;
};
class Solution {
public:
void solve(std::vector<std::vector<char>>& board) {
int m = board.size();
int n = board[0].size();
UnionFind uf(m * n + 1);
int dummy = m * n;
// 先将四条边上为'O'的节点连接起来
for (int i = 0; i < m; ++i) {
if (board[i][0] == 'O') {
uf.unite(dummy, i * n);
}
if (board[i][n - 1] == 'O') {
uf.unite(dummy, i * n + n - 1);
}
}
for (int j = 0; j < n; ++j) {
if (board[0][j] == 'O') {
uf.unite(dummy, j);
}
if (board[m - 1][j] == 'O') {
uf.unite(dummy, (m - 1) * n + j);
}
}
// 再将内部相邻的'O'连接起来
// 上 下 左 右
std::vector<std::vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
if (board[i][j] == 'X') continue;
for (const auto& dir : directions) {
if (board[i + dir[0]][j + dir[1]] == 'X') continue;
uf.unite(n * i + j, n * (i + dir[0]) + j + dir[1]);
}
}
}
// 最后将所有不与dummy连通的'O'设置为'X'即可
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (board[i][j] == 'O' && !uf.connected(dummy, n * i + j)) {
board[i][j] = 'X';
}
}
}
}
};给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程
equations[i]的长度为 4，并采用两种不同的形式之一："a==b"或"a!=b"。在这里，a和b是小写字母（不一定不同），表示单字母变量名。 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回true，否则返回false。
这一道题，显然是用并查集来解决，思路很简单，由于相等具有传递性，可以认为，一开始所有的字母变量都是独立的 集合，通过等式传递性，可以将这些相等的字母合并到同一个集合，最后看不等式中，是否存在连通的字母，如果存在 则表示等式方程不满足条件。
#include <vector>
#include <unordered_map>
class UnionFind {
public:
UnionFind(int num) {
for (int i = 0; i < num; ++i) {
parent_.push_back(i);
}
}
void unite(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent_[pRoot] = qRoot;
}
int find(int p) {
if (p != parent_[p]) {
parent_[p] = find(parent_[p]);
}
return parent_[p];
}
private:
std::vector<int> parent_;
};
class Solution {
public:
bool equationsPossible(const std::vector<std::string>& equations) {
// 26个小写字母
UnionFind uf(26);
for (const auto& e : equations) {
if (e[1] == '!') {
continue;
}
uf.unite(e[0] - 'a', e[3] - 'a');
}
for (const auto& e : equations) {
if (e[1] == '=') {
continue;
}
if (uf.find(e[0] - 'a') == uf.find(e[3] - 'a')) {
return false;
}
}
return true;
}
};给定一个未排序的整数数
nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度O(n)的算法解决此问题。
这道题目可以用并查集来解决。初始状态下数组中的每个元素都是一个独立的集合，然后遍历数组，将当前元素相邻的 元素合并到一个集合，最后返回所有集合中元素个数最多的数量。这里要注意去重。
#include <vector>
#include <unordered_map>
class UnionFind {
public:
UnionFind(int num) {
for (int i = 0; i < num; ++i) {
parent_.push_back(i);
size_.push_back(1);
}
}
void unite(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent_[pRoot] = qRoot;
size_[qRoot] += size_[pRoot];
}
int find(int p) {
if (p != parent_[p]) {
parent_[p] = find(parent_[p]);
}
return parent_[p];
}
int maxConnectedSize() {
int ret = 0;
for (int i = 0; i < parent_.size(); ++i) {
if (parent_[i] == i) {
ret = std::max(ret, size_[i]);
}
}
return ret;
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};
class Solution {
public:
int longestConsecutive(std::vector<int>& nums) {
// 用于记录元素和下标的对应关系，同时也用来去重
std::unordered_map map;
// 构造一个并查集实例，以下标来表示nums中的一个数字
// 初始状态下，每个元素都是独立的集合
UnionFind uf(nums.size());
for (int i = 0; i < nums.size(); ++i) {
// 去重
if (map.find(nums[i]) != map.end()) {
continue;
}
// 将比当前元素小1的元素连接起来
if (map.find(nums[i] - 1) != map.end()) {
uf.unite(i, map[nums[i] - 1]);
}
// 将比当前元素大1的元素连接起来
if (map.find(nums[i] + 1) != map.end()) {
uf.unite(i, map[nums[i] + 1]);
}
// 记录元素和下标的对应关系
map[nums[i]] = i;
}
// 返回最终所有集合中，元素最多的集合的元素个数
return uf.maxConnectedSize();
}
};