求最少篮子个数---最大公约数

本文主要是介绍求最少篮子个数---最大公约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是一道360的笔试题，有几种颜色的球，每个球有n个。求最少用几个篮子可以将这些球装到篮子里，每个篮子只有一种颜色的球且最少2个球。同一个颜色的球可以装到不同篮子。

思路：采用最大公约数求。

package mttest;import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.text.*;
import java.math.*;
import java.util.regex.*;public class Main2 {/*请完成下面这个函数，实现题目要求的功能
当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ 
******************************开始写代码******************************/static int main(int[] a) {int len = a.length;if(len==1)return 0;HashMap<Integer, Integer> hashMap = new HashMap<>();for(int i = 0; i < a.length; i++){if(hashMap.containsKey(a[i]))hashMap.put(a[i], hashMap.get(a[i])+1);elsehashMap.put(a[i], 1);}int size = hashMap.size();int[] b = new int[size];int i = 0;Set<Entry<Integer,Integer>> entrySet = hashMap.entrySet();for (Entry<Integer, Integer> entry : entrySet) {Integer num = entry.getValue();b[i] = num;i++;}int maxgysarray = maxgysarray(b,b.length);if(len%maxgysarray != 0 || maxgysarray < 2)return 0;elsereturn len/maxgysarray;}//最大公约数的求解步骤private static int maxgysarray(int[] b, int length) {int max;max = maxgys(b[0],b[1]);for(int i = 1; i < length-1; i++)max = maxgys(max, b[i]);return max;}private static int maxgys(int a, int b) {while(a!=0 && b!=0) {if(a<b)b -= a;elsea -= b;}return a==0?b:a;
}
/******************************结束写代码******************************/public static void main(String[] args){Scanner in = new Scanner(System.in);int res;int number = in.nextInt();int[] a = new int[number];for(int i = 0; i < number; i++)a[i] = in.nextInt();res = main(a);System.out.println(String.valueOf(res));    }
}

这篇关于求最少篮子个数---最大公约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---