关于javascript:js-基础算法题二

一、判断一个数是不是质数(素数)

• 质数又称素数。一个大于 1 的自然数，除了 1 和它本身外，不能被其余自然数整除的数叫做质数；否则称为合数。
• 0 和 1 既不是质数也不是合数，最小的质数是 2

function isPrime(num) {
  // 这里非凡解决了一下小于等于 3 的数，因为小于等于 3 的自然数只有 2 和 3 是质数。if (num <= 3) return n > 1
  // 循环 2 到 num 之间的数，不能超过 num
  for (let i = 2; i < num; i++) {
    // 如果 2~num 之间有能够被 num 整除的就返回 false
    if (num % i === 0) {return false}
  }
  // 否则返回 true
  return true
}
console.log(isPrime(5)) // true

优化： 如果 n 是合数，必然存在非 1 的两个约数 p1 和 p2，其中 p1<=sqrt(n)，p2>=sqrt(n)。由此咱们能够改良上述办法优化循环次数。

function isPrime2(num) {if (num <= 3) return n > 1
  let sqrt = parseInt(Math.sqrt(num))
  for (let i = 2; i <= sqrt; i++) {if (num % i === 0) {return false}
  }
  return true
}
console.log(isPrime2(4)) // false

二、斐波那契数列

• 形容: 斐波那契数，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的办法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N\*），
  用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
• 斐波那契数列：1、1、2、3、5、8、13、21、34、……

递归写法

function fibonaqi(n) {
  // 递归必须要有进口
  if (n === 1 || n === 2) return 1
  return fibonaqi(n - 1) + fibonaqi(n - 2)
}
console.log(fibonaqi(12))

循环

function fibonaqi2(n) {if (n <= 2) {return 1}
  // 定义三个变量，前两个开始的数和 sum
  let sum = 0
  let x = 1
  let y = 1
  // 从第二个开始循环
  for (let i = 2; i < n; i++) {
    // 计算和
    sum = x + y
    x = y
    y = sum
  }

  return temp
}
console.log(fibonaqi2(12))

三、求最大公约数

办法 1：应用循环

function greatestCommonDivisor(a, b) {
  // 记录 a 大还是 b 大
  let flag = a > b
  // 失去 a 和 b 的余数
  let n = flag ? a % b : b % a
  // 如果余数是 0 最大公约数就是小的那个数
  if (n === 0) return flag ? b : a
  let res = 0
  for (let i = n; i > 0; i--) {
    // 这里倒序 a 和 b 的余数失去第一个能被 a 和 b 整除的数就进行循环
    if (a % i === 0 && b % i === 0) {
      res = i
      break
    }
  }
  return res
}
console.log(greatestCommonDivisor(4, 8)) // 4
console.log(greatestCommonDivisor(93, 31)) // 1

办法 2：应用递归

function greatestCommonDivisor2(a, b) {if (a % b === 0) {return b}
  return greatestCommonDivisor2(b, a % b)
}
console.log(greatestCommonDivisor2(4, 8)) // 4
console.log(greatestCommonDivisor2(93, 31)) // 1

四、判断数组中是否有两数之和

• 在一个未排序的数组中找出是否有任意两数之和等于给定的数。
• 这题很简略，不要想得太简单
  应用数组的 indexOf 办法

function sumFind(arr, num) {
  // 循环遍历数组
  for (let i = 0; i < arr.length; i++) {// 失去 num 和 arr[i]的插值
    let temp = num - arr[i]
    // 判断 arr 中是否有这个差值，但要排出本人
    if (arr.indexOf(temp, i + 1) !== -1) {
      // 有就返回 true
      return true
    }
  }
  // 最初都没有的话返回 false
  return false
}
console.log(sumFind([6, 4, 3, 2, 1, 7], 11))

五、用正则实现 trim() 革除字符串两端空格

function trim(str) {return str.replace(/^\s*|\s*$/g, '')
}
console.log(trim('hello world')) // hello world

六、宣讲会安顿

• 一些我的项目要占用一个会议室宣讲，会议室不能同时包容两个我的项目的宣讲。给你每一个我的项目开始的工夫和完结的工夫(数组，外面是一个个具体的我的项目)，你来安顿宣讲的日程，要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。

• 步骤：

  1. 先依照会议的 end 工夫升序排序;
  2. 排除了因为正在进行会议而无奈进行的会议(now > arr[i].start)
  3. 会议能举办，则 res++，并且更新目前工夫 now (now = arr[i].end;)。

function getMostCount(arr) {
  // 判断是否有会议
  if (!arr || arr.length < 1) return
  // 将会议依照完结工夫排序
  arr.sort((a, b) => a.end - b.end)
  console.log(arr)
  // 记录会议次数
  let res = 1
  // 记录上一次会议的完结工夫
  let now = arr[0].end
  for (let i = 1; i < arr.length; i++) {
    // 如果上一次会议的完结工夫和这一次会议开始工夫不重合，则 res++
    if (now < arr[i].start) {
      res++
      now = arr[i].end
    }
  }
  return res
}
let arr = [{ start: 6, end: 8},
  {start: 7, end: 9},
  {start: 11, end: 12},
  {start: 10, end: 14},
  {start: 16, end: 18},
]
console.log(getMostCount(arr)) // 3

七、水仙花数

• 所谓的“水仙花数”是指一个三位数其各位数字的立方和等于该数自身，例如 153 是“水仙花数”，因为：153 = 13 + 53 + 33。
• 依据“水仙花数”的定义，判断一个数是否为“水仙花数”，最重要的是要把给出的三位数的个位、十位、百位别离拆分，并求其立方和（设为 s），若 s 与给出的三位数相等，三位数为“水仙花数”，反之，则不是。

function narcissusNumber(n) {
  //“水仙花数”是指满足某一条件的三位数，依据这一信息能够确定整数的取值范畴是 100〜999
  if (n < 100 || n > 1000) {return false}
  // 别离取出个位、十位、百位
  let ge = n % 10
  let shi = parseInt((n / 10) % 10)
  let bai = parseInt(n / 100)
  if (ge * ge * ge + shi * shi * shi + bai * bai * bai === n) {return true}
  return false
}
for (let i = 100; i < 1000; i++) {if (narcissusNumber(i)) {console.log(i) // 153  370  371  407
  }
}

八、计算平年

• 条件一是可能被 4 整除、然而不能被 100 整除；
• 条件二是可能被 400 整除。满足两个条件中的一个即能判断是平年。

function getLeapYear(start, end) {let arr = []
  for (let i = start; i <= end; i++) {if ((i % 4 === 0 && i % 100 !== 0) || i % 400 === 0) {arr.push(i)
    }
  }
  return arr
}
console.log(getLeapYear(1900, 2100))

九、1，2，3，4 四个数字, 能组合成多少种互不雷同且没有反复的三位数

function fun() {
  // 定义一个空数组，用于记录每次组合的数
  let arr = []
  for (let i = 1; i <= 4; i++) {for (let j = 1; j <= 4; j++) {for (let k = 1; k <= 4; k++) {if (i !== j && i !== k && j != k) {arr.push(i * 100 + j * 10 + k)
        }
      }
    }
  }
  return arr.length
}
console.log(fun())

十、猴子吃桃问题

• 猴子吃桃子问题：猴子第一天摘下 N 个桃子，过后就吃了一半，还不过瘾，就又吃了一个。
• 第二天又将剩下的桃子吃掉一半，又多吃了一个。当前每天都吃前一天剩下的一半零一个。
• 到第 10 天在想吃的时候就剩一个桃子了。求第一天共摘下来多少个桃子？

function fun() {
  let sum = 1
  for (let i = 1; i < 10; i++) {sum = (sum + 1) * 2
  }
  return sum
}
console.log(fun())

欢送大佬斧正