JavaScript基础算法题

  最近开始了前端基础知识的复习，在这个文章里进行一个简单的记录，如果内容不特别多会全部更新在这里。由于封装成函数可能不利于理解和说明，在这里的大部分题目的解答都不会封装成函数。

输出1-21之间不能被7整除数的累加和

let res = 0
// for 循环的 循环增值 i++ 会在函数执行完成后开始
// 所以从 1 开始就应该在初始化i的时候直接 let i = 1
for (let i = 1; i <= 21; i++) {
  // 余数 0 的数 = 能被 7 整除的数
  if (i % 7) res += i
}
console.log(res)

循环数除了 for 也可以用 while。

let res = 0
let index = 1
while (index <= 21) {
  if (index % 7) res += index
  index++
}
console.log(res)

数的循环的各种方法在此仅叙述一次，个人感觉还是 for 循环数比较清晰，后续都会直接用 for 循环了。

同时在这里再赘述一下 for 循环，我感觉对 for 循环的执行流程这样的解释是更加容易理解和接受的。

for (表达式1; 表达式2; 表达式3)
{
  语句;
}

执行流程：

1. 执行表达式1（所以我们可以在这里 let 变量，也可以在 for 循环之前写这个表达式1）
2. 执行表达式2
   • 值为真：执行 for 中的内嵌语句，执行表达式3
   • 值为假：循环结束

来源：for的用法详解，for循环完全攻略-CSDN博客

将1998-2008之间的闰年年份输出

for (let i = 1998; i <= 2008; i++) {
  // 条件：能被 4 整除，但不能被 100 整除（普通闰年） 或 能被 400 整除（世纪闰年）。
  // 写法一：
  if ((!(i % 4) && i % 100) || !(i % 400)) console.log("闰年", i)
  // 写法二：
  if ((i % 4 === 0 && i % 100 !== 0) || i % 400 === 0) console.log("闰年", i)
}

求乘积等于100的所有乘数和被乘数（正负整数）

// 求乘积等于100的所有乘数和被乘数（正负整数）
let pairs = []
for (let i = 1; i * i <= 100; i++) {
  // 找到 100 除以 i 没有余数的，即 i 是 100 的因子
  if (100 % i === 0) {
    let a = i
    let b = 100 / i
    pairs.push([a, b], [-a, -b])
  }
}
console.log(pairs)

倒序遍历输出数组

const list = [1, 2, 3, 4, 5]
const reverseList = []
for (let i = list.length - 1; i >= 0; i--) {
  reverseList.push(list[i])
}
console.log(reverseList)

当然，list 本身就是有 reverse 方法的，根据 V8 引擎的 Array.prototype.reverse C++ 源代码，这里写一个等效的函数。

// V8 JavaScript 引擎实现的 Array.prototype.reverse（简化版）
void ArrayReverse(TQArray arr) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left < right) {
        // 交换 arr[left] 和 arr[right]
        std::swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

Array.prototype.myReverse = function () {
  let left = 0
  let right = this.length - 1
  while (left < right) {
    // 交换 this[left] 和 this[right]
    ;[this[left], this[right]] = [this[right], this[left]]
    left++
    right--
  }
  return this // 返回结果会直接修改原数组
}

const arr = [1, 2, 3, 4, 5]
console.log(arr.myReverse())

额外说明：其中交互两个值的方法是 ES6 解构赋值（Destructuring Assignment） 的交换变量语法，等效于以下函数。

let temp = this[left];
this[left] = this[right];
this[right] = temp;

冒泡排序

原理：三分钟学会冒泡排序_哔哩哔哩

function bubble(arr, order = "asc") {
  const length = arr.length
  // 外层循环：遍历 length-1 轮
  for (let i = 0; i < length - 1; i++) {
    // 内层循环：遍历还未确定值的 length-1-i 轮
    for (let j = 0; j < length - 1 - i; j++) {
      // 对相邻的两个元素进行比较
      // 正序：前一个元素 > 后一个元素 => 交换，否则不交换
      // 倒序：前一个元素 < 后一个元素 => 交换，否则不交换
      if ((order === "asc" && arr[j] > arr[j + 1]) || (order === "desc" && arr[j] < arr[j + 1])) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // 交换位置
      }
    }
  }
  return arr
}

console.log(bubble([8, 10, 5, 3, 9, 2, 6, 4, 7, 1]))
console.log(bubble([8, 10, 5, 3, 9, 2, 6, 4, 7, 1], "desc"))

判断素数

说明：素数是大于1，且只能被1和它本身整除的正整数。

const num = 7
const result = true
// 由于素数是一定能被1和它本身整除，所以需要避免出现这两个值
for (let i = 2; i < num; i++) {
  // 取模语法：被除数 % 除数（顺序同除法/）
  if (!(num % i)) result = false
}
console.log(result)

判断水仙花数

说明：水仙花数（Narcissistic Number）是指一个 n 位数，其各位数字的 n 次方和等于它本身的数。

例子：153=1^3^+5^3^+3^3^

const num = 153
let sum = 0
const str = num.toString()
for (const number of str) {
  // 使用 pow 计算 n 次方
  sum += Math.pow(Number(number), str.length)
}
if (sum === num) {
  console.log(num, "是水仙花数")
} else {
  console.log(num, "不是水仙花数")
}

题外话-为什么叫水仙花数：“水仙花”这个名字来源于其“独特而美丽”的特性，就像水仙花一样，它能够自我完美地符合条件，因此得名。这个数字有时也被称为“自恋数”，因为它是由自己的数字经过幂运算后，完美恢复其本身的数值。

计算使用1/2/5，凑出20的所有可能性（顺序无关）

方法一：递归法/回溯法

function findCombinations({ numList, targetNum, allCombos = [], currentCombo = [], startIndex = 0 }) {
  // 当前 = 0，保存组合（说明这种组合刚刚好可以凑齐）
  if (targetNum === 0) {
    // 这里需要传 currentCombo 的副本（通过拓展运算符），避免引用的影响
    allCombos.push([...currentCombo])
    return
  }
  // 当前 < 0，终止递归（说明这种组合已经走到了不合理的地步）
  if (targetNum < 0) {
    return
  }
  // 当前 > 0，通过递归加上下一个值（尝试加上每一个值）
  for (let i = startIndex; i < numList.length; i++) {
    // 尝试加上当前值
    currentCombo.push(numList[i])
    // 进行递归，通过设置 startIndex 从当前位置继续，避免重复的组合
    findCombinations({ numList, targetNum: targetNum - numList[i], allCombos, currentCombo, startIndex: i })
    // 回溯，移除最一次加上的值，尝试其他组合（时机是上面的递归执行到 return 为止）
    currentCombo.pop()
  }
}

let res = []
findCombinations({ numList: [1, 2, 5], targetNum: 20, allCombos: res })
console.log(res.length)

方法二：动态规划

思路：使用一个数组 dp，其中 dp[i] 表示凑成数字 i 的所有组合方式的个数。通过逐步更新这个数组来找出所有可能的组合。

简单来说，就是先看1的组合，在1的组合的基础上去凑2的组合，再以此类推得到整个数组。

function findCombinations({ numList, targetNum }) {
  // 初始化 dp 数组，其每个元素都是一个数组，用来存储所有组合
  // 说明：在这里写 targetNum+1, 是因为有 0 这个元素的存在，长度需要再大一位
  const dp = Array(targetNum + 1).fill([])

  // 手动写 0 的结果（只有一种方式，即不选任何值）
  dp[0] = [[]]

  // 遍历每个值
  for (const num of numList) {
    // 通过遍历更新 dp 数组
    for (let i = num; i <= targetNum; i++) {
      // 把前一个 dp 数组的组合 + 新的数 num
      const newCombinations = dp[i - num].map(combination => [...combination, num])
      // 合并 dp 数组的值
      dp[i] = dp[i].concat(newCombinations)
    }
  }

  return dp[targetNum]
}

const res = findCombinations({ numList: [1, 2, 5], targetNum: 20 })
console.log(res.length)

下面，以运行 { numList: [1, 2, 5], targetNum: 5 } 为例，分析 dp 数组是如何变化的。

初始化后 dp 状态：

dp = [
  [[]],  // dp[0]：能组成 0 的唯一方式：空集 []
  [],    // dp[1]
  [],    // dp[2]
  [],    // dp[3]
  [],    // dp[4]
  []     // dp[5]
]

numList 中取1，即 num=1 ，遍历 i = 1 → 5：

• i = 1: dp[1 - 1] = dp[0] = [[]]

  newCombinations = [[]].map(c => [...c, 1]) = [[1]];
  dp[1] = [[1]];

• i = 2: dp[2 - 1] = dp[1] = [[1]]

  newCombinations = [[1]].map(c => [...c, 1]) = [[1, 1]];
  dp[2] = [[1, 1]];

• i = 3: dp[3 - 1] = dp[2] = [[1, 1]]

  newCombinations = [[1, 1]].map(c => [...c, 1]) = [[1, 1, 1]];
  dp[3] = [[1, 1, 1]];

• 结束后 dp 状态：

  dp = [
    [[]],
    [[1]],
    [[1, 1]],
    [[1, 1, 1]],
    [[1, 1, 1, 1]],
    [[1, 1, 1, 1, 1]]
  ]

numList 中取2，即 num=2 ，遍历 i = 2 → 5：

• i = 2: dp[2 - 2] = dp[0] = [[]]

  newCombinations = [[]].map(c => [...c, 2]) = [[2]];
  dp[2] = [[1, 1], [2]];

• i = 3: dp[3 - 2] = dp[1] = [[1]]

  newCombinations = [[1]].map(c => [...c, 2]) = [[1, 2]];
  dp[3] = [[1, 1, 1], [1, 2]];

• i = 4: dp[4 - 2] = dp[2] = [[1, 1], [2]]

  newCombinations = [[1, 1], [2]].map(c => [...c, 2]) = [[1, 1, 2], [2, 2]];
  dp[4] = [[1, 1, 1, 1], [1, 1, 2], [2, 2]];

• 结束后 dp 状态：

  dp = [
    [[]],
    [[1]],
    [[1, 1], [2]],
    [[1, 1, 1], [1, 2]],
    [[1, 1, 1, 1], [1, 1, 2], [2, 2]],
    [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2]]
  ]

numList 中取5，即 num=5 ，遍历 i = 5 ：

• i = 5: dp[5 - 5] = dp[0] = [[]]

  newCombinations = [[]].map(c => [...c, 5]) = [[5]];
  dp[5] = [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]];

• 结束后 dp 状态：

  dp = [
    [[]],
    [[1]],
    [[1, 1], [2]],
    [[1, 1, 1], [1, 2]],
    [[1, 1, 1, 1], [1, 1, 2], [2, 2]],
    [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]]
  ]

方法三：暴力枚举（只能处理题目要求的 numList 有三个数的情况）

function findCombinationsBruteForce({ numList, targetNum }) {
  const allCombos = []

  // 循环遍历三个值能乘以的最大的数
  for (let i = 0; i <= targetNum / numList[0]; i++) {
    for (let o = 0; o <= targetNum / numList[1]; o++) {
      for (let u = 0; u <= targetNum / numList[2]; u++) {
        // 筛选满足条件的组合并记录
        if (i * numList[0] + o * numList[1] + u * numList[2] === targetNum) {
          allCombos.push([i, o, u])
        }
      }
    }
  }

  return allCombos
}

const res = findCombinationsBruteForce({ numList: [1, 2, 5], targetNum: 20 })
console.log(res.length)

判断对称数（正整数）

const num = 123321

// 方法1：字符串反转
const str = num.toString()
if (str === str.split("").reverse().join("")) {
  console.log(num, "是对称数")
} else {
  console.log(num, "不是对称数")
}

// 方法2：数学方法反转
let reversed = 0
let original = num
if (num % 10 === 0) {
  console.log(num, "不是对称数")
} else {
  while (original > 0) {
    reversed = reversed * 10 + (original % 10)
    // 使用 Math.floor() 向下取整
    original = Math.floor(original / 10)
  }
  if (num === reversed) {
    console.log(num, "是对称数")
  } else {
    console.log(num, "不是对称数")
  }
}

题目来源

说明：文章仅题目和极少一部分思路照抄自以下文章。

59道JS常见逻辑算法程序题(附带题目和答案)-CSDN博客