Explication détaillée de l'algorithme d'entrevue Js

L’essor de l’IA a amené tout le monde à accorder de plus en plus d’attention aux algorithmes. En tant qu'ingénieur front-end, les algorithmes sont souvent notre faiblesse. Cet article est traduit d'une question d'entretien étrangère. Liste de quelques questions d'entretien qui sont simplement liées aux algorithmes

Articles connexes recommandés  : La collection la plus complète de questions d'entretien js en 2020 (dernière)

Nombres premiers

Q : Comment vérifieriez-vous un nombre premier ?

A : Un nombre premier ne peut être divisible que par lui-même et 1. Je vais donc exécuter une boucle while et ajouter 1. (Regardez l'exemple de code, si vous n'arrivez pas à le comprendre, ce n'est pas votre truc. Revenez en arrière et apprenez d'abord les bases de javaScript, puis revenez.)

Méthode 1

function isPrime(n){
 var pisor = 2;
 while (n > pisor){
 if(n % pisor == 0){
  return false; 
 }
 else
  pisor++;
 }
 return true;
}
isPrime(137); // = true
isPrime(237); // = false

Q : Pouvez-vous faire mieux ?

R : Oui. Le diviseur augmente de un à la fois. Après 3, je peux ajouter 2. Si un nombre est divisible par un nombre pair, il sera divisible par 2.

Supplémentaire : si vous n'avez pas besoin d'augmenter le diviseur jusqu'à ce nombre. Vous pouvez arrêter plus tôt. Laissez-moi vous l'expliquer dans les étapes ci-dessous (vous pouvez le lire plusieurs fois si vous en avez besoin)

Première étape, aucun nombre n'est divisible par un nombre supérieur à la moitié. Par exemple, 13 ne sera jamais divisible par 7,8,9... il peut même être la moitié d'un nombre pair. Par exemple, 16 sera divisible par 8, mais jamais par 9, 10, 11, 12...
Conclusion : Un nombre ne sera jamais divisible par un nombre supérieur à la moitié de sa valeur. Ainsi, nous pouvons boucler 50 % de moins.

La deuxième étape, maintenant, si un nombre n'est pas divisible par 3. (S'il est divisible par 3, alors ce n'est pas premier). Ensuite, il n’est divisible par aucun nombre supérieur à 1/3 de sa valeur. Par exemple, 35 n'est pas divisible par 3. Il ne sera donc jamais divisible par un nombre supérieur à 35/3, jamais divisible par 12, 13, 14... Si vous prenez un nombre pair comme 36, il ne sera jamais divisible par 13, 14, 15.

Conclusion : Un nombre est divisible par le tiers de sa valeur.

Étape 3, par exemple, vous avez un nombre 127. 127 n'est pas divisible par 2, vous devez donc cocher au maximum 63,5. Deuxièmement, 127 n'est pas divisible par 3. Vous vérifierez donc à 127/3 environ 42. Il n'est pas divisible par 5, le diviseur doit être inférieur à 127/5, soit environ 25 et non 7. Alors, où s'arrêter ?
Conclusion : Le diviseur sera inférieur à math.sqrt(N)

Méthode 2

Ne vous inquiétez pas si vous ne comprenez pas, juste laissez-le tranquille. Peu importe si vous n'êtes pas chercheur.

function isPrime(n)
{
 var pisor = 3, 
  limit = Math.sqrt(n);
 //check simple cases
 if (n == 2 || n == 3)
  return true;
 if (n % 2 == 0)
  return false;
 while (pisor <= limit)
 {
 if (n % pisor == 0)
  return false;
 else
  pisor += 2;
 }
 return true;
}
isPrime(137); // = true
isPrime(237); // = false

Facteurs premiers

Q : Comment trouver tous les facteurs premiers d'un nombre ?
A : Exécuter une boucle while. Commencez à diviser par 2. S'il ne peut pas être divisé, enregistrez le diviseur jusqu'à ce qu'il soit terminé.

function primeFactors(n){
 var factors = [], 
  pisor = 2;
 while(n>2){
 if(n % pisor == 0){
  factors.push(pisor); 
  n= n/ pisor;
 }
 else{
  pisor++;
 }  
 }
 return factors;
}
 primeFactors(69); // = [3, 23]

Q : Quelle est la complexité du temps d'exécution ? Pouvez-vous faire mieux ?

A : O(n). Vous pouvez commencer le diviseur à partir de 3 et additionner jusqu'à 2. Car si un nombre est divisible par un nombre pair, il sera divisible par 2. Il n’est donc pas nécessaire de diviser par des nombres pairs. De plus, vous n’aurez pas un facteur supérieur à la moitié de sa valeur. Si vous voulez compliquer les choses, utilisez les concepts supplémentaires de la première question.

Fibonacci (Fibonacci)

Q : Comment obtenir le nième numéro de Fibonacci ?
A : Je crée un tableau et commence par itérer.

La série Fibonacci est l'une des questions d'entretien les plus populaires pour les débutants. Donc, vous devez apprendre celui-ci.

Méthode 1

function fibonacci(n){
 var fibo = [0, 1];
 if (n <= 2) return 1;
 for (var i = 2; i <=n; i++ ){
 fibo[i] = fibo[i-1]+fibo[i-2];
 }
 return fibo[n];
} 
fibonacci(12); // = 144

Q : Quelle est la complexité du temps d'exécution ?

A : O(n);

Q : Pouvez-vous le rendre récursif ?

Méthode 2

function fibonacci(n){
 if(n < =1) {
  return n;
 } else {
  return fibonacci(n-1) + fibonacci (n-2);
 }
}
fibonacci(12); // = 144

Q : Quelle est la complexité du temps d'exécution ?
A : O(2n) ; détails sur la complexité temporelle

Plus grand diviseur commun

Q : Comment trouveriez-vous deux Qu'est-ce que le plus grand commun diviseur des nombres ?

function greatestCommonpisor(a, b){
 var pisor = 2, 
  greatestpisor = 1;
 //if u pass a -ve number this will not work. fix it dude!!
 if (a < 2 || b < 2)
  return 1;
 while(a >= pisor && b >= pisor){
 if(a %pisor == 0 && b% pisor ==0){
  greatestpisor = pisor;  
 }
 pisor++;
 }
 return greatestpisor;
}
greatestCommonpisor(14, 21); // 7
greatestCommonpisor(69, 169); // = 1

Paradigme algorithmique

Désolé. Je ne peux pas non plus l'expliquer. Parce que moi-même, je n'arrive pas à le comprendre dans 80 % des cas. Mon coach en analyse d'algorithmes m'a dit cela et l'a volé dans les notes de cours (j'étais un bon élève, d'ailleurs !)

function greatestCommonpisor(a, b){
 if(b == 0)
  return a;
 else 
  return greatestCommonpisor(b, a%b);
}

REMARQUE : utilisez votre cerveau pour le comprendre.

Déduplication

Q : Comment supprimeriez-vous les membres en double d'un tableau ?
A : Exécutez une boucle et enregistrez un objet/un tableau associatif. Si je trouve un élément pour la première fois, je définis sa valeur sur true (ce qui me dira que l'élément a été ajouté une fois). Si je trouve cet élément dans l'objet, je ne l'insère pas dans le tableau de retour.

function removeDuplicate(arr){
 var exists ={},
  outArr = [], 
  elm;
 for(var i =0; i<arr.length; i++){
 elm = arr[i];
 if(!exists[elm]){
  outArr.push(elm);
  exists[elm] = true;
 }
 }
 return outArr;
}
removeDuplicate([1,3,3,3,1,5,6,7,8,1]); // = [1, 3, 5, 6, 7, 8]

Fusionner deux tableaux triés

Q : Comment fusionner deux tableaux triés ?
A : Je garderai un pointeur pour chaque tableau (regardez le code et notez ceci).

function mergeSortedArray(a, b){
 var merged = [], 
   aElm = a[0],
   bElm = b[0],
   i = 1,
   j = 1;
 if(a.length ==0)
  return b;
 if(b.length ==0)
  return a;
 /* 
 if aElm or bElm exists we will insert to merged array
 (will go inside while loop)
  to insert: aElm exists and bElm doesn't exists
       or both exists and aElm < bElm
  this is the critical part of the example      
 */
 while(aElm || bElm){
  if((aElm && !bElm) || aElm < bElm){
   merged.push(aElm);
   aElm = a[i++];
  }  
  else {
   merged.push(bElm);
   bElm = b[j++];
  }
 }
 return merged;
}
mergeSortedArray([2,5,6,9], [1,2,3,29]);// = [1, 2, 2, 3, 5, 6, 9, 29]

Échanger les valeurs de deux nombres sans utiliser de variables temporaires

Q : Comment échanger deux nombres sans utiliser de variables temporaires ?

function swapNumb(a, b){
 console.log('before swap: ','a: ', a, 'b: ', b);
 b = b -a;
 a = a+ b;
 b = a-b;
 console.log('after swap: ','a: ', a, 'b: ', b); 
}
swapNumb(2, 3);
//  = before swap: a: 2 b: 3
//  = after swap: a: 3 b: 2

位操作：对不起，我无法向你解释这一点。 Kinjal Dave建议到 logical conjunction理解它。将浪费您30分钟。

function swapNumb(a, b){
 console.log("a: " + a + " and b: " + b);
 a = a ^ b;
 b = a ^ b;
 a = a ^ b;
 console.log("a: " + a + " and b: " + b);
}
swapNumb(2, 3);
// = a: 2 and b: 3
// = a: 3 and b: 2

字符串反向

Q：如何在JavaScript中反转字符串？
A：可以遍历字符串并将字母连接到新字符串。

方法1

function reverse(str){
 var rtnStr = '';
 for(var i = str.length-1; i>=0;i--){
  rtnStr +=str[i];
 }
 return rtnStr;
}
reverse('you are a nice dude');
// = "edud ecin a era uoy"

Q：你知道在现代浏览器中串联效果很好，但在像IE8这样的旧浏览器中会变慢。 还有什么不同的方法，可以扭转一个字符串？

A：当然.我可以使用数组，也可以添加一些检查。如果字符串是NULL或其他字符串，这将失败。让我也做一些类型检查。使用此数组类似于在某些服务器端语言中使用字符串缓冲区。

方法2

function reverse(str){
 var rtnStr = [];
 if(!str || typeof str != &#39;string&#39; || str.length < 2 ) return str;
 for(var i = str.length-1; i>=0;i--){
  rtnStr.push(str[i]);
 }
 return rtnStr.join(&#39;&#39;);
}

Q： 运行时间复杂度是多少？
A： O(n)；
Q：可以做得更好？
A：我可以遍历索引的一半，它会节省一点点。 （这是没用的，可能不会打动面试官）

方法3

function reverse(str) {
 str = str.split('');
 var len = str.length,
   halfIndex = Math.floor(len / 2) - 1,
   revStr;
 for (var i = 0; i <= halfIndex; i++) {
  revStr = str[len - i - 1];
  str[len - i - 1] = str[i];
  str[i] = revStr;
 }
 return str.join(&#39;&#39;);
}

Q：这有效，但你可以做递归的方式吗？
A：可以。

方法4

function reverse (str) {
  if (str === "") {
    return "";
  } else {
    return reverse(str.substr(1)) + str.charAt(0);
  }
}

方法5

Q：你可以在方法中使用任何构建，使它更清洁吗？

function reverse(str){
 if(!str || str.length <2) return str;
 return str.split(&#39;&#39;).reverse().join(&#39;&#39;);
}

方法6

Q：你可以做反向函数作为字符串扩展吗？
A：我需要将这个函数添加到String.prototype，而不是使用str作为参数，我需要使用this

String.prototype.reverse = function (){
 if(!this || this.length <2) return this;
 return this.split(&#39;&#39;).reverse().join(&#39;&#39;);
}
&#39;abc&#39;.reverse();
// = &#39;cba&#39;

单词反转

Q：你如何在句子中颠倒单词？
A：您必须检查整个字符串的空白区域。确定是否可能有多个空格。

//have a tailing white space
//fix this later
//now i m sleepy
function reverseWords(str){
 var rev = [], 
   wordLen = 0;
 for(var i = str.length-1; i>=0; i--){
  if(str[i]==' ' || i==0){
   rev.push(str.substr(i,wordLen+1));
   wordLen = 0;
  }
  else
   wordLen++;
 }
 return rev.join(' ');
}

内置方法的快速解决方案：

function reverseWords(str){
 return str.split(' ').reverse();
}

原位反转

Q: 如果你有一个字符串如”I am the good boy”， 怎样变为 “I ma eht doog yob”？ 注意这些单词位置不变但是被反转了。

A: 要做到这一点，我必须做字符串反向和字反转。

function reverseInPlace(str){
 return str.split(' ').reverse().join(' ').split('').reverse().join('');
}
reverseInPlace('I am the good boy');// = "I ma eht doog yob"

Q: ok。好的，你能不使用内置反向函数做到吗？
A: (内心独白)有没有搞错！！

//sum two methods.
//you can simply split words by ' '
//and for each words, call reverse function
//put reverse in a separate function
//if u cant do this, 
//have a glass of water, and sleep

第一个非重复字符

Q: 怎么在字符串中找到第一个非重复字符？
A: 有什么条件吗？
A: 比如是否区分大小写？
面试官可能会说No。
A: 是长字符串还是短字符串？
Q: 这些有什么关系吗？

A:例如，如果它是一个非常长的字符串，说一百万个字符，我想检查是否有26个英文字符正在重复。 我可能会检查是否所有字符都在每200个字母中重复（例如），而不是循环遍历整个字符串。 这将节省计算时间。
Q: 简单起见， 这个字符串是 “the quick brown fox jumps then quickly blow air”。

function firstNonRepeatChar(str){
 var len = str.length,
   char, 
   charCount = {};
 for(var i =0; i<len; i++){
  char = str[i];
  if(charCount[char]){
   charCount[char]++;
  }
  else
   charCount[char] = 1;
 }
 for (var j in charCount){
  if (charCount[j]==1)
    return j;
 }
} 
firstNonRepeatChar(&#39;the quick brown fox jumps then quickly blow air&#39;);// = "f"

这有一个问题，不能再循环中及时退出。

删除重复的字符

Q: 怎样删除字符串中的重复字符？

A: 这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗？。

如果面试官说，这是区分大小写的，那么你就很轻松了。 如果他说不。你可以使用string.toLowercase（）来把字符串。面试官可能不喜欢这个方法。 因为返回字符串不会拥有相同的大小写。 所以

function removeDuplicateChar(str){
 var len = str.length,
   char, 
   charCount = {}, 
   newStr = [];
 for(var i =0; i<len; i++){
  char = str[i];
  if(charCount[char]){
   charCount[char]++;
  }
  else
   charCount[char] = 1;
 }
 for (var j in charCount){
  if (charCount[j]==1)
    newStr.push(j);
 }
 return newStr.join(&#39;&#39;);
}
removeDuplicateChar(&#39;Learn more javascript dude&#39;); // = "Lnmojvsciptu"

回文检查

Q: 如何检查一个字符串是否是回文？

A: 把字符串反转，如果反转前后相等，那么它就是回文。

function isPalindrome(str){
 var i, len = str.length;
 for(i =0; i<len/2; i++){
  if (str[i]!== str[len -1 -i])
    return false;
 }
 return true;
}
isPalindrome(&#39;madam&#39;)
// = true
isPalindrome(&#39;toyota&#39;)
// = false

或者

function checkPalindrom(str) {
  return str == str.split('').reverse().join('');
}

类似的：在 O(n)时间复杂度内判断一个字符串是否包含在回文字符串内。你能在O（1）时间解决问题吗？

找缺失的数字

Q: 在一个1到100的未排序数组中找到缺失的数，你怎么做？

说明：数组中的数字为1到100。 数组中只有一个数字缺失。数组未排序。找到缺少的数字。

A: 你必须表现得像是在想很多。然后讨论n＝n（n＋1）／2的线性级数之和

function missingNumber(arr){
 var n = arr.length+1, 
   sum = 0,
   expectedSum = n * (n+1)/2;
 for(var i = 0, len = arr.length; i < len; i++){
  sum += arr[i];
 }
 return expectedSum - sum;
}
missingNumber([5, 2, 6, 1, 3]);
// = 4

注意： 这个会返回任意长度数组中缺失的那个

两数之和

Q: 在一个未排序的数组中找出是否有任意两数之和等于给定的数？
A: 简单！双重循环。

function sumFinder(arr, sum){
 var len = arr.length;
 for(var i =0; i<len-1; i++){ 
   for(var j = i+1;j<len; j++){
    if (arr[i] + arr[j] == sum)
      return true;
   }
 }
 return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = false

Q: 时间复杂度？
A: O(n2)。
Q: 有更优解？
A: 我想想。我可以用一个对象来存储当前元素和和值的差值。当我拿到一个新元素，如果这个元素的差值在对象中存在，那么我就能判断出是否存在。

function sumFinder(arr, sum){
 var differ = {}, 
   len = arr.length,
   substract;
 for(var i =0; i<len; i++){
   substract = sum - arr[i];
   if(differ[substract])
    return true;    
   else
    differ[arr[i]] = true;
 }
 return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = false

最大和

Q: 找到任意两个元素的最大总和？

A: 这实际上非常简单直接。 找到两个最大的数字并返回它们的总和

function topSum(arr){
 var biggest = arr[0], 
   second = arr[1], 
   len = arr.length, 
   i = 2;
 if (len<2) return null;
 if (biggest<second){
  biggest = arr[1];
  second = arr[0];
 } 
 for(; i<len; i++){
  if(arr[i] > biggest){
   second = biggest;
   biggest = arr[i];
  }
  else if (arr[i]>second){
   second = arr[i];
  }
 }
 return biggest + second;
}

统计零

Q: 统计从1到n的零总数？

A: 如果 n = 100，则0的数目将是11（0,10,20,30,40,50,60,70,80,90,100）。 请注意，100有两个0.这个看起来很简单，但有点棘手

说明：所以这里的重点是。 如果你有一个1到50的数字，那么这个数值就是5，就是50除以10.然而，如果这个数值是100，这个数值是11，你将得到100/10 = 10和 10/10 = 1。 那就是你将如何在一个数字中得到更多的零，如（100，200，1000）；

function countZero(n){
 var count = 0;
 while(n>0){
  count += Math.floor(n/10);
  n = n/10;
 }
 return count;
}
countZero(2014);
// = 223

子字符串

Q: 在字符串中匹配子字符串？

A: 在迭代字符串时将使用指针（一个用于字符串，另一个用于子字符串）。 然后用另一个变量来保存初始匹配的起始索引。

function subStringFinder(str, subStr){
 var idx = 0,
   i = 0,
   j = 0,
   len = str.length,
   subLen = subStr.length;
  for(; i<len; i++){
   if(str[i] == subStr[j])
     j++;
   else
     j = 0;
   //check starting point or a match  
   if(j == 0)
    idx = i;
   else if (j == subLen)
    return idx;
 }
 return -1;
}
subStringFinder(&#39;abbcdabbbbbck&#39;, &#39;ab&#39;)
// = 0
subStringFinder(&#39;abbcdabbbbbck&#39;, &#39;bck&#39;)
// = 9
//doesn&#39;t work for this one.
subStringFinder(&#39;abbcdabbbbbck&#39;, &#39;bbbck&#39;) 
// = -1

排列

Q: 如何获取字符串中的所有排列？

A: 根据您对算法的了解程度，这可能会很困难。、

function permutations(str){
  var arr = str.split(''),
    len = arr.length, 
    perms = [],
    rest,
    picked,
    restPerms,
    next;
  if (len == 0)
    return [str];
  for (var i=0; i<len; i++)
  {
    rest = Object.create(arr);
    picked = rest.splice(i, 1);
    restPerms = permutations(rest.join(&#39;&#39;));
    for (var j=0, jLen = restPerms.length; j< jLen; j++)
    {
      next = picked.concat(restPerms[j]);
      perms.push(next.join(&#39;&#39;));
    }
  }
  return perms;
}

上面是我整理给大家的，希望今后会对大家有帮助。

相关学习推荐：javascript视频教程

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!