-
208. 实现 Trie (前缀树) - 力扣（LeetCode）
法一：节点数组实现
class Trie {
public:
Trie() {
root = new Node();
}
void insert(string word) {
find(word, true, false);
}
bool search(string word) {
return find(word, false, false);
}
bool startsWith(string prefix) {
return find(prefix, false, true);
}
private:
struct Node {
int cnt;
vector<Node*> children;
Node() {
cnt = 0;
children = vector<Node*>(26, nullptr);
}
};
Node* root;
bool find(const string& s, bool isInsert, bool isPrefix) {
Node* cur = root;
for (char ch : s) {
if (cur->children[ch - 'a'] == nullptr)
if (isInsert)
cur->children[ch - 'a'] = new Node();
else
return false;
cur = cur->children[ch - 'a'];
}
if (isInsert) cur->cnt++;
if (isPrefix) return true;
return cur->cnt > 0;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
法二：节点map实现
class Trie {
public:
Trie() {
root = new Node();
}
void insert(string word) {
find(word, true, false);
}
bool search(string word) {
return find(word, false, false);
}
bool startsWith(string prefix) {
return find(prefix, false, true);
}
private:
struct Node {
int cnt;
unordered_map<char, Node*> children;
Node() : cnt(0) {}
};
Node* root;
bool find(const string& s, bool isInsert, bool isPrefix) {
Node* cur = root;
for (char ch : s) {
if (cur->children.find(ch) == cur->children.end())
if (isInsert)
cur->children[ch] = new Node();
else
return false;
cur = cur->children[ch];
}
if (isInsert) cur->cnt++;
if (isPrefix) return true;
return cur->cnt > 0;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
root = new Node();
m = board.size();
n = board[0].size();
this->board = board;
visited = vector<vector<bool>>(m, vector<bool>(n, false));
for (const string& word : words) insert(word);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
visited[i][j] = true;
dfs(i, j, root);
visited[i][j] = false;
}
return vector<string>(ans.begin(), ans.end());
}
private:
struct Node {
int cnt;
unordered_map<char, Node*> children;
Node() : cnt(0) {}
};
void insert(const string& str) {
Node* cur = root;
for (char ch : str) {
if (cur->children.find(ch) == cur->children.end())
cur->children[ch] = new Node();
cur = cur->children[ch];
}
cur->cnt++;
}
void dfs(int x, int y, Node* cur) {
if (cur == nullptr) return;
char ch = board[x][y];
if (cur->children.find(ch) == cur->children.end()) return;
Node* next = cur->children[ch];
str.push_back(ch);
if (next->cnt > 0) ans.insert(str);
if (next->children.empty()) {
cur->children.erase(ch);
delete next;
}
else
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
dfs(nx, ny, next);
visited[nx][ny] = false;
}
str.pop_back();
}
Node* root;
int m, n;
vector<vector<char>> board;
vector<vector<bool>> visited;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
string str;
unordered_set<string> ans;
};
-
547. 省份数量 - 力扣（LeetCode）
法一：DFS
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
n = isConnected.size();
this->isConnected = isConnected;
visited = vector<bool>(n);
ans = 0;
for (int i = 0; i < n; i++)
if (!visited[i]) {
visited[i] = true;
dfs(i);
ans++;
}
return ans;
}
private:
vector<bool> visited;
vector<vector<int>> isConnected;
int ans, n;
void dfs(int x) {
for (int i = 0; i < n; i++)
if (isConnected[x][i] && !visited[i]) {
visited[i] = true;
dfs(i);
}
}
};
法二：并查集
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
fa = vector<int>(n);
// 初始化并查集
for (int i = 0; i < n; i++)
fa[i] = i;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (isConnected[i][j])
unionSet(i, j);
int ans = 0;
for (int i = 0; i < n; i++)
if (find(i) == i)
ans++;
return ans;
}
private:
vector<int> fa;
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void unionSet(int x, int y) {
x = find(x), y = find(y);
if (x != y) fa[x] = y;
}
};
-
130. 被围绕的区域 - 力扣（LeetCode）
法一：DFS
class Solution {
public:
void solve(vector<vector<char>>& board) {
m = board.size();
n = board[0].size();
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(board, 0, j);
dfs(board, m - 1, j);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O')
board[i][j] = 'X';
if (board[i][j] == 'A')
board[i][j] = 'O';
}
}
private:
int m, n;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
void dfs(vector<vector<char>>& board, int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n) return;
if (board[x][y] != 'O') return;
board[x][y] = 'A';
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
dfs(board, nx, ny);
}
}
};
法二：并查集
class Solution {
public:
void solve(vector<vector<char>>& board) {
m = board.size();
n = board[0].size();
fa = vector<int>(m * n + 1);
for (int i = 0; i <= m * n; i++) fa[i] = i;
int outSide = m * n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (board[i][j] == 'X') continue;
for (int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni < 0 || nj < 0 || ni >= m || nj >= n)
unionSet(num(i, j), outSide);
else
if (board[ni][nj] == 'O')
unionSet(num(i, j), num(ni, nj));
}
}
outSide = find(outSide);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'O' && find(num(i, j)) != outSide)
board[i][j] = 'X';
}
private:
vector<int> fa;
int m, n;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void unionSet(int x, int y) {
x = find(x), y = find(y);
if (x != y) fa[x] = y;
}
int num(int x, int y) {
return x * n + y;
}
};
-
145. 超市 - AcWing题库
利用并查集压缩路径思想
#include<bits/stdc++.h>
using namespace std;
int n;
// <profit, day>
pair<int, int> a[10000];
int fa[10001];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main() {
while (cin >> n) {
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
sort(a, a + n);
for (int i = 0; i <= 1e4; i++) fa[i] = i;
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
int profit = a[i].first;
int day = a[i].second;
int lastAvailableDay = find(day);
if (lastAvailableDay > 0) {
ans += profit;
fa[lastAvailableDay] = lastAvailableDay - 1;
}
}
cout << ans << endl;
}
return 0;
}
