人寿研发笔试第三题

划分机器人家族
整体思路——贪心算法

一个家族区间[l,r]合法的条件：所有相邻两数差的绝对值的gcd（最大公约数）不等于1，且区间内没有重复的元素

题目让求划分家族的最少数量，因此先明确需要新增家族的几种情况：
需要新增家族的三种情况：

1. 相邻的两个数差为0或1是不行的，会新增家族；
2. 一样的数不能出自一个厂家，用map标记
3. 相邻两个差值的gcd不能等于1，否则也会新增家族
   其他情况直接将当前元素加入当前家族

import java.util.*;
import java.lang.*;

public class Main{

    static int[] nums;
    static Map<Integer,Integer> map = new HashMap<>();

    //辗转相除法求最大公约数
    public static int func(int a, int b){
        while(b!=0){
            int tmp = a%b;
            a=b;
            b=tmp;
        }
        return a;
    }

    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        nums = new int[n+2];

        for(int i=1; i<=n; i++){
            nums[i] = sc.nextInt();
        }
        nums[n+1] = 0;

        int sum=1;
        int p=0;

        p = Math.abs(nums[2]-nums[1]);
        map.put(nums[1],1);

        for(int i=2; i<=n; i++){

            if(map.containsKey(nums[i]) && map.get(nums[i])==1){ //2.相同的数不能来自一个家族

                for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){
                    int next = (int)iterator.next();
                    iterator.remove();
                }
                map.put(nums[i],1); 
                sum++;
                p=Math.abs(nums[i+1]-nums[i]);
                continue;
            }
            if(p==0 || p==1){  //1.如果相邻两个数的差为1或者0，应该新增家族
                for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){ 
                    int next = (int)iterator.next();
                    iterator.remove();
                }
                map.put(nums[i],1);
                sum++;
                p=Math.abs(nums[i+1]-nums[i]);
                continue;
            }

            //3.下面判断相邻两个差值的gcd是否等于1

            int q = Math.abs(nums[i]-nums[i-1]); 

            if(q==0 || q==1){
                for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){
                    int next = (int)iterator.next();
                    iterator.remove();
                }
                map.put(nums[i],1);
                sum++;
                p=Math.abs(nums[i+1]-nums[i]);
                continue;
            }

            if(func(q,p) == 1){ //如果当前差值和前面的最大公约数为1，应当新增家族
                for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){
                    int next = (int)iterator.next();
                    iterator.remove();
                }
                map.put(nums[i],1);
                sum++;
                p=Math.abs(nums[i+1]-nums[i]);
            }
            else{ //如果满足gcd>1那么直接把这个机器人加到这个厂里，并把新的gcd当成比较对象
                p=func(q,p);
                map.put(nums[i],1);
            }
        }
        System.out.println(sum);
    }
}