给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
示例 1
输入：grid = [[“a”,“a”,“a”,“a”],[“a”,“b”,“b”,“a”],[“a”,“b”,“b”,“a”],[“a”,“a”,“a”,“a”]]
输出：true
示例 2：
输入：grid = [[“c”,“c”,“c”,“a”],[“c”,“d”,“c”,“c”],[“c”,“c”,“e”,“c”],[“f”,“c”,“c”,“c”]]
输出：true
示例 3
输入：grid = [[“a”,“b”,“b”],[“b”,“z”,“b”],[“b”,“b”,“a”]]
输出：false
提示：
m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。
判断环就是判断连通性，利用并查集处理是最简单的方法。我们需要遍历矩阵然后往两个方向搜索，左和右。
这样做的理由是在遍历矩阵的过程中会不会往回走，而我们最后判断环的地方其实就是某个环在矩阵中右下角左边那个点和右下角那个点union的时候发现他们其实是在一个集合中，这样肯定就是一个环了。在union的时候推荐吧格子的坐标转换为1维，这样比较好处理，而转换的方法也很简单：行坐标×列数+列坐标即可。
class Solution {
#define maxn 250005
int fa[maxn];
int row,col;
int dir[2][2]={{0,1},{1,0}};
void init(){
for(int i=0;i<maxn;++i){
fa[i]=i;
}
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int union_( int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
fa[fx]=fy;
return 1;
}
return 0;//返回0代表二者已经在一个集合中，1代表将二者union到一起了
}
public:
bool containsCycle(vector<vector<char>>& grid) {
init();
row=grid.size();
col=grid[0].size();
for(int i=0;i<row;++i){
for(int j=0;j<col;++j){
for(int k=0;k<2;++k){
int ti=i+dir[k][0];
int tj=j+dir[k][1];
if(ti==row||tj==col){
continue;
}
int a=i*col+j;
int b=ti*col+tj;
if(grid[i][j]==grid[ti][tj]){
if(!union_(a,b)){
return true;
}
}
}
}
}
return false;
}
};
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意：你 不能 变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。
示例 1：
输入：grid = [[2,4,3],[6,5,2]]
输出：true
示例 2：
输入：grid = [[1,2,1],[1,2,1]]
输出：false
示例 3：
输入：grid = [[1,1,2]]
输出：false
示例 4：
输入：grid = [[1,1,1,1,1,1,3]]
输出：true
示例 5：
输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
这道题就比较简单了，首先打个表，先把方向数组dir定义好，然后定义一个数组data[i][j][k]代表编号为 i 的格子在 j 这个方向连通的编号k。为了与编号对应，这里 i定义为7，0的时候全部设置为非法即可。而观察方向我们可以知道每个编号可以在两个方向与其他编号连通，比如编号 1，它可以在左方向与1 ，3 ，5这三个编号连通，在右方向可以与1，4，6连通。那么在打表的时候注意j要和方向数组的方向一致。
打过表后就简单了，遍历矩阵将每个格子与周围四个格子进行union操作，最后观察[0,0],[row-1,col-1]是否连通即可。
class Solution {
#define maxn 250005
int fa[maxn];
void init(){
for(int i=0;i<maxn;++i){
fa[i]=i;
}
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int union_(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
fa[fx]=fy;
return 1;
}
return 0;
}
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int data[7][4][3]={
{{-1,-1,-1,},{-1,-1,-1,},{-1,-1,-1,},{-1,-1,-1,}},
{{-1,-1,-1,},{1,3,5},{-1,-1,-1,},{1,4,6}},
{{2,3,4},{-1,-1,-1,},{2,5,6},{-1,-1,-1,}},
{{-1,-1,-1,},{-1,-1,-1,},{2,5,6},{1,4,6}},
{{-1,-1,-1,},{1,3,5},{2,5,6},{-1,-1,-1,}},
{{2,3,4},{-1,-1,-1,},{-1,-1,-1,},{1,4,6}},
{{2,3,4},{1,3,5},{-1,-1,-1,},{-1,-1,-1,}}
};
public:
bool hasValidPath(vector<vector<int>>& grid) {
int i,j,k;
int m=grid.size();
int n=grid[0].size();
init();
for(i=0;i<m;++i){
for(j=0;j<n;++j){
for(k=0;k<4;++k){
int ti=i+dir[k][0];
int tj=j+dir[k][1];
if(ti==-1||tj==-1||ti==m||tj==n){
continue;
}
int a=i*n+j;
int b=ti*n+tj;
int ag=grid[i][j];
int bg=grid[ti][tj];
if(data[ag][k][0]==bg||data[ag][k][1]==bg||data[ag][k][2]==bg){
union_(a,b);
}
}
}
}
return find(0)==find(m*n-1) ;
}
};
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = “dcab”, pairs = [[0,3],[1,2]]
输出：“bacd”
示例 2：
输入：s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
输出：“abcd”
示例 3：
输入：s = “cba”, pairs = [[0,1],[1,2]]
输出：“abc”
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母
更为简单的一题，我们读过题后就发现这道题就是典型的找朋友类型的题目，我们把可以交换顺序的位置成为朋友，那么自然朋友的朋友在这道题中也是朋友，那么我们就可以把他们放到一个集合中。（比如[0,1],[1,2]我们可以先让0，1交换再让1，2交换，最后再把0，1交换这样就相当于把原来的0，2交换而1不变)。
而一旦确定了某个下标存在的集合我们就可以找到该集合的所有元素代表的字母，再把他们放到一个数组中，按照字典序排序，最后按照下标顺序把排序好的字母放入其中即可。
这里还是有些地方需要解释的的：
首先就是这样做就需要把每个集合中的每个元素的下标和字母都记录下来。字母不用多说，我们需要的只是他们的字典序，而下标我们自然想要一个升序序列，这在遍历的过程中，自然而然的就做到了，因为我们这里是先根据pair的数据进行union操作，在我们遍历s的时候所有集合以及他们的代表元素（也就是集合编号）已经确定了，这样在遍历的过程中我们只需要利用find找到每个下标的组数再把下标和字母放到对应的位置即可，这里下标天然的就是升序序列。
class Solution {
#define maxn 100005
int fa[maxn];
void init(){
for(int i=0;i<maxn;++i){
fa[i]=i;
}
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int union_(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
fa[fx]=fy;
return 1;
}
return 0;
}
vector<int> groupchar[maxn],groupidx[maxn];
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
init();
for(int i=0;i<pairs.size();++i){
union_(pairs[i][0],pairs[i][1]);
}
for(int i=0;i<s.size();++i){
int group=find(i);
groupidx[group].push_back(i);
groupchar[group].push_back(s[i]);
}
for(int i=0;i<s.size();++i){
sort(groupchar[i].begin(),groupchar[i].end(),[&](const int & a,const int & b){
return a<b;
});
for(int j=0;j<groupchar[i].size();++j){
s[groupchidx[i][j]]=groupchar[i][j];
}
}
return s;
};