算法中级

这部分没有具体的知识点，全都以习题的形式来巩固之前的内容。这里我直接将题目和解答思路放上来：

---

Introduction to the Intermediate Algorithm Scripting Challenges

• Sum All Numbers in a Range 1. 求区间和

  题干： 第一题给定一个数组作为参数，数组中包含两个数字（大小顺序不定），需要求出这两个数字之间所有数字的和。我写了两个解法：

  第一个解法用for循环，循环出两个数字之间所有的数，让他们累加到result上。

  这里用到了Math.min(num1, num2)和Max.max(num1, num2).

  function sumAll(arr) {
    let result = 0;
    for(let i = Math.min(arr[0], arr[1]); i <= Math.max(arr[0], arr[1]); i ++) {
      result += i;
    }
    return result;
  }
  
  sumAll([1, 4]);

  第二个方法是小学学过的等差数列求合法，我还记得口诀：首项加末项的和，乘以项数除以2。这里需要注意项数的求法，首项减末项的绝对值加1

  function sumAll(arr) {
    return (arr[0]+arr[1])*(Math.abs(arr[0]-arr[1])+1)/2;
  }
  
  sumAll([1, 4]);

• Diff Two Arrays 2. 对比数组差别

  题干： 这题需要比较两个数组，返回一个新的数组，里面的元素只在其中一个数组出现过。

  这题本来看到重复第一反应是利用set来做，但是其实是只返回出现了一次的，也就是说重复的元素两个都需要去掉，所以set不太有用。我采用的方法是两个数组分别筛选出另一个数组里没有的元素，然后添加到新数组中。

  function diffArray(arr1, arr2) {
    let newArr = [];
    arr1.filter(ele => {
    	if(arr2.indexOf(ele) === -1){
    		newArr.push(ele);
    	}
    });
    arr2.filter(ele => {
    	if(arr1.indexOf(ele) === -1){
    		newArr.push(ele);
    	}
    });
    return newArr;
  }
  
  diffArray([1, 2, 3, 5], [1, 2, 3, 4, 5]);

• Seek and Destroy

  题干：这一题同样考察筛选排除。参数给定一个数组和不确定数量的数字，要筛选出数组里和给定数字不相等的元素，返回数组。这里很容易就想到了filter，但是怎么用filter，因为如果单纯用===去比较太麻烦了，而且不知道到底笔记几位，所以我想到的是把剩余的参数全部放进新数组里，比较方便的做法就是解构赋值（ES6的很多语法真的都非常好用），然后indexOf判断一下就OK了。

  需要注意的点是用args，不要有arguments，因为在Chrome中，arguments是保留关键字，无法直接用。

  function destroyer(...args) {
    let [, ...newArr] = args;
    return args[0].filter(ele => newArr.indexOf(ele) === -1);
  }
  
  destroyer([1, 2, 3, 1, 2, 3], 2, 3);

• Wherefore art thou

  题干：参数collection是一个包含若干对象的数组，参数source是一个对象，需要找出collection中包含了source对象中的值且值与source相等的对象，返回这些对象的集合数组

  这题首先会想到需要遍历collection中的每个对象，然后需要想到如何比较两个对象，所以我把比较对象的方法compare先单独存成一个变量，而且给定了一个参数默认值props，遍历props中的属性，比较collection中每个对象是否包含这个属性且属性值与source中一样，这里不必先判断hasOwnProperty，直接比较久可以了。最后查看不相等的值的个数。

  function whatIsInAName(collection, source) {
    let compare = function(obj, arr = Object.keys(source)){
      return arr.filter(prop => obj[prop] !== source[prop]);
    }
    return collection.filter(obj => compare(obj).length === 0);
  }
  
  whatIsInAName([{ first: "Romeo", last: "Montague" }, { first: "Mercutio", last: null }, { first: "Tybalt", last: "Capulet" }], { last: "Capulet" });

• Spinal Tap Case

  题干： 这题的要求是给定一个字符串，字符串由几个单词混合组成，连接单词的可能是空格，可能是_，也可能单词混合在一起，区分方法的首字母大写，要把这一组单词转换成由-连接的全是小写格式的字符串。

  这题麻烦的地方是需要考虑的情况比较多，可以从结果出发，我们其实需要做的是辨认出每个单词，由横线连接array.join('-'),然后转换成小写string.toLowerCase()，所以我们将单词区分出来放进一个数组就可以了，我的做法是：

  1. 先解决单词分开的情况，如果单词由空格或者_来连接，即不是单词和单词连接在一起的情况，我们用/[^A-Za-z]/来表示，然后以这个字符为标志切分字符串str.split(/[^A-Za-z]/)，这样会返回两种结果，一个是["a", "b", "c"]的数组，数组里面的每个元素不一定正好就是一个单独的单词，有可能是两个单词连在一起，后一个单词首字母大写的情况；还有一种是["abc"]，即单词没有区分开
  2. 接下来我们需要对切分获得的数组进行遍历，让里面的每个元素都执行一个函数，这个函数让他们能把连在一起的单词切分开，这里用到的正则是/[A-Z]?[a-z]+/g，表示第一个字母可能是大写，也可能是小写（句首单词可能都是小写），之后都是小写，这样可以遇到首字母大写的单词就切开，这样就返回一个二维数组。
  3. 分别对两个数组进行在-连接，如果数组中只有一个元素，那么连接不起作用，正好可以在不多用-的情况下把单词连接起来

  function spinalCase(str) {
    let arr = str.split(/[^A-Za-z]/);
    let re = /[A-Z]?[a-z]+/g;
    return arr.map(val => val.match(re).join("-")).join("-").toLowerCase();
  }
  
  spinalCase('This Is Spinal Tap');

• Pig Latin

  题干：这题的要求是给定一个参数字符串，如果参数字符串以元音字母开头，则直接在字符串末尾添加"way"，如果不是以元音字母开头，则将第一个元音字母之前的辅音字母挪到末尾，再添加"ay"。

  这里我用了一个很简单的正则判断元音字母，/[aeiou]/，然后找出第一个元音字母的位置，如果索引是0，即单词元音字母开头，则str+="way"，如果不是元音字母开头，则去掉开头的辅音字母str.slice(index)，再把辅音字母挪到末尾+str.slice(0,index)，再加上"ay"

  function translatePigLatin(str) {
    let re = /[aeiou]/;
    let index = str.match(re)===null? null:str.match(re).index;
    if(index === 0) {
      str += 'way';
    } else {
      str = str.slice(index) + str.slice(0, index) + "ay";
    }
    return str;
  }
  
  translatePigLatin("consonant");

• Search and Replace

  题干： 这题给定三个参数，第一个是一个字符串句子，第二、三个都是单词，需要在字符串句子中找到第二个参数，并替换成第三个

  这题其实很简单，核心就是string.replace(word1, word2)，唯一需要注意的是判断word1和word2是否首字母大写，这里用before[0] === before[0].toUpperCase()来判断就可以了，如果原单词都是小写，替换的单词就都是小写（没有改变），如果原单词首字母大写，替换的单词就首字母大写after = after[0].toUpperCase() + after.slice(1)

  function myReplace(str, before, after) {
    if(before[0] === before[0].toUpperCase()) {
      after = after[0].toUpperCase() + after.slice(1);
    } 
    return str.replace(before,after);
  }
  
  myReplace("A quick brown fox jumped over the lazy dog", "jumped", "leaped");

• DNA Pairing

  题干： 给定一个字符串，字符串只包含”C”, “G”, “A”, “T”四个字母，其中，[“C”, “G”]和[“A”, “T”]是两对基因，要求根据字符串的每个字母，找到对应的基因对，返回数组，里面每个元素都是对应的基因对，且基因对的第一个元素是字符串中的字母。

  这题有一个有点坑的点，我最开始想的是保存两个变量pair1和pair2，遍历字符串，让pair1.indexOf(string)，找到字母对应的基因对，如果index是0就返回这个数组，如果不是0就返回pair.reverse()，但是reverse()方法是直接修改数组的顺序，所以会导致最后输出的数组顺序都是一样的。

  最终的解决方案是把4种可能的基因对都放在一个数组里，遍历字符串的每个字母，去执行寻找功能，再遍历基因对的每一个数组，看看字母在哪个数组中的索引值是0，就在result数组中push这个数组。

  function pairElement(str) {
    let pairs = [["C", "G"], ["G", "C"], ["A", "T"], ["T", "A"]];
    let result = [];
    str.split("").map(val => {
      pairs.forEach(arr => {
        if(arr.indexOf(val) === 0) {
          result.push(arr);
        }
      })
    })
    return result;
  }
  
  pairElement("GCG");

• Missing letters

  题干：参数是一串按顺序排列的字符串，需要判断中间缺少了哪个字母，需要返回这个字母，如果不缺就返回undefined

  相邻字母的Unicode编码差1，利用这一点可以比较每个字母比后一个字母的编码是不是正好少1，如果不是，那这个字母之后就缺了一个字母，用String.fromCharCode可以获得这个字母

  function fearNotLetter(str) {
    for(let i = 0; i < str.length; i ++) {
      if(str.charCodeAt(i) - str.charCodeAt(i + 1) < -1) {
        return String.fromCharCode(str.charCodeAt(i) + 1);
      }
    }
    return undefined;
  }
  
  fearNotLetter("abce");

• Sorted Union

  题干： 参数是不定个数个数组，需要将这些数组组合起来，返回一个没有重复元素且顺序按照参数先后顺序的数组。

  一看到数组去重，现在会条件反射想到Set，因为比其他方法方便太多。这里我用变量all存储所有参数数组中的元素，然后利用new Set(all)来获得一个没有重复元素的数据Set，再利用Array.from(set)来将元素转换成数组

  function uniteUnique(...args) {
    let all = [];
    [...args].map(arr => all=all.concat(arr));
    return Array.from(new Set(all));
  }
  
  uniteUnique([1, 3, 2], [5, 2, 1, 4], [2, 1]);

• Convert HTML Entities

  题干：转换HTML转义符

  这题的思路是创建一个对象保存转义符，这样切换的时候可以统一使用string.replace(ele, entities[ele])的方法。然后使用正则把需要转义的内容筛选出来就可以了。

  function convertHTML(str) {
    let entities = {
      "<" : "&lt;",
      ">" : "&gt;",
      "&" : "&amp;",
      "'" : "&apos;",
      '"' : '&quot;'
    }
    let re = /[^A-Za-z\s]/g
    let arr = str.match(re);
    arr===null? str = str: arr.map(ele => str = str.replace(ele, entities[ele]));
    return str;
  }
  
  convertHTML("Dolce & Gabbana");

• Sum All Odd Fibonacci Numbers

  题干：这题需要求给定小于参数num的斐波那契数列中所有奇数的和。

  首先我们需要知道什么是斐波那契数列，从1, 1开始，后面每一个数字是前两个数字的和，

  function sumFibs(num) {
    let fibs = [1, 1];
    let oddSum = 2;
    while(true) {
    	let item = fibs[0] + fibs[1];
    	if(num < item) {
    		return oddSum;
    	}
    	if(item % 2) {
    		oddSum += item;
    	}
    	fibs[0] = fibs[1];
    	fibs[1] = item;
    }
  }
  
  sumFibs(4);

• Sum All Primes

  题干：求小于参数num的所有质数的和

  这题先确定怎么判断质数，然后再求和

  function sumPrimes(num) {
    let isPrime = function(num) {
    	for(let i = 2; i < num; i ++) {
    		if(num % i === 0) {
    			return false;
    		}
      }
    	return true;
    }
    let result = 0;
    for(let j = 2; j <= num; j ++) {
    	if(isPrime(j)){
    		result+=j;
    	}
    }
    return result;
  }
  
  sumPrimes(10);

• Smallest Common Multiple

  题干：求最小公倍数

  最大公倍数的求法是两个数相乘除以最大公约数，所以要先求出最大公约数。然后求积。

  function smallestCommons(arr) {
    function gcd(a, b){
      if(a % b === 0){
        return b;
      }
      return gcd(b, a % b);
    }
    var max = Math.max.apply(null, arr);
    var min = Math.min.apply(null, arr);
    var result = min;
    for(var i = min + 1; i <= max; i ++){
      result *= i / gcd(i, result);
    }
    return result;
  }
  
  
  smallestCommons([1,5]);

• Drop it

  题干：找出参数arr中第一个符合参数func条件的元素，并截取数组arr中自这个元素起的剩余部分

  我的解决方案是遍历数组arr.map，找出符合func条件的所有元素，并在indice数组中记录它们的索引值，sort()排序后取第一个值，利用数组的array.slice方法来截取数组

  function dropElements(arr, func) {
    let result= [];
    let indice = [];
    arr.map(val => {
      if(func(val) === true) {
      	indice.push(arr.indexOf(val));
      }
    })
    if(indice.length > 0) {
    	result = arr.slice(indice.sort()[0])
    }
    return result;
  }
  
  dropElements([1, 2, 3], function(n) {return n < 3; });

• Steamroller

  题干：这题的参数是一个多维数组，需要将里面的元素解析到一个一维数组中，作为结果返回

  像这类判断数据类型然后可能需要反复做同一个转换操作的内容肯定会用到递归思想，这里就是判断数组内的元素是不是数组，如果是数组就再解析，不是数组就直接push到结果内。

  需要注意的是如何判断一个元素是不是数组，我刚开始想到的是用typeof，但是马上就会发现其实有问题，因为typeof不适合判断复杂类型的数据，所以这里用到Object.prototype.toString.call(val)，结果也和typeof的结果略有不同，这里会返回一个数组转成的字符串[object Array]

  function steamrollArray(arr) {
    let result = [];
    arr.map(val => {
      if(Object.prototype.toString.call(val) === "[object Array]") {
        result = result.concat(steamrollArray(val));
      } else {
        result.push(val);
      }
    })
    return result;
  }
  
  steamrollArray([1, [2], [3, [[4]]]]);

• Binary Agents

  题干：将二进制参数转换成字符串

  核心知识点是parseInt(num, 2)将二进制编码转换成十进制数，和String.fromCharCode(num)将Unicode编码转换成字符串。用string.split将字符串切分成数组再遍历就可以了。

  function binaryAgent(str) {
    let result = "";
    str.split(" ").map(val => result += String.fromCharCode(parseInt(val, 2)));
    return result;
  }
  
  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

  题干：判断参数collection数组中是否都有pre这个属性，以及这个属性的值是否都为真

  像这类判断每个值的题，会很容易想到用map遍历，但是这样其实还需要再判断遍历之后返回的值，比较麻烦，如果用filter来筛选出不符合要求的元素，并且判断包含这些元素的数组的长度，如果长度为0则表示所有的元素都符合要求，如果不为0则表示有元素不符合，不需要判断具体长度，这样会方便一些。

  function truthCheck(collection, pre) {
    if(collection.filter(val=> Boolean(val[pre]) === false).length === 0){
    	return true;
    }
    return false;
  }
  
  truthCheck([{"user": "Tinky-Winky", "sex": "male"}, {"user": "Dipsy", "sex": "male"}, {"user": "Laa-Laa", "sex": "female"}, {"user": "Po", "sex": "female"}], "sex");

• Arguments Optional

  题干：给定不定数量的参数，如果判断类型，如果是数字就求和。

  这一题需要把情况列出来，我先判断了两个参数的情况，如果两个参数都是数字，直接求和，如果两个参数，不是全是数字，则返回undefined，如果只有一个参数，且是数字，则返回一个function，再判断这个新方法的新参数及求和

  function addTogether(...args) {
    if([...args].length === 2 && typeof [...args][0] === "number" && typeof [...args][1] === "number") {
  		return args[0] + args[1];
  	} else if ([...args].length === 2) {
  		return undefined;
  	} else if ([...args].length === 1 && typeof [...args][0] === "number") {
  		return function(arg) {
  			if(typeof arg !== "number") {
  				return undefined;
  			} else {
  				return args[0] + arg;
  			}
  		}
  	}
  }
  
  addTogether(2,3);

• Make a Person

  这一题考察对象的属性和方法，没什么难点，直接设定和获取就好了

  var Person = function(firstAndLast) {
    // Complete the method below and implement the others similarly
    let name = firstAndLast.split(" ");
    this.getFullName = function() {
      return name.join(" ");
    };
    this.getFirstName = function() {
      return name[0];
    }
    this.getLastName = function() {
      return name[1];
    }
    this.setFirstName = function(first) {
      name[0]= first;
    }
    this.setLastName = function(last) {
      name[1]= last;
    }
    this.setFullName = function(firstAndLast) {
      name = firstAndLast.split(" ");
    }
    return this;
  };
  
  var bob = new Person('Bob Ross');
  bob.getFullName();

• Map the Debris

  这一题唯一需要弄清楚的就是怎么计算这个公转周期。之后利用公式，也没有什么难度。

  function orbitalPeriod(arr) {
    var GM = 398600.4418;
    var earthRadius = 6367.4447;
    let result = [];
    arr.map(val => {
    	val.orbitalPeriod=Math.round(Math.sqrt(Math.pow((val.avgAlt+earthRadius), 3)/GM)*2*Math.PI);
    	val = {name: val.name, orbitalPeriod: val.orbitalPeriod};
    	result.push(val)
    })
    return result;
  }
  
  orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);