02. 基础算法 - 数组类.md

数组

1. 公式运算——电话号码的组合

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

示例：
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

export default (str) => {
  // 建立电话号码键盘映射
  let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  // 把输入的字符串按单字符分隔成数组，234 => [2,3,4]
  let num = str.split('')
  // 保存键盘映射后的字母内容，如 23 => ['abc',def]
  let code = []
  num.forEach(item => {
    if (map[item]) {
      code.push(map[item])
    }
  })

  let comb = (arr) => {
    // 临时变量用来保存前两个组合的结果
    let tmp = []
    // 最外层的循环是遍历第一个元素，里层的循环是遍历第二个元素
    for (let i = 0, il = arr[0].length; i < il; i++) {
      for (let j = 0, jl = arr[1].length; j < jl; j++) {
        tmp.push(`${arr[0][i]}${arr[1][j]}`)
      }
    }
    arr.splice(0, 2, tmp)
    if (arr.length > 1) {
      comb(arr)
    }
    return arr[0]
  }
  return comb(code)
}

2. 归类运算——卡牌分组

给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 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

// 卡牌分组
export default (arr) => {
  arr.sort((a, b) => a - b)
  let min = Number.MAX_SAFE_INTEGER // 记录最少相同个数
  let dist = [] // 目标数组
  for (let i = 0, len = arr.length, temp = []; i < len; i++) {
    temp.push(arr[i])
    for (let j = i + 1; j < len; j++) {
      if (arr[i] === arr[j]) {
        temp.push(arr[j])
      } else {
        if (temp.length < min) {
          min = temp.length
        }
        dist.push([...temp])
        temp.length = 0
        i = j
        break
      }
    }
  }
  return dist.every(item => {
    if (item.length % min === 0) {
      return true
    }
  })
}

3. 筛选运算——种花问题

// 种花问题
export default (arr, n) => {
  let count = 0
  arr.push(0)
  for (let i = 0, len = arr.length - 1; i < len; i++) {
    if (arr[i] === 0) {
      if (i === 0 && arr[1] === 0) {
        count++
        i++
      } else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
        count++
        i++
      }
    }
  }
  return count >= n
}

4. 二进制运算——格雷编码

// 格雷编码
export default (n) => {
  // 递归函数，用来算输入为n的格雷编码序列
  let make = (n) => {
    if (n === 1) {
      return ['0', '1']
    } else {
      let prev = myake(n - 1),y
          result = [],
          max = Math.pow(2, n) - 1
      for (let i = 0, len = prev.length; i < len; i++) {
        result[i] = `0${prev[i]}`
        result[max - i] = `1${prev[i]}`
      }
      return result
    }
  }
  return make(n)
}

总结

• 问题抽象
• 数学建模
• 动态输入