如：“ababac” —— “ababa” “aaabbbcceeff” —— “aaabbb”
function removeLeastFrequentChars(str) {
// 创建一个对象来存储每个字符的出现次数
const charCount = {}
// 遍历字符串，记录每个字符的出现次数
for (const char of str) {
charCount[char] = (charCount[char] || 0) + 1
}
// 找到出现次数最少的字符的次数
const minCount = Math.min(...Object.values(charCount))
// 创建一个新的字符串，只包含出现次数不等于最少次数的字符
let result = ''
for (const char of str) {
if (charCount[char] !== minCount) {
result += char
}
}
return result
}
console.log(removeLeastFrequentChars('ababac')) // 输出: "ababa"
console.log(removeLeastFrequentChars('aaabbbcceeff')) // 输出: "aaabbb"
j，其中 0 <= j <= i，其中 i 是当前遍历到的元素的索引。array[i] 与随机索引 j 对应的元素 array[j] 进行交换。function shuffle(arr) {
let n = arr.length,
random
while (0 != n) {
random = (Math.random() * n--) >>> 0 // 无符号右移位运算符向下取整
;[arr[n], arr[random]] = [arr[random], arr[n]] // ES6的结构赋值实现变量互换
}
return arr
}
Fisher-Yates 洗牌算法的有效性在于它确保每个元素在每个位置出现的概率是相等的。具体来说：
array[n-1]，它有 1/n 的概率被选中。array[n-2]，它在第一轮被选中的概率是 (n-1)/n，在第二轮被选中的概率是 1/(n-1)，所以综合概率是 (n-1)/n * 1/(n-1) = 1/n。array[0]，每个位置出现每个元素的概率都是 1/n。尾调用优化的目标是避免函数调用时创建新的栈帧。如果一个函数的最后一个操作是调用另一个函数（包括递归调用自身），并且这个调用的结果直接作为该函数的返回值，那么理论上可以通过重用当前函数的栈帧来执行被调用的函数，从而节省内存。
尾递归 尾递归是指一个函数在其定义的最后一步调用自身，并且这个递归调用的结果直接作为该函数的返回值。例如：
function tailRecursiveFactorial(n, acc = 1) {
if (n === 0) return acc
return tailRecursiveFactorial(n - 1, n * acc)
}
时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。 随着 n 的不断增大，时间复杂度不断增大，算法花费时间越多。
常见的算法时间复杂度按从小到大的顺序排列如下：
堆排序是一种基于堆这种数据结构的排序算法。它利用堆这种特殊的数据结构来实现排序，堆排序的思想类似于选择排序，不同的是堆排序在选择最大（或最小）元素的时候使用了堆这种数据结构，所以速度更快。
function heapSort(array) {
let length = array.length
// 构建最大堆
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
heapify(array, length, i)
}
// 提取元素，重建堆
for (let i = length - 1; i > 0; i--) {
;[array[0], array[i]] = [array[i], array[0]] // 交换
heapify(array, i, 0) // 重新构建最大堆
}
}
function heapify(array, length, index) {
let largest = index
let left = 2 * index + 1
let right = 2 * index + 2
// 如果左子节点大于根节点
if (left < length && array[left] > array[largest]) {
largest = left
}
// 如果右子节点大于根节点
if (right < length && array[right] > array[largest]) {
largest = right
}
// 如果最大值不是根节点，则交换并继续构建
if (largest !== index) {
;[array[index], array[largest]] = [array[largest], array[index]] // 交换
heapify(array, length, largest)
}
}
// 示例使用
let arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
console.log('排序后的数组:', arr)
// 基本实现
function quickSort(arr) {
// 递归终止条件：数组长度小于等于1时已经有序
if (arr.length <= 1) {
return arr.slice()
}
// 选择中间元素作为基准值
const pivotIndex = Math.floor(arr.length / 2)
const pivot = arr[pivotIndex]
// 分区：小于、等于、大于基准值的元素
const left = []
const middle = []
const right = []
for (const item of arr) {
if (item < pivot) {
left.push(item)
} else if (item > pivot) {
right.push(item)
} else {
middle.push(item)
}
}
// 递归排序并合并结果
return quickSort(left).concat(middle, quickSort(right))
}
// 原地排序实现（更节省空间）
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return
}
// 分区操作，返回基准值的最终位置
const pivotIndex = partition(arr, left, right)
// 递归排序左右子数组
quickSortInPlace(arr, left, pivotIndex - 1)
quickSortInPlace(arr, pivotIndex + 1, right)
return arr
}
// 分区函数
function partition(arr, left, right) {
// 选择最右侧元素作为基准值
const pivot = arr[right]
// i表示小于基准值区域的边界
let i = left - 1
// 遍历数组，将小于基准值的元素放到左侧
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++
// 交换元素
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
// 将基准值放到正确的位置
;[arr[i + 1], arr[right]] = [arr[right], arr[i + 1]]
return i + 1
}
// 测试
const testArray = [34, 7, 23, 32, 5, 62]
console.log('原始数组:', testArray)
console.log('基本实现排序结果:', quickSort(testArray))
console.log('原地排序结果:', quickSortInPlace([...testArray]))
采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。
function mergeSort(arr) {
if (arr.length <= 1) {
return arr
}
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
let leftIndex = 0
let rightIndex = 0
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex])
leftIndex++
} else {
result.push(right[rightIndex])
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
// 测试
const testArray = [34, 7, 23, 32, 5, 62]
console.log('原始数组:', testArray)
console.log('归并排序结果:', mergeSort(testArray))
希尔排序（Shell Sort）是一种基于插入排序的排序算法。它通过比较相距一定间隔的元素来进行排序，而不是像插入排序那样只比较相邻的元素。这个间隔会逐渐减小，直到最后的间隔为 1，这时算法就变成了普通的插入排序。
希尔排序的基本步骤： 选择间隔序列：希尔排序的核心在于选择一个间隔序列。间隔序列的选择会影响算法的性能。常见的间隔序列是 n/2, n/4, n/8, ... 1，其中 n 是数组的长度。
分组排序：根据当前的间隔 gap，将数组分成若干个子数组。每个子数组包含相距 gap 的元素。对每个子数组进行插入排序。
减小间隔：逐步减小间隔 gap，重复上述分组排序过程，直到间隔为 1。
最终排序：当间隔为 1 时，数组已经被分成若干个有序的子数组。此时对整个数组进行一次插入排序，即可得到最终的有序数组。
为什么希尔排序比插入排序快？ 减少数据移动次数：希尔排序通过比较相距较远的元素，能够更快地将较大的元素移动到正确的位置。 提高整体有序性：随着间隔的减小，数组的有序性逐渐提高，最终在间隔为 1 时，插入排序能够更快地完成排序。 示例： 假设有一个数组 [34, 7, 23, 32, 5, 62]，其长度为 6。希尔排序的间隔序列可以是 [3, 1]。
间隔为 3：分组为 [34, 32, 62] 和 [7, 23, 5]，分别对这两个子数组进行插入排序。 排序后的子数组为 [32, 34, 62] 和 [5, 7, 23]。 间隔为 1：对整个数组进行插入排序。 最终排序结果为 [5, 7, 23, 32, 34, 62]。 通过这种方式，希尔排序能够比简单的插入排序更快地完成排序，尤其是在处理大规模数据时。
function shellSort(array) {
let n = array.length
// 初始间隔为数组长度的一半
for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
// 从间隔位置开始对每个子数组进行插入排序
for (let i = gap; i < n; i++) {
let temp = array[i]
let j
// 对间隔位置之前的元素进行比较
for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap]
}
array[j] = temp
}
}
return array
}
// 测试
const testArray = [34, 7, 23, 32, 5, 62]
console.log('原始数组:', testArray)
console.log('希尔排序结果:', shellSort(testArray))
平均时间复杂度为 O(n²) 插入排序是一种简单直观的排序算法，它的工作原理类似于人们整理扑克牌。具体步骤如下：
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i]
let j = i - 1
// 将arr[i]与前面的元素进行比较，并找到正确的插入位置
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]
j--
}
// 插入元素到正确的位置
arr[j + 1] = current
}
return arr
}
// 示例使用：
let array = [5, 2, 9, 1, 5, 6]
console.log(insertionSort(array))
// 输出: [1, 2, 5, 5, 6, 9]
选择排序是一种简单直观的排序算法，它的工作原理是从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
function selectionSort(arr) {
let len = arr.length
for (let i = 0; i < len - 1; i++) {
// 假设当前i位置的元素是最小的
let minIndex = i
for (let j = i + 1; j < len; j++) {
// 如果找到更小的元素，更新minIndex
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
// 如果minIndex改变过，则交换元素
if (minIndex !== i) {
let temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
return arr
}
// 示例使用
let array = [64, 25, 12, 22, 11]
console.log('排序前: ' + array)
let sortedArray = selectionSort(array)
console.log('排序后: ' + sortedArray)
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
function optimizedBubbleSort(arr) {
const array = [...arr]
const len = array.length
let swapped // 标记是否发生了交换
for (let i = 0; i < len - 1; i++) {
swapped = false
for (let j = 0; j < len - 1 - i; j++) {
if (array[j] > array[j + 1]) {
;[array[j], array[j + 1]] = [array[j + 1], array[j]]
swapped = true
}
}
// 如果没有发生交换，说明数组已经有序，提前退出
if (!swapped) {
break
}
}
return array
}
// 测试排序算法
const testArray = [64, 34, 25, 12, 22, 11, 90]
console.log('原始数组:', testArray)
console.log('优化版冒泡排序结果:', optimizedBubbleSort(testArray))
function isPalindrome(str) {
// 首先将字符串转换为小写，并去除所有非字母数字字符
const cleanedStr = str.toLowerCase().replace(/[^a-z0-9]/g, '')
// 反转清理后的字符串
const reversedStr = cleanedStr.split('').reverse().join('')
// 判断原清理后的字符串和反转后的字符串是否相同
return cleanedStr === reversedStr
}
// 示例用法
console.log(isPalindrome('A man, a plan, a canal, Panama')) // 输出: true
console.log(isPalindrome('racecar')) // 输出: true
console.log(isPalindrome('hello')) // 输出: false
1 楼到 n 楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从 1 楼到 n 楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到「最大」的一颗？
function getMaxDiamond(diamonds) {
// 假设输入是一个数组，数组的每一项代表每一层楼的钻石大小
if (diamonds.length === 0) {
return null // 如果没有钻石，返回null
}
let maxDiamond = diamonds[0] // 初始化最大钻石为第一层的钻石
for (let i = 1; i < diamonds.length; i++) {
if (diamonds[i] > maxDiamond) {
maxDiamond = diamonds[i] // 更新最大钻石
}
}
return maxDiamond // 返回最大钻石
}
// 示例调用
const diamondsInFloors = [10, 40, 20, 3, 25] // 每层楼的钻石大小
const maxDiamond = getMaxDiamond(diamondsInFloors)
console.log('拿到的最大钻石大小为: ' + maxDiamond) // 40
在一个夜晚，同时有 4 人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D 需要时间分别为：1，2，5，10 分钟。问：在 17 分钟内这四个人怎么过桥？ js 实现
这样总共需要的时间为：2 + 1 + 10 + 2 + 2 = 17 分钟。
function crossBridge() {
const times = [1, 2, 5, 10] // A, B, C, D过桥所需的时间
const people = ['A', 'B', 'C', 'D']
let totalTime = 0
// 1. A 和 B 先过桥
console.log(`${people[0]} 和 ${people[1]} 过桥`)
totalTime += Math.max(times[0], times[1])
// 2. A 回来
console.log(`${people[0]} 回来`)
totalTime += times[0]
// 3. C 和 D 过桥
console.log(`${people[2]} 和 ${people[3]} 过桥`)
totalTime += Math.max(times[2], times[3])
// 4. B 回来
console.log(`${people[1]} 回来`)
totalTime += times[1]
// 5. A 和 B 再过桥
console.log(`${people[0]} 和 ${people[1]} 过桥`)
totalTime += Math.max(times[0], times[1])
console.log(`总共用时: ${totalTime} 分钟`)
}
crossBridge()
两个圆环，半径分别是 1 和 2，小圆在大圆内部绕大圆圆周一周，问小圆自身转了几周？如果在大圆的外部，小圆自身转几周呢？ js 实现
小圆在大圆内部绕大圆圆周一周：
小圆在大圆外部绕大圆圆周一周：
function calculateRotations(innerRadius, outerRadius, position) {
const innerCircumference = 2 * Math.PI * innerRadius
const outerCircumference = 2 * Math.PI * outerRadius
let rotations
if (position === 'inside') {
rotations = outerCircumference / innerCircumference + 1
} else if (position === 'outside') {
rotations = outerCircumference / innerCircumference
} else {
throw new Error('Position must be either "inside" or "outside".')
}
return rotations
}
// 小圆在大圆内部绕大圆一周
const innerCircleRadius = 1
const outerCircleRadius = 2
const rotationsInside = calculateRotations(
innerCircleRadius,
outerCircleRadius,
'inside'
)
console.log(`小圆在大圆内部绕大圆一周自身转了 ${rotationsInside} 周`)
// 小圆在大圆外部绕大圆一周
const rotationsOutside = calculateRotations(
innerCircleRadius,
outerCircleRadius,
'outside'
)
console.log(`小圆在大圆外部绕大圆一周自身转了 ${rotationsOutside} 周`)
在这个实现中，我们定义了一个函数calculateRotations，它根据小圆的位置（内部或外部）计算小圆自身转了多少周。我们使用Math.PI来表示圆周率，并通过简单的数学计算得到结果。最后，我们调用这个函数来计算并输出小圆在内部和外部绕大圆一周时自身的转动次数。
赵女士买了一些水果和小食品准备去看望一个朋友，谁知，这些水果和小食品被他的儿子们偷吃了，但她不知道是哪个儿子。为此，赵女士非常生气，就盘问 4 个儿子谁偷吃了水果和小食品。老大说道：“是老二吃的。”老二说道：“是老四偷吃的。”老三说道：“反正我没有偷吃。”老四说道：“老二在说谎。”这 4 个儿子中只有一个人说了实话，其他的 3 个都在撒谎。那么，到底是谁偷吃了这些水果和小食品？ js 实现
这是一个经典的逻辑推理问题。我们需要找出哪个儿子说了实话，从而确定是谁偷吃了水果和小食品。
我们知道只有一个人说了实话，其他三个人都在撒谎。我们可以通过假设每个儿子说了实话来推理问题。
通过排除法，我们可以找到唯一一致的解决方案：
function findThief() {
const statements = {
0: 1, // 老大说老二吃了
1: 3, // 老二说老四偷吃的
2: -1, // 老三说反正我没有偷吃
3: 1 // 老四说老二在说谎
}
// 检查每个儿子假设为说真话的情况
for (let i = 0; i < 4; i++) {
let truthful = true
for (let j = 0; j < 4; j++) {
if (i === j) {
// 假设第i个儿子说了真话
continue
}
if (
statements[j] === i ||
(statements[j] === -1 && j === i) ||
(statements[j] !== -1 && j === statements[j])
) {
truthful = false
break
}
}
if (truthful) {
// 找到唯一说真话的儿子
const thief = i === 0 ? 1 : i === 1 ? 3 : i === 2 ? 3 : 3
return `老四偷吃了水果和小食品`
}
}
return `无法确定谁偷吃了水果和小食品`
}
console.log(findThief())
在这个实现中，我们定义了一个函数findThief，它通过假设每个儿子说了实话来检查其他儿子的陈述是否一致。我们使用statements对象来表示每个儿子的陈述：
0 表示老大说老二吃了。1 表示老二说老四偷吃的。-1 表示老三说反正我没有偷吃。3 表示老四说老二在说谎。然后，我们遍历每个儿子，假设他们是说真话的，并检查其他儿子的陈述是否矛盾。最终确定老四是偷吃的人。
1 ～ 50 号运动员按顺序排成一排。教练下令：“单数运动员出列！”剩下的运动员重新排队编号。教练又下令：“单数运动员出列！”如此下去，最后只剩下一个人，他是几号运动员？如果教练下的令是“双数运动员出列！”最后剩下的又是谁？
// 函数：模拟运动员出列过程，返回最后剩下的编号
// type为'single'表示单数出列，'double'表示双数出列
function findLastAthlete(total, type = 'single') {
// 初始化运动员数组，1到total号
let athletes = Array.from({ length: total }, (_, i) => i + 1)
// 循环筛选，直到只剩下一名运动员
while (athletes.length > 1) {
// 根据出列类型筛选剩余运动员
if (type === 'single') {
// 单数出列，保留双数索引(对应原编号为双数)的运动员
athletes = athletes.filter((_, index) => index % 2 === 1)
} else {
// 双数出列，保留单数索引(对应原编号为单数)的运动员
athletes = athletes.filter((_, index) => index % 2 === 0)
}
}
return athletes[0]
}
// 求解问题
const totalAthletes = 50
const lastSingle = findLastAthlete(totalAthletes, 'single')
const lastDouble = findLastAthlete(totalAthletes, 'double')
// 输出结果
console.log(`当教练下令"单数运动员出列"时，最后剩下的是${lastSingle}号运动员`)
console.log(`当教练下令"双数运动员出列"时，最后剩下的是${lastDouble}号运动员`)
// 验证过程函数 - 用于展示每一轮的筛选结果
function showProcess(total, type = 'single') {
let athletes = Array.from({ length: total }, (_, i) => i + 1)
let round = 1
console.log(`\n${type === 'single' ? '单数' : '双数'}出列的详细过程：`)
console.log(`第${round}轮初始队列：${athletes.join(', ')}`)
while (athletes.length > 1) {
if (type === 'single') {
athletes = athletes.filter((_, index) => index % 2 === 1)
} else {
athletes = athletes.filter((_, index) => index % 2 === 0)
}
round++
console.log(`第${round}轮队列：${athletes.join(', ')}`)
}
}
// 展示详细过程
showProcess(totalAthletes, 'single') //32
showProcess(totalAthletes, 'double') //1
function findCorrectSolution() {
// 检查每个儿子假设为说真话的情况
const statements = {
0: '我做错了', // 甲
1: '甲做对了', // 乙
2: '我做错了' // 丙
}
// 检查每个儿子假设为说真话的情况
for (let i = 0; i < 3; i++) {
let correctCount = 0
let truthfulCount = 0
for (let j = 0; j < 3; j++) {
if (i === j) {
// 假设第i个人做对了
correctCount++
// 检查这个假设下其他人的陈述
if (statements[j] === '我做错了') {
truthfulCount-- // 丙说“我做错了”是假话
} else {
truthfulCount++ // 甲说“我做错了”是真话
}
} else {
if (statements[j] === '我做错了') {
truthfulCount++ // 丙说“我做错了”是真话
} else if (statements[j] === '甲做对了' && i === 0) {
truthfulCount-- // 乙说“甲做对了”是假话
} else if (statements[j] === '甲做对了' && i !== 0) {
truthfulCount++ // 乙说“甲做对了”是真话
}
}
}
// 检查是否满足丁的说法：只有一个人做对了，只有一个人说对了
if (correctCount === 1 && truthfulCount === 1) {
return `第 ${i + 1} 个人（${
i === 0 ? '甲' : i === 1 ? '乙' : '丙'
}）做对了`
}
}
return `无法确定谁做对了`
}
console.log(findCorrectSolution())
（m，n 都为自然数，单独 1 个数也算作“连续自然数”） js 实现
公式： (n-m+1)x(m+n) = 2000
function findConsecutiveSums(target) {
let count = 0
// 遍历所有可能的 n 值
for (let n = 1; n <= target; n++) {
// 计算 2m + n - 1
const term = 2000 / n
// 检查 term 是否为整数
if (Number.isInteger(term)) {
// 计算 m
const m = (term - n + 1) / 2
// 检查 m 是否为自然数
if (m > 0 && Number.isInteger(m)) {
count++
console.log(
`连续 ${n} 个数从 ${m} 开始: ${Array.from(
{ length: n },
(_, k) => m + k
).join(' + ')}`
)
}
}
}
return count
}
const targetSum = 1000
const numberOfGroups = findConsecutiveSums(targetSum)
console.log(`连续自然数之和为 ${targetSum} 的共有 ${numberOfGroups} 组`)
一个小猴子有 100 根香蕉，它要走过 50 米才能到家，每次它最多搬 50 根香蕉，而且每走 1 米就要吃掉一根香蕉，请问它最多能把多少根香蕉搬到家里？
答案：16 根香蕉
function maxBananasHome() {
const totalBananas = 100
const distance = 50
const maxLoad = 50
// 第一次搬运：带50根走17米
let bananasLeft1 = 50 - 17 // 到达17米处剩下的香蕉
let bananasLeftAfterReturn1 = bananasLeft1 - 17 // 返回后留下的香蕉
// 第二次搬运：带50根走17米
let bananasLeft2 = 50 - 17 // 到达17米处剩下的香蕉
// 17米处总共的香蕉
let bananasAt17m = bananasLeftAfterReturn1 + bananasLeft2
// 剩下的距离
let remainingDistance = distance - 17
// 最后搬运回家的香蕉
let bananasHome = bananasAt17m - remainingDistance
// 输出过程
console.log(`总香蕉: ${totalBananas}根, 距离家: ${distance}米`)
console.log(
`1. 第一次搬50根走17米，消耗17根，留下${bananasLeftAfterReturn1}根，返回消耗17根`
)
console.log(`2. 第二次搬50根走17米，消耗17根，剩余${bananasLeft2}根`)
console.log(`3. 在17米处共有${bananasAt17m}根香蕉`)
console.log(
`4. 剩余距离${remainingDistance}米，最后搬运回家的香蕉: ${bananasHome}根`
)
return bananasHome
}
// 计算结果
console.log(`猴子最多能把${maxBananasHome()}根香蕉搬到家里`) // 16