电话号码的组合
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。数字和字母的映射和电话的按键相同。注意：1不对应任何字母
示例：
输入："23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
说明：上面的答案是按照字典序排列的，但是你可以任意选择答案输出的顺序
思路：当数字只有2个的时候，进行排列组合会非常的容易计算和理解。所以无论多少个数字，都可以转换成22进行组合的情况。
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)
} else {
return tmp
}
return arr[0]
}
return comb(code)
}
接下来写测试用例
import telComb from '../../code/array/lesson1'
test('telComb:23', () => {
expect(telComb('23')).toEqual(['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'])
})
test('telComb:234', () => {
expect(telComb('234')).toEqual([
'adg', 'adh', 'adi',
'aeg', 'aeh', 'aei',
'afg', 'afh', 'afi',
'bdg', 'bdh', 'bdi',
'beg', 'beh', 'bei',
'bfg', 'bfh', 'bfi',
'cdg', 'cdh', 'cdi',
'ceg', 'ceh', 'cei',
'cfg', 'cfh', 'cfi'
])
})
然后npm test进行测试。
卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字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,1,2,2,2,2]
输出：true
解释：可行的分组是[1,1],[2,2],[2,2]
export default (arr) => {
// 对这副牌进行排序，升序、降序都可以
// 排序目标：让相同的数字紧挨着
arr.sort((a, b) => a - b)
// 最小值是当前浏览器支持的最大值Number.MAX_SAFE_INTEGER
let min = Number.MAX_SAFE_INTEGER
let dst = []
let result = true
// tmp临时变量
// 下面这个for循环作用是把arr按照不同的数字给分成单独的数组
// 每个数组里的数字是相同的
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 {
// 保障min代表的永远是相同数字组成的元素数量最小值
if (min > tmp.length) {
min = tmp.length
}
// 数组是引用类型，所以下面这行代码不能直接pushtmp
// 如果直接push的话，接下来的循环会改变tem
// 会导致dst里面的tmp引用也跟着不停的变
// [].concat()相当于开辟了一个新的内存空间
dst.push([].concat(tmp))
// length等于0是真正的清空临时数组
tmp.length = 0
// 跳过相同数字
i = j
break
}
}
}
// 循环dst里的每一项
// 只要有一项的长度不是最小长度的整数倍，就返回false
// forEach不能中断循环，所有这里用的every
dst.every(item => {
if (item.length % min !== 0) {
result = false
return false
}
})
return result
}
写测试用例
import cardGroup from '../../code/array/lesson2'
test('cardGroup:[1,2,3,4,4,3,2,1]', () => {
expect(cardGroup([1, 2, 3, 4, 4, 3, 2, 1])).toBe(true)
})
test('cardGroup:[1,1,1,2,2,2,3,3]', () => {
expect(cardGroup([1, 1, 1, 2, 2, 2, 3, 3])).toBe(false)
})
test('cardGroup:[1,1,2,2,2,2]', () => {
expect(cardGroup([1, 1, 2, 2, 2, 2])).toBe(true)
})
练习题：种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数n，能否在不打破种植规则的情况下种入n朵花？能则返回true，不能则返回false
示例1：
输入：flowerbed = [1,0,0,0,1], n=1
输出：true
示例2：
输入：flowerbed = [1,0,0,0,1], n=2
输出：false
注意：
1.数组内已种好的花不会违反种植规则。
2.输入的数组长度范围为[1,20000]
export default (arr, n) => {
// 计数器
let max = 0
for (let i = 0, len = arr.length; i < len; i++) {
if (arr[i] === 0) {
// 判断一下是不是起始边界
if (i === 0 && arr[1] === 0) {
max++
i++
} else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
max++
i++
}
// 判断一下是不是结束边界
else if (i === Number(arr.length - 2) && arr[arr.length - 3] !== 0 && arr[arr.length - 1] === 0) {
max++
console.log(max)
}
}
}
return max >= n
}
测试用例：
import flower from '../../code/array/lesson3'
test('flower:[1,0,0,0,1],1', () => {
expect(flower([1, 0, 0, 0, 1], 1)).toBe(true)
})
test('flower:[1,0,0,0,1],2', () => {
expect(flower([1, 0, 0, 0, 1], 2)).toBe(false)
})
