网易2018校招笔试题-数组能不能满足重排列后任意相邻的元素积都是4的倍数

Java基础

浏览数:4

2019-9-11

    今天看了一下网易最新的校招笔试题:

    小易有一个长度为N的正整数数列A = {A[1], A[2], A[3]…, A[N]}。牛博士给小易出了一个难题:
     对数列A进行重新排列,使数列A满足所有的A[i] * A[i + 1](1 ≤ i ≤ N – 1)都是4的倍数。
     小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。

代码如下:

 1 import java.util.Scanner;
 2 
 3 /**
 4  * Created by jy on 2017/9/9.
 5  */
 6 public class fourBeiShu {
 7     public static boolean isRequired(int length, int[] a) {
 8         int jiShu = 0;
 9         int four = 0;
10         int ouShu = 0;
11         for (int i = 0; i <= length - 1; i++) {
12             //不符合要求
13             if (a[i] <= 0) {
14                 return false;
15             }
16             //奇数个数
17             if (a[i] % 2 == 1) {
18                 jiShu++;
19             }
20             //只是二的倍数个数
21             if (a[i] % 2 == 0 && a[i] % 4 != 0) {
22                 ouShu++;
23             }
24             //4的倍数
25             if (a[i] % 4 == 0) {
26                 four++;
27 
28             }
29         }
30         //4的倍数大于数组长度的一半-1,可以满足a[i]和a[i+1]中必定有一个是4的倍数,这样漏掉了全是偶数的情况,如2 2 6
31         if (four >= length - four - 1) {
32             return true;
33         }
34         //4的倍数的个数必须大于等于奇数个数(如果有奇数的话),同时,偶数个数必须至少2个,1 3 5 4 4 4 2 2 2 2 2 2 2 2 2
35         if ((four >= jiShu) && (ouShu >= 2)) {
36             return true;
37         }
38 
39         return false;
40     }
41 
42     public static void main(String[] args) {
43         Scanner in = new Scanner(System.in);
44         int num = in.nextInt();
45         int n;
46         int[] a;
47         for (int i = 0; i < num; i++) {
48             n = in.nextInt();
49             a = new int[n];
50             for (int j = 0; j < n; j++) {
51                 a[j] = in.nextInt();
52             }
53             boolean b = isRequired(n, a);
54             if (b) {
55                 System.out.println("Yes");
56             } else {
57                 System.out.println("No");
58             }
59         }
60     }
61 }

 

作者:jy的blog