检查图形是否存在（java）

debugcn 发表于 Dev

安娜

确定是否存在具有顶点度数序列 (s = s1, s2...sn) 的图。解决此问题的最佳和最优化算法是什么。

 Input:
    the first line contains `t<100` - amount of sequnces.
    the second line contains value `n <= 1000000`(length of a sequence).
    the third line contains  contains `n` non-negative integer numbers. And so on.
Output:
    if the graph can exist print "yes" otherwise print "no".
For example: 
Input:
3
5
1 2 3 2 1
4
3 3 2 2
3
1 3 2
Output:
No
Yes
Yes

最大执行时间应为 0.4 秒。这是我的代码（如果奇数顶点的数量是偶数，则该图存在）：

    import java.util.Scanner;
public class Main {
      public static final Scanner in = new Scanner(System.in);
    public static void isGraph (int []a, int n) {
        int k=0;
        for(int i=0; i< n; i++) {
            if(a[i] %2 != 0) {
                k++;
            }
        }
        if(k%2 == 0)
           System.out.println("Yes");
        else
            System.out.println("No");

    }
    public static void main(String[] args) throws Exception{
        double t1 = System.nanoTime();
        int n;
        int []a;
        int t = Integer.parseInt(in.nextLine());
        while(t-- > 0) {
            n = in.nextInt();
            a = new int[n];
            for(int i=0; i<n; i++)
                a[i] = in.nextInt();
            isGraph(a,n);
        }
        System.out.println(System.nanoTime() - t1);
    }
}

但是这个程序的执行时间超过了0.4秒。我超出了运行时间。我如何优化代码并加快运行速度。可能有另一种算法可以解决此任务，请帮助我。

伊恩·麦克

我想我有一个更快的方法给你。请验证这一点。如果您担心偶数/奇数的最终结果，那么似乎没有理由跟踪 k 计数器。您可以保留运行序列是偶数还是奇数的动态值：

public static void isGraph (int []a, int n) {
    int k = 0;
    for(int i=0; i< n; i++) {
        k += a[i] & 1;
    }
    if(k%2 == 0)
        System.out.println("Yes");
    else
        System.out.println("No");

}

这可能对您的阅读有所帮助：但是，我没有这方面的经验，我是从竞赛网站上获得的：

慢读方法：

/** Read count integers using Scanner */
static int scanInteger(int count) {
    Scanner scanner = new Scanner(input);
    int last = 0;
    while (count-- > 0) {
        last = scanner.nextInt();
    }
    return last;
 }

更快的方法：

static int readIntegers(int count) 
    throws IOException {
    BufferedReader reader = new BufferedReader(
           new InputStreamReader(input) );
    StringTokenizer tokenizer = new StringTokenizer("");
    int last = 0;
    while (count-- > 0) {
        if (! tokenizer.hasMoreTokens() ) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        last = Integer.parseInt(tokenizer.nextToken());
    }
    return last;
}

编辑：展示如何避免两个阶段，其中阶段 1 是读取循环，阶段 2 是算法：

public static void main(String[] args) throws Exception{
    double t1 = System.nanoTime();
    int n;
    // int []a;  //  Not necessary
    int t = Integer.parseInt(in.nextLine());
    while(t-- > 0) {
        n = in.nextInt();
        // a = new int[n];  // Not necessary
        int k = 0;
        int a;
        for(int i=0; i<n; i++) {
            a = in.nextInt();
            k += a & 1;
        }
        // isGraph(a,n);  // Not necessary
        if(k % 2 == 0)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
    System.out.println(System.nanoTime() - t1);
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。