leetcode-914.卡牌分组

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 <= deck.length <= 10000
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)
}