AlgorithmsinJavaScript（附10个面试常用算法解法及思路）关注github，每日一道面试题详解Introduction面试过程通常从Aninitial电话面试开始，然后是现场面试，以检查编程技能和文化契合度。几乎无一例外，最终的决定因素是编码能力。通常，不仅要求得到正确答案，还要求有清晰的思维过程。在编码中，就像在生活中一样，正确的答案并不总是很清楚，但好的推理通常就足够了。推理能力有效地预测了学习、适应和进化的潜力。好的工程师永远在成长，好的公司永远在创新。算法挑战很有用，因为解决它们的方法不止一种。这为决策制定和决策计算提供了可能性。在解决算法问题时，我们应该挑战自己，从多个角度看待问题定义，然后权衡各种方法的利弊。经过足够多的试验，我们甚至可能会看到一个普遍的事实：没有“完美”的解决方案。要真正掌握算法，必须了解它们与数据结构的关系。数据结构和算法就像阴阳、杯和水一样密不可分。没有杯子就装不下水。没有数据结构，我们就没有对象可以应用逻辑。没有水，杯子是空的，没有营养。没有算法就不能转换或“消费”对象。要了解和分析JavaScript中的数据结构，请参阅JavaScript中的数据结构入门。在JavaScript中，算法只是将某种数据结构输入转换为某种数据结构输出的函数。函数内部的逻辑决定了如何转换。首先，应事先明确定义输入和输出。这就需要我们充分理解手头的问题，因为把问题分析透彻，不用写任何代码，自然就能得出解决方案。一旦你完全理解了问题，你就可以开始思考解决方案了。需要什么变量？有多少个循环？是否有JavaScript内置方法可以提供帮助？需要考虑那些边缘情况吗？复杂或重复的逻辑会使代码非常难以阅读和理解。能不能考虑抽象成多个函数？算法通常需要可扩展。随着输入大小的增加，函数将如何执行？是否应该有某种缓存机制？通常需要牺牲内存优化（空间）来换取性能提升（时间）。把问题具体化，画个图吧！当解决方案的具体结构开始出现时，伪代码就可以开始了。为了给面试官留下深刻印象，请提前寻找重构和重用代码的机会。有时可以将行为相似的函数组合成一个更通用的函数，该函数接受一个额外的参数。其他时候，函数curry效果更好。保证函数功能的测试和维护的绝对便利性也非常重要。换句话说，在做出解决问题的决策时需要考虑架构和设计模式。BigO（复杂度）为了计算算法的运行时复杂度，我们需要将算法的输入大小外推到无穷大，从而近似计算算法的复杂度。最优算法具有恒定的时间和空间复杂度。这意味着它不关心输入的数量增长多少，其次是对数时间复杂度或空间复杂度，然后是线性、二次和指数。最糟糕的是阶乘时间复杂度或空间复杂度。算法的复杂度可以用以下符号表示：Constabt：O(1)Logarithmic：O(logn)Linear：O(n)Linearithmic：O(nlogn)Quadratic：O(n^2)Expontential：O(2^n)Factorial:O(n!)在设计算法的结构和逻辑时，时间复杂度和空间复杂度的优化和权衡是重要的一步。数组最佳算法通常使用语言中固有的标准对象来实现。可以说，计算机科学中最重要的东西是数组。在JavaScript中，没有其他对象比数组拥有更多的实用方法。值得记住的数组方法有：sort、reverse、slice和splice。数组元素从索引0开始插入，因此最后一个元素的索引为array.length-1。数组在推元素方面有很好的性能，但是在数组中间插入、删除和查找元素的性能不是很好。JavaScript中数组的大小可以动态增长。数组的各种操作复杂度Push:O(1)Insert:O(n)Delet:O(n)Searching:O(n)OptimizedSearching:O(logn)Map和Set是类似于数组的数据结构。集合中的元素不重复。在地图中，每个项目都由一个键和一个值组成。当然也可以用对象来存储键值对，但是键必须是字符串。迭代与使用循环迭代数组的数组密切相关。在JavaScript中，有五种最常用的遍历方法，使用最多的是for循环，for循环可以按任意顺序遍历数组的索引。如果无法确定迭代次数，我们可以使用while和dowhile循环，直到满足某个条件。对于任何对象，我们都可以使用forin和forof循环遍历它的键和值。为了获得键和值，我们可以使用entries()。我们也可以随时使用break语句终止循环，或者使用continue语句跳出本次循环，进入下一个循环。本机数组提供以下迭代方法：indexOf、lastIndexOf、includes、fill、join。此外，我们可以在以下方法中提供回调函数：findIndex、find、filter、forEach、map、some、every、reduce。递归在一篇开创性的论文中，Church-Turing论文证明了任何迭代函数都可以用递归函数复制，反之亦然。有时递归方法更简洁、更清晰、更优雅。以这个迭代阶乘函数为例：constfactorial=number=>{letproduct=1for(leti=2;i<=number;i++){product*=i}returnproduct}如果使用递归，只需要一行需要代码const_factorial=number=>{returnnumber<2?1:number*_factorial(number-1)}所有递归函数都具有相同的模式。它们包括创建一个调用自身的递归部分和一个不调用自身的基本部分。每当函数调用自身时，都会创建一个新的执行上下文并将其推送到执行堆栈的顶部。这一直持续到满足基本情况为止。然后执行栈会将栈顶元素一个一个压入。因此，滥用递归会导致堆栈溢出错误。最后，我们一起来思考一些常见的算法问题吧！1.StringReversal一个函数接受一个字符串作为参数并返回反转后的字符串World!"),"!dlroWolleH");})})这道题思考的重点是我们可以使用数组自带的逆向方法。首先我们使用split方法将字符串转为数组，然后使用reverse将字符串反转，最后使用join方法将其转为字符串。或者，您可以使用数组的reduce方法。给定一个字符串，每个字符都需要访问一次。虽然这种情况发生了很多次，但时间复杂度归一化为线性。由于没有单独的内部数据结构，空间复杂度是常数。constreverse=string=>string.split('').reverse().join('')const_reverse=string=>string.split('').reduce((res,char)=>char+res)2.回文回文是发音一致的单词或短语。写一个函数来检查。describe("Palindrome",()=>{it("应该返回true",()=>{assert.equal(isPalindrome("雪茄？把它扔进罐子里，太悲剧了"),true);})it("Shouldreturnfalse",()=>{assert.equal(isPalindrome("sitadestlove"),false);})})思维函数只需要对输入的单词或词组进行简单的判断后反转是否和原来输入的一样，可以参考第一个问题的解答。我们可以使用数组的every方法来检查第i个字符是否与array.length-i-th字符匹配。但是这个方法会对每个字符检查2次，这是不必要的。那么，我们可以使用reduce方法。和问题1一样，时间复杂度和空间复杂度是一样的。constisPalindrome=string=>{constvalidCharacters="abcdefghijklmnopqrstuvwxyz".split("")conststringCharacters=string//过滤掉特殊符号。toLowerCase().split("").reduce((characters,character)=>validCharacters.indexOf(character)>-1?characters.concat(character):characters,[]);返回stringCharacters.join("")===stringCharacters.reverse().join("")3。Integerreversedto给定一个整数，反转数字的顺序。describe("整数反转",()=>{it("应该反转整数",()=>{assert.equal(reverse(1234),4321);assert.equal(reverse(-1200),-21);})})想想用toString方法把数字类型转成字符串，然后按照字符串倒置的步骤进行。反转完成后，使用parseInt方法转换回数字类型，然后使用Math.sign添加符号，只需要一行代码即可完成。该算法在空间和时间上也具有相同的复杂性，因为我们重用了字符串反转的逻辑。constrevserInteger=integer=>parseInt(number.toString().split('').reverse().join(''))*Math.sign(integer)4.最常出现的字符给定一个字符串，返回出现次数最多的字符频繁出现的字符describe("MaxCharacter",()=>{it("Shouldreturnmaxcharacter",()=>{assert.equal(max("HelloWorld!"),"l");})})思路可以创建一个对象，然后遍历字符串，将字符串的每个字符作为对象的key，value为对应字符出现的次数。那么我们就可以遍历这个对象，找到value最大的key。虽然我们使用两个单独的循环来迭代两个不同的输入（字符串和字符映射），但时间复杂度仍然是线性的。它可能来自字符串，但最终，字符映射的大小将达到一个极限，因为在任何语言中都只有有限数量的字符。空间复杂度是常数。constmaxCharacter=(str)=>{constobj={}letmax=0letcharacter=''for(letindexinstr){obj[str[index]]=obj[str[index]]+1||1}for(letiinobj){if(obj[i]>max){max=obj[i]character=i}}returncharacter}5.找出字符串中元音的个数，给一个单词或短语，统计元音出现的次数describe("Vowels",()=>{it("Shouldcountvowels",()=>{assert.equal(vowels("helloworld"),3);})})最容易想到的解决方案是使用正则表达式提取所有元音并对其进行计数。如果不允许使用正则表达式，我们可以简单地遍历每个字符并检查它是否是元音字母，这应该首先将输入参数转换为小写字母。这两种方法都具有线性时间复杂度和恒定空间复杂度，因为每个字符都需要检查并且临时基元可以忽略不计。constvowels=str=>{constchoices=['a','e','i','o','u']letcount=0for(letcharacterinstr){if(choices.includes(str[character])){count++}}returncount}constvowelsRegs=str=>{constmatch=str.match(/[aeiou]/gi)返回匹配？match.length:0}6.给定数组和大小的数组分隔符，将数组项拆分为给定大小的数组列表。describe("数组分块",()=>{it("应该实现数组分块",()=>{assert.deepEqual(chunk([1,2,3,4],2),[[1,2],[3,4]]);assert.deepEqual(块([1,2,3,4],3),[[1,2,3],[4]]);assert.deepEqual(块([1,2,3,4],5),[[1,2,3,4]]);})})一个好的解决方案是使用内置的slice方法。这会产生更清晰的代码。这可以通过while循环或for循环来实现，它们以给定大小的步长递增。这些算法都具有线性时间复杂度，因为每个数组项都需要访问一次。它们还具有线性空间复杂度，因为维护了内部“块”数组，该数组与输入数组成比例增长。constchunk=(array,size)=>{constchunks=[]letindex=0while(index
