FreeCodeCamp 算法题 1

浅浅的花香味﹌ 2022-04-27 22:54 140阅读 0赞

## 翻转字符串 (Reverse a String) ##

> 参考博客：[singsing.io/blog/fcc/ba…][singsing.io_blog_fcc_ba]
> 
> 题目要求：输入 'hello' 输出 'olleh'

思路一：

*  利用 Array.reverse() 进行反转
 *  利用 String.split() 进行 String => Array
 *  需要输出 String, 所以还要 Array.join() 进行 Array => String

function reverseString(str) {
      // 请把你的代码写在这里
      return str.split('').reverse().join('')
    }
    reverseString("hello"); // "olleh"
    复制代码

思路二：利用 for 循环遍历

*  String\[index\] 跟数组一样，有下标由 0 开始，ES5语法
 *  String.charAt(i) 这个则是 ES3语法

function reverseString(str) {
      let result = ''
      for(let i = str.length - 1; i >= 0; i--) {
        result += str[i]
      }
      return result
    }
    reverseString("hello"); // "olleh"
    复制代码

思路三： 利用递归

function reverseString(str) {
      if (str.length === 1) {
        return str
      } else {
        return reverseString(str.substr(1)) + str[0]
      }
    }
    reverseString("hello"); // "olleh"
    // 注意：递归涉及到两个因素，递归调用以及弹出过程。reverseString(str.substr(1)) 就是递归调用，+ str[0] 就是弹出过程
    复制代码

## 计算一个整数的阶乘 (Factorialize a Number) ##

> 参考博客：[singsing.io/blog/fcc/ba…][singsing.io_blog_fcc_ba 1]
> 
> 题目地址：[www.freecodecamp.cn/challenges/…][www.freecodecamp.cn_challenges]

计算一个整数的阶乘 如果用字母 n 来代表一个整数，阶乘代表着所有小于或等于n的整数的乘积。 阶乘通常简写成 n! 例如: 5! = 1 \* 2 \* 3 \* 4 \* 5 = 120

即：function (num) => num!

*  传统思路 while 循环

// 利用 while 循环
    function factorialize(num) {
      var result = 1;
      while(num > 1) {
        result *= num;
        num--;
      }
      return result;
    }
    
    factorialize(5); // 120
    复制代码

*  可不可以看成是一个累计数？

// 利用 reduce
    // Array(num)：新建一个数组 num 代表 length
    // Array.fill(0)：数组元素全部赋值为 0
    // Array.map(fn): 遍历函数每个元素，回调函数返回的作为新的数组的值
    // reduce(fn, initialAcc): 一个累计器
    // 回调函数 fn(acc, val, index, array) acc 为累计值， val 为当前项的值， index 下标， array 原来的数组
    // initialAcc 为 acc 的初始值，若无则默认为数组的第一项的值
    
    const factorialize = num => Array(num).fill(0).map((value, index) => index + 1).reduce((acc, val) => acc *= val, 1)
    factorialize(5) // 120
    复制代码

*  这个应该可以用递归

## 检查回文字符串 (Check for Palindromes) ##

> 题目：[www.freecodecamp.cn/challenges/…][www.freecodecamp.cn_challenges 1]
> 
> 参考博客：[singsing.io/blog/fcc/ba…][singsing.io_blog_fcc_ba 2]

首先回文字符串的意思就是字符串正着读和反着读是一样的。 比如：

*  aba 反转得到 aba，两者相同，return true
 *  abc 反转得到 cba，abc != cba，return false

然后字符串忽略大小写，忽略标点符号，空格：所以我们可以把忽略的标点符号和空格都替换掉，替换成空串('')，也可以看作是删掉标点符号和空格。

我们用到的替换字符串：`String.replace(regexp|substr, newSubStr|function)`

*  第一个参数是匹配的子串，可以是一个正则表达式，也可以是一个字符串
 *  第二个参数是替换的字符串，可以是一个字符串，也可以是一个函数返回的字符串

然后正则表达式匹配是可以用`$1, $2`

// 交换字符串中的两个单词
    var re = /(\w+)\s(\w+)/;
    var str = "John Smith";
    var newstr = str.replace(re, "$2, $1");
    // Smith, John
    console.log(newstr);
    复制代码

然后忽略大小写，我们统一转为小写：`String.toLowerCase()`这时候得到的就是一个有效的字符串。 这时候我们要反转字符串，简单的方法就是利用`Array.reserve()`去反转。

function palindrome(s) {
      const str =  s.replace(/[^a-zA-Z0-9]/g,'').toLowerCase() // 记得要加上g 全局匹配
      const strReverse = str.split('').reverse().join('')
      return str === strReverse
    }
    复制代码

## 找出最长单词 (Find the Longest word in a String) ##

> 题目：[www.freecodecamp.cn/challenges/…][www.freecodecamp.cn_challenges 2]
> 
> 参考博客：[singsing.io/blog/fcc/ba…][singsing.io_blog_fcc_ba 3]

思路是这样的：

1.  分割成一个个单词，字符串分割：`String.split()`
2.  然后遍历所有单词的长度，找出最大的，并返回该数值，字符串长度：`String.length`

我的代码：

function findLongestWord(str) {
      return str.split(' ').reduce((acc, val) => acc = acc < val.length ? val.length : acc, 0)
    }
    
    findLongestWord("The quick brown fox jumped over the lazy dog")
    复制代码

第一步：分割字符串基本没办法优化，所以不同的解法基本在第二步，找出一个数组中的最大值。为什么说是一个数组中的最大值呢，因为字符串分割后就变成了数组。

我的解法就是普通的，冒泡排序，遍历一次拿到最大值。

多种解法也就是在变相考如果求数组中最大的值：

*  array.reduce((acc, val) => acc > val ? acc : val)
 *  Math.max.apply(null, array)
 *  array.sort((a, b) => b - a)\[0\]

进而有

// 结合 Math.max(a, b) 会返回 a, b 间最大的值
    function findLongestWord(str) {
      // 第一版写法
      // return str.split(' ').reduce((acc, val) => acc = acc < val.length ? val.length : acc, 0)
      
      // 可以不用给 acc 赋值
      // return str.split(' ').reduce((acc, val) => acc < val.length ? val.length : acc, 0)
      
      // 结合 Math.max()
      return str.split(' ').reduce((a, b) => Math.max(a, b.length), 0)
    }
    
    
    // Math.max.apply(null, array)
    function findLongestWord(str) {
      return Math.max.apply(null, str.split(' ').map(item => item.length))
    }
    
    // Math.max + ...扩展运算符
    function findLongestWord(str) {
      return Math.max(...str.split(' ').map(item => item.length))
    }
    
    findLongestWord("The quick brown fox jumped over the lazy dog")
    
    // array.sort((a, b) => b - a)[0]
    function findLongestWord(str) {
      return str.split(' ').map(item => item.length).sort((a, b) => b - a)[0]
    }
    
    findLongestWord("The quick brown fox jumped over the lazy dog")
    复制代码

另外：Math.max() 使用 apply 和 ...扩展运算符的局限：当数组过大时，可能会出错。 这是因为函数的参数长度限制，在标准里头：Argument length limited to 65536，当然不同浏览器可能不一样。

> However, both spread (...) and apply will either fail or return the wrong result if the array has too many elements, because they try to pass the array elements as function parameters. See [Using apply and built-in functions][] for more details. The reduce solution does not have this problem.

## 句中单词首字母大写 (Title Case a Sentence) ##

> 题目：[www.freecodecamp.cn/challenges/…][www.freecodecamp.cn_challenges 3]
> 
> 参考博客：[singsing.io/blog/fcc/ba…][singsing.io_blog_fcc_ba 4]

// 这是我最初的想法
    function titleCase(str) {
      return str.toLowerCase().split(' ').map(item => item.replace(item[0], item[0].toUpperCase())).join(' ');
    }
    
    titleCase("I'm a little tea pot");
    复制代码

参考了博客的内容后，发现直接用`String.replace()`就可以了。博客里的其他遍历的方法，基本也是跟我类似的。

只是我用的是`replace`去替换，他里面用的是`slice`分割拼接

即：`String.replace(item[0], item[0].toUpperCase())`也可以换成`String[0] + String.slice(1)`

正则表达式，参考资料：[github.com/KRISACHAN/f…][github.com_KRISACHAN_f]

*  `()`代表分组，多次匹配
 *  `\s`代表匹配任何空白字符，所以适用于匹配空格
 *  `^`代表匹配开头
 *  `[a-z]`代表匹配小写字母的任意一个
 *  `g`全局匹配

需求：

*  匹配开头为小写字母的，或者开头为空白字符+小写字母 => `/(\s|^)[a-z]/g`
 *  替换成大写字母：`toUpperCase()` 要使用函数`item => item.toUpperCase()`不能直接用 `'$1'.toUpperCase()`
 *  另外`toUpperCase`会忽略掉不能转换的东西，比如特殊字符、大写字符和空格

最终代码：

function titleCase(str) {
      return str.toLowerCase().replace(/(\s|^)[a-z]/g, item => item.toUpperCase())
     }
    titleCase("I'm a little tea pot");
    复制代码

[singsing.io_blog_fcc_ba]: https://link.juejin.im?target=http%3A%2F%2Fsingsing.io%2Fblog%2Ffcc%2Fbasic-reverse-a-string
[singsing.io_blog_fcc_ba 1]: https://link.juejin.im?target=http%3A%2F%2Fsingsing.io%2Fblog%2Ffcc%2Fbasic-factorialize-a-number%2F
[www.freecodecamp.cn_challenges]: https://link.juejin.im?target=https%3A%2F%2Fwww.freecodecamp.cn%2Fchallenges%2Ffactorialize-a-number
[www.freecodecamp.cn_challenges 1]: https://link.juejin.im?target=https%3A%2F%2Fwww.freecodecamp.cn%2Fchallenges%2Fcheck-for-palindromes
[singsing.io_blog_fcc_ba 2]: https://link.juejin.im?target=http%3A%2F%2Fsingsing.io%2Fblog%2Ffcc%2Fbasic-check-for-palindromes%2F
[www.freecodecamp.cn_challenges 2]: https://link.juejin.im?target=https%3A%2F%2Fwww.freecodecamp.cn%2Fchallenges%2Ffind-the-longest-word-in-a-string
[singsing.io_blog_fcc_ba 3]: https://link.juejin.im?target=http%3A%2F%2Fsingsing.io%2Fblog%2Ffcc%2Fbasic-find-the-longest-word-in-a-string%2F
[Using apply and built-in functions]: https://link.juejin.im?target=https%3A%2F%2Fdeveloper.mozilla.org%2Fen-US%2Fdocs%2FWeb%2FJavaScript%2FReference%2FGlobal_Objects%2FFunction%2Fapply%23Using_apply_and_built-in_functions
[www.freecodecamp.cn_challenges 3]: https://link.juejin.im?target=https%3A%2F%2Fwww.freecodecamp.cn%2Fchallenges%2Ftitle-case-a-sentence
[singsing.io_blog_fcc_ba 4]: https://link.juejin.im?target=http%3A%2F%2Fsingsing.io%2Fblog%2Ffcc%2Fbasic-title-case-a-sentence%2F
[github.com_KRISACHAN_f]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2FKRISACHAN%2Ffront-end-project%2Ftree%2Fmaster%2Flearning%2Fregexp-JS