企业官网建设流程全解析

北京微信网站制作电话,网站轮播动态图如何做,在线室内设计网站,wordpress next posts link914. 卡牌分组 问题描述 给定一副卡牌#xff0c;每张卡牌上有一个整数。你需要判断是否可以将这些卡牌分成若干组#xff0c;使得#xff1a; 每组至少有2张卡牌每组中的所有卡牌上的数字都相同 示例#xff1a; 输入: deck [1,2,3,4,4,3,2,1] 输出: true 解释: 可能的分…914. 卡牌分组问题描述给定一副卡牌每张卡牌上有一个整数。你需要判断是否可以将这些卡牌分成若干组使得每组至少有2张卡牌每组中的所有卡牌上的数字都相同示例输入: deck [1,2,3,4,4,3,2,1] 输出: true 解释: 可能的分组是 [1,1], [2,2], [3,3], [4,4] 输入: deck [1,1,1,2,2,2,3,3] 输出: false 解释: 没有办法将卡牌分成满足要求的组。 输入: deck [1] 输出: false 解释: 卡牌数量少于2无法分组。算法思路最大公约数统计每个数字出现的频次所有频次的最大公约数必须大于等于2如果最大公约数 ≥ 2说明可以将所有频次都分成大小为最大公约数的组代码实现方法一最大公约数 HashMapclassSolution{/** * 判断卡牌是否可以按要求分组 * * param deck 卡牌数组每个元素表示卡牌上的数字 * return 如果可以分组返回true否则返回false */publicbooleanhasGroupsSizeX(int[]deck){// 边界情况卡牌数量少于2if(deck.length2){returnfalse;}// 统计每个数字的出现频次MapInteger,IntegercountMapnewHashMap();for(intcard:deck){countMap.put(card,countMap.getOrDefault(card,0)1);}// 获取所有频次值intgcdValue-1;for(intcount:countMap.values()){if(gcdValue-1){gcdValuecount;}else{gcdValuegcd(gcdValue,count);// 如果最大公约数已经变成1可以提前返回if(gcdValue1){returnfalse;}}}// 所有频次的最大公约数必须大于等于2returngcdValue2;}/** * 计算两个数的最大公约数欧几里得算法 * * param a 第一个数 * param b 第二个数 * return 最大公约数 */privateintgcd(inta,intb){while(b!0){inttempb;ba%b;atemp;}returna;}}方法二Stream APIclassSolution{/** * 使用Java 8 Stream API * * param deck 卡牌数组 * return 如果可以分组返回true否则返回false */publicbooleanhasGroupsSizeX(int[]deck){if(deck.length2){returnfalse;}// 统计频次并计算GCDMapInteger,LongcountMapArrays.stream(deck).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting()));longgcdValuecountMap.values().stream().reduce(-1L,(a,b)-a-1?b:gcd(a,b));returngcdValue2;}privatelonggcd(longa,longb){while(b!0){longtempb;ba%b;atemp;}returna;}}算法分析时间复杂度O(n m log k)n 是卡牌总数m 是不同数字的个数k 是最大频次值最大公约数计算的时间复杂度为 O(log k)空间复杂度方法一O(m)m为不同数字的个数方法二O(maxCard)maxCard为卡牌上的最大数字算法过程输入deck [1,2,3,4,4,3,2,1]统计频次{1:2, 2:2, 3:2, 4:2}计算最大公约数初始gcdValue 2gcd(2, 2) 2gcd(2, 2) 2gcd(2, 2) 2最终gcdValue 2 2返回true输入deck [1,1,1,2,2,2,3,3]统计频次{1:3, 2:3, 3:2}计算最大公约数初始gcdValue 3gcd(3, 3) 3gcd(3, 2) 1最终gcdValue 1 2返回false测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[]deck1{1,2,3,4,4,3,2,1};System.out.println(Test 1: solution.hasGroupsSizeX(deck1));// true// 测试用例2无法分组int[]deck2{1,1,1,2,2,2,3,3};System.out.println(Test 2: solution.hasGroupsSizeX(deck2));// false// 测试用例3单张卡牌int[]deck3{1};System.out.println(Test 3: solution.hasGroupsSizeX(deck3));// false// 测试用例4两张相同卡牌int[]deck4{1,1};System.out.println(Test 4: solution.hasGroupsSizeX(deck4));// true// 测试用例5所有卡牌相同int[]deck5{1,1,1,1,1,1};System.out.println(Test 5: solution.hasGroupsSizeX(deck5));// true// 测试用例6频次互质int[]deck6{1,1,2,2,2,2};System.out.println(Test 6: solution.hasGroupsSizeX(deck6));// true// 测试用例7频次为质数int[]deck7{1,1,1,1,2,2,2,2,2,2};System.out.println(Test 7: solution.hasGroupsSizeX(deck7));// true// 测试用例8包含0int[]deck8{0,0,1,1,1,1,2,2,2,2,2,2};System.out.println(Test 8: solution.hasGroupsSizeX(deck8));// true// 测试用例9大数值int[]deck9{1000,1000,1000,1000,1000,1000};System.out.println(Test 9: solution.hasGroupsSizeX(deck9));// true}关键点最大公约数所有频次必须有一个公共因子 ≥ 2这个公共因子就是所有频次的最大公约数边界处理卡牌总数 2 时直接返回 false常见问题为什么最大公约数 ≥ 2 如果最大公约数 g ≥ 2那么每个频次都可以被g整除每个数字可以分成count/g组每组g张卡牌