算法基础

发表于 更新于 分类于 阅读次数： Disqus：

这部分习题难度不大，复习和巩固了很多数据结构基础部分提到的处理字符串和数组的方法，但是有些平时容易觉得自己明白的内容还是有很多迷惑人的地方，容易让习题出错。

我按照习题的顺序来梳理出现的知识点（以下是我自己的解法，可能不是最优方法），另外附加几个我觉得重点辨析在最后面：

Introduction to Basic Algorithm Scripting

  1. 摄氏度、华氏度换算 Convert Celsius to Fahrenheit
    这题很简单，会初中的一元一次方程就能写出来 
    1
    2
    3
    4
    5
    function convertToF(celsius) {
      let fahrenheit = celsius * 9/5 + 32;
      return fahrenheit;
    }
    convertToF(30);

  1. 字符串逆序处理 Reverse a String
    这题的目的是将字符串的顺序倒过来，可以联想到数组的.reverse()方法。所以解题方法是：

    1. 字符串转数组 string.split("");
    2. 数组逆序 array.reverse();
    3. 数组转字符串 array.join("");
    1
    2
    3
    4
    function reverseString(str) {
      return str.split("").reverse().join("");
    }
    reverseString("hello");

  1. 求阶乘 Factorialize a Number
    阶乘是高中知识了吧，我记得表达式应该是num！，表示1*2*3*…*n。所以这一题我用的是

    1. for循环，让变量i从1开始递增，并且让结果一开始为1
    2. 每一个i都与result想乘result *= i
    1
    2
    3
    4
    5
    6
    7
    8
    function factorialize(num) {
      let result = 1;
      for(let i = 1; i <= num; i ++) {
        result *= i;
      }
      return result;
    }
    factorialize(5);

  1. 查找字符串句子中最长的单词 Find the Longest Word in a String
    这题很容易在一开始的时候想到要两两比较，但是这样实在有些麻烦，而且效率也很低，要不停判断两个字符串的长度。我用的方法是：

    1. 把字符串转化成由单词组成的数组string.split(" ")
    2. 用array.sort()方法来对数组进行排序，排序规则是单词长度由长到短排列
    3. 新数组的第一个元素将是长度最长的单词，直接获取arr[0].length就可以得到结果了
    1
    2
    3
    4
    5
    function findLongestWordLength(str) {
      let arr = str.split(" ").sort((a, b) => b.length - a.length);
      return arr[0].length;
    }
    findLongestWordLength("The quick brown fox jumped over the lazy dog");

  1. 查找数组中最大的数组 Return Largest Numbers in Arrays
    这题和上一题的核心思路是一样的，不过这一题的参数数组是一个二维数组，需要将数组里的每个数组元素找出来，组成新的数组，所以比上一题多了一步。
    思路：

    1. 获取参数数组中的每一个数组元素，并获取其中最大的数字
    2. 将这个数组添加到新数组中
    3. 返回新数组作为结果

    这里我用了两个方法，思路上都是按照上述步骤来实现的，唯一的区别是获取参数数组中每个元素的方法

    • 方法1用的方法是for...in循环
    • 方法2用的是数组的map方法来遍历
    1
    2
    3
    4
    5
    6
    7
    8
    function largestOfFour(arr) {
      let resArr = [];
      for(let i in arr) {
        resArr.push(arr[i].sort((a, b) => b-a)[0]);
      }
      return resArr;
    }
    largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //方法2
    function largestOfFour(arr) {
      let result = [];
      arr.map(val=> {
      	val.sort((a, b)=>b-a);
      	result.push(val[0]);
      })
      return result;
    }
    console.log(largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]));

  1. 验证元素的结尾字符串 Confirm the Ending
    这题给了两个参数，一个str字符串，一个target字符串，需要验证str字符串是否以target字符串结尾。题干里也说了，这个函数最简单的验证方法是用字符串的endsWith()函数，但是这里需要我们用除了endsWith()函数之外的方法。这里我提供两个思路作为参考。

    第一个思路是获取str字符串的最后几位（位数和target参数的长度相等），然后和target字符串比较，看是否相等。这里有两个实现方法：

    1. 用字符串的string.slice(start, end)方法来获取字符串的最后几位，可以知道end对应的索引就是字符串的长度（即字符串的最后一位再多一位，因为slice函数取到end位，但不包含end位），start即str字符串长度减去target字符串长度；然后将这一部分字符串与target比较
    1
    2
    3
    4
    5
    6
    7
    8
    //思路1 实现1
    function confirmEnding(str, target) {
        if(str.slice(str.length - target.length, str.length) === target) {
      	return true;
      }
      return false;
    }
    confirmEnding("Bastian", "n");
    1. 第二种实现方法是用用string.indexOf()方法，我们常用string.indexOf()来检验字符串是否包含某个字符串，但是这样结果只能返回string字符串中首次出现target字符串的索引号，如confirmEnding("Congratulation", "on")就会返回"Con"中的"on"，因此我们还需要使用第二个参数，是一个可选参数，即从什么位置开始查找，这里我们和上面一种实现方法一样，从str.length-target.length开始查找
    1
    2
    3
    4
    5
    6
    7
    8
    //思路1 实现2
    function confirmEnding(str, target) {
        if(str.indexOf(target, str.length-target.length) > 0) {
      	return true;
      }
      return false;
    }
    confirmEnding("Bastian", "n");

    第二个思路就是用正则表达式来完成，其实用正则表达式更为直观，直接/target$/就可以了，这里写了两个实现方法只有细微区别，就是怎么写这个正则表达式，因为这里正则表达式需要包含变量。

    1. 正则表达式的第一个实现方法就是把正则表达式用eval()方法来连接变量和字符串
    1
    2
    3
    4
    5
    6
    7
     //方法2
     //字符串拼接的方法在正则里加入变量
     function confirmEnding(str, target) {
       let re = eval('/'+target+'$/');
       return re.test(str);
     }
    confirmEnding("Bastian", "n");
    1. 第二个实现方法是利用正则表达式的构造函数，把变量target和正则标识符加起来就行了
    1
    2
    3
    4
    5
    6
    7
    //方法2
    //用正则构造函数在正则里加入变量
    function confirmEnding(str, target) {
      let re = new RegExp(target+"$");;
      return re.test(str);
    }
    confirmEnding("Bastian", "n");

  1. 重复字符串Repeat a String Repeat a String
    这题和求阶乘的思路也差不多，就是用for循环来重复参数num次，每次在结果result字符串中添加一次参数str。这里需要注意的一个小坑是，我刚开始想要图方便，想的是让for循环中的i从1开始循环，这样直接在参数str后面添加str就好了，但是这里的一个坑是这样str在每次添加之后都变成了新的字符串，这样添加出来的字符串重复次数会超过num要求的次数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function repeatStringNumTimes(str, num) {
      let result = "";
      if(num < 0) {
        result = "";
      } else {
        for(let i = 0; i < num; i ++) {
          result += str;
        }
      }
      return result;
    }
    repeatStringNumTimes("abc", 3);

  1. 截取字符串Truncate a String
    这题的要求是给定两个参数str和num，如果num大于或等于str的长度，则直接返回str，如果num小于str的长度，则截取str的前num位，并加上...。

    这里我的做法是

    1. 对num与str的长度做判断，将结果分为两种状况，即num大于等于str.length和num小于str.length，这里的一个小技巧是两种结果返回的都是str，只不过小于的状况下，str会有变化，这样可以只判断num < str.length，总之都是return str，这样可以省略一步判断，让代码更简洁
    2. 截取字符串使用str.slice(start, end)函数，需要注意的是，str.slice(start, end)这一部分是我们需要的结果，但函数最终返回str，因此这里需要将str.slice(start, end)赋值给str
    1
    2
    3
    4
    5
    6
    7
    function truncateString(str, num) {
      if(num < str.length) {
        str = str.slice(0, num)+'...';
      }
      return str;
    }
    truncateString("A-tisket a-tasket A green and yellow basket", 8);

  1. 函数筛选数组元素Finders Keepers
    这题给了两个参数，一个数组arr和一个函数func，我们需要把符合函数func要求的第一个元素给找出来。这题挺简单的，毕竟连函数func的内容都给定了， 相当于筛选的条件已经写好了，我们只用将这个筛选条件套到数组上就行，所以用arr.filter(func)来获取所有满足func函数的元素，返回结果是一个新的数组，我们获取第一个元素即可。

    1
    2
    3
    4
    function findElement(arr, func) {
      return arr.filter(func)[0];
    }
    findElement([1, 2, 3, 4], num => num % 2 === 0);
  1. 判断元素是否为布尔值类型Boo who
    这题需要判断给的参数是不是布尔值，用typeof就可以获得参数的类型
1
2
3
4
5
6
7
function booWho(bool) {
  if(typeof bool === "boolean") {
    return true;
  }
  return false;
}
booWho(null);

  1. 所有单词首字母大写Title Case a Sentence
    做这道题的时候我被迷惑了一下，一下想到CSS里的capitalize，以为JS里也有这样简便的方法可以直接实现首字母大写，后来发现是我想多了。

    我实现的方法是分别让每个单词实现首字母大写，再还原成数组：

    1. 字符串转数组，还是用string.split()方法，这里需要注意的是不同于之前将单词字符串转为元素是字母的数组，直接用string.split("")，这里切成单词需要用空格作为切换标志，所以是string.split(" ")
    2. 用array.map()函数遍历数组中的每一个单词元素
    3. 实现首字母大写，每一个单词都是第一个字母大写str[0].toUpperCase()，剩余的字母小写，这里的一个小坑是容易理所当然觉得后面的字母直接截取就好了，但是这题里有的单词是大小写混用的，所以需要先str.toLowerCase()，然后截取除了第一个之外的部分substring(1, str.length)
    4. 数组还原成字符串，用array.join(" ")函数，注意怎么用空格切开就怎么用空格还原
    1
    2
    3
    4
    function titleCase(str) {
      return str.split(" ").map(val=>val[0].toUpperCase() + val.toLowerCase().substring(1, val.length)).join(" ");
    }
    titleCase("I'm a little tea pot");

  1. slice函数和splice函数Slice and Splice
    这里的的slice和splice函数对应的都是Array.prototype.slice和Array.prototype.splice函数，需要注意的是字符串也有slice函数String.prototype.slice()。

    • Array.prototype.slice()函数的作用是浅拷贝数组的一部分到一个新数组里，它返回的是一个新的数组，原数组不改变
      • array.splice() 拷贝array[0-end]
      • array.slice(start) 拷贝array[start, end]
      • array.slice(start, end)拷贝array[start, end]
    • Array.prototype.splice()函数的作用是删除部分元素，它返回的是删除的元素组成的数组，原数组会随之发生改变
      • array.splice(start)返回array[start-end]，原数组为[]
      • array.splice(start, count)返回array[start, start+count],原数组为[0, start].concat([start+count, end])
      • array.splice(start, count, ...items)返回array[start, start+count]，原数组添加...items元素，原数组为[0,start].concat([...items]).concat([start+count, end])
    1
    2
    3
    4
    5
    6
    7
    function frankenSplice(arr1, arr2, n) {
      let newArr = arr2.slice(0, n);
      newArr.splice(newArr.length, 0, ...arr1);
      newArr.splice(newArr.length, 0, ...arr2.slice(n));
      return newArr;
    }
    frankenSplice([1, 2, 3], [4, 5, 6], 1);

  1. 判断元素的布尔值Falsy Bouncer
    这题和第10题不太一样，是要判断哪些值的布尔值为false，把他们从数组中删除。

    1. 用array.filter()数组的筛选函数来筛查每个值
    2. 筛选的标准是元素的布尔值是true，可以直接用Boolean()函数
    1
    2
    3
    4
    5
    function bouncer(arr) {
      arr = arr.filter(val => Boolean(val) === true)
      return arr;
    }
    console.log(bouncer([7, "ate", "", false, 9]));

  1. 获取元素在数组中的位置Where do I Belong
    这题给定两个参数，一个数组arr和一个数字num，需要检测出如果将数字num添加到数组arr中之后，按升序排列，数字num在数组arr的哪个位置。

    1. 先将数字num添加到数组中，这里用push()或者shift()都无所谓
    2. 让数组arr按照升序排列，需要注意几个地方
      • array.sort()方法默认设置是将元素按照字符串Unicode码点来排列，也就是说1000会排在89后面，所以一定要加上排序规则array.sort((a, b) => a-b)
      • 排序规则array.sort((a, b) => a-b)实际上sort()函数内部是另一个函数compare(a, b), 如果这个函数的结果小于0，则a排在b前面，等于0，两者位置不变，结果大于0，则a排在b后面，所以这里要让他们升序，即前一个小于后一个数，用a-b，如果需要降序，则筛选条件是sort((a, b) => b -a)
      • Array.prototype.sort()函数返回的结果是排序后的原数组，即数组还是那个数组，只是顺序变了，所以不需要arr = arr.sort()这样来赋值给原数组
    3. 利用array.indexOf()就可以找到num在数组中的位置
    1
    2
    3
    4
    5
    6
    function getIndexToIns(arr, num) {
      arr.push(num);
      arr.sort((a, b) => a-b);
      return arr.indexOf(num);
    }
    getIndexToIns([40, 60], 50);

  1. 字符串的包含关系Mutations
    这题需要判断参数arr中的两个字符串，即arr[0]和arr[1]直接的包含关系，如果arr[0]包含arr[1]的所有字母，则返回true，否则返回false。需要注意的是arr[1]的字母在arr[0]中出现的顺序不一定和arr[1]本身的顺序完全一致。

    所以我设定了一个extra变量来检测arr[1]的每个字母是否都包含在arr[0]中：

    1. 将arr[1]转换成数组，并保证都是小写字母arr[1].toLowerCase().split("")
    2. 检验数组中的每个字母元素，筛选出没有出现在arr[0]中的元素array.filter()
    3. 判断这个新数组的长度，如果是空数组，则表明arr[0]包含了arr[1]中的所有字母，可以返回true，否则有字母是不在arr[0]中的，返回false
    1
    2
    3
    4
    5
    6
    7
    8
    function mutation(arr) {
      let extra = arr[1].toLowerCase().split("").filter(val => arr[0].toLowerCase().indexOf(val) === -1);
      if(extra.length > 0) {
        return false;
      }
      return true;
    }
    mutation(["hello", "hey"]);

  1. 切分数组Chunky Monkey
    这题给了数组arr和数字size两个参数，需要将数组arr按照size指定的长度来切分，返回的新数组是一个二维数组，里面的每一个元素是原数组切分出来的部分，长度即是size。

    一看到切分，很容易就想到array.slice()，只是需要确定一下开始和结束的位置，以size=2为例，切分的位置将是0-2, 2-4, 4-6...，用i*size, (i+1)*size就很容易得到切分的区域，但是还需要确定一下区分的次数，因为数组的长度不一定是size的整数倍，最后一个新数组里的元素可能长度并不正好是size的值，在slice()函数里，如果切分的结束为止多于数组的长度，则会自动忽略，所以我们用Math.ceil(arr.length/size)来确定切分的次数，然后在新的数组result里添加切分出来的小数组，即可获得结果。

    1
    2
    3
    4
    5
    6
    7
    8
    function chunkArrayInGroups(arr, size) {
      let result = [];
      for(let i = 0; i < Math.ceil(arr.length/size); i ++) {
        result.push(arr.slice(i * size, (i + 1) * size));
      }
      return result;
    }
    chunkArrayInGroups(["a", "b", "c", "d"], 2);

  • 辨析1： map(), reduce(), sort(), filter()

    这4个函数是JS的高阶函数，都非常好用，我不记得在哪个课上看到有老师把它们4个拎出来一起讲了，我的问题在于它们返回的值是什么，这决定了再使用的时候是否需要将使用它们的结果重新赋给原数组。所以这里一起回顾一下。

    • map方法的参数是一个函数，它返回一个新数组，里面的每个元素都是原数组中的元素调用函数之后的结果

      1
      2
      3
      const arr1 = [1, 2, 3];
      const arr2 = arr1.map(x => x * 2);
      console.log(arr2);  //[2, 4, 6]

    • reduce方法返回一个结果值，我记得老师当时说的这个叫汇总，就是对数组中的每个元素都执行一个函数操作，最后只返回一个值

      1
      2
      3
      const arr1 = [1, 2, 3];
      let result = arr1.reduce((a, b) => a + b);
      console.log(result);   //6

    • sort方法前面第14题提到了，是返回排序后的原数组，不产生新数组

      1
      2
      3
      4
      5
      const arr1 = [2, 3, 1];
      const arr2 = arr1.sort((a, b) => a-b);
      console.log(arr1);  //[1, 2, 3]
      console.log(arr2);  //[1, 2, 3]
      console.log(arr1 === arr2); // true

    • filter方法实现筛选/过滤功能，它的参数是一个函数，返回值是一个新的数组，数组内的元素都满足函数要求（千万不要记反了），原数组不变

      1
      2
      3
      4
      const arr1 = [2, 4, 5];
      const arr2 = arr1.filter(val => val > 3);
      console.log(arr1);  //[2, 4, 5]
      console.log(arr2);  //[4, 5]

  • 辨析2：map和forEach

    两个函数都用于遍历数组，且都能够对每个元素进行函数操作，区别在于

    • map返回一个新的数组，**forEach没有返回值**

      1
      2
      3
      4
      5
      6
      7
      const arr1 = [1, 2, 3];
      const arr2 = arr1.forEach(val => val + 1);
      console.log(arr2);  //undefined
      arr1.forEach(val => console.log(val + 1));
      //2
      //3
      //4

      可以理解成forEach是悄无声息地干了一些活儿，除非你主动问它是不是它干的，否则它不会主动告诉你

  • 辨析3：数组的splice和slice方法

    详解请见第12题

  • 辨析4：字符串的slice, substring, substr,split方法

    • 字符串的**slice方法与数组的slice方法类似，用于提取字符串的一部分，返回一个新的字符串**

      1
      2
      3
      4
      const str1 = 'hello world';
      const str2 = str1.slice(2, 3);
      console.log(str2);  //"l"
      console.log(str1);  //"hello world"

    • substring方法和slice方法基本相同，传入两个参数，一个是起点位置，一个是重点位置（不包含）

    • substr方法同样用于提取字符串的一部分，返回一个新的字符串，区别在于第二个参数是截取的长度

    • split方法用于切分字符串，它返回由切分的字符串组成的新数组

函数 用途 返回值
map() 遍历 返回一个新数组
reduce() 汇总 返回一个结果值
sort() 排序 返回排序后的原数组
filter() 筛选 返回满足筛选要求的新数组
forEach() 遍历 无返回值
splice() 删除/添加元素 返回由删除值组成的新数组，原数组随之改变
slice() 浅拷贝数组元素 返回新数组，原数组不变
slice(start, [,end]) 提取字符串 返回新的字符串
substring(start, [,end]) 提取字符串 返回新的字符串
substr(start,[,len]) 提取字符串 返回新的字符串
split() 切分字符串 返回一个新数组