Front-end algorithm Topic analysis (1)

preface

A few days ago, WHEN I was on Github, I saw some front-end algorithm questions. I made them myself and found them quite interesting. Therefore, I sorted out the algorithm folder containing daily-question and will continue to add them in the future.

Off-topic: Actually, I don’t know what to name this article. I read the article named by the Nuggets and sorted out several templates:

1. You Don’t Know Series — Front-end Algorithms You Don’t Know
2. Satisfy series – “Front-end Algorithms this is enough”
3. Soul Series — Soul Torture of Front-end Algorithms
4. Do you Really Know It – Do You Really Know Front-end Algorithms?
5. 10, 000 words long suggested collection series – “(10, 000 words long, strongly suggest collection, miss no) before the end of the algorithm”

Finally think or a bit simple, do not make title party hahaha 😜

01- Translate numbers into Chinese

---

Title description:

Complete toChineseNum, which can convert numbers toChinese uppercase representation and process to ten thousand level, such as toChineseNum(12345), which returns twelve thousand three hundred and forty-five.

---

Ideas:

Classify the above eight digits and the following:

1. definegetResultMethod handles eight digits
2. Eight digits are processed, cut into two parts, and analyzed with five digits. If the number exceeds five digits, the last five digits are integrated, and the one divided by the last five digits is integrated. If there are no more than five digits, the conversion is done in the same way as the last five digits. Finally, deal with the special case zero.
3. Processing more than eight digits, the same cut into two parts, the last eight digits with 2 processing, the rest withgetResultAdd ‘billion’ after processing

---

Reference answer:

function toChineseNum(num) {
  num += ' '
  let numLength = num.length
  let numStr = 'One, two, three, four, five, six, seven, eight, ninety.'
  let unitArr = [' '.'ten'.'best'.'千'.'万']
  function getResult(str) {
    let res = ' ';
    if (str.length > 5) {
      let first = str.slice(- 5);
      let second = str.slice(0, str.length - 5);
      for (let i in second) {
        res = res + numStr[second[i]] + unitArr[second.length - i];
      }
      for (let i in first) {
        res = res + numStr[first[i]] + unitArr[first.length - i - 1]; }}else {
      let first = str.slice(- 5);
      for (let i in first) {
        res = res + numStr[first[i]] + unitArr[first.length - i - 1];
      }
    }
    res = res.replace(/ zero [zero hundred thousand]+/g.'zero').replace(/ zero + $/ g.' ').replace(/ LingWan/g.'万')
    return res;
  }
  
  if (numLength > 8) {
    return getResult(num.slice(0, numLength - 8)) + '亿' + getResult(num.slice(- 8 -))}return getResult(num)
}

console.log(toChineseNum(1000005600454456))

Copy the code

02- Numbers add commas

---

Title description:

Complete the function commafy, which takes a number as an argument and returns a string, by adding a comma every three digits of the integer from right to left, such as 12000000.11 to 12,000,000.11.

---

Ideas:

1. This problem mainly examines whether the train of thought is rigorous, is divided into positive and negative numbers, integer and non-integer
2. Add commas to deal with integer parts. Insert commas every 3 bits. You can use arrayssplice()Insert a comma

---

Reference answer:

function commafy (num) {
    let numStr = num + ' ';
    let arr = num < 0 ? numStr.slice(1).split('. ') : numStr.split('. ');
    let a = arr[0].split(' '); // Integer parts are cut into arrays
    for(let i = a.length - 3; i > 0; i=i- 3) {
      a.splice(i, 0.', ')}let res = arr[1]? a.join(' ') + '. ' + arr[1] : a.join(' ')
    return num < 0 ? The '-' + res : res;
}

console.log(commafy(12564654.456456)) / / 12564654456 456
Copy the code

03- Hexadecimal color value to RGB value

---

Title description:

Complete the hexToRGB function, which converts hexadecimal color values to RGB values:

hexToRGB('#F0F0F0') // => rgb(240, 240, 240)
hexToRGB('#9fc') // => rgb(153, 255, 204)
hexToRGB('Invalid color') // => null
Copy the code

---

Ideas:

How to calculate from hexadecimal to decimal. The letters A, B, C, D, E, and F are case insensitive and represent 10, 11, 12, 13, 14, and 15. How does a regular match match only three digits or letters, or only six digits or letters

---

Reference answer:

const hexToRGB = (hex) = > {
  if (!/(^\#([a-fA-F0-9]{3})$)|(^\#([a-fA-F0-9]{6})$)/g.test(hex)) return null
  let allNumberStr = '0123456789abcdef' // All digits in hexadecimal
  let len = hex.slice(1).length;
  let str = len === 6 ? hex.slice(1) : hex.slice(1) [0].repeat(2) + hex.slice(1) [1].repeat(2) + hex.slice(1) [2].repeat(2);
  let arrStr = str.split(' ');
  let newArrStr = arrStr.map((item, index) = > {
    return allNumberStr.indexOf((item + ' ').toLowerCase())
  })
  let num1 = newArrStr[0] * 16 + newArrStr[1];
  let num2 = newArrStr[2] * 16 + newArrStr[3];
  let num3 = newArrStr[4] * 16 + newArrStr[5];
  return `rgb(${num1}.${num2}.${num3}) `
}

console.log(hexToRGB('#fffaaa'))
Copy the code

04- Convert hump naming

---

Title description:

When He went to work as a front-end supervisor at a new company, he found that part of the front-end code was written by C/C++ programmers who liked to use underscores like is_good. He decided to write a script to replace all these variable names.

Complete the toCamelCaseVar function, which can take a string as an argument and replace a variable name like is_good with isGood.

---

Ideas:

• You can use the re and string methodsreplace()implementation

---

Reference answer:

const toCamelCaseVar = (variable) = > {
  variable = variable.replace(/[\_|-](\w)/g.function (all, letter) {
    return letter.toUpperCase();
  });
  return variable.slice(0.1).toLowerCase() + variable.slice(1)}console.log(toCamelCaseVar('Foo_style_css')) // fooStyleCss
console.log(toCamelCaseVar('Foo-style-css')) // fooStyleCss
Copy the code

05- Listen for array changes

---

Title description:

In the front-end MVVM framework, we often need to listen for changes in data, and arrays are important objects to listen for. Please complete ObserverableArray, its instance and ordinary array instance functions are the same, but when calling, push, pop, shift, unshift, splice, sort, reverse these methods, in addition to do the same, still can print the method name. Such as:

const arr = new ObserverableArray()

arr.push('Good') // => print 'push', a becomes ['Good']
Copy the code

Note that you can’t change Array’s Prototype. The value of the return function is the same as that of the native operation.

---

Ideas:

• Can take advantage of es6ProxyListening implementation implementation

---

Reference answer:

function ObserverableArray() {
  return new Proxy([], {
    get(target, propKey) {
      const matArr = ['push'.'pop'.'shift'.'unshift'.'splice'.'sort'.'reverse'];
      matArr.indexOf(propKey) > - 1 && console.log(propKey);
      return target[propKey]
    }
  })
}
const arr = new ObserverableArray()

arr.push('Good') // => print 'push', a becomes ['Good']
arr.push('Good2') // => print 'push', a becomes ['Good', 'Good2']
arr.unshift('Good2') / / = > print 'unshift, became a [' Good2', 'Good', 'Good2]
console.log(arr) // ['Good2','Good', 'Good2']

Copy the code

06- Verifies whether a number is prime

---

Ideas:

A prime number, also known as a prime number, is a natural number greater than 1 that has no other factors except 1 and itself. There are several cases:

1. If this number is 2 or 3, it must be prime;

2. If it’s even, it’s definitely not prime

3. If the number is not divisible by any number from 3 to its square root, m must be prime. And the divisor can increase by 2 each time (excluding even numbers)

---

Reference answer:

function isPrime(num){
  if (typeofnum ! = ='number') {
    throw new TypeError('num should be number')}if (num === 2 || num === 3) {
		return true;
	};
	if (num % 2= = =0) {
		return false;
	};
	let divisor = 3, limit = Math.sqrt(num);
	while(limit >= divisor){
		if (num % divisor === 0) {
			return false;
		}
		else {
			divisor += 2; }}return true;
}
console.log(isPrime(30));  // false
console.log(isPrime(31));  // true
Copy the code

07- Fibonacci series

---

What are Fibonacci numbers?

The Fibonacci sequence, also known as the Golden section sequence, was introduced by mathematician Leonardoda Fibonacci as an example of rabbit reproduction. It refers to a sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34… In mathematics, the Fibonacci sequence is defined recursively as follows: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n >=3, n∈N*)) Fibonacci sequence has been directly applied in modern physics, quasicrystal structure, chemistry and other fields. For this reason, the American Mathematical Society has published a mathematical journal named Fibonacci Sequence Quarterly since 1963. Used to publish research results in this area.

---

Ideas:

From the above definition, there are three cases of the Fibonacci sequence:

1. F(1)=1
2. F(2)=1
3. F(n)=F(n-1)+F(n-2) (n >=3, n∈ n \*)

Try a recursive implementation

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.time('fibonacci');
console.log(fibonacci(40)); / / 102334155
console.timeEnd('fibonacci'); / / 1106.791 ms
Copy the code

The recursive analysis carefully, you will find that f (40) = f (39) + f (38), f (39) = f (38) + f (37), f (38) = f (37) + f (36), f (40) and f (39) to calculate f (38), One more calculation of f(38), there are obvious efficiency problems. Instead, let’s try it from the bottom up (1-40). First compute f(2) based on f(0) and f(1), then compute F (3) based on f(1) and f(2)… And so on and so forth, we can figure out the NTH term. Time complexity O(n). :

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  let fiboOne = 1,
    fiboTwo = 0,
    fiboSum = 0;
  for (let i = 2; i <= n; i++) {
    fiboSum = fiboOne + fiboTwo;
    fiboTwo = fiboOne;
    fiboOne = fiboSum;
  }
  return fiboSum;
}
console.time('fibonacci');
console.log(fibonacci(40)); / / 102334155
console.timeEnd('fibonacci'); / / 4.376 ms
Copy the code

It can be seen that the time is nearly 1000ms less, and the larger the number, the larger the time difference

---

Reference answer:

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  let fiboOne = 1,
    fiboTwo = 0,
    fiboSum = 0;
  for (let i = 2; i <= n; i++) {
    fiboSum = fiboOne + fiboTwo;
    fiboTwo = fiboOne;
    fiboOne = fiboSum;
  }
  return fiboSum;
}
Copy the code

08- Add the two numbers

---

Title description:

Can you use javascript to add two string numbers?

---

Ideas:

• This question examines the addition of two numbers that exceed the js maximum value, which can be realized by using the law of addition of primary mathematics. Ten million… Add up the bits, one in ten.

---

Reference answer:

function add(a, b) {
  // See how far the two strings differ in length. The smaller ones are preceded by 0, such as 10000 and 1, followed by 10000 and 00001
  let leng = Math.abs(a.length - b.length);
  if (a.length > b.length) {
    b = Array(leng).join('0') + '0' + b;
  } else if (a.length < b.length) {
    a = Array(leng).join('0') + '0' + a;
  }
  // Convert a string to an array and invert it, just as elementary addition starts with the bits
  let textArrA = a.split(' ').reverse(),
    textArrB = b.split(' ').reverse(),
    resultArr = [];

  // Loop through the array
  for (let i = 0; i < a.length; i++) {
    If the sum is less than 10, put the sum in the target array. If the sum is greater than 10, divide by 10 to put the remainder in the target array. Then the next digit of the textArrA array is + 1.
    let sum = parseInt(textArrA[i]) + parseInt(textArrB[i]);

    I === a. length-1; I === a. length-1
    if (parseInt(sum / 10) = = =0 || i === a.length - 1) {
      resultArr.push(sum);
    } else {
      resultArr.push(sum % 10);
      textArrA[i + 1] = parseInt(textArrA[i + 1]) + 1; }}// Invert the destination array and convert it to a string
  return resultArr.reverse().join(' ');
}

console.log(add('1045747'.'10')); / / 1045757
Copy the code

09- Greatest Common Divisor & least common multiple

---

Greatest common divisor: The largest number divisible by two numbers at the same time

Least common multiple: The smallest number that divides two numbers exactly at the same time

---

Ideas:

• If the largest common divisor is found, the largest common divisor is the first number that can be divisible by both numbers. If the least common multiple, then from the large value one by one, find the first number can divide two numbers exactly at the same time is the least common multiple

---

Reference answer:

// The greatest common divisor
function maxDivisor(num1, num2) {
  let max = num1 > num2 ? num1 : num2,
    min = num1 > num2 ? num2 : num1;
  for (var i = min; i >= 1; i--) {
    if (max % i == 0 && min % i == 0) {
      returni; }}}console.log(maxDivisor(60.30)); / / 30

// Least common multiple
function minDivisor(num1, num2) {
  let max = num1 > num2 ? num1 : num2,
    min = num1 > num2 ? num2 : num1,
    result = 0;
  // This loop terminates when both numbers are prime and the maximum conditional value is I = min
  for (var i = 1; i <= min; i++) {
    result = i * max;
    if (result % max == 0 && result % min == 0) {
      returnresult; }}}console.log(minDivisor(6.8)); / / 24
Copy the code

10- Verify palindrome

---

What is a palindrome?

Palindromes are words that read the same thing from left to right and from right to left. For example: ABA, ABBA, level.

---

Ideas:

1. Use the array method to generate the inverted new string to compare with the original string

function isPalindrome(str) {
  str = ' ' + str;
  if(! str || str.length <2) {
    return false;
  }
  return (
    Array.from(str)
      .reverse()
      .join(' ') === str
  );
}
Copy the code

2. Generate a new string to compare with the original string through a reverse loop

function isPalindrome(str) {
  str = ' ' + str;
  if(! str || str.length <2) {
    return false;
  }
  var newStr = ' ';
  for (var i = str.length - 1; i >= 0; i--) {
    newStr += str[i];
  }
  return str1 === str;
}
Copy the code

3. Compare one string by one from beginning to middle and from end to middle based on the middle point, if one is different, thenreturn falseThis method has the least number of cycles and the highest efficiency

function isPalindrome(str) {
  str = ' ' + str;
  if(! str || str.length <2) {
    return false;
  }
  for (let i = 0; i < str.length / 2; i++) {
    if(str[i] ! == str[str.length -1 - i]) {
      return false; }}return true;
}
Copy the code