JavaScript 算法(三)
欧几里得距离
在任意数量的维度中计算两点之间的距离。
- 使用
Object.keys
和Array.prototype.map()
计算两个坐标单点之间的差; - 使用
Math.hypot()
计算两个点之间的欧几里得距离。
const euclideanDistance = (a: number[], b: number[]) =>
Math.hypot(...Object.keys(a).map((k) => b[+k] - a[+k]))
console.log(euclideanDistance([1, 1], [2, 3])) // ~2.2361
console.log(euclideanDistance([1, 1, 1], [2, 3, 2])) // ~2.4495
typescript
等差数列
创建一个从指定正整数到指定限制的数组。
- 使用
Array.from()
创建所需长度的数组,在给定范围内填充数组。
const arithmeticProgression = (n: number, limit: number) =>
Array.from({ length: Math.ceil(limit / n) }, (_, i) => (i + 1) * n)
console.log(arithmeticProgression(5, 25)) // [5, 10, 15, 20, 25]
typescript
给定数值的质数
生成给定数字的质数。
- 生成一个从 2 到给定数字的数组;
- 使用
Array.prototype.filter
过滤符合条件的数字。
const primes = (num: number) => {
let arr = Array.from({ length: num - 1 }).map((x, i) => i + 2)
const sqroot = Math.floor(Math.sqrt(num))
const numsTillSqroot = Array.from({ length: sqroot - 1 }).map((_, i) => i + 2)
numsTillSqroot.forEach(x => (arr = arr.filter(y => y % x !== 0 || y === x)))
return arr
}
console.log(primes(10)) // [2, 3, 5, 7]
console.log(primes(30)) // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
typescript
子字符串的数量
统计给定子串的字符串中的数量。
- 使用
Array.prototype.indexOf()
在 str 中搜索值; - 如果找到该值更新索引,并递增 counter;
- 使用 while 循环,该循环在
Array.prototype.indexOf()
为-1
时立即返回。
const countSubstrings = (str: string, searchValue: string) => {
let count = 0
let i = 0
while (true) {
const r = str.indexOf(searchValue, i)
if (r !== -1) {
[count, i] = [count + 1, r + 1]
} else {
return count
}
}
}
console.log(countSubstrings('tiktok tok tok tik tok tik', 'tik')) // 3
console.log(countSubstrings('tutut tut tut', 'tut')) // 4
typescript
子字符串的索引
在给定的字符串中找到子字符串的所有索引。
- 使用
Array.prototype.indexOf()
在 str 中搜索值; - 如果找到该值更新索引并用 yield 返回索引;
- 使用 while 循环,该循环在
Array.prototype.indexOf()
为-1
时立即返回。
const indexOfSubstrings = function* (str: string, searchValue: string) {
let i = 0
while (true) {
const r = str.indexOf(searchValue, i)
if (r !== -1) {
yield r
i = r + 1
} else {
return
}
}
}
console.log([...indexOfSubstrings('tiktok tok tok tik tok tik', 'tik')]) // [0, 15, 23]
console.log([...indexOfSubstrings('tutut tut tut', 'tut')]) // [0, 2, 6, 10]
console.log([...indexOfSubstrings('hello', 'hi')]) // []
typescript
凯撒密码
使用 “凯撒密码” 对给定的字符串进行加密或解密。
- 使用 % 运算符和三元运算符计算正确地加密/解密密钥;
- 使用扩展运算符和
Array.prototype.map()
在给定的字母上迭代; - 使用
String.prototype.CharCodeAt()
和String.fromCharCode()
转换每个字母,忽略特殊字符,空格等; - 使用
Array.prototype.join()
将所有字母组合到字符串中; - 最后一个参数用于设置是否是解密操作。
const caesarCipher = (str: string, shift: number, decrypt: boolean = false) => {
const s = decrypt ? (26 - shift) % 26 : shift
const n = s > 0 ? s : 26 + (s % 26)
return [...str]
.map((l, i) => {
const c = str.charCodeAt(i)
if (c >= 65 && c <= 90) {
return String.fromCharCode(((c - 65 + n) % 26) + 65)
}
if (c >= 97 && c <= 122) {
return String.fromCharCode(((c - 97 + n) % 26) + 97)
}
return l
})
.join('')
}
console.log(caesarCipher('Hello World!', -3)) // 'Ebiil Tloia!'
console.log(caesarCipher('Ebiil Tloia!', 23, true)) // 'Hello World!'
typescript
全排列
生成数组元素的所有排列方式。
const permutations = (arr: number[]): number[][] => {
if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : [arr]
return arr.reduce(
(acc, item, i) =>
acc.concat(
permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [
item,
...val
])
),
[] as number[][]
)
}
console.log(permutations([1, 33, 5]))
// [
// [ 1, 33, 5 ],
// [ 1, 5, 33 ],
// [ 33, 1, 5 ],
// [ 33, 5, 1 ],
// [ 5, 1, 33 ],
// [ 5, 33, 1 ]
// ]
typescript
卢恩算法
实现用于验证各种标识号的卢恩算法,例如信用卡号、IMEI 编号等。
- 使用
String.prototype.split()
,Array.prototype.reverse()
、Array.prototype.map()
与parseInt()
结合使用,以获取数字数组; - 使用
Array.prototype.shift()
获取最后一个数字; - 使用
Array.prototype.reduce()
实现卢恩算法; - 如果总和除以 10 等于 0 返回 true,否则返回 false。
const luhnCheck = (num: number | string) => {
const arr = (num + '')
.split('')
.reverse()
.map(x => parseInt(x))
const lastDigit = arr.shift() as number
let sum = arr.reduce(
(acc, val, i) => (i % 2 !== 0 ? acc + val : acc + ((val *= 2) > 9 ? val - 9 : val)),
0
)
sum += lastDigit
return sum % 10 === 0
}
console.log(luhnCheck('4485275742308327')) // true
console.log(luhnCheck(6011329933655299)) // true
console.log(luhnCheck(123456789)) // false
typescript
近邻算法
使用近邻算法将数据集合中每一个记录进行分类。
- 使用
Array.prototype.map()
将数据映射成对象,使用Math.hypot()
,Object.keys()
及其标签计算元素与点的欧几里得距离; - 使用
Array.prototype.sort()
和Array.prototype.slice()
计算点的 k 最近邻居; - 使用
Array.prototype.recue()
、Object.keys()
与Array.prototype.indexOf()
,查找其中最常见的标签。
interface ClassCount {
[key: number]: number
}
const kNearestNeighbors = (data: number[][], labels: number[], point: number[], k: number = 3) => {
const kNearest = data
.map((el, i) => ({
dist: Math.hypot(...Object.keys(el).map((key) => point[+key] - el[+key])),
label: labels[i]
}))
.sort((a, b) => a.dist - b.dist)
.slice(0, k)
return kNearest.reduce(
(acc, { label }, i) => {
acc.classCounts[label] =
Object.keys(acc.classCounts).indexOf(label + '') !== -1
? acc.classCounts[label] + 1
: 1
if (acc.classCounts[label] > acc.topClassCount) {
acc.topClassCount = acc.classCounts[label]
acc.topClass = label
}
return acc
},
{
classCounts: {} as ClassCount,
topClass: kNearest[0].label,
topClassCount: 0
}
).topClass
}
const data = [[0, 0], [0, 1], [1, 3], [2, 0]];
const labels = [0, 1, 1, 0];
console.log(kNearestNeighbors(data, labels, [1, 2], 2)) // 1
console.log(kNearestNeighbors(data, labels, [1, 0], 2)) // 0
typescript
均值聚类算法
使用 k-均值聚类算法将给定数据分组为 k。
- 使用
Array.from()
和Array.prototype.slice()
初始化群集质心,距离和类别; - 如果
itr
在上一个迭代中有更改,使用 while 循环重新分配和更新步骤; - 使用
Math.hypot()
、Object.keys()
和Array.prototype.map()
计算每个数据点和质心之间的欧几里得距离; - 使用
Array.prototype.indexOf()
、Math.min()
查找最接近的质心; - 使用
Array.from()
、Array.prototype.reduce()
和parseFloat()
,以及Number.prototype.toFixed()
来计算新的质心。
const kMeans = (data: number[][], k: number = 1) => {
const centroids = data.slice(0, k)
const distances = Array.from<number[][], number[]>({ length: data.length }, () =>
Array.from<number[], number>({ length: k }, () => 0)
)
const classes = Array.from({ length: data.length }, () => -1)
let itr = true
while (itr) {
itr = false
for (let d in data) {
for (let c = 0; c < k; c++) {
distances[d][c] = Math.hypot(
...Object.keys(data[0]).map(key => data[d][+key] - centroids[c][+key])
)
}
const m = distances[d].indexOf(Math.min(...distances[d]))
if (classes[d] !== m) itr = true
classes[d] = m
}
for (let c = 0; c < k; c++) {
centroids[c] = Array.from({ length: data[0].length }, () => 0)
const size = data.reduce((acc, _, d) => {
if (classes[d] === c) {
acc++
for (let i in data[0]) centroids[c][i] += data[d][i]
}
return acc
}, 0)
for (let i in data[0]) {
centroids[c][i] = parseFloat(Number(centroids[c][i] / size).toFixed(2))
}
}
}
return classes
}
console.log(kMeans([[0, 0], [0, 1], [1, 3], [2, 0]], 2)) // [0, 1, 1, 0]
typescript