JavaScript算法练习总结（二）

￡神魔★判官ぃ 2022-06-01 13:15 186阅读 0赞

**1、数制转换 回文用栈的方式**  
数制转换的基本思想：假设想将数字n转换为以b基数的数字，那么：

最高位为n%b,将此位压入栈。

使用n/b代替n。

重复步骤1和2，直到n = 0;且没有余数

持续将栈内元素弹出，直到栈为空，依次将这些元素排列，得到转换后数字的字符串形式即所需。

但有一点，这个转换的算法只针对于基数为2-9的情况。超过之后涉及到字母及ASCI 码等。

//栈
    function Stack() { 
        this.dataStore = [];
        this.top = 0;
        this.push = push;
        this.pop = pop;
        this.peek = peek;
        this.length = length;
    }
    
    function push(element) { 
        this.dataStore[this.top++] = element;
    }
    
    function pop(element) { 
        return this.dataStore[--this.top];
    }
    
    function peek() { 
        return this.dataStore[this.top - 1];
    }
    
    function length() { 
        return this.top;
    }
    
    function clear() { 
        this.top = 0;
    }
    
    //使用栈进行数制转换
    
    function mulBase(num, base) { 
        var s = new Stack();
        do {
            s.push(num % base);
            num = Math.floor(num /= base);
        } while (num > 0);
        var converted = "";
        while (s.length() > 0) {
            converted += s.pop();
        }
        return converted;
    }
    
    var num = 32;
    var base = 2;
    var newNum = mulBase(num, base);
    console.log(num + " convered to base " + base + " is " + newNum);
    num = 125;
    base = 8;
    var newNum = mulBase(num, base);
    console.log(num + " convered to base " + base + " is " + newNum);

**2、Sum All Numbers in a Range**   
题目：我们会传递给你一个包含两个数字的数组。返回这两个数字和它们之间所有数字的和。

最小的数字并非总在最前面。

//1.0
    function sumAll(arr) { 
        var max = Math.max(arr[0], arr[1]);
        var min = Math.min(arr[0], arr[1]);
        var newArr = [];
        for (var i = 0; i <= max - min; i++) {
            newArr[i] = min + i;
        }
        return newArr.reduce(function(a, b) {  return a + b; });
    }
    
    sumAll([1, 4]);
    //2.0
    function sumAll(arr) { 
        var sum = (arr[1] + arr[0]) * (Math.abs(arr[1] - arr[0]) + 1) / 2;
        return sum;
    }
    sumAll([1, 4]);

**3、Diff Two Arrays**  
比较两个数组，然后返回一个新数组，该数组的元素为两个给定数组中所有独有的数组元素。换言之，返回两个数组的差异。

我本来想的是先合到一个数组里，然后将数组中有相同的元素删除。但是这样就显得麻烦了一些。

改用FCC提示中的方法来写。

思路就是从数组1中过滤出和2中不同的添到新数组中。

从数组2中过滤出和1中不同的添到新数组中。 最后合成一个数组。

还有一种意思差不多 用indexOf方法判断某个元素是否在数组中，如果不在（返回-1），则把这个元素加到新数组内。

**4、Where art thou**   
写一个 function，它遍历一个对象数组（第一个参数）并返回一个包含相匹配的属性-值对（第二个参数）的所有对象的数组。如果返回的数组中包含 source 对象的属性-值对，那么此对象的每一个属性-值对都必须存在于 collection 的对象中。

例如，如果第一个参数是 \[\{ first: “Romeo”, last: “Montague” \}, \{ first: “Mercutio”, last: null \}, \{ first: “Tybalt”, last: “Capulet” \}\]，第二个参数是 \{ last: “Capulet” \}，那么你必须从数组（第一个参数）返回其中的第三个对象，因为它包含了作为第二个参数传递的属性-值对。

**5、Search and Replace**  
使用给定的参数对句子执行一次查找和替换，然后返回新句子。

第一个参数是将要对其执行查找和替换的句子。

第二个参数是将被替换掉的单词（替换前的单词）。

第三个参数用于替换第二个参数（替换后的单词）。

//1.0 if判断
    function myReplace(str, before, after) {
        if (before[0] == before[0].toUpperCase()) {
            after = after[0].toUpperCase() + after.slice(1);
        }
        str = str.replace(before, after);
        return str;
    }
    //2.0 使用正则
    function myReplace(str, before, after) {
        var reg = /^[A-Z]/;
        if (reg.test(before.charAt(0))) {
            after = after[0].toUpperCase() + after.slice(1);
        }
        str = str.replace(before, after);
        return str;
    }
    console.log(myReplace("A quick brown fox jumped over the lazy dog", "jumped", "leaped"));

**6、Pig Latin**  
把指定的字符串翻译成 pig latin。

Pig Latin 把一个英文单词的第一个辅音或辅音丛（consonant cluster）移到词尾，然后加上后缀 “ay”。

如果单词以元音开始，你只需要在词尾添加 “way” 就可以了。

[Pig Latin][] 被称为儿童黑话，

理解了儿童黑话的规则再写算法就会简单很多。

//1.0
    function translate(str) {
      var vowel = ["a","e","i","o","u"];
      if(vowel.indexOf(str[0]) >= 0){
        return str + "way";
      }
      while(vowel.indexOf(str[0]) < 0 ){
        str = str.substr(1) + str.substr(0,1);
      }
      return str+"ay";
    }
    translate("consonant");
    
    //2.0 正则表达式
    function translate(str) {
      var vowelIndex = /[aeuio]/.exec(str).index;
    
      return str.substr(vowelIndex) + (str.substr(0,vowelIndex) || "w") + "ay";
    }
    
    translate("glove");

**7、DNA Pairing**  
DNA 链缺少配对的碱基。依据每一个碱基，为其找到配对的碱基，然后将结果作为第二个数组返回。

Base pairs（碱基对） 是一对 AT 和 CG，为给定的字母匹配缺失的碱基。

在每一个数组中将给定的字母作为第一个碱基返回。

例如，对于输入的 GCG，相应地返回 \[\[“G”, “C”\], \[“C”,”G”\],\[“G”, “C”\]\]

字母和与之配对的字母在一个数组内，然后所有数组再被组织起来封装进一个数组。

//1.0
    function pair(str) { 
        var newStr = str.split('');
        var pair = '';
        var result = newStr.map(function(item, index, array) { 
            switch (item) {
                case 'A':
                    pair = 'T';
                    break;
                case 'T':
                    pair = 'A';
                    break;
                case 'G':
                    pair = 'C';
                    break;
                case 'C':
                    pair = 'G';
                    break;
            }
            return [item, pair];
        });
        return result;
    }
    
    pair("GCG");

//2.0
    function pair(str) {
        var f = {
            "A": "T",
            "T": "A",
            "G": "C",
            "C": "G"
        };
        return str.split('').map((cur) => { return [cur, f[cur]]; }); } pair("GCG");

**8、Missing letters**   
从传递进来的字母序列中找到缺失的字母并返回它。

如果所有字母都在序列中，返回 undefined。

//利用ASCI码差值转换
    function fearNotLetter(str) { 
        for (var i = 0; i < str.length; i++) {
            var value = str.charCodeAt(i + 1) - str.charCodeAt(i);
            if (value > 1) {
                return String.fromCharCode(str.charCodeAt(i) + 1);
            }
        }
        return undefined;
    }
    
    console.log(fearNotLetter("abce"));

**9、Sorted Union**  
写一个 function，传入两个或两个以上的数组，返回一个以给定的原始数组排序的不包含重复值的新数组。

换句话说，所有数组中的所有值都应该以原始顺序被包含在内，但是在最终的数组中不包含重复值。

非重复的数字应该以它们原始的顺序排序，但最终的数组不应该以数字顺序排序

> 部分解法来自于网络

[Pig Latin]: https://zh.wikipedia.org/wiki/%E5%85%92%E7%AB%A5%E9%BB%91%E8%A9%B1