Js 인터뷰 알고리즘에 대한 자세한 설명

AI의 등장으로 모든 사람들이 알고리즘에 점점 더 많은 관심을 기울이게 되었습니다. 프론트엔드 엔지니어로서 알고리즘은 종종 우리의 약점입니다. 이 기사는 외국 인터뷰 질문을 번역한 것입니다. 간단한 알고리즘 관련 면접 질문 나열

관련 기사 추천:2020년 가장 완벽한 js 면접 질문 모음(최신)

소수

Q: You How 소수를 확인할 수 있나요?

A: 소수는 자기 자신과 1로만 나누어질 수 있습니다. 그래서 while 루프를 실행하고 1을 더하겠습니다. (코드예제를 보시고 이해가 안된다면 별거 아닙니다. 돌아가서 javaScript의 기본을 먼저 배우고 다시 오세요.)

방법 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: 더 잘할 수 있나요? ?

A: 네. 제수는 한 번에 하나씩 증가합니다. 3 뒤에 2를 더할 수 있습니다. 숫자가 임의의 짝수로 나누어지면 2로도 나누어집니다.

추가됨: 이 숫자로 제수를 늘릴 필요가 없는 경우. 더 일찍 멈출 수 있습니다. 아래 단계에서 설명하겠습니다(필요한 경우 몇 번 더 읽으세요)

1단계, 어떤 숫자도 절반보다 큰 숫자로 나눌 수 없습니다. 예를 들어, 13은 7,8,9로 나누어지지 않습니다. 짝수의 절반이 될 수도 있습니다. 예를 들어, 16은 8로 나누어 떨어지지만 9, 10, 11, 12로는 나누어지지 않습니다...
결론: 숫자는 해당 값의 절반보다 큰 숫자로 나누어지지 않습니다. 따라서 루프를 50% 더 적게 반복할 수 있습니다.

두 번째 단계, 이제 숫자가 3으로 나누어 떨어지지 않으면. (3으로 나누어지면 소수가 아니다.) 그러면 해당 값의 1/3보다 큰 숫자로 나눌 수 없습니다. 예를 들어 35는 3으로 나누어지지 않습니다. 그러므로 35/3보다 큰 수로는 결코 나누어지지 않으며, 12, 13, 14로도 결코 나누어지지 않습니다. 36과 같은 짝수를 취하면 13, 14, 15로 결코 나누어지지 않습니다.

결론: 숫자는 해당 값의 1/3로 나누어집니다.

3단계, 예를 들어 127이라는 숫자가 있습니다. 127은 2로 나누어지지 않으므로 최대 63.5를 확인해야 합니다. 둘째, 127은 3으로 나누어지지 않습니다. 따라서 127/3 약 42를 확인하게 됩니다. 5로 나눌 수 없으며 약수는 127/5보다 작아야 하며 이는 7이 아닌 25 정도입니다. 그럼 어디에서 멈춰야 할까요?
결론: 제수는 math.sqrt(N)보다 작습니다.

방법 2

이해할 수 없더라도 걱정하지 말고 그대로 두세요. 연구자가 아니어도 상관없습니다.

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

소인수

Q: 숫자의 모든 소인수를 찾는 방법은 무엇인가요?
A: while 루프를 실행합니다. 2로 나누기를 시작합니다. 나눌 수 없는 경우에는 완료될 때까지 제수를 기록합니다.

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: 실행 시간 복잡성은 무엇입니까? 더 잘할 수 있나요?

A: O(n). 제수는 3부터 시작하여 최대 2까지 더할 수 있습니다. 왜냐하면 어떤 숫자가 짝수로 나누어지면 그 숫자는 2로도 나누어지기 때문입니다. 따라서 짝수로 나눌 필요가 없습니다. 또한 해당 값의 절반보다 큰 요소는 없습니다. 복잡하게 만들고 싶다면 질문 1의 보충 개념을 사용하세요.

피보나치(피보나치)

Q: n번째 피보나치 수를 구하는 방법은 무엇인가요?
A: 배열을 만들고 반복부터 시작합니다.

피보나치 수열은 초보자에게 가장 인기 있는 면접 질문 중 하나입니다. 그러므로 이것을 배워야 합니다.

방법 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: 실행 시간 복잡도는 무엇입니까?

A: O(n);

Q: 재귀적으로 만들 수 있나요?

방법 2

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

Q: 실행 시간 복잡도는 무엇입니까?
A: O(2n); 시간 복잡도에 대한 세부정보

최대 공약수

Q: 두 숫자의 최대 공약수를 어떻게 찾을 수 있나요?

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

알고리즘 패러다임

죄송합니다. 나도 설명할 수 없다. 나 자신은 80%의 시간 동안 그것을 이해할 수 없기 때문이다. 내 알고리즘 분석 코치가 나에게 이것을 말했고, 수업 노트에서 그것을 훔쳤습니다. (저는 좋은 학생이었습니다, 그런데!)

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

참고: 그것을 이해하려면 두뇌를 사용하세요.

중복 제거

Q: 배열에서 중복된 구성원을 어떻게 제거합니까?
A: 루프를 실행하고 객체/연관 배열을 저장합니다. 처음으로 요소를 찾으면 해당 값을 true로 설정합니다(이렇게 하면 해당 요소가 한 번 추가되었음을 알 수 있습니다). 객체에서 이 요소를 찾으면 이를 반환 배열에 삽입하지 않습니다.

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]

두 개의 정렬된 배열 병합

Q: 두 개의 정렬된 배열을 병합하는 방법은 무엇입니까?
A: 각 배열에 대한 포인터를 유지하겠습니다(코드를 보고 이를 기록해 두세요).

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]

임시 변수를 사용하지 않고 두 숫자의 값 교환하기

Q: 임시 변수를 사용하지 않고 두 숫자를 교환하는 방법은 무엇인가요?

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视频教程

위 내용은 Js 인터뷰 알고리즘에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!