Js基礎演算法有哪些

這次帶給大家Js基礎演算法有哪些，使用Js基礎演算法的注意事項有哪些，以下就是實戰案例，一起來看一下。

素數

Q：你會如何驗證一個質數？

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：可以。除數一次增加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

如果你無法理解也不用擔心，別管它。如果那你不是一個研究人員就沒關係。

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 <p style="text-align: left;"><span style="color: #ff0000">素數因子<strong></strong></span></p>Q：如何求出一個數的所有質數因子？ <p style="text-align: left;">A：執行一個while迴圈。開始除以2，如果不能整除，記錄這個除數，直到完成。 <br></p><pre class="brush:php;toolbar:false">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整除。因此，你不需要除以偶數。此外，你不會有一個大於其價值一半的因素。如果你想讓它變得複雜，那就用第一題的補充概念吧。

Fibonacci（斐波那契）

#Q：如何取得第n個斐波納契數字？

A： 我建立一個陣列並從迭代開始。

斐波那契系列是初學者的最受歡迎的面試問題之一。所以，你必須學習這一個。

方法1

function fibonacci(n){
 var fibo = [0, 1];
 if (n Q： 運行時間複雜度是多少？ <p style="text-align: left;"></p>A： O(n);<p style="text-align: left;"></p>Q： 你能讓它<p style="text-align: left;">遞迴<a href="http://www.php.cn/wiki/80.html" target="_blank">嗎？ </a></p><p style="text-align: left;">方法2<strong></strong></p><pre class="brush:php;toolbar:false">function fibonacci(n){
 if(n Q： 運行時間複雜度是多少？ <p style="text-align: left;">A： O(2n)；關於時間複雜度的細節<br></p><p style="text-align: left;"><span style="color: #ff0000">最大公約數<strong></strong></span></p>Q: 你會如何找到兩個數字的最大公約數？ <p style="text-align: left;"></p><pre class="brush:php;toolbar:false">function greatestCommonpisor(a, b){
 var pisor = 2, 
  greatestpisor = 1;
 //if u pass a -ve number this will not work. fix it dude!!
 if (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： 执行一个循环，并保存一个对象/关联数组。如果我第一次找到一个元素，我会设置它的值为真（这将告诉我元素添加一次）。如果我在对象中找到这个元素，我不会将它插入到返回数组中。

function removeDuplicate(arr){
 var exists ={},
  outArr = [], 
  elm;
 for(var i =0; i<arr.length removeduplicate><p style="text-align: left;"><span style="color: #ff0000"><strong>合并两个排序的数组</strong></span></p>
<p style="text-align: left;">Q： 怎样合并两个已排序数组？<br>A： 我将为每个数组保留一个指针（看代码，并注意这个）。</p>
<pre class="brush:php;toolbar:false">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 <p style="text-align: left;">不通过临时<a href="http://www.php.cn/wiki/70.html" target="_blank">变量</a>交换两个数的值</p><p style="text-align: left;">Q：如何在不使用临时变量的情况下交换两个数字？</p><pre class="brush:php;toolbar:false">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 != 'string' || str.length =0;i--){
  rtnStr.push(str[i]);
 }
 return rtnStr.join('');
}

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 <p style="text-align: left;">Q：这有效，但你可以做递归的方式吗？<br>A：可以。</p><p style="text-align: left;"><strong>方法4</strong></p><pre class="brush:php;toolbar:false">function reverse (str) {
  if (str === "") {
    return "";
  } else {
    return reverse(str.substr(1)) + str.charAt(0);
  }
}

方法5

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

function reverse(str){
 if(!str || str.length <p style="text-align: left;"><strong>方法6</strong></p><p style="text-align: left;">Q：你可以做反向函数作为字符串扩展吗？<br>A：我需要将这个函数添加到String.prototype，而不是使用str作为参数，我需要使用this</p><pre class="brush:php;toolbar:false">String.prototype.reverse = function (){
 if(!this || this.length <p style="text-align: left;"><span style="color: #ff0000"><strong>单词反转</strong></span></p><p style="text-align: left;">Q：你如何在句子中颠倒单词？<br>A：您必须检查整个字符串的空白区域。确定是否可能有多个空格。</p><pre class="brush:php;toolbar:false">//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 firstnonrepeatchar><p style="text-align: left;">这有一个问题，不能再循环中及时退出。</p>
<p style="text-align: left;"><span style="color: #ff0000"><strong>删除重复的字符</strong></span></p>
<p style="text-align: left;">Q: 怎样删除字符串中的重复字符？</p>
<p style="text-align: left;">A: 这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗？。</p>
<p style="text-align: left;">如果面试官说，这是区分大小写的，那么你就很轻松了。 如果他说不。你可以使用string.toLowercase（）来把字符串。面试官可能不喜欢这个方法。 因为返回字符串不会拥有相同的大小写。 所以</p>
<pre class="brush:php;toolbar:false">function removeDuplicateChar(str){
 var len = str.length,
   char, 
   charCount = {}, 
   newStr = [];
 for(var i =0; i<len removeduplicatechar><p style="text-align: left;"><span style="color: #ff0000"><strong>回文检查</strong></span></p>
<p style="text-align: left;">Q: 如何检查一个字符串是否是回文？</p>
<p style="text-align: left;">A: 把字符串反转，如果反转前后相等，那么它就是回文。</p>
<pre class="brush:php;toolbar:false">function isPalindrome(str){
 var i, len = str.length;
 for(i =0; i<len ispalindrome><p style="text-align: left;">或者</p>
<pre class="brush:php;toolbar: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 <p style="text-align: left;">注意： 这个会返回任意长度数组中缺失的那个</p><p style="text-align: left;"><span style="color: #ff0000"><strong>两数之和</strong></span></p><p style="text-align: left;">Q: 在一个未排序的数组中找出是否有任意两数之和等于给定的数？<br>A: 简单！双重循环。</p><pre class="brush:php;toolbar:false">function sumFinder(arr, sum){
 var len = arr.length;
 for(var i =0; i<len-1 sumfinder><p style="text-align: left;">Q: 时间复杂度？<br>A: O(n2)。<br>Q: 有更优解？<br>A: 我想想。我可以用一个对象来存储当前元素和和值的差值。当我拿到一个新元素，如果这个元素的差值在对象中存在，那么我就能判断出是否存在。</p>
<pre class="brush:php;toolbar:false">function sumFinder(arr, sum){
 var differ = {}, 
   len = arr.length,
   substract;
 for(var i =0; i<len sumfinder><p style="text-align: left;"><span style="color: #ff0000"><strong>最大和</strong></span></p>
<p style="text-align: left;">Q: 找到任意两个元素的最大总和？</p>
<p style="text-align: left;">A: 这实际上非常简单直接。 找到两个最大的数字并返回它们的总和</p>
<pre class="brush:php;toolbar:false">function topSum(arr){
 var biggest = arr[0], 
   second = arr[1], 
   len = arr.length, 
   i = 2;
 if (len 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 substringfinder><p style="text-align: left;"><span style="color: #ff0000"><strong>排列</strong></span></p>
<p style="text-align: left;">Q: 如何获取字符串中的所有排列？</p>
<p style="text-align: left;">A: 根据您对算法的了解程度，这可能会很困难。、</p>
<pre class="brush:php;toolbar:false">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><p>相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！</p>
<p>推荐阅读：</p>
<p style="text-align: left;"><a href="http://www.php.cn/js-tutorial-394797.html" target="_blank">你微信小程序登录鉴权使用技巧</a><br></p>
<p style="text-align: left;"><a href="http://www.php.cn/js-tutorial-394795.html" target="_blank">webpack模块热替换使用详解</a><br></p></len>

以上是Js基礎演算法有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！