leetcode并查集、拓扑排序两题
685. 冗余连接 II
在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。
返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
题解
这个题挺难的。
最后具体分为几种情况:
有冲突,无环。要把最后的冲突边记录一下,最后返回冲突边。
有环,无冲突。记录最后的成环的边,最后返回。
有冲突,有环。说明冲突边的终点结点1还是在环里的,此时,要把1和它的父亲结点这条边去掉,既要去环,也要去冲突。
class Solution {
private int[] father;
private int getFather(int k) {
while(father[k]!=k) {
//father[k]
k = father[k];
}
return father[k];
}
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
father = new int[n+1];
for(int i=1;i<=n;i++) {
father[i] = i;
}
int conflict = -1;
int circle = -1;
for(int i=0;i<n;i++) {
int u = edges[i][0];
int v = edges[i][1];
if(father[v]!=v) {
//表示已经有父亲了,又来一个父亲,不行
conflict = i;
continue;
} else if(getFather(u)==getFather(v)) {
// 排除一个人两个父亲的情况之后,父亲还相等,那就是环了
circle = i;
continue;
}
father[v] = u;
}
if(circle==-1) {
return edges[conflict];
}
if(conflict==-1) {
return edges[circle];
}
return new int[]{father[edges[conflict][1]],edges[conflict][1]};
}
}
1591. 奇怪的打印机 II
给你一个奇怪的打印机,它有如下两个特殊的打印规则:
每一次操作时,打印机会用同一种颜色打印一个矩形的形状,每次打印会覆盖矩形对应格子里原本的颜色。
一旦矩形根据上面的规则使用了一种颜色,那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 m x n
的矩形 targetGrid ,其中 targetGrid[row][col]
是位置 (row, col) 的颜色。
如果你能按照上述规则打印出矩形 targetGrid ,请你返回 true ,否则返回 false 。
提示:
m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60
本来想用个取巧的方法,结果顺序不一定是从1到60。
这种也被认为是对的,没考虑到。
错误答案
class Solution {
public boolean isPrintable(int[][] targetGrid) {
// 主要是两点:1 相同颜色不能再被使用,也就是例如找3,
// 一次得把3全部找出来,判断能不能涂成一个矩形(没被三占的地方要比3大)
// 2 新颜色会覆盖旧颜色,所以还是上面那个说法
int top;
int bottom;
int left;
int right;
for(int k=1;k<=60;k++) {
top = targetGrid.length;
bottom = -1;
left = targetGrid[0].length;
right = -1;
for(int i=0;i<targetGrid.length;i++) {
for(int j=0;j<targetGrid[0].length;j++) {
if(targetGrid[i][j]==k) {
top = Math.min(i,top);
bottom = Math.max(i,bottom);
left = Math.min(j,left);
right = Math.max(j,right);
}
}
}
for(int i=top;i<=bottom;i++) {
for(int j=left;j<=right;j++) {
if(targetGrid[i][j]<k) {
return false;
}
}
}
}
return true;
}
}
拓扑排序
class Solution {
public boolean isPrintable(int[][] targetGrid) {
// 主要是两点:1 相同颜色不能再被使用,也就是例如找3,
// 一次得把3全部找出来,判断能不能涂成一个矩形(没被三占的地方要比3大)
// 2 新颜色会覆盖旧颜色,所以还是上面那个说法
int top;
int bottom;
int left;
int right;
int[] indegree = new int[61];
List<List<Integer>> out = new ArrayList<>();
for(int k=0;k<=60;k++) {
out.add(new ArrayList<>());
}
for(int k=1;k<=60;k++) {
top = targetGrid.length;
bottom = -1;
left = targetGrid[0].length;
right = -1;
// 找到当前k的区域矩形
for(int i=0;i<targetGrid.length;i++) {
for(int j=0;j<targetGrid[0].length;j++) {
if(targetGrid[i][j]==k) {
top = Math.min(i,top);
bottom = Math.max(i,bottom);
left = Math.min(j,left);
right = Math.max(j,right);
}
}
}
for(int i=top;i<=bottom;i++) {
for(int j=left;j<=right;j++) {
if(targetGrid[i][j]!=k) {
indegree[targetGrid[i][j]]++;
out.get(k).add(targetGrid[i][j]);
}
}
}
}
Deque<Integer> deque = new LinkedList<>();
Set<Integer> alreadyPaint = new HashSet<>();
for(int k=1;k<=60;k++) {
if(indegree[k]==0) {
deque.addLast(k);
}
}
while(!deque.isEmpty()) {
int cur = deque.pollFirst();
alreadyPaint.add(cur);
for(int o:out.get(cur)) {
indegree[o]--;
if(indegree[o]==0) {
deque.addLast(o);
}
}
}
return alreadyPaint.size()==60;
}
}