目录

题目1 使数组中所有元素都等于零

思路

代码

题目2 分组的最大数量

思路

代码

题目3 找到离给定两个节点最近的节点

思路

代码

题目4 图中的最长环

思路

代码

题目1 使数组中所有元素都等于零

思路

 这个题目的思路非常简单和清晰，但我一开始理解有一些问题，直接用一个set记录不同的数字的个数即可。

代码

class Solution {
    public int minimumOperations(int[] nums) {
        Set st = new HashSet<>();
        for(int num:nums){
            if(num!=0){
                st.add(num);
            }
        }
        return st.size();
    }
}

题目2 分组的最大数量

思路

一开始没有思路，其实这题的思路就是贪心，因为一旦数组排好序，以1，2，3的大小去组成这样的分组就可以符合题目的要求，剩下的不足分组可以直接加到最后一组。

代码

class Solution {
    public int maximumGroups(int[] grades) {
        //Arrays.sort(grades);
        int n = grades.length;
        int i = 1;
        int count = 0;
        while(n>=i){
            n-=i;
            i++;
            count++;
        }
        return count;
    }
}

题目3 找到离给定两个节点最近的节点

思路

一开始思路是从两个节点然后去找一个交汇的点，但是这样找的话两个节点的移动速度不一样，不是很好实现，这个思路不对。

解题思路就是和题目类似的，维护两个数组

d1记录node1到各个节点的距离  初始化为最大值

d2记录node2到各个节点的距离  初始化为最大值

遍历所有的节点0<=i

特殊情况是 

1->2  2->1  这种成环的图可能返回的不是唯一答案

代码

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        //d1记录node1到各个节点的距离  初始化为最大值
        //d2记录node2到各个节点的距离  初始化为最大值
        int n = edges.length;
        int[] d1 = new int[n];
        int[] d2 = new int[n];
        for(int i=0;i
            d1[i] = n;
            d2[i] = n;
        }
        bfs(d1,node1,edges);
        bfs(d2,node2,edges);
        int ans = n;
        int node = -1;
        for(int i=0;i
            if(Math.max(d1[i],d2[i])
                ans = Math.max(d1[i],d2[i]);
                node = i;
            }
        }
        return node;
    }
    private void bfs(int[] d,int node,int[] edges){
        int n = edges.length;
        for(int i=0;node>=0 && d[node]==n;node = edges[node]){  //node>=0没有越界 而且 d[node]==n没有访问过
            d[node] = i++;
        }
    }
}

题目4 图中的最长环

思路

方法一 dfs直接遍历

方法二  拓扑排序 找到不在环内的直接用vis标记，不用再用新的数组

代码

方法一 自己写的dfs 总觉得有一些细节没想明白

class Solution {
    int res = -1;
    int[] vis;
    int[] cnts;
    public int longestCycle(int[] edges) {
        int n = edges.length;
        vis = new int[n];
        cnts = new int[n];
        for(int i=0;i
            dfs(i,edges,0);
        }
        return res;
    }
    public boolean dfs(int i,int[] edges,int cnt){
        if(vis[i]==1){
            res = Math.max(res,cnt-cnts[i]);
            return false;
        }
        if(vis[i]==-1) return true;
        vis[i] = 1;
        cnts[i] = cnt;
        if(edges[i]!=-1){
            if(!dfs(edges[i],edges,cnt+1)) return false;
        }
        vis[i] = -1;
        return true;
    }
    
    
}

方法二

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int[] inDegree = new int[n]; //入度表
        for(int i=0;i
            if(edges[i]!=-1)
                inDegree[edges[i]]++;   
        }
        Deque q = new ArrayDeque<>();
        for(int i=0;i
            if(inDegree[i]==0){
                q.offer(i);
            }
        }
        boolean[] vis = new boolean[n];  
        int cnt = 0;
        while(!q.isEmpty()){
            int cur = q.poll();
            cnt++;
            vis[cur] = true;
            if(edges[cur]!=-1){
                int nxt = edges[cur];
                inDegree[nxt]--;
                if(inDegree[nxt]==0) q.offer(nxt);
            }
        }
        //如何快速判断有无环
        if(cnt==n) return -1;
        
        int ans = -1;
        for(int i=0;i
            if(!vis[i] ){
                ans = Math.max(ans,bfs(i,edges,vis));
            }
        }
        return ans;
    }
    private int bfs(int node,int[] edges,boolean[] vis){
        int len = 0;
        while(node>=0 && !vis[node]){
            vis[node] = true;
            node = edges[node];
            len++;
        }
        return len;
    }
}

方法三  记录访问时间法

利用时间戳找环

代码

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        int clk = 1;  //全局访问时间
        int ans = -1;
        int[] time = new int[n];
        for(int i=0;i
            if(time[i]>0) continue;
            int start_time = clk;
            for(int node = i;node>=0;node=edges[node]){
                if(time[node]>0){
                    if(time[node]>=start_time){
                        ans = Math.max(ans,clk-time[node]);
                    }
                    break;
                }
                time[node] = clk++;
            }
 
        }
        return ans;
    }
}