Js面试算法

AI的兴起,使得大家对算法的关注也越来越高。而作为一个前端工程师,算法很多时候是我们的弱点,本文译自国外一篇面试题。列出了一些简单算是跟算法相关的面试题。

素数

Q:你将如何验证一个素数?
A:一个素数只能被它自己和1整除。所以,我将运行一个while循环并加1。(看代码示例,如果你无法理解,那这不是你的菜。先回去学习javaScript基础知识然后再回来吧。)

方法1
  1. function isPrime(n){
  2. var divisor = 2;
  3. while (n > divisor){
  4. if(n % divisor == 0){
  5. return false;
  6. }
  7. else
  8. divisor++;
  9. }
  10. return true;
  11. }
  12. isPrime(137); // = true
  13. 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

如果你不能理解也不用担心,别管它。如果那你不是一个研究人员就没关系。

  1. function isPrime(n)
  2. {
  3. var divisor = 3,
  4. limit = Math.sqrt(n);
  5. //check simple cases
  6. if (n == 2 || n == 3)
  7. return true;
  8. if (n % 2 == 0)
  9. return false;
  10. while (divisor <= limit)
  11. {
  12. if (n % divisor == 0)
  13. return false;
  14. else
  15. divisor += 2;
  16. }
  17. return true;
  18. }
  19. isPrime(137); // = true
  20. isPrime(237); // = false

素数因子

Q:如何求出一个数的所有素数因子?
A:执行一个while循环。开始除以2,如果不能整除,记录这个除数,直到完成。

  1. function primeFactors(n){
  2. var factors = [],
  3. divisor = 2;
  4. while(n>2){
  5. if(n % divisor == 0){
  6. factors.push(divisor);
  7. n= n/ divisor;
  8. }
  9. else{
  10. divisor++;
  11. }
  12. }
  13. return factors;
  14. }
  15. primeFactors(69); // = [3, 23]

Q:运行时间复杂度是多少? 你能做得更好吗?
A:O(n)。可以将除数从3开始,累加2。因为,如果一个数被任何偶数整除,它将被2整除。因此,你不需要除以偶数。此外,你不会有一个大于其价值一半的因素。如果你想让它变得复杂,那就用第一题的补充概念吧。

Fibonacci(斐波那契)

Q:如何获得第n个斐波纳契数字?
A: 我创建一个数组并从迭代开始。

斐波那契系列是面向初学者的最受欢迎的面试问题之一。 所以,你必须学习这一个。

方法1
  1. function fibonacci(n){
  2. var fibo = [0, 1];
  3. if (n <= 2) return 1;
  4. for (var i = 2; i <=n; i++ ){
  5. fibo[i] = fibo[i-1]+fibo[i-2];
  6. }
  7. return fibo[n];
  8. }
  9. fibonacci(12); // = 144

Q: 运行时间复杂度是多少?
A: O(n);
Q: 你能让它递归吗?

方法2
  1. function fibonacci(n){
  2. if(n < =1) {
  3. return n;
  4. } else {
  5. return fibonacci(n-1) + fibonacci (n-2);
  6. }
  7. }
  8. fibonacci(12); // = 144

Q: 运行时间复杂度是多少?
A: O(2n);关于时间复杂度的细节

最大公约数

Q: 你会如何找到两个数字的最大公约数?

  1. function greatestCommonDivisor(a, b){
  2. var divisor = 2,
  3. greatestDivisor = 1;
  4. //if u pass a -ve number this will not work. fix it dude!!
  5. if (a < 2 || b < 2)
  6. return 1;
  7. while(a >= divisor && b >= divisor){
  8. if(a %divisor == 0 && b% divisor ==0){
  9. greatestDivisor = divisor;
  10. }
  11. divisor++;
  12. }
  13. return greatestDivisor;
  14. }
  15. greatestCommonDivisor(14, 21); // 7
  16. greatestCommonDivisor(69, 169); // = 1
算法范式

很抱歉。我也无法解释它。 因为我自己80%的情况下都不能理解它。 我的算法分析教练告诉我这个,又从课堂笔记偷走(我是一个好学生,顺便说一句!)

  1. function greatestCommonDivisor(a, b){
  2. if(b == 0)
  3. return a;
  4. else
  5. return greatestCommonDivisor(b, a%b);
  6. }

注意:用你的大脑来理解它。

去重

Q:你将如何从数组中删除重复的成员?
A: 执行一个循环,并保存一个对象/关联数组。如果我第一次找到一个元素,我会设置它的值为真(这将告诉我元素添加一次)。如果我在对象中找到这个元素,我不会将它插入到返回数组中。

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

合并两个排序的数组

Q: 怎样合并两个已排序数组?
A: 我将为每个数组保留一个指针(看代码,并注意这个)。

  1. function mergeSortedArray(a, b){
  2. var merged = [],
  3. aElm = a[0],
  4. bElm = b[0],
  5. i = 1,
  6. j = 1;
  7. if(a.length ==0)
  8. return b;
  9. if(b.length ==0)
  10. return a;
  11. /*
  12. if aElm or bElm exists we will insert to merged array
  13. (will go inside while loop)
  14. to insert: aElm exists and bElm doesn't exists
  15. or both exists and aElm < bElm
  16. this is the critical part of the example
  17. */
  18. while(aElm || bElm){
  19. if((aElm && !bElm) || aElm < bElm){
  20. merged.push(aElm);
  21. aElm = a[i++];
  22. }
  23. else {
  24. merged.push(bElm);
  25. bElm = b[j++];
  26. }
  27. }
  28. return merged;
  29. }
  30. mergeSortedArray([2,5,6,9], [1,2,3,29]);// = [1, 2, 2, 3, 5, 6, 9, 29]

不通过临时变量交换两个数的值

Q:如何在不使用临时变量的情况下交换两个数字?

  1. function swapNumb(a, b){
  2. console.log('before swap: ','a: ', a, 'b: ', b);
  3. b = b -a;
  4. a = a+ b;
  5. b = a-b;
  6. console.log('after swap: ','a: ', a, 'b: ', b);
  7. }
  8. swapNumb(2, 3);
  9. // = before swap: a: 2 b: 3
  10. // = after swap: a: 3 b: 2

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

  1. function swapNumb(a, b){
  2. console.log("a: " + a + " and b: " + b);
  3. a = a ^ b;
  4. b = a ^ b;
  5. a = a ^ b;
  6. console.log("a: " + a + " and b: " + b);
  7. }
  8. swapNumb(2, 3);
  9. // = a: 2 and b: 3
  10. // = a: 3 and b: 2

字符串反向

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

方法1
  1. function reverse(str){
  2. var rtnStr = '';
  3. for(var i = str.length-1; i>=0;i--){
  4. rtnStr +=str[i];
  5. }
  6. return rtnStr;
  7. }
  8. reverse('you are a nice dude');
  9. // = "edud ecin a era uoy"

Q:你知道在现代浏览器中串联效果很好,但在像IE8这样的旧浏览器中会变慢。 还有什么不同的方法,可以扭转一个字符串?
A:当然.我可以使用数组,也可以添加一些检查。如果字符串是NULL或其他字符串,这将失败。让我也做一些类型检查。使用此数组类似于在某些服务器端语言中使用字符串缓冲区。

方法2
  1. function reverse(str){
  2. var rtnStr = [];
  3. if(!str || typeof str != 'string' || str.length < 2 ) return str;
  4. for(var i = str.length-1; i>=0;i--){
  5. rtnStr.push(str[i]);
  6. }
  7. return rtnStr.join('');
  8. }

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

方法3
  1. function reverse(str) {
  2. str = str.split('');
  3. var len = str.length,
  4. halfIndex = Math.floor(len / 2) - 1,
  5. revStr;
  6. for (var i = 0; i <= halfIndex; i++) {
  7. revStr = str[len - i - 1];
  8. str[len - i - 1] = str[i];
  9. str[i] = revStr;
  10. }
  11. return str.join('');
  12. }

Q:这有效,但你可以做递归的方式吗?
A:可以。

方法4
  1. function reverse (str) {
  2. if (str === "") {
  3. return "";
  4. } else {
  5. return reverse(str.substr(1)) + str.charAt(0);
  6. }
  7. }
方法5

Q:你可以在方法中使用任何构建,使它更清洁吗?

  1. function reverse(str){
  2. if(!str || str.length <2) return str;
  3. return str.split('').reverse().join('');
  4. }
方法6

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

  1. String.prototype.reverse = function (){
  2. if(!this || this.length <2) return this;
  3. return this.split('').reverse().join('');
  4. }
  5. 'abc'.reverse();
  6. // = 'cba'

单词反转

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

  1. //have a tailing white space
  2. //fix this later
  3. //now i m sleepy
  4. function reverseWords(str){
  5. var rev = [],
  6. wordLen = 0;
  7. for(var i = str.length-1; i>=0; i--){
  8. if(str[i]==' ' || i==0){
  9. rev.push(str.substr(i,wordLen+1));
  10. wordLen = 0;
  11. }
  12. else
  13. wordLen++;
  14. }
  15. return rev.join(' ');
  16. }

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

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

原位反转

Q: 如果你有一个字符串如”I am the good boy”, 怎样变为 “I ma eht doog yob”? 注意这些单词位置不变但是被反转了。
A: 要做到这一点,我必须做字符串反向和字反转。

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

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

  1. //sum two methods.
  2. //you can simply split words by ' '
  3. //and for each words, call reverse function
  4. //put reverse in a separate function
  5. //if u cant do this,
  6. //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”。

  1. function firstNonRepeatChar(str){
  2. var len = str.length,
  3. char,
  4. charCount = {};
  5. for(var i =0; i<len; i++){
  6. char = str[i];
  7. if(charCount[char]){
  8. charCount[char]++;
  9. }
  10. else
  11. charCount[char] = 1;
  12. }
  13. for (var j in charCount){
  14. if (charCount[j]==1)
  15. return j;
  16. }
  17. }
  18. firstNonRepeatChar('the quick brown fox jumps then quickly blow air');// = "f"

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

删除重复的字符

Q: 怎样删除字符串中的重复字符?
A: 这与第一个非重复字符非常相似。你应该问一些类似的问题。它是区分大小写的吗?。
如果面试官说,这是区分大小写的,那么你就很轻松了。 如果他说不。你可以使用string.toLowercase()来把字符串。面试官可能不喜欢这个方法。 因为返回字符串不会拥有相同的大小写。 所以

  1. function removeDuplicateChar(str){
  2. var len = str.length,
  3. char,
  4. charCount = {},
  5. newStr = [];
  6. for(var i =0; i<len; i++){
  7. char = str[i];
  8. if(charCount[char]){
  9. charCount[char]++;
  10. }
  11. else
  12. charCount[char] = 1;
  13. }
  14. for (var j in charCount){
  15. if (charCount[j]==1)
  16. newStr.push(j);
  17. }
  18. return newStr.join('');
  19. }
  20. removeDuplicateChar('Learn more javascript dude'); // = "Lnmojvsciptu"

回文检查

Q: 如何检查一个字符串是否是回文?
A: 把字符串反转,如果反转前后相等,那么它就是回文。

  1. function isPalindrome(str){
  2. var i, len = str.length;
  3. for(i =0; i<len/2; i++){
  4. if (str[i]!== str[len -1 -i])
  5. return false;
  6. }
  7. return true;
  8. }
  9. isPalindrome('madam')
  10. // = true
  11. isPalindrome('toyota')
  12. // = false

或者

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

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

找缺失的数字

Q: 在一个1到100的未排序数组中找到缺失的数,你怎么做?
说明:数组中的数字为1到100。 数组中只有一个数字缺失。数组未排序。找到缺少的数字。
A: 你必须表现得像是在想很多。然后讨论n=n(n+1)/2的线性级数之和

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

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

两数之和

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

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

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

  1. function sumFinder(arr, sum){
  2. var differ = {},
  3. len = arr.length,
  4. substract;
  5. for(var i =0; i<len; i++){
  6. substract = sum - arr[i];
  7. if(differ[substract])
  8. return true;
  9. else
  10. differ[arr[i]] = true;
  11. }
  12. return false;
  13. }
  14. sumFinder([6,4,3,2,1,7], 9);
  15. // = true
  16. sumFinder([6,4,3,2,1,7], 2);
  17. // = false

最大和

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

  1. function topSum(arr){
  2. var biggest = arr[0],
  3. second = arr[1],
  4. len = arr.length,
  5. i = 2;
  6. if (len<2) return null;
  7. if (biggest<second){
  8. biggest = arr[1];
  9. second = arr[0];
  10. }
  11. for(; i<len; i++){
  12. if(arr[i] > biggest){
  13. second = biggest;
  14. biggest = arr[i];
  15. }
  16. else if (arr[i]>second){
  17. second = arr[i];
  18. }
  19. }
  20. return biggest + second;
  21. }

统计零

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);

  1. function countZero(n){
  2. var count = 0;
  3. while(n>0){
  4. count += Math.floor(n/10);
  5. n = n/10;
  6. }
  7. return count;
  8. }
  9. countZero(2014);
  10. // = 223

子字符串

Q: 在字符串中匹配子字符串?
A: 在迭代字符串时将使用指针(一个用于字符串,另一个用于子字符串)。 然后用另一个变量来保存初始匹配的起始索引。

  1. function subStringFinder(str, subStr){
  2. var idx = 0,
  3. i = 0,
  4. j = 0,
  5. len = str.length,
  6. subLen = subStr.length;
  7. for(; i<len; i++){
  8. if(str[i] == subStr[j])
  9. j++;
  10. else
  11. j = 0;
  12. //check starting point or a match
  13. if(j == 0)
  14. idx = i;
  15. else if (j == subLen)
  16. return idx;
  17. }
  18. return -1;
  19. }
  20. subStringFinder('abbcdabbbbbck', 'ab')
  21. // = 0
  22. subStringFinder('abbcdabbbbbck', 'bck')
  23. // = 9
  24. //doesn't work for this one.
  25. subStringFinder('abbcdabbbbbck', 'bbbck')
  26. // = -1

排列

Q: 如何获取字符串中的所有排列?
A: 根据您对算法的了解程度,这可能会很困难。、

  1. function permutations(str){
  2. var arr = str.split(''),
  3. len = arr.length,
  4. perms = [],
  5. rest,
  6. picked,
  7. restPerms,
  8. next;
  9. if (len == 0)
  10. return [str];
  11. for (var i=0; i<len; i++)
  12. {
  13. rest = Object.create(arr);
  14. picked = rest.splice(i, 1);
  15. restPerms = permutations(rest.join(''));
  16. for (var j=0, jLen = restPerms.length; j< jLen; j++)
  17. {
  18. next = picked.concat(restPerms[j]);
  19. perms.push(next.join(''));
  20. }
  21. }
  22. return perms;
  23. }

本文译自Thatjsdude- JS: Interview Algorithm

写于 2018年4月4日面试 4215

如非特别注明,文章皆为原创。

转载请注明出处: https://www.liayal.com/article/5ac46c20a6cf4e67bc05c9f4

你不想说点啥么?
😀😃😄😁😆😅😂🤣☺️😊😇🙂🙃😉😌😍😘😗😙😚😋😜😝😛🤑🤗🤓😎🤡🤠😏😒😞😔😟😕🙁☹️😣😖😫😩😤😠😡😶😐😑😯😦😧😮😲😵😳😱😨😰😢😥🤤😭😓😪😴🙄🤔🤥😬🤐🤢🤧😷🤒🤕😈👿👹👺💩👻💀☠️👽👾🤖🎃😺😸😹😻😼😽🙀😿😾👐👐🏻👐🏼👐🏽👐🏾👐🏿🙌🙌🏻🙌🏼🙌🏽🙌🏾🙌🏿👏👏🏻👏🏼👏🏽👏🏾👏🏿🙏🙏🏻🙏🏼🙏🏽🙏🏾🙏🏿🤝👍👍🏻👍🏼👍🏽👍🏾👍🏿👎👎🏻👎🏼👎🏽👎🏾👎🏿👊👊🏻👊🏼👊🏽👊🏾👊🏿✊🏻✊🏼✊🏽✊🏾✊🏿

评论

~ 评论还没有,沙发可以有 O(∩_∩)O~