算法题目整理分析--卡牌分组

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

此时,你需要选定一个数字 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

初步解答

export default (deck) => {
  let numStatistics = {}
  let minCount = 2
  deck.forEach(item => {
    if (!numStatistics[item]) {
      numStatistics[item] = 1
    } else {
      numStatistics[item]++
    }
  })
  let maxCount = getMaxCount(numStatistics)
  let count = null
  for (let i = minCount; i < (maxCount - 1 + minCount); i++) {
    let allMatch = true
    for (let key in numStatistics) {
      if ((numStatistics[key] % i) !== 0) {
        allMatch = false
      }
    }
    if (allMatch) {
      count = i
    }
  }
  return !!count
}

let getMaxCount = (json) => {
  let max = 0
  for (let key in json) {
    if (json[key] > max) {
      max = json[key]
    }
  }
  return max
}

思路整理:

  • 1:将数组聚合到json中,并得到对应出现的次数
  • 2:获取其中最大的出现次数
  • 3:按最大出现次数进行循环,从2开始
  • 4:如果所有数据取模都为0,则存在大于2的最大公约数

这是我最初的解答方法,基本上是能解出问题,但是思路比较直接。

第二次测试

这次准备的是找出一个计算最大公约数的方法,然后通过正则去分割数组

export default (deck) => {
  let str = deck.sort().join('')
  let sameWordArr = str.match(/(\d)\1+|\d/g)
  while (sameWordArr.length > 1) {
    let firstStrLength = sameWordArr.shift().length
    let secondStrLength = sameWordArr.shift().length
    let divsiorNum = getMaxCommonDivisor(firstStrLength, secondStrLength)
    if (divsiorNum < 2) {
      return false
    }
    let newCode = '0'.repeat(divsiorNum)
    sameWordArr.unshift(newCode)
  }
  return sameWordArr.length ? sameWordArr[0].length > 1 : false
}
let getMaxCommonDivisor = (a, b) => {
  if (a % b === 0) {
    return b
  } else {
    return getMaxCommonDivisor(b, a % b)
  }
}

知识点分析:

  • 1:正则/(\d)\1+|\d/g: 匹配一个或多个连续相同的数字。其中,\1是匹配正则中的第一个子项
  • 2:getMaxCommonDivisor: 求最大公约数,如果取模不为0,则用较小的和余数继续取模

问题分析:

如果只用示例中的数字,肯定是没问题的。但是如果数组这涉及到多位数,比如 100,22,432,因为正则是按照个数去匹配的,并没有考虑到多位数的情况,所有匹配结果肯定是有问题的

第三次测试

export default (deck) => {
  let str = deck.sort().join(',') + ','
  let sameWordArr = str.match(/(\d+,)\1+|\d+,/g)
  let sameWordArrFormat = sameWordArr.map(item => {
    let arr = item.split(',')
    arr = arr.splice(0, arr.length - 1)
    return ('0').repeat(arr.length)
  })
  while (sameWordArrFormat.length > 1) {
    let firstStrLength = sameWordArrFormat.shift().length
    let secondStrLength = sameWordArrFormat.shift().length
    let divsiorNum = getMaxCommonDivisor(firstStrLength, secondStrLength)
    if (divsiorNum < 2) {
      return false
    }
    let newCode = '0'.repeat(divsiorNum)
    sameWordArrFormat.unshift(newCode)
  }
  return sameWordArrFormat.length ? sameWordArrFormat[0].length > 1 : false
}
// 计算最大公约数
let getMaxCommonDivisor = (a, b) => {
  if (a % b === 0) {
    return b
  } else {
    return getMaxCommonDivisor(b, a % b)
  }
}

针对上一个问题,我的思路是,将数字按','分开,然后在找数字+','去匹配,匹配结果还要将最后一位','去掉,然后才是正常需要的数据。

虽然取了个巧,但是由于位数问题,反而感觉还没有第一种方法处理的更加稳妥。小聪明却绕了个远

随机浏览