- 图总结
- 广度优先搜索
- 单词接龙 (
medium)
- 单词接龙 (
- 深度优先搜索
- 并查集
- 最短路径
- 最短路径.一 (
hard迪杰斯特拉算法)
- 最短路径.一 (
- 最小生成树
- 最小生成树一.Prim算法 (
hard) - 最小生成树二.Kruscal算法 (
hard)
- 最小生成树一.Prim算法 (
- 拓扑排序
- 广度优先搜索
解法：带权值并查集 + 分子分母表达式转换
class UnionSet {
public:
UnionSet(const set<string> st) {
for (auto iter = st.begin(); iter != st.end(); ++iter) {
const string& str = *iter;
parent_mp_[str] = str;
weight_mp_[str] = 1.0;
size_mp_[str] = 1;
}
}
bool IsSameSet(const string& str1, const string& str2) {
return FindRoot(str1) == FindRoot(str2);
}
void Union(const string& str1, const string& str2, double val) {
const string& root1 = FindRoot(str1);
const string& root2 = FindRoot(str2);
double d1 = GetDivideToRoot(str1);
double d2 = GetDivideToRoot(str2);
if (size_mp_[root1] > size_mp_[root2]) {
parent_mp_[root2] = root1;
weight_mp_[root2] = d1 / d2 / val;
size_mp_[root1] = size_mp_[root1] + size_mp_[root2];
size_mp_.erase(root2);
} else {
parent_mp_[root1] = root2;
weight_mp_[root1] = d2 / d1 * val;
size_mp_[root2] = size_mp_[root1] + size_mp_[root2];
size_mp_.erase(root1);
}
}
double GetRes(const string& str1, const string& str2) {
if (str1 == str2) {
return 1.0;
}
if (!IsSameSet(str1, str2)) {
return -1.0;
}
return GetDivideToRoot(str1) / GetDivideToRoot(str2);
}
private:
// 当前节点 -> 父节点映射
unordered_map<string, string> parent_mp_;
// 当前节点 / 父节点 的结果
unordered_map<string, double> weight_mp_, size_mp_;
string FindRoot(const string& str) {
if (parent_mp_[str] != str) {
return FindRoot(parent_mp_[str]);
}
return str;
}
double GetDivideToRoot(const string& str) {
double res = 1.0;
string tmp = str;
while (parent_mp_[tmp] != tmp) {
res *= weight_mp_[tmp];
tmp = parent_mp_[tmp];
}
return res;
}
};
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
set<string> st;
for (const auto& equation : equations) {
st.insert(equation[0]);
st.insert(equation[1]);
}
UnionSet union_set(st);
for (int i = 0; i < equations.size(); ++i) {
const string& s1 = equations[i][0];
const string& s2 = equations[i][1];
if (union_set.IsSameSet(s1, s2)) continue;
union_set.Union(s1, s2, values[i]);
}
vector<double> res;
res.reserve(queries.size());
for (const auto& query : queries) {
if (st.find(query[0]) == st.end() || st.find(query[0]) == st.end()) {
res.emplace_back(-1.0);
} else {
res.emplace_back(union_set.GetRes(query[0], query[1]));
}
}
return res;
}
};解法：建立图的数据结构，dfs整个图，并记录已经访问过的node，如果遍历到某个节点发现与他相连的节点数大于1且都访问过，说明图中存在环；另外还有一种特殊情况考虑，所有的节点构成了多个隔离的环，这种情况遍历一次的节点数不等于总结点数
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (n < 1) return true;
vector<bool> visited(n ,false);
vector<vector<int>> graph(n, vector<int>());
for (const auto edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
int cnt = 0;
visited[0] = true;
return recursive(graph, visited, 0, cnt) && cnt == n;
}
bool recursive(const vector<vector<int>>& graph, vector<bool>& visited, int n, int& cnt) {
bool flag = false;
++cnt;
for (const int a : graph[n]) {
if (!visited[a]) {
visited[a] = true;
if (!recursive(graph, visited, a, cnt)) {
return false;
}
visited[a] = false;
flag = true;
}
}
if (!flag && graph[n].size() > 1) {
return false;
}
return true;
}
};现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
考察拓扑排序，利用课程之间的关系建立有向图，如果课程A之前需要完成课程B，那么在图中A指向B，同时定义数组degree统计每个节点的入度。定义队列que，首先将当前入度为0的节点(优先需要学习的课程)加入队列，定义变量cnt用于计数。然后进入循环，每次循环访问队首元素a，并弹出a，访问a指向的每个节点b，将b的入度减1，如果此时b的入度为0，则此时课程b可以进行学习，将b加入队列，然后进入下一次循环，每次循环都将cnt加1，直到队列为空时结束循环。最后，如果cnt等于课程数，说明所有的课程都加入过队列，它们可以有序地进行学习，返回true；否则，返回false。
设有向图的顶点数为v，边数为e
- 时间复杂度：O(v + e)
- 空间复杂度：O(v + e)
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>());
vector<int> degree(numCourses, 0);
for (const auto& vec : prerequisites) {
int from = vec[1];
int to = vec[0];
graph[from].push_back(to);
++degree[to];
}
queue<int> que;
for (int i = 0; i < numCourses; ++i) {
if (degree[i] == 0) {
que.push(i);
}
}
int cnt = 0;
while (!que.empty()) {
int cur = que.front();
que.pop();
for (const auto& a : graph[cur]) {
--degree[a];
if (degree[a] == 0) {
que.push(a);
}
}
++cnt;
if (cnt >= numCourses) return true;
}
return false;
}
};现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
处理过程同 课程表，只是需要加一步，在循环中每次从队列弹出队首元素的时候，将这个队首元素加入结果即可。
设有向图的顶点数为v，边数为e
- 时间复杂度：O(v + e)
- 空间复杂度：O(v + e)
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int >> graph(numCourses,vector<int>());
vector<int> degree(numCourses,0);
for(auto a : prerequisites)
{
int from = a.second;
int to = a.first;
graph[from].push_back(to);
degree[to]++;
}
queue<int> que;
for(int i=0;i<degree.size();i++)
{
if(degree[i] == 0)
que.push(i);
}
vector<int> res;
int cnt = 0;
while(!que.empty())
{
int a = que.front();
que.pop();
res.push_back(a);
for(auto b : graph[a])
{
degree[b]--;
if(degree[b] == 0)
que.push(b);
}
cnt++;
}
if(cnt == numCourses) return res;
return vector<int>(0);
}
};给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
考察图的广度优先遍历，由于是单词转换，建立图的时候，只相差一个字母的两个字符串构成相连的节点，利用这种关系可以建立无向图。遍历的过程类似 二叉树的层序遍历，利用队列结构来实现 BFS 的过程。对于图的结构，需要定义bool类型的数组visited来记录访问过的节点，从而就避免了重复访问同一个节点。由于需要统计最短转换的步数，在 DFS 过程中需要进行分层处理，每经过一层，将计数值cnt加一，直到访问到 endWord，返回cnt。
设有向图的顶点数为v，边数为e
- 时间复杂度：O(v)
- 空间复杂度：O(v)
class Solution {
public:
bool isNext(string str1,string str2)
{
int len1 = str1.size();
int len2 = str2.size();
if(len1 != len2)
return false;
int cnt = 0;
for(int i=0;i<len1;i++)
{
if(str1[i] != str2[i])
cnt++;
}
if(cnt == 1)
return true;
return false;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if(beginWord == endWord)
return 0;
int len = wordList.size();
queue<string> que;
vector<int> visited(len,false);
que.push(beginWord);
int cnt = 1;
string pre = beginWord;
string next;
while(!que.empty())
{
auto cur = que.front();
que.pop();
if(cur == endWord)
return cnt;
for(int i=0;i<len;i++)
{
auto s = wordList[i];
if(!visited[i] && isNext(s,cur))
{
que.push(s);
visited[i] = true;
next = s;
}
}
if(cur == pre)
{
pre = next;
cnt++;
}
}
return 0;
}
};给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
考察图的 DFS。我们遍历二维网格，定义bool类型的数组vis记录访问过的字符，对于遍历的每一个字符，如果这个字符为'1'并且没有被访问过(vis为false)，则找到一块新陆地，将结果res加1，同时就从这个字符开始进行 DFS，将这一块陆地上的所有'1'访问一遍。然后遍历下一个字符，重复前面的处理过程。遍历结束之后，结果res即为所求。
设二维网格的行数为m，列数为n
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
class Solution {
public:
void dfs(int h,int l,vector<vector<bool>>& vis,vector<vector<char>>& grid)
{
if(h < 0 || h >= grid.size())
return;
if(l < 0 || l >= grid[0].size())
return;
if(grid[h][l] == '0' || vis[h][l])
return;
vis[h][l] = true;
dfs(h,l-1,vis,grid);
dfs(h,l+1,vis,grid);
dfs(h-1,l,vis,grid);
dfs(h+1,l,vis,grid);
}
int numIslands(vector<vector<char>>& grid) {
if(grid.size() == 0)
return 0;
int res = 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> vis(m,vector<bool>(n,false));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(grid[i][j] == '1' && !vis[i][j])
{
res++;
dfs(i,j,vis,grid);
}
}
return res;
}
};给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
方法同 岛屿的个数，利用图的 DFS，因为与边界上的'0'相连的'0'都不会被填充，我们首先遍历二维矩阵的边界上的字符，如果字符为'0'，则从这个位置开始在二维矩阵中进行 DFS，将相连的所有'0'(包括自己)都填充为'$'。此时二维矩阵中剩下的'0'都需要被填充为'X'，我们遍历二维矩阵，遇到'0'就将它填充为'X'。最后，将二维矩阵中的'$'恢复到'0'即可。
设二维矩阵的行数为m，列数为n
- 时间复杂度：O(mn)
- 空间复杂度：O(1)
class Solution {
public:
void dfs(int x,int y,vector<vector<char>>& vec)
{
int row = vec.size();
int col = vec[0].size();
if(x < 0 || y < 0 || x >= row || y >= col || vec[x][y] != 'O')
return;
vec[x][y] = '$';
dfs(x+1,y,vec);
dfs(x-1,y,vec);
dfs(x,y+1,vec);
dfs(x,y-1,vec);
}
void solve(vector<vector<char>>& board) {
if(board.empty()) return;
int row = board.size();
int col = board[0].size();
int i=0,j=0;
for(;j<col;j++)
{
if(board[i][j] == 'O')
dfs(i,j,board);
}
j = col-1;
for(;i<row;i++)
{
if(board[i][j] == 'O')
dfs(i,j,board);
}
i = row-1;
for(;j>=0;j--)
{
if(board[i][j] == 'O')
dfs(i,j,board);
}
j=0;
for(;i>=0;i--)
{
if(board[i][j] == 'O')
dfs(i,j,board);
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(board[i][j] == 'O')
board[i][j] = 'X';
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(board[i][j] == '$')
board[i][j] = 'O';
}
}
};给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
示例 2:
输入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
暴力求解，首先定义变量res记录结果，然后遍历矩阵，对于遍历的每一个整数，都以它为起点进行 DFS，搜索的同时记录当前路径的长度，每次搜索到一个递增路径的终点时，就将当前路径的长度和res比较，取两者较大值。遍历结束后，得到的res即为所有递增路径长度的最大值。但是由于对于每一个整数都需要重新对矩阵进行 DFS，整个过程会非常耗时。
在方法1的基础上进行优化，结合动态规划的思想，定义数组dp，设dp[i][j]表示以第i行，第j列元素为起点的最长序列的长度。那么最终我们就是要求所有dp[i]][j]中的最大值。如果知道其中某个dp[i][j]怎么求，那么问题也就解决了。
既然dp[i][j]表示以第i行，第j列元素为终点的最长序列的长度，可以求出分别以matrix[i][j]周围4个方向(上下左右)上元素为终点的递增序列的长度，在满足递增特性的情况下，dp[i][j]就是几个方向中最长序列长度的最大值再加1。以向上方向为例：
-
如果
matrix[i][j] <= matrix[i-1][j]，那么只包含当前元素，最长序列长度为1； -
如果
matrix[i][j] > matrix[i-1][j]，那么最长序列的长度取dp[i - 1][j] + 1和dp[i][j]两者的较大值。
根据前面的分析，我们首先遍历矩阵，对于遍历的每一个元素matrix[i][j]，递归地求出以这个元素为终点的最长递增路径dp[i][j]，得到所有dp[i][j]的最大值即为所有最长递增路径的长度。在递归的过程中dp数组保存了中间值，避免了求重复的子问题，因此减少了时间。
注意：递归的过程不会产生无限循环。比如：以matrix[i][j]为终点求dp[i][j]，如果此时matrix[i][j] > matrix[i-1][j]，那么需要依赖dp[i-1][j]，那么求dp[i-1][j]肯定不需要依赖dp[i][j]，因为只有满足递增性质时，才会发生递归。
class Solution {
public:
int dfs(int x,int y,const vector<vector<int>>& vec,vector<vector<int>>& dp)
{
if(dp[x][y] != 0)
return dp[x][y];
int row = vec.size();
int col = vec[0].size();
dp[x][y] = 1;
if(x > 0 && vec[x-1][y] < vec[x][y])
{
int cnt = dfs(x-1,y,vec,dp) + 1;
dp[x][y] = max(dp[x][y],cnt);
}
if(x < row - 1 && vec[x+1][y] < vec[x][y])
{
int cnt = dfs(x+1,y,vec,dp) + 1;
dp[x][y] = max(cnt,dp[x][y]);
}
if(y > 0 && vec[x][y-1] < vec[x][y])
{
int cnt = dfs(x,y-1,vec,dp) + 1;
dp[x][y] = max(dp[x][y],cnt);
}
if(y < col - 1 && vec[x][y+1] < vec[x][y])
{
int cnt = dfs(x,y+1,vec,dp) + 1;
dp[x][y] = max(dp[x][y],cnt);
}
return dp[x][y];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.empty()) return 0;
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int>> dp(row,vector<int>(col,0));
int res = INT_MIN;
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
int a = dfs(i,j,matrix,dp);
res = max(res,a);
}
return res;
}
};在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:
- 输入的二维数组大小在 3 到 1000。
- 二维数组中的整数在1到N之间，其中N是输入数组的大小。
遍历图的每一个边对应的数值对[u,v]，遍历的时候以每个数值作为小集合，建立并查集，处理情况如下：
- 如果
u和v不属于同一个集合，则将它们合并到同一个集合中，接着遍历下一条边； - 如果
u和v属于同一个集合，说明之前u和v在图中已经相连，那么[u,v]就是冗余的那条边。
class UnionSet
{
public:
UnionSet(int n){
for(int i=1;i<=n;i++)
{
tr_mp[i] = i;
sz_mp[i] = 1;
}
}
int findRoot(int idx)
{
if(tr_mp[idx] == idx)
return idx;
return findRoot(tr_mp[idx]);
}
void unionTree(int idx1,int idx2)
{
if(findRoot(idx1) == findRoot(idx2))
return;
int root1 = findRoot(idx1);
int root2 = findRoot(idx2);
if(root1 < root2)
tr_mp[root1] = root2;
else
tr_mp[root2] = root1;
}
bool isSame(int idx1,int idx2)
{
return findRoot(idx1) == findRoot(idx2);
}
private:
unordered_map<int,int> tr_mp;
unordered_map<int,int> sz_mp;
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = INT_MIN;
for(auto a : edges)
for(auto b : a)
{
n = max(b,n);
}
UnionSet ust(n);
for(auto a : edges)
{
int idx1 = a[0];
int idx2 = a[1];
if(!ust.isSame(idx1,idx2))
{
ust.unionTree(idx1,idx2);
continue;
}
return a;
}
}
};班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
- N 在[1,200]的范围内。
- 对于所有学生，有M[i][i] = 1。
- 如果有M[i][j] = 1，则有M[j][i] = 1。
由于朋友关系具有传递性，很显然符合并查集的特性，遍历二维数组，将所有的朋友合并到一个集合，遍历结束之后，返回集合的个数就是朋友圈的个数。
class UnionSet
{
public:
UnionSet(int n)
{
for(int i=0;i<n;i++)
{
fatherMp[i] = i;
sizeMp[i] = 1;
}
}
bool isSameSet(int node1,int node2)
{
return findHead(node1) == findHead(node2);
}
void Union(int node1,int node2)
{
int head1 = findHead(node1);
int head2 = findHead(node2);
if(head1 == head2)
return;
if(sizeMp[head1] <= sizeMp[head2])
{
fatherMp[head1] = head2;
sizeMp[head2] = sizeMp[head1] + sizeMp[head2];
sizeMp.erase(head1);
}
else{
fatherMp[head2] = head1;
sizeMp[head1] = sizeMp[head1] + sizeMp[head2];
sizeMp.erase(head2);
}
}
int findHead(int node)
{
//递归找集合的根
int head;
if(fatherMp[node] == node)
return node;
else{
head = findHead(fatherMp[node]);
}
return head;
}
int getSize()
{
return sizeMp.size();
}
private:
unordered_map<int,int> fatherMp,sizeMp;
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if(M.empty())
return 0;
int size = M[0].size();
UnionSet st(size);
for(int i=0;i<size;i++)
{
for(int j=i+1;j<size;j++)
{
if(M[i][j] == 1)
{
st.Union(i,j);
}
}
}
return st.getSize();
}
};给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
遍历二维网格的每一个位置board[i][j]，如果board[i][j] == word[0]，则从board[i][j]开始向二维网格的上下左右四个方向进行深度优先搜索，同时开辟一个bool类型的数组vis，用于记录已经访问过的字母，在每一层递归搜索到一个字母board[a][b]，令vis[a][b] = true，然后向该字母的上下左右四个方向进行搜索（进入下一层递归），如果四个方向中有一个满足条件（返回true），本层递归的bool结果就为true，否则，返回false，待四个方向都搜索完成（递归返回）之后恢复vis[a][b] = false。在搜索的过程中用一个变量idx记录当前搜索的字母在单词中的索引。递归结束条件为：
- 如果字母位置越界或者字母已经被访问过或者搜索到的字母不等于
word[idx]，则返回false； - 如果
idx == word.size()，则满足条件返回true。
最终，得到递归函数的bool类型即为所求。
class Solution {
public:
bool dfs(const vector<vector<char>>& board,vector<vector<bool>>& vis,const string& word,int a,int b,int idx)
{
if(idx == word.size())
return true;
if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || vis[a][b] || word[idx] != board[a][b])
return false;
vis[a][b] = true;
bool res = false;
res = dfs(board,vis,word,a - 1,b,idx + 1) || dfs(board,vis,word,a + 1,b,idx + 1)
|| dfs(board,vis,word,a,b - 1,idx + 1) || dfs(board,vis,word,a,b + 1,idx + 1);
vis[a][b] = false;
return res;
}
bool exist(vector<vector<char>>& board, string word) {
if(board.empty())
return false;
int row = board.size();
int col = board[0].size();
if(word.size() > row * col)
return false;
vector<vector<bool>> vis(row,vector<bool>(col,false));
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(board[i][j] == word[0])
{
if(dfs(board,vis,word,i,j,0))
return true;
}
}
return false;
}
};给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
对单词列表中的每个单词，都到board中进行 DFS，符合条件的则加入结果数组中，这个过程非常耗时。
在方法1的基础上进行优化，建立字典树，将所有要搜索的单词都添加到字典树中(详见 实现Trie)，注意字典树的节点数据结构中添加了一个string类型的成员，用于保存在这个节点结束的单词。然后遍历二维网格，从遍历到的每一个元素开始向四个方向进行深度优先搜索，如果搜索的时候当前元素在字典树中存在，那么就继续搜索下去，搜索的同时，如果发现搜索到某一个节点的时候在字典树中构成了一个单词，那么就将这个单词添加到结果中。相反如果元素在字典树中不存在, 那么就结束当前分支的搜索。
注意：在 DFS 的过程中，需要记录已经访问过的节点，可以开辟一个二维数组vis来标记，也可以直接在原矩阵上修改，搜索完之后再改回来。
class node
{
public:
node()
{
for(int i=0;i<26;i++)
arr[i] = nullptr;
}
node* arr[26];
string s;
};
class Trie
{
public:
node* root;
Trie()
{
root = nullptr;
}
void insert(const string& word)
{
if(word.empty()) return;
if(!root) root = new node;
auto temp = root;
for(int i=0;i<word.size();i++)
{
char ch = word[i];
int idx = ch - 'a';
if(!temp->arr[idx])
temp->arr[idx] = new node;
temp = temp->arr[idx];
}
temp->s = word;
}
bool inTrie(const string& word)
{
auto temp = root;
if(!root) return false;
for(auto ch : word)
{
int idx = ch - 'a';
if(temp->arr[idx])
{
temp = temp->arr[idx];
}
else
return false;
}
return true;
}
};
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
if(board.empty() || words.empty()) return vector<string>();
vector<string> vec;
Trie* tree = new Trie;
for(auto word : words)
{
tree->insert(word);
}
int row = board.size();
int col = board[0].size();
vector<vector<bool>> vis(row,vector<bool>(col,false));
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
dfs(i,j,board,tree->root,vis,vec);
}
sort(vec.begin(),vec.end());
return vec;
}
void dfs(int i,int j,vector<vector<char>>& board,node* tree,vector<vector<bool>>& vis,vector<string>& vec)
{
int row = board.size();
int col = board[0].size();
if(i < 0 || i >= row || j < 0 || j >= col || vis[i][j] || !tree->arr[board[i][j] - 'a'])
return;
int idx = board[i][j] - 'a';
tree = tree->arr[idx];
if( !(tree->s.empty()) )
{
vec.push_back(tree->s);
tree->s.clear();
}
vis[i][j] = true;
dfs(i-1,j,board,tree,vis,vec);
dfs(i+1,j,board,tree,vis,vec);
dfs(i,j-1,board,tree,vis,vec);
dfs(i,j+1,board,tree,vis,vec);
vis[i][j] = false;
}
};万圣节的早上，小Hi和小Ho在经历了一个小时的争论后，终于决定了如何度过这样有意义的一天——他们决定去闯鬼屋！
在鬼屋门口排上了若干小时的队伍之后，刚刚进入鬼屋的小Hi和小Ho都颇饥饿，于是他们决定利用进门前领到的地图，找到一条通往终点的最短路径。
鬼屋中一共有N个地点，分别编号为1..N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。那么小Hi和小Ho至少要走多少路程才能够走出鬼屋去吃东西呢？
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^3，M<=10^4, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
对于100%的数据，满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
对于每组测试数据，输出一个整数Ans，表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。
样例输入
5 23 5 4
1 2 708
2 3 112
3 4 721
4 5 339
5 4 960
1 5 849
2 5 98
1 4 99
2 4 25
2 1 200
3 1 146
3 2 106
1 4 860
4 1 795
5 4 479
5 4 280
3 4 341
1 4 622
4 2 362
2 3 415
4 1 904
2 1 716
2 5 575
样例输出
123
迪杰斯特拉算法
#include <vector>
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
void Dijkstral(int src,vector<int>& dist,vector<bool>& vis,vector<vector<int>>& graph)
{
int vex = graph.size();
while (1)
{
int idx = -1;
int dis = INT_MAX;
for (int i=0;i<dist.size();i++)
{
if(!vis[i])
{
if(dist[i] < dis)
{
dis = dist[i];
idx = i;
}
}
}
if(dis == INT_MAX)
break;
vis[idx] = true;
for(int i=0;i<vex;i++)
{
if(!vis[i] && graph[i][idx] < INT_MAX)
{
if(dist[i] > graph[idx][i] + dist[idx])
dist[i] = graph[idx][i] + dist[idx];
}
}
}
}
int main()
{
int vex,edge;
cin >> vex >> edge;
int src,dst;
cin >> src >> dst;
vector<vector<int>> graph(vex,vector<int>(vex,INT_MAX));
while (edge--)
{
int a,b,len;
cin >> a >> b >> len;
graph[a-1][b-1] = min(graph[a-1][b-1],len);
graph[b-1][a-1] = graph[a-1][b-1];
}
vector<int> dist(vex,INT_MAX);
dist[src-1] = 0;
for(int i=0;i<vex;i++)
{
if(i != src-1 && graph[src-1][i] != INT_MAX)
{
dist[i] = graph[src-1][i];
}
}
vector<bool> vis(vex,false);
Dijkstral(src,dist,vis,graph);
cout << dist[dst-1] << endl;
return 0;
}最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
样例输入
5
0 1005 6963 392 1182
1005 0 1599 4213 1451
6963 1599 0 9780 2789
392 4213 9780 0 5236
1182 1451 2789 5236 0
样例输出
4178
Prim算法
#include <vector>
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
void Prim(vector<int>& dist,vector<vector<int>>& graph,int& sum)
{
int vex = graph.size();
while (1)
{
int idx = -1;
int dis = INT_MAX;
for (int i=0;i<vex;i++)
{
if(dist[i] != 0)
{
if(dist[i] < dis)
{
dis = dist[i];
idx = i;
}
}
}
if(dis == INT_MAX)
break;
sum += dis;
dist[idx] = 0;
for(int i=0;i<vex;i++)
{
if(dist[i] != 0 && graph[i][idx] < INT_MAX)
{
if(dist[i] > graph[idx][i])
{
dist[i] = graph[idx][i];
}
}
}
}
}
int main()
{
int vex;
cin >> vex;
vector<vector<int>> graph(vex,vector<int>(vex,0));
for(int i=0;i<vex;i++)
for(int j=0;j<vex;j++)
{
int a;
cin >> a;
graph[i][j] = a;
}
vector<int> dist(vex,INT_MAX);
dist[0] = 0;
for(int i=1;i<vex;i++)
{
dist[i] = graph[i][0];
}
int min_sum = 0;
Prim(dist,graph,min_sum);
cout << min_sum << endl;
return 0;
}随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。
所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行，每行描述一条路线，其中第i行为3个整数N1_i, N2_i, V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1_i, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
样例输入
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185
样例输出
92
Kruscal算法
#include <vector>
#include <iostream>
#include <fstream>
#include <limits.h>
#include <algorithm>
using namespace std;
struct edge
{
int begin;
int end;
int weight;
edge(int b,int e,int w):begin(b),end(e),weight(w){}
};
inline bool cmp(const edge& e1,const edge& e2)
{
return e1.weight > e2.weight;
}
int findRoot(int idx,const vector<int>& path)
{
while(path[idx] != idx)
{
idx = path[idx];
}
return idx;
}
void Kruscal(vector<edge>& graph,int& sum,const int& v)
{
int e = graph.size();
int cnt = 0;
//根据权值weight建立最小堆,建立堆时间复杂度O(e)
make_heap(graph.begin(),graph.end(),cmp);
vector<int> path(v,0);
for (int i=0;i<v;i++)
{
path[i] = i;
}
//循环时间复杂度O(eloge)
while(cnt < v-1 && !graph.empty())
{
edge tmp = graph[0];
int m = tmp.begin;
int n = tmp.end;
//从堆中删除最小边
pop_heap(graph.begin(),graph.end(),cmp);
graph.pop_back();
if(findRoot(m,path) != findRoot(n,path))
{
path[m] = n;
sum += tmp.weight;
++cnt;
}
}
return;
}
int main()
{
int N,M;
cin >> N >> M;
vector<vector<int>> graph(N,vector<int>(N,INT_MAX));
for(int i=0;i<M;i++)
{
int a,b,w;
cin >> a >> b >> w;
graph[a-1][b-1] = min(graph[a-1][b-1],w);
}
vector<edge> edges;
for (int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
if(graph[i][j] < INT_MAX)
{
edges.push_back(edge(i,j,graph[i][j]));
}
}
}
int res = 0;
Kruscal(edges,res,N);
cout << res << endl;
return 0;
}