编程知识 cdmana.com

JS basic algorithm question (2)

One 、 To judge whether a number is a prime number ( prime number )

  • Prime numbers are also called prime numbers . One is greater than 1 The natural number of , except 1 And beyond itself , Numbers that cannot be divided by other natural numbers are called prime numbers ; Otherwise, it is called sum .
  • 0 and 1 It's neither prime nor sum , The minimum prime number is 2
function isPrime(num) {
  //  Here's a special treatment for less than or equal to 3 Number of numbers , Because less than or equal to 3 The natural number of is only 2 and 3 Prime number .
  if (num <= 3) return n > 1
  //  loop 2 To num Number between , No more than num
  for (let i = 2; i < num; i++) {
    //  If 2~num Between can be num If you divide it, you return to it false
    if (num % i === 0) {
      return false
    }
  }
  //  Otherwise return to true
  return true
}
console.log(isPrime(5)) // true

Optimize : If n Is the sum , There must be non 1 Two divisors of p1 and p2, among p1<=sqrt(n),p2>=sqrt(n). Therefore, we can improve the above method to optimize the number of cycles .

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

Two 、 Fibonacci sequence

  • describe :  Fibonacci number , It refers to such a sequence :1、1、2、3、5、8、13、21、…… In Mathematics , The Fibonacci sequence is defined recursively as follows :F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,n∈N\*),
    In words , It's Fibonacci sequence 0 and 1 Start , Then the coefficients of the Fibonacci series are added by the previous two numbers .
  • Fibonacci sequence :1、1、2、3、5、8、13、21、34、……

Recursive writing

function fibonaqi(n) {
  //  Recursion must have an exit 
  if (n === 1 || n === 2) return 1
  return fibonaqi(n - 1) + fibonaqi(n - 2)
}
console.log(fibonaqi(12))

loop

function fibonaqi2(n) {
  if (n <= 2) {
    return 1
  }
  //  Define three variables , The first two start numbers and  sum
  let sum = 0
  let x = 1
  let y = 1
  //  Start with the second cycle 
  for (let i = 2; i < n; i++) {
    //  The calculation and 
    sum = x + y
    x = y
    y = sum
  }

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

3、 ... and 、 Find the greatest common divisor

Method 1: Using a loop

function greatestCommonDivisor(a, b) {
  //  Record a Big or b Big 
  let flag = a > b
  //  obtain a and b The remainder of 
  let n = flag ? a % b : b % a
  //  If the remainder is 0 The greatest common divisor is the smaller one 
  if (n === 0) return flag ? b : a
  let res = 0
  for (let i = n; i > 0; i--) {
    //  This is in reverse order a and b The remainder of gets the first one that can be a and b The integer number stops the loop 
    if (a % i === 0 && b % i === 0) {
      res = i
      break
    }
  }
  return res
}
console.log(greatestCommonDivisor(4, 8)) // 4
console.log(greatestCommonDivisor(93, 31)) // 1

Method 2: Using recursion

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

Four 、 Determine whether there is a sum of two numbers in the array

  • In an unsorted array, find out if the sum of any two numbers equals the given number .
  • The question is very simple , Don't think too complicated
    array-based indexOf Method
function sumFind(arr, num) {
  //  Loop through groups 
  for (let i = 0; i < arr.length; i++) {
    //  obtain num and arr[i] Interpolation of 
    let temp = num - arr[i]
    //  Judge arr Whether there is this difference in , But let yourself out 
    if (arr.indexOf(temp, i + 1) !== -1) {
      //  Go back when you have true
      return true
    }
  }
  //  If you don't have one in the end false
  return false
}
console.log(sumFind([6, 4, 3, 2, 1, 7], 11))

5、 ... and 、 Implement with regular trim() Clear the spaces at both ends of the string

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

6、 ... and 、 Arrangement of the lecture

  • Some projects need to occupy a conference room for propaganda , The conference room can't accommodate two projects at the same time . Give you the time to start and end each project ( Array , There are specific projects ), You will arrange the schedule of the lecture , Ask the conference room to do Most of the lectures were delivered by . Back to the most lectures .
  • step :

    1. First, according to the meeting end Time ascending sort ;
    2. Excluding meetings that cannot be held because of ongoing meetings (now > arr[i].start)
    3. The meeting can be held , be res++, And update the current time now (now = arr[i].end;).
function getMostCount(arr) {
  //  Judge whether there is a meeting 
  if (!arr || arr.length < 1) return
  //  Sort meetings by end time 
  arr.sort((a, b) => a.end - b.end)
  console.log(arr)
  //  Record the number of meetings 
  let res = 1
  //  Record the end time of the last meeting 
  let now = arr[0].end
  for (let i = 1; i < arr.length; i++) {
    //  If the end time of the last meeting does not coincide with the start time of this meeting , be  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

7、 ... and 、 Narcissistic number

  • So-called “ Narcissistic number ” It refers to a three digit number whose cubic sum equals to the number itself , for example 153 yes “ Narcissistic number ”, because :153 = 13 + 53 + 33.
  • according to “ Narcissistic number ” The definition of , Judge whether a number is “ Narcissistic number ”, The most important thing is to put the given three digit bit 、 ten 、 Split the hundreds separately , And find the sum of its cubes ( Set to s), if s Equal to the three digits given , Three figures are “ Narcissistic number ”, conversely , It is not .
function narcissusNumber(n) {
  //  “ Narcissistic number ” It refers to a three digit number that satisfies a certain condition   , According to this information, it can be determined that the value range of the integer is  100〜999
  if (n < 100 || n > 1000) {
    return false
  }
  //  Take out a bit separately 、 ten 、 Hundred bit 
  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
  }
}

8、 ... and 、 Calculate leap years

  • Condition one is to be able to be 4 to be divisible by 、 But can't be 100 to be divisible by ;
  • The second condition is that it can be 400 to be divisible by . If one of the two conditions is satisfied, it can be judged that it is a leap year .
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))

Nine 、1,2,3,4 Four Numbers , How many different kinds of three digits can be combined without repetition

function fun() {
  //  Define an empty array , Used to record the number of each combination 
  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())

Ten 、 The problem of monkeys eating peaches

  • The problem of monkeys eating peaches : The monkey picked it off the first day N A peach , I ate half of it , Not yet , I ate another one .
  • The next day, I will eat half of the remaining peaches , Another one . After that, I will eat half and one left over from the previous day every day .
  • To the first 10 When I want to eat, there is only one peach left . How many peaches were picked on the first day ?
function fun() {
  let sum = 1
  for (let i = 1; i < 10; i++) {
    sum = (sum + 1) * 2
  }
  return sum
}
console.log(fun())

Welcome the boss to correct

版权声明
本文为[Huang Wantong]所创,转载请带上原文链接,感谢

Scroll to Top