914.卡牌分组

题目

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

• 每组都有 X 张牌。
• 组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

示例 1：
**

输入：[1,2,3,4,4,3,2,1]

输出：true

解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：
**

输入：[1,1,1,2,2,2,3,3]

输出：false

解释：没有满足要求的分组。

示例 3：
**

输入：[1]

输出：false

解释：没有满足要求的分组。

示例 4：
**

输入：[1,1]

输出：true

解释：可行的分组是 [1,1]

示例 5：
**

输入：[1,1,2,2,2,2]

输出：true

解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：
**

1. 1 <= deck.length <= 10000
2. 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 *

测试最大公约数

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实现

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)
}