头像

梦想黑洞




在线 



梦想黑洞
24分钟前
    private static int spfa(){
        Arrays.fill(d,0x3f3f3f3f);
        d[1]=0;
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        vis[1]=true;
        while(!q.isEmpty()){
            // 取出队头结点,取出来的标记为false
            int t=q.poll();
            vis[t] = false;
            // 遍历以当前节点为初始结点可以到达的结点,更新距离
            // 因为当前节点是从队列中取出的,队列中的结点距离都是减少的,所以以它为初始结点的结点的距离也会减少,所以还应该更新这些节点的距离
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                if(d[j]>d[t]+w[i]){//这个判断语句为啥不能直接删掉呢?结点t是距离减少的点,那他可以扩展的结点的距离不是一定会减少吗???
                    d[j]=d[t]+w[i];
                    if(vis[j]==false){
                        vis[j]=true;
                        q.add(j);
                    }
                }
            }
        }
        return d[n];
    }




1.只有有向图才有拓扑序列,拓扑序列可以不唯一。
2.入度为0的结点作为拓扑序列的起始节点,其他节点遍历到的时候入度自减,直至减至0,才将此节点加入拓扑序列。


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
class Main{
    static int N=100010;
    static int M=2*N;
    static int idx=0;
    static int[] h=new int[N];
    static int[] e=new int[M];
    static int[] ne=new int[M];
    static int[] q=new int[N];
    static int[] d=new int[N];//记录每个节点的入度
    static int n;
    public static void main(String[] args) throws IOException{
        Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
        n=in.nextInt();
        int m=in.nextInt();
        Arrays.fill(h,-1);
        // 建立有向图的邻接表
        for(int i=0;i<m;i++){
            int a=in.nextInt();
            int b=in.nextInt();
            add(a,b);
            // 建立一条边,更新一次节点b的入度
            d[b]++;
        }
        // 如果有拓扑序列,输出拓扑序列,没有的话输出-1.
        if(topSort()){
            for(int i=0;i<n;i++){
                out.write(q[i]+" ");
            }
        }else{
            out.write("-1");
        }
        out.flush();
    }

    private static boolean topSort(){
        int hh=0;
        int tt=-1;
        // 将入度为0的结点全部插入队列,入度为0的结点可以作为起始节点。
        for(int i=1;i<=n;i++){
            if(d[i]==0){
                q[++tt]=i;
                // break;
            }
        }
        // 当队列不空时
        while(hh<=tt){
            // 取出队头结点,并删除
            int t=q[hh++];
            // 遍历队头结点可以到达的结点
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                // 入度自减
                d[j]--;
                // 如果入度减到了0,则可以作为之后结点的起始节点,将此节点插入到队列中
                if(d[j]==0){
                    q[++tt]=j;
                }
            }
        }
        // 队列数组的下标是从0到n-1
        // 如果队列尾节点的下标是n-1,说明全部遍历了一遍,有拓扑序列,否则没有返回false
        return tt==n-1;
    }

    private static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}


活动打卡代码 AcWing 847. 图中点的层次

数组模拟队列进行bfs求距离

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
class Main{
    static int N=100010;
    static int M=2*N;
    static int idx=0;
    static int[] h=new int[N];
    static int[] e=new int[M];
    static int[] ne=new int[M];
    static int[] q=new int[N];
    static int[] d=new int[N];
    static int n;
    public static void main(String[] args) throws IOException{
        Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
        n=in.nextInt();
        int m=in.nextInt();
        // 这里要在add之前把h数组都初始化成-1
        Arrays.fill(h,-1);
        for(int i=0;i<m;i++){
            int a=in.nextInt();
            int b=in.nextInt();
            add(a,b);
        }
        out.write(bfs()+"");
        out.flush();
    }

    private static int bfs(){
        int hh=0;
        int tt=0;
        // 将存储距离的数组也初始化成-1
        Arrays.fill(d,-1);
        // 目前模拟的队列中只有一个节点1
        q[0]=1;
        // 节点1到节点1的距离是0
        d[1]=0;
        // bfs模板
        // 当队列不为空时:
        while(hh<=tt){
            // 取出队头元素并删除
            int t=q[hh++];
            // 遍历可以扩展的结点
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                // 如果当前节点没有遍历过,更新当前节点到节点1的距离并插入到队列中
                if(d[j]==-1){
                    d[j]=d[t]+1;
                    q[++tt]=j;
                }
            }
        }

        return d[n];
    }

    private static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // pre是当前节点的前驱节点,初始值为null
        ListNode pre=null;

        // 从头结点开始遍历链表
        while(head!=null){
            ListNode t=head.next;

            //当前节点的next指向前驱节点(当前节点是头结点时,他的next指向null)
            head.next=pre;

            //遍历下一个节点时,将pre置为当前节点
            pre=head;

            //当前节点接着向后遍历
            // 注:不能直接写成head=head.next,因为head.next的值已经改变了,所以需要在刚开始循环的时候用临时变量存储起来。
            head=t;

        }
        return pre;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 下面注释中:连续重复的节点是一段
    public ListNode deleteDuplication(ListNode head) {
       ListNode dummy=new ListNode(1);
       dummy.next=head;

    // 设置虚拟头结点的意义在于边界结点的判断
       ListNode l=dummy;
       ListNode r;
       while(l.next!=null){
           r=l.next;
        // l指针指向上一段的最后一个节点,r指针最终指向下一段的第一个节点
           while(r!=null && l.next.val==r.val) r=r.next;

           if(l.next.next==r){  //当前段长度为1
              l=l.next; 
           }else{               //当前段长度大于1
               l.next=r;
           }
       }
       return dummy.next;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode findKthToTail(ListNode h, int k) {
        //h是链表头结点
        ListNode t=h;
        // n记录链表长度
        int n=0;
        while(t!=null){
            n++;
            t=t.next;
        }
        // 如果k大于链表长度,则返回null
        if(k>n) return null;
        // 否则返回从前往后数第n-k+1个结点
        int res=n-k+1;
        t=h;
        while(--res>0){
            t=t.next;
        }
        return t;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 只写出这个方法即可,不用写输入输出。
    // 常规方法:通过前驱结点的next指针来删除当前节点,但是题目中没给出。(不选)
    // 取巧点:将“删除当前节点” 转换成 “删除当前节点的next结点”,
    //         这样就不会用到当前节点的前驱节点的next指针,而会用到当前节点的next指针。
    public void deleteNode(ListNode node) {
        // 将当前节点的next结点的值赋给当前节点,这样“删除当前节点的next结点”就等效于“删除当前节点”。
        node.val=node.next.val;
        // 删除当前节点的next结点。
        node.next=node.next.next;
    }
}






1.试除法 O(sqrt(num))
2.质数(素数)的判定:
条件一:.大于1的自然数
条件二:.因子只有1和它本身。

package ch04;

import java.util.Scanner;

public class T866_Prime {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=0;
        while(n-->0) {
            m=in.nextInt();
            if (isPrime(m)) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }

    private static boolean isPrime(int num) {

        if (num<2) {
            return false;
        }
//      因为num的质因子总是成对出现的,所以只需要枚举两个成对出现中较小的质因子即可。
//      最好不要这样写终止条件:1.i<=sqrt(num) (调用sqrt方法慢)  2.i*i<=num  (i如果是一个大数的话,容易溢出)
//      最好写成:i<=num/i。
        for (int i = 2; i <=num/i;i++) {
            if (num%i==0) {
                return false;
            }
        }
        return true;
    }
}



活动打卡代码 AcWing 867. 分解质因数

试除法 O(sqrt(num))

package ch04;

import java.util.Scanner;

public class T867_SolvePrime {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=0;
        while(n-->0) {
            m=in.nextInt();
            solvePrime(m);
        }
    }


    private static void solvePrime(int num) {
        if (num<2) {
            System.out.println();
            return;
        }
        int cnt=0;
//      知识点:num至少包含一个大于sqrt(n)的质因子。所以可以先枚举1-sqrt(num)的因子,最后判断是否有大于sqrt(num)的质因子。
        for (int i = 2; i <=num/i; i++) {
//          输出的i一定是质数,不会是合数
//          因为num已经不包含2~(i-1)的质因子,所以i也不包含2~(i-1)的质因子,否则不能整除,所以i是质数。
            if (num%i==0) {
//              记录目前质因子的个数。
                cnt=0;
                while(num%i==0) {
                    num/=i;
                    cnt++;
                }
                System.out.println(i+" "+cnt);
            }

        }
//      如果试除之后的数大于1,则将大于sqrt(num)的质因子输出。
        if (num>1) {
            System.out.println(num+" 1");
        }
        System.out.println();
    }
}