Twitter OA March 19

Twitter 最近在下 OA 雨刚刚做完，共两题：

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求过啊。

写了一下第一题，代码有点丑 主要思路就是求出所有质因数，统计各个质因数的个数，再求出他们的最大公约数，。如果最大公约数是1就返回false，这里有加入负数的考虑情况。

1.     public static boolean sqrtpq(int n) {
   
2.         if (n == 1 || n == 0)
   
3.             return true;
   
4.         int flag = 0;
   
5.         if(n < 0) {
   
6.             flag = 1;
   
7.             n = -n;
   
8.         }
   
9.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   
10.         ArrayList<Integer> list = new ArrayList<Integer>();
    
11.         int cnt = 0;
    
12.         while(n % 2 == 0) {
    
13.             cnt++;
    
14.             n = n / 2;
    
15.         }
    
16.         if(cnt != 0)
    
17.             map.put(2, cnt);
    
18.         int i = 3;
    
19.         while(n != 1){
    
20.             cnt = 0;
    
21.             while(n % i == 0) {
    
22.                 cnt++;
    
23.                 n = n / i;
    
24.             }
    
25.             if(cnt != 0)
    
26.                 map.put(i,cnt);
    
27.             i += 2;
    
28.         }
    
29.         for(Integer key : map.keySet()) {
    
30.             list.add(map.get(key));
    
31.         }
    
32.         int gcd = ngcd(list, list.size());
    
33.         
    
34.         if(gcd == 1)
    
35.             return false;
    
36.         if(flag == 0)
    
37.             return true;
    
38.         
    
39.         gcd = gcd - 1;
    
40.         while((gcd & 1) == 1) {
    
41.             gcd >>= 1;
    
42.         }
    
43.         if (gcd== 0)
    
44.             return false;
    
45.         else
    
46.             return true;
    
47.          
    
48.     }

复制代码

海盗包子 发表于 2016-3-24 09:22
写了一下第一题，代码有点丑 主要思路就是求出所有质因数，统计各个质因数的个数，再求出他们的最 ...

1. public class Solution {
   
2.   static int gcd(int a, int b) {
   
3.     if (a == 0 || b == 0)
   
4.       return a + b;
   
5.     return gcd(b, a % b);
   
6.   }
   
7. 
   
8.   static boolean pq(int a) {
   
9.     if (a == 0 || a == 1)
   
10.       return true;
    
11.     Map<Integer, Integer> m = new HashMap<>();
    
12.     for (int i = 2; i <= a; i++) {
    
13.       if (a % i == 0) {
    
14.         int count = 0;
    
15.         while (a % i == 0) {
    
16.           count++;
    
17.           a /= i;
    
18.         }
    
19.         m.put(i, count);
    
20.       }
    
21.     }
    
22.     List<Integer> l = m.values().stream().collect(Collectors.toList());
    
23.     int g = l.get(0);
    
24.     for (Integer i : l) {
    
25.       g = gcd(g, i);
    
26.     }
    
27.     return g != 1;
    
28.   }
    
29. 
    
30.   public static void main(String[] args) {
    
31.     System.out.println(pq(144));
    
32.   }
    
33. }
    

复制代码

海盗包子 发表于 2016-3-24 09:22
写了一下第一题，代码有点丑 主要思路就是求出所有质因数，统计各个质因数的个数，再求出他们的最 ...

ngcd是自己写的求gcd的函数吗

求问，Game of Thrones 求的是是否为palindrome 还是 palindrome anagram的个数？

duoduo33 发表于 2016-3-20 09:46
求问，Game of Thrones 求的是是否为palindrome 还是 palindrome anagram的个数？

没问个数。只问是否

请问第一题，楼主也是用 sqrt() 下去解吗？

xoxoxoxooxoxoxo 发表于 2016-3-20 09:51
请问第一题，楼主也是用 sqrt() 下去解吗？

没太清楚你意思

请问楼主OA是可以一个小时内提交多次嘛？提交次数会不会对结果有影响呢？

请问楼主 第一题的思路是神马

xoxoxoxooxoxoxo 发表于 2016-3-20 09:51
请问第一题，楼主也是用 sqrt() 下去解吗？

找出所有的质数因子，
看质数个数能不能都除以二，三。。。

请问楼主 第一题有负数的情况吗