leetcode-914.卡牌分组

custer · · 1070 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# 914.卡牌分组 # 题目 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 `X`,使我们可以将整副牌按下述规则分成 1 组或更多组: * 每组都有 `X` 张牌。 * 组内所有的牌上都写着相同的整数。 仅当你可选的 `X >= 2` 时返回 `true`。<br /> <br />**示例 1:**<br />** > **输入:**[1,2,3,4,4,3,2,1] > **输出:**true > **解释:**可行的分组是 [1,1],[2,2],[3,3],[4,4] **示例 2:**<br />** > **输入:**[1,1,1,2,2,2,3,3] > **输出:**false > **解释:**没有满足要求的分组。 **示例 3:**<br />** > **输入:**[1] > **输出:**false > **解释:**没有满足要求的分组。 **示例 4:**<br />** > **输入:**[1,1] > **输出:**true > **解释:**可行的分组是 [1,1] **示例 5:**<br />** > **输入:**[1,1,2,2,2,2] > **输出:**true > **解释:**可行的分组是 [1,1],[2,2],[2,2] **提示:**<br />** 1. `1 <= deck.length <= 10000` 1. `0 <= deck[i] < 10000` --- # 思考 **计算两个数 a, b 的最大公约数** * **a = ****c**** * b + ****d ** * **d = 0 a = c * b** * **d > 0 a = c * b + d **->b = e *d + f**  * **f = 0 b = e * d          <-  a = ****c**** * ( ****e**** * d ) + ****d** * **f > 0**** b = ****e**** * d + ****f    ****<-  a = ****c**** * ( ****e**** * d + f ) + ****d****  ** 测试最大公约数 ```go package main import "fmt" func GreatestCommonDivisor(a, b int) int { for b != 0 { return GreatestCommonDivisor(b, a % b) } return a } func main() { fmt.Println(GreatestCommonDivisor(6, 9)) // 3 fmt.Println(GreatestCommonDivisor(2, 8)) // 2 fmt.Println(GreatestCommonDivisor(2, 3)) // 1 } ``` # Go实现 ```go package main import ( "fmt" "math" ) func GreatestCommonDivisor(a, b int) int { // 定义求最大公约数的方法 for b != 0 { return GreatestCommonDivisor(b, a % b) } return a } func hasGroupsSizeX(deck []int) bool { // 1. 统计各个数出现的次数 m := make(map[int]int) min := math.MaxInt64 for _, v := range deck { if m[v] != 0{ m[v] += 1 } else { m[v] = 1 } } fmt.Println("min: ", min) // 2. 遍历找出最小次数 for i, v := range m { fmt.Printf("数字:%d, 出现了 %d 次\n", i, v) if min > v { min = v } } fmt.Printf("各个数出现的最小次数:%d\n", min) // 3. 求次数与最小次数之间是否存在最大公约数 for _, v := range m { fmt.Printf("min=%d, 与 %d 之间的最大公约数是 %d\n", min, v, GreatestCommonDivisor(min, v)) if(GreatestCommonDivisor(min, v)<=1) { fmt.Println("false") return false } } fmt.Println("true") return true } func main() { a := []int{1,2,3,4,4,3,2,1} hasGroupsSizeX(a) } ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1070 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传