FCC中级算法题

发表于 | 分类于 |

Pig Latin 儿童黑话

需求：
把指定的字符串翻译成 pig latin。
Pig Latin 把一个英文单词的第一个辅音或辅音丛（consonant cluster）移到词尾，然后加上后缀 “ay”。
如果单词以元音开始，你只需要在词尾添加 “way” 就可以了。
见过网上其他人的方法，都是先确定单词内是否具有元音字母，之后还需要你确定是否构成单词。

此处，为了简化代码，不做单词的验证，同时，第一次测试将实验直接验证首字母为元音是否可行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function translate(str) {
  var p=/[^aeiou]/;
  var index=0;
  //计算出第一个元音字母在字符串中的位置
  for(var i=0; i<str.length; i++){
    if(p.test(str.charAt(i))){
      continue;
    }  
    index = i;
    break;
  }
  //元音字母为首字母时，给字符串加way后缀
  if(index===0){
    str+='way';
  }
  //将辅音丛加至结尾,并加上'ay'后缀
  else{
    var arr=str.split('');
    var del=arr.splice(0,index);
    arr=arr.concat(del);
    str=arr.join('') + 'ay';
  }
  return str;
}
translate("glove") ;

DNA Pairing DNA配对

DNA 链缺少配对的碱基。依据每一个碱基，为其找到配对的碱基，然后将结果作为第二个数组返回。
Base pairs（碱基对） 是一对 AT 和 CG，为给定的字母匹配缺失的碱基。
在每一个数组中将给定的字母作为第一个碱基返回。
例如，对于输入的 GCG，相应地返回 [[“G”, “C”], [“C”,”G”],[“G”, “C”]]
字母和与之配对的字母在一个数组内，然后所有数组再被组织起来封装进一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function pair(str) {
  var newArr = str.split('');
  for(i=0;i<newArr.length;i++){
  switch (newArr[i]){
    case "G":newArr[i] = newArr[i]+"C";break;
      case "C":newArr[i] = newArr[i]+"G";break;
      case "A":newArr[i] = newArr[i]+"T";break;
      case "T":newArr[i] = newArr[i]+"A";break;
  }
    newArr[i] = newArr[i].split('');
    }
  return newArr;
}
pair("GCG");

Missing letter 消失的字母

从传递进来的字母序列中找到缺失的字母并返回它。
如果所有字母都在序列中，返回 undefined。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function fearNotLetter(str) {
  for(i=0;i<str.length;i++){
    var a = str.charCodeAt(i)-str.charCodeAt(i-1);
      if( a !== 1){
        for(j=0;j<a-1;j++){
          return String.fromCharCode(str.charCodeAt(i)-1);
        }
        }
      }
}
fearNotLetter("bcd");

Boo who

type of

1
2
3
4
5
function boo(bool) {
  return (typeof bool=='boolean');
}
boo([1, 2, 3]);

Sorted Union

写一个 function，传入两个或两个以上的数组，返回一个以给定的原始数组排序的不包含重复值的新数组。
换句话说，所有数组中的所有值都应该以原始顺序被包含在内，但是在最终的数组中不包含重复值。
非重复的数字应该以它们原始的顺序排序，但最终的数组不应该以数字顺序排序。

本题的思路在于，传入的实参数量是不一定的，因此，不能直接对几个形参使用array.concat();，使用arguments();来获取实参数值。然后进行去重。

1
2
3
4
5
6
7
8
9
10
function unite(arr1, arr2, arr3) {
  var newArr1 = Array.prototype.slice.call(arguments);
   newArr1 = newArr1.reduce(function(a,b){
     return a.concat(b);
   });
  var newArr2 = Array.from(new Set(newArr1));
  return newArr2;
}
unite([1, 3, 2], [5, 2, 1, 4], [2, 1]);

Convert HTML Entities

将字符串中的字符 &、<、>、” （双引号）, 以及 ‘ （单引号）转换为它们对应的 HTML 实体。

  1. 这里需要使用到str.match(),该函数可以返回匹配到的字符
  2. 关于正则中的几个修饰符
    • i：不分大小写
    • g:匹配所有（否则仅仅匹配一个）
    • m:多行匹配，搭配^和$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function convert(str) {
  var p = /[&<>"']/g;
  var HtmlEntities = {
    '&':'&amp;',
    '<':'&lt;',
    '>':'&gt;',
    "'":"&apos;",
    '"':'&quot;'
  };
  var arr = str.match(p);
  if(!arr){
    return str;
  }else{
    for(i=0;i<arr.length;i++){
      str = str.replace(arr[i],HtmlEntities[arr[i]]);
    }
  }
  return str;
}
convert("Dolce & Gabbana");

Spinal Tap Case

将字符串转换为 spinal case。Spinal case 是 all-lowercase-words-joined-by-dashes 这种形式的，也就是以连字符连接所有小写单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function spinalCase(str) {
  var newStr = '';
  if(str.match(/ /)){
    for(i=0;i<str.length;i++){
      str = str.replace(' ','-');
    }
     return str.toLowerCase();//首先判断，当单词之间有空格时，可直接替换
  }else{
     newStr = str.replace(/[^a-zA-Z]/g,"");
    var p = /[A-Z]/g;
  var arr = newStr.match(p);
  var newArr = newStr.split('');
  for(i=0;i<arr.length;i++){
   newArr.splice(newStr.indexOf(arr[i]),0,'-');//在每个大写字母前添加"-"
    newStr = newArr.join('');//由于添加完后的数组已经发生变化，索引和原始字符串不再一致，需要重新定义字符串
     /*var a = newStr.indexOf(arr[i]);
    var b= newStr.indexOf(arr[i+1]);
       newArr[i] = newStr.slice(a,b);*/
  }
   if(/[a-zA-z]/.test(newArr[0])){
      newStr = newArr.join('').toLowerCase();
   }else{
     newArr.shift();
     newStr = newArr.join('').toLowerCase();
   }
  // 如果首字母也为大写，那么需要进行判断来删除首字母前面添加的'-'
  return newStr;
    }
}
spinalCase("The_Andy_Griffith_Show");

Sum All Odd Fibonacci Numbers

给一个正整数num，返回小于或等于num的斐波纳契奇数之和。
斐波纳契数列中的前几个数字是 1、1、2、3、5 和 8，随后的每一个数字都是前两个数字之和。
例如，sumFibs(4)应该返回 5，因为斐波纳契数列中所有小于4的奇数是 1、1、3。

提示：此题不能用递归来实现斐波纳契数列。因为当num较大时，内存会溢出，推荐用数组来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var sumFibs = function() {
  var cache = [1,1];
  return function(num){
    if(num>=cache.length){
      for(var i= cache.length;i<num;i++){
        cache[i] = cache[ i-2 ] + cache [i - 1];
      }
    }
    var arr = cache.filter(function(ele){
      return ele%2 !== 0&&ele <= num;
    });
    return arr.reduce(function(a,b){
      return a+b;
    });
  };
}();
sumFibs(4);

Sum All Primes

求小于等于给定数值的质数之和。

只有 1 和它本身两个约数的数叫质数。例如，2 是质数，因为它只能被 1 和 2 整除。1 不是质数，因为它只能被自身整除。

给定的数不一定是质数。

首先需要了解求质数的算法，比较受推荐有两种。

  1. 首先尝试2，然后尝试只要尝试小于√x 的质数（因数的成对出现）；

  2. 筛法。首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……

刚开始的思路是，创建一个0-n的数组，对数组的value进行筛选,但是这样性能很差，数组内每个数字占内存较大，想到创建一个n的数组，获取索引值并判断，将布尔值存入数组索引位置，最后在获得索引值index，相加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function sumPrimes(num) {
   var newArr = Array(num+1).fill(true);
  newArr[0] = newArr[1] = false;
  for(i=2;i<= Math.sqrt(num);i++){
    if(newArr[i]){
      for(j=i;j*i<= num;j++){
        newArr[j*i] = false;
      }
    }
  }
  var resArr = [];
  for(x =0;x< newArr.length;x++){
    resArr.push(newArr.indexOf(true,x));
  }
  resArr = Array.from(new Set(resArr)).filter(function(val){
    return val>0;
  });
  return resArr.reduce(function(a,b){
    return a + b;
  });
}
sumPrimes(10);

Smallest Common Multiple最小公倍数

  1. 在此之前要了解欧拉算法求最大公约数。
    简单的说，求两个数的最大公约数，用大数对小数求模，如果能被整除，则小数是这两个数的最大公约数。
    如果不能整除，就用小数对余数再次求模，循环此过程直到返回能除尽的那个除数。就是最大公约数。
    比如20和15，用20除以15余数为5，然后用15除以余数5，能够整除，所以返回出来的除数5为这两个数的最大公约数。
  2. 有了最大公约数，就可以求最小公倍数。
    最小公倍数的求法是：彼此之间的乘积除以最大公约数。

因为是求几个连续自然数之间的公倍数，所以，求出前两个最小公倍数之后，用这个最小公倍数和下一个值比较。然后就得出了新的最小公倍数。主要用的是递归的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function smallestCommons(arr) {
  var resArr = [];
  arr = arr.sort(function(pre,next){
    return next-pre;
  });
  var max = function(m,n){
    if(m%n === 0){
      return n;
    }else{
      return max(n,m%n);
    }
  };
  var num = arr[1];
  for(var i = arr[1]+1;i<=arr[0];i++){
    num *=i/max(num,i);
  }
  return num;
}
smallestCommons([1,13]);

Finders Keepers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function find(arr, func) {
  var num = 0;
  for(i=0;i<arr.length;i++){
    if(func(arr[i])){
      num = arr[i];
      break;
    }
    }
  if (num === 0){
    return undefined;
  }
  return num;
}
find([1, 3, 5, 8, 9, 10],  function(num){ return num % 2 === 0; });

Drop it

让我们来丢弃数组(arr)的元素，从左边开始，直到回调函数return true就停止。

第二个参数，func，是一个函数。用来测试数组的第一个元素，如果返回fasle，就从数组中抛出该元素(注意：此时数组已被改变)，继续测试数组的第一个元素，如果返回fasle，继续抛出，直到返回true。

最后返回数组的剩余部分，如果没有剩余，就返回一个空数组。

我的思路是先先通过filter遍历后获得同伙函数的值，将遍历后数组的第一个元素与传入的arr数组进行indexOf索引匹配，然后用silce()分割即可，这里要注意，如果遍历后所得数组为空，需要做判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function drop(arr, func) {
  var newArr = arguments[0];// Drop them elements.
  newArr = newArr.filter(function(val){
    return func(val);
  });
  if(newArr.length!== 0){
    arr = arr.slice(arr.indexOf(newArr[0]));
  }
  else{
    arr = [];
  }
  return arr;
}
drop([1, 2, 3, 4], function(n) {return n > 5;});

Steamroller

对嵌套的数组进行扁平化处理。你必须考虑到不同层级的嵌套。
如果只在外面声明一个全局的新数组，那么无法得出新数组，而在函数内声明，则需要使用闭包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function steamroller(arr) {
  var result = [];
  function steam(ifarr){
    if(Array.isArray(ifarr)){
      return ifarr.forEach(function(val){
        return steam(val);
      });
    }else{
      result.push(ifarr);
    }
  }
  steam(arr);
  return result;
}
steamroller([1, [2], [3, [[4]]]]);

Binary Agents

传入二进制字符串，翻译成英语句子并返回。

二进制字符串是以空格分隔的。parseInt转换进制，map遍历数组

1
2
3
4
5
6
7
8
9
function binaryAgent(str) {
  var newArr = str.split(' ');
  newArr = newArr.map(function(val){
    return String.fromCharCode(parseInt(val,2));
  });
  return newArr.join('');
}
binaryAgent("01000001 01110010 01100101 01101110 00100111 01110100 00100000 01100010 01101111 01101110 01100110 01101001 01110010 01100101 01110011 00100000 01100110 01110101 01101110 00100001 00111111");

Everything Be True

完善编辑器中的every函数，如果集合(collection)中的所有对象都存在对应的属性(pre)，并且属性(pre)对应的值为真。函数返回ture。反之，返回false。

1
2
3
4
5
6
7
8
9
10
11
12
function every(collection, pre) {
  var counter = 0;// Create a counter to check how many are true.
  for(var i in collection){
     // Check for each object
    if(collection[i].hasOwnProperty(pre) && Boolean(collection[i][pre])){
      counter++;
    } // If it is has property and value is truthy
  }
  return counter == collection.length;
}// Outside the loop, check to see if we got true for all of them and return true or false
every([{"user": "Tinky-Winky", "sex": "male"}, {"user": "Dipsy", "sex": "male"}, {"user": "Laa-Laa", "sex": "female"}, {"user": "Po", "sex": "female"}], "sex");

Arguments Optional

创建一个计算两个参数之和的 function。如果只有一个参数，则返回一个 function，该 function 请求一个参数然后返回求和的结果。

例如，add(2, 3) 应该返回 5，而 add(2) 应该返回一个 function。

调用这个有一个参数的返回的 function，返回求和的结果：

var sumTwoAnd = add(2);

sumTwoAnd(3) 返回 5。

如果两个参数都不是有效的数字，则返回 undefined。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function add() {
  if(typeof arguments[0] !== 'number' || (arguments.length>1 && typeof arguments[1] !== 'number')){
    return undefined;
  }
  if(arguments.length!=2){
    var newArg = arguments[0];
    return function(num){
      if(typeof num !== 'number'){
        return undefined;
      }else{
        return newArg + num;
      }
    };
  }else{
    return arguments[0]+arguments[1];
  }
}