Js面试算法详解
素数
Q：你将如何验证一个素数？
A：一个素数只能被它自己和1整除。所以，我将运行一个while循环并加1。（看代码示例，如果你无法理解，那这不是你的菜。先回去学习javaScript基础知识然后再回来吧。）
方法1
functionisPrime(n){
vardivisor=2;
while(n>divisor){
if(n%divisor==0){
returnfalse;
}
else
divisor++;
}
returntrue;
}
isPrime(137);//=true
isPrime(237);//=false
Q：你能做得更好吗？
A：可以。除数一次增加1个。在3之后我可以增加2.如果一个数可以被任何偶数整除，它将被2整除。
补充：如果你不需要把除数增加到这个数。你可以更早停止。让我在下面的步骤中解释一下（如果需要可以多读几遍）
第一步，任何数字都不能被大于它的一半的数字整除。例如，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整除。
结论：一个数字可以被其数值的三分之一整除。
第三步，例如，你有一个数字127。127不能被2整除，因此你最多应该检查63.5。其次，127不能被3整除。因此，您将检查到127/3大约42。它不能被5整除，除数应该小于127/5大约25，而不是7。那么，我们该在哪里停下来？
结论：除数将小于math.sqrt（N）
方法2
如果你不能理解也不用担心，别管它。如果那你不是一个研究人员就没关系。
functionisPrime(n)
{
vardivisor=3,
limit=Math.sqrt(n);
//checksimplecases
if(n==2||n==3)
returntrue;
if(n%2==0)
returnfalse;
while(divisor<=limit)
{
if(n%divisor==0)
returnfalse;
else
divisor+=2;
}
returntrue;
}
isPrime(137);//=true
isPrime(237);//=false
素数因子
Q：如何求出一个数的所有素数因子？
A：执行一个while循环。开始除以2，如果不能整除，记录这个除数，直到完成。
functionprimeFactors(n){
varfactors=[],
divisor=2;
while(n>2){
if(n%divisor==0){
factors.push(divisor);
n=n/divisor;
}
else{
divisor++;
}
}
returnfactors;
}
primeFactors(69);//=[3,23]
Q：运行时间复杂度是多少？你能做得更好吗？
A：O(n)。可以将除数从3开始，累加2。因为，如果一个数被任何偶数整除，它将被2整除。因此，你不需要除以偶数。此外，你不会有一个大于其价值一半的因素。如果你想让它变得复杂，那就用第一题的补充概念吧。
Fibonacci（斐波那契）
Q：如何获得第n个斐波纳契数字？
A：我创建一个数组并从迭代开始。
斐波那契系列是面向初学者的最受欢迎的面试问题之一。所以，你必须学习这一个。
方法1
functionfibonacci(n){
varfibo=[0,1];
if(n<=2)return1;
for(vari=2;i<=n;i++){
fibo[i]=fibo[i-1]+fibo[i-2];
}
returnfibo[n];
}
fibonacci(12);//=144
Q：运行时间复杂度是多少？
A：O(n)；
Q：你能让它递归吗？
方法2
functionfibonacci(n){
if(n<=1){
returnn;
}else{
returnfibonacci(n-1)+fibonacci(n-2);
}
}
fibonacci(12);//=144
Q：运行时间复杂度是多少？
A：O(2n)；关于时间复杂度的细节
最大公约数
Q:你会如何找到两个数字的最大公约数？
functiongreatestCommonDivisor(a,b){
vardivisor=2,
greatestDivisor=1;
//ifupassa-venumberthiswillnotwork.fixitdude!!
if(a<2||b<2)
return1;
while(a>=divisor&&b>=divisor){
if(a%divisor==0&&b%divisor==0){
greatestDivisor=divisor;
}
divisor++;
}
returngreatestDivisor;
}
greatestCommonDivisor(14,21);//7
greatestCommonDivisor(69,169);//=1
算法范式
很抱歉。我也无法解释它。因为我自己80％的情况下都不能理解它。我的算法分析教练告诉我这个，又从课堂笔记偷走（我是一个好学生，顺便说一句！）
functiongreatestCommonDivisor(a,b){
if(b==0)
returna;
else
returngreatestCommonDivisor(b,a%b);
}
注意：用你的大脑来理解它。
去重
Q：你将如何从数组中删除重复的成员？
A：执行一个循环，并保存一个对象/关联数组。如果我第一次找到一个元素，我会设置它的值为真（这将告诉我元素添加一次）。如果我在对象中找到这个元素，我不会将它插入到返回数组中。
functionremoveDuplicate(arr){
varexists={},
outArr=[],
elm;
for(vari=0;i
合并两个排序的数组
Q：怎样合并两个已排序数组？
A：我将为每个数组保留一个指针（看代码，并注意这个）。
functionmergeSortedArray(a,b){
varmerged=[],
aElm=a[0],
bElm=b[0],
i=1,
j=1;
if(a.length==0)
returnb;
if(b.length==0)
returna;
/*
ifaElmorbElmexistswewillinserttomergedarray
(willgoinsidewhileloop)
toinsert:aElmexistsandbElmdoesn'texists
orbothexistsandaElm
不通过临时变量交换两个数的值
Q：如何在不使用临时变量的情况下交换两个数字？
functionswapNumb(a,b){
console.log('beforeswap:','a:',a,'b:',b);
b=b-a;
a=a+b;
b=a-b;
console.log('afterswap:','a:',a,'b:',b);
}
swapNumb(2,3);
//=beforeswap:a:2b:3
//=afterswap:a:3b:2
位操作：对不起，我无法向你解释这一点。KinjalDave建议到logicalconjunction理解它。将浪费您30分钟。
functionswapNumb(a,b){
console.log("a:"+a+"andb:"+b);
a=a^b;
b=a^b;
a=a^b;
console.log("a:"+a+"andb:"+b);
}
swapNumb(2,3);
//=a:2andb:3
//=a:3andb:2
字符串反向
Q：如何在JavaScript中反转字符串？
A：可以遍历字符串并将字母连接到新字符串。
方法1
functionreverse(str){
varrtnStr='';
for(vari=str.length-1;i>=0;i--){
rtnStr+=str[i];
}
returnrtnStr;
}
reverse('youareanicedude');
//="edudecinaerauoy"
Q：你知道在现代浏览器中串联效果很好，但在像IE8这样的旧浏览器中会变慢。还有什么不同的方法，可以扭转一个字符串？
A：当然.我可以使用数组，也可以添加一些检查。如果字符串是NULL或其他字符串，这将失败。让我也做一些类型检查。使用此数组类似于在某些服务器端语言中使用字符串缓冲区。
方法2
functionreverse(str){
varrtnStr=[];
if(!str||typeofstr!='string'||str.length<2)returnstr;
for(vari=str.length-1;i>=0;i--){
rtnStr.push(str[i]);
}
returnrtnStr.join('');
}
Q：运行时间复杂度是多少？
A：O(n)；
Q：可以做得更好？
A：我可以遍历索引的一半，它会节省一点点。（这是没用的，可能不会打动面试官）
方法3
functionreverse(str){
str=str.split('');
varlen=str.length,
halfIndex=Math.floor(len/2)-1,
revStr;
for(vari=0;i<=halfIndex;i++){
revStr=str[len-i-1];
str[len-i-1]=str[i];
str[i]=revStr;
}
returnstr.join('');
}
Q：这有效，但你可以做递归的方式吗？
A：可以。
方法4
functionreverse(str){
if(str===""){
return"";
}else{
returnreverse(str.substr(1))+str.charAt(0);
}
}
方法5
Q：你可以在方法中使用任何构建，使它更清洁吗？
functionreverse(str){
if(!str||str.length<2)returnstr;
returnstr.split('').reverse().join('');
}
方法6
Q：你可以做反向函数作为字符串扩展吗？
A：我需要将这个函数添加到String.prototype，而不是使用str作为参数，我需要使用this
String.prototype.reverse=function(){
if(!this||this.length<2)returnthis;
returnthis.split('').reverse().join('');
}
'abc'.reverse();
//='cba'
单词反转
Q：你如何在句子中颠倒单词？
A：您必须检查整个字符串的空白区域。确定是否可能有多个空格。
//haveatailingwhitespace
//fixthislater
//nowimsleepy
functionreverseWords(str){
varrev=[],
wordLen=0;
for(vari=str.length-1;i>=0;i--){
if(str[i]==''||i==0){
rev.push(str.substr(i,wordLen+1));
wordLen=0;
}
else
wordLen++;
}
returnrev.join('');
}
内置方法的快速解决方案：
functionreverseWords(str){
returnstr.split('').reverse();
}
原位反转
Q:如果你有一个字符串如”Iamthegoodboy”，怎样变为“Imaehtdoogyob”？注意这些单词位置不变但是被反转了。
A:要做到这一点，我必须做字符串反向和字反转。
functionreverseInPlace(str){
returnstr.split('').reverse().join('').split('').reverse().join('');
}
reverseInPlace('Iamthegoodboy');//="Imaehtdoogyob"
Q:ok。好的，你能不使用内置反向函数做到吗？
A:(内心独白)有没有搞错！！
//sumtwomethods.
//youcansimplysplitwordsby''
//andforeachwords,callreversefunction
//putreverseinaseparatefunction
//ifucantdothis,
//haveaglassofwater,andsleep
第一个非重复字符
Q:怎么在字符串中找到第一个非重复字符？
A:有什么条件吗？
A:比如是否区分大小写？
面试官可能会说No。
A:是长字符串还是短字符串？
Q:这些有什么关系吗？
A:例如，如果它是一个非常长的字符串，说一百万个字符，我想检查是否有26个英文字符正在重复。我可能会检查是否所有字符都在每200个字母中重复（例如），而不是循环遍历整个字符串。这将节省计算时间。
Q:简单起见，这个字符串是“thequickbrownfoxjumpsthenquicklyblowair”。
functionfirstNonRepeatChar(str){
varlen=str.length,
char,
charCount={};
for(vari=0;i
这有一个问题，不能再循环中及时退出。
删除重复的字符
Q:怎样删除字符串中的重复字符？
A:这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗？。
如果面试官说，这是区分大小写的，那么你就很轻松了。如果他说不。你可以使用string.toLowercase（）来把字符串。面试官可能不喜欢这个方法。因为返回字符串不会拥有相同的大小写。所以
functionremoveDuplicateChar(str){
varlen=str.length,
char,
charCount={},
newStr=[];
for(vari=0;i
回文检查
Q:如何检查一个字符串是否是回文？
A:把字符串反转，如果反转前后相等，那么它就是回文。
functionisPalindrome(str){
vari,len=str.length;
for(i=0;i
或者
functioncheckPalindrom(str){
returnstr==str.split('').reverse().join('');
}
类似的：在O(n)时间复杂度内判断一个字符串是否包含在回文字符串内。你能在O（1）时间解决问题吗？
找缺失的数字
Q:在一个1到100的未排序数组中找到缺失的数，你怎么做？
说明：数组中的数字为1到100。数组中只有一个数字缺失。数组未排序。找到缺少的数字。
A:你必须表现得像是在想很多。然后讨论n＝n（n＋1）／2的线性级数之和
functionmissingNumber(arr){
varn=arr.length+1,
sum=0,
expectedSum=n*(n+1)/2;
for(vari=0,len=arr.length;i
注意：这个会返回任意长度数组中缺失的那个
两数之和
Q:在一个未排序的数组中找出是否有任意两数之和等于给定的数？
A:简单！双重循环。
functionsumFinder(arr,sum){
varlen=arr.length;
for(vari=0;i
Q:时间复杂度？
A:O(n2)。
Q:有更优解？
A:我想想。我可以用一个对象来存储当前元素和和值的差值。当我拿到一个新元素，如果这个元素的差值在对象中存在，那么我就能判断出是否存在。
functionsumFinder(arr,sum){
vardiffer={},
len=arr.length,
substract;
for(vari=0;i
最大和
Q:找到任意两个元素的最大总和？
A:这实际上非常简单直接。找到两个最大的数字并返回它们的总和
functiontopSum(arr){
varbiggest=arr[0],
second=arr[1],
len=arr.length,
i=2;
if(len<2)returnnull;
if(biggestbiggest){
second=biggest;
biggest=arr[i];
}
elseif(arr[i]>second){
second=arr[i];
}
}
returnbiggest+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）；
functioncountZero(n){
varcount=0;
while(n>0){
count+=Math.floor(n/10);
n=n/10;
}
returncount;
}
countZero(2014);
//=223
子字符串
Q:在字符串中匹配子字符串？
A:在迭代字符串时将使用指针（一个用于字符串，另一个用于子字符串）。然后用另一个变量来保存初始匹配的起始索引。
functionsubStringFinder(str,subStr){
varidx=0,
i=0,
j=0,
len=str.length,
subLen=subStr.length;
for(;i
排列
Q:如何获取字符串中的所有排列？
A:根据您对算法的了解程度，这可能会很困难。、
functionpermutations(str){
vararr=str.split(''),
len=arr.length,
perms=[],
rest,
picked,
restPerms,
next;
if(len==0)
return[str];
for(vari=0;i
总结
以上所述是小编给大家介绍的Js面试算法详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！