老师, 卡牌分组这一节我有一些疑问

来源:3-5 卡牌分组-代码演示

onjuju

2019-02-16

跟着老师学完这门课后,我自己去leetcode重新实现了一遍,但发现无法通过编译,所以慢慢调试了很久,不知道我的理解有没有问题,希望老师可以帮我看一下,谢谢老师!

这是老师的源代码:

function masterCard (arr) {
  // 对这副牌进行排序,升序、降序都可以
  arr.sort((a, b) => a - b)
  let min = Number.MAX_SAFE_INTEGER
  let dst = []
  let result = true
  for (let i = 0, len = arr.length, tmp = []; i < len; i++) {
    tmp.push(arr[i])
    for (let j = i + 1; j < len - 1; j++) {
      if (arr[i] === arr[j]) {
        tmp.push(arr[j])
      } else {
        if (min > tmp.length) {
          min = tmp.length
        }
        dst.push([].concat(tmp))
        tmp.length = 0
        i = j
        break
      }
    }
  }
  // 这里我分别在浏览器中打印了函数的dst, 也就是将各个数字整理成一个个数组的那个对象
  console.log(dst)
  dst.every(item => {
    if (item.length % min !== 0) {
      result = false
      return false
    }
  })
  return result
}

masterCard(['1','2','3','4','4','3','2','1']) // true  dst: [[1,1], [2], [3]]
masterCard(['0','0','0','0','1','1','2','3','4']) // true  dst: [[0,0,0,0], [1]]

我认为这里的dst的结果并不完整,循环那里的条件有一些问题。
以及在函数最后的判断部分,题意说明每组的X要大于等于2时才返回true,而上面两个例子判断时都是以最小长度为1来判断,导致都返回了true

我自己修改了循环部分的代码,可以得出正确的dst

function hasGroup (arr) {
  arr.sort((a, b) => a - b)
  let min = Number.MAX_SAFE_INTEGER
  let dst = []
  let result = true
  for (let i = 0, len = arr.length, tmp = []; i < len; i++) {
    tmp.push(arr[i])
    for (let j = i + 1; j <= len; j++) {
      if (arr[i] === arr[j]) {
        tmp.push(arr[j])
      } else {
        if (min > tmp.length) {
          min = tmp.length
        }
        dst.push([].concat(tmp))
        tmp.length = 0
        i = j - 1
        break
      }
    }
  }
  console.log(dst)
  dst.every(item => {
    if (item.length % min !== 0) {
      result = false
      return false
    } else {
    	return true
    }
  })
  return min > 1 && result
}

hasGroup(['1','2','3','4','4','3','2','1']) // true  dst: [[1,1], [2,2], [3,3], [4,4]]
hasGroup(['0','0','0','0','1','1','2','3','4']) // false  dst: [[0,0,0,0], [1,1], [2], [3], [4]]

当跳出内层j循环时,如果给i直接赋值j,进入外层i循环时i又会加上1,就会跳过一个数,所以我改成了i = j - 1。
以及在内层j循环中,因为如果只循环到数组的最后一个值,会向tmp加入这个数,但无法执行到将tmp加入dst这个操作,所以我将循环多进行了一次

但这样仍然存在一个问题,就是当输入的数组为[‘1’,‘1’,‘1’,‘1’,‘2’,‘2’,‘2’,‘2’,‘2’,‘2’]时,计算结果为false

hasGroup(['1','1','1','1','2','2','2','2','2','2']) // false  dst: [[1,1,1,1], [2,2,2,2,2,2]]

而实际上这组数字存在 [1,1], [1,1], [2,2], [2,2], [2,2] 这样可行的分组。

因此,在考虑最后结果时不应单单以最短的数组长度作为分组的基数,我认为应该以所有数字分组长度的最大公约数来作为基数,以该基数来检测是否可以拆分成每组长度>1且组内数字相等的分组

// 获得两个数的最大公约数
function getBigFactor(a,b){
  return b === 0 ? a : getBigFactor(b,a%b)
}
function hasGroup (arr) {
  arr.sort((a, b) => a - b)
  let min = Number.MAX_SAFE_INTEGER
  let max = Number.MIN_SAFE_INTEGER
  let dst = []
  let result = true
  let radix = Number.MAX_SAFE_INTEGER
  for (let i = 0, len = arr.length, tmp = []; i < len; i++) {
    tmp.push(arr[i])
    for (let j = i + 1; j <= len; j++) {
      if (arr[i] === arr[j]) {
        tmp.push(arr[j])
      } else {
        if (i === 0) {
        	// 第一次循环, 基数为该数字分组的长度
        	radix = tmp.length
        } else {
        	// 获取所有分组长度的最大公约数
        	let temp = getBigFactor(radix, tmp.length)
        	radix = temp < radix ? temp : radix
        }
        dst.push([].concat(tmp))
        tmp.length = 0
        i = j - 1
        break
      }
    }
  }
  console.log(dst)
  console.log(radix)
  dst.every(item => {
    if (item.length % radix !== 0) {
      result = false
      return false
    } else {
    	return true
    }
  })
  return radix > 1 && result
}
hasGroup(['1','1','1','1','2','2','2','2','2','2']) // true  radix: 2

大体还是按照课程的思路实现,增加了一个radix变量,每次循环都尝试寻找所有组合长度的最大公约数,最后以该变量为基准进行判断。

写回答

3回答

快乐动起来呀

2019-02-17

嗯,你说的是对的,这里确实漏掉了情况,我会更新这一节的内容,等排期哈,感谢反馈

1
1
_玲
哈哈,我也发现这个问题了呢,题目中X >= 2
2019-02-19
共1条回复

黄ty的前端血泪学习史

2019-02-20

谢谢补充

1
0

饕餮3

2019-02-21

// 获取所有分组长度的最大公约数
        let temp = getBigFactor(radix, tmp.length)
        radix = temp < radix ? temp : radix

上面你是不是写的有点冗余

直接这样写是不是更好

radix=getBigFactor(radix, tmp.length)

0
1
onjuju
是的,多谢指正!
2019-02-22
共1条回复

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程