33

leetcode-914.卡牌分组

 3 years ago
source link: https://studygolang.com/articles/19916?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK