|
目录
题目1?使数组中所有元素都等于零
思路
代码
题目2?分组的最大数量
思路
代码
题目3?找到离给定两个节点最近的节点
思路
代码
题目4?图中的最长环
思路
代码
思路
?这个题目的思路非常简单和清晰，但我一开始理解有一些问题，直接用一个set记录不同的数字的个数即可。
代码
class Solution {
public int minimumOperations(int[] nums) {
Set<Integer> st = new HashSet<>();
for(int num:nums){
if(num!=0){
st.add(num);
}
}
return st.size();
}
}
思路
一开始没有思路，其实这题的思路就是贪心，因为一旦数组排好序，以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;
}
}
思路
一开始思路是从两个节点然后去找一个交汇的点，但是这样找的话两个节点的移动速度不一样，不是很好实现，这个思路不对。
解题思路就是和题目类似的，维护两个数组
d1记录node1到各个节点的距离??初始化为最大值
d2记录node2到各个节点的距离??初始化为最大值
遍历所有的节点0<=i<n，按照题目要求 max(d1[i],d2[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<n;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<n;i++){
if(Math.max(d1[i],d2[i])<ans){
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++;
}
}
}
思路
方法一 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<n;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<n;i++){
if(edges[i]!=-1)
inDegree[edges[i]]++;
}
Deque<Integer> q = new ArrayDeque<>();
for(int i=0;i<n;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<n;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<n;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;
}
}
|