FreeCodeCamp 算法题 #5
Comments
翻转字符串 (Reverse a String)
思路一：
function reverseString(str) {
// 请把你的代码写在这里
return str.split('').reverse().join('')
}
reverseString("hello"); // "olleh"思路二：利用 for 循环遍历
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)
计算一个整数的阶乘 即：function (num) => num!
// 利用 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
function factorialize(num) {
if (num > 1) {
return factorialize(num - 1) * num;
} else {
return 1;
}
}
factorialize(5); // 120
// 好像这种比较简洁
function factorialize(num) {
// 初始及弹出条件
if (num === 0) {
return 1;
}
// 递归调用
return num * factorialize(num - 1)
} |
检查回文字符串 (Check for Palindromes)
首先回文字符串的意思就是字符串正着读和反着读是一样的。
然后字符串忽略大小写，忽略标点符号，空格：所以我们可以把忽略的标点符号和空格都替换掉，替换成空串('')，也可以看作是删掉标点符号和空格。 我们用到的替换字符串：
然后正则表达式匹配是可以用 // 交换字符串中的两个单词
var re = /(\w+)\s(\w+)/;
var str = "John Smith";
var newstr = str.replace(re, "$2, $1");
// Smith, John
console.log(newstr);然后忽略大小写，我们统一转为小写： 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)
思路是这样的：
我的代码： 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")第一步：分割字符串基本没办法优化，所以不同的解法基本在第二步，找出一个数组中的最大值。为什么说是一个数组中的最大值呢，因为字符串分割后就变成了数组。 我的解法就是普通的，冒泡排序，遍历一次拿到最大值。 多种解法也就是在变相考如果求数组中最大的值：
进而有 // 结合 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，当然不同浏览器可能不一样。
|
句中单词首字母大写 (Title Case a Sentence)
// 这是我最初的想法
function titleCase(str) {
return str.toLowerCase().split(' ').map(item => item.replace(item[0], item[0].toUpperCase())).join(' ');
}
titleCase("I'm a little tea pot");参考了博客的内容后，发现直接用 正则表达式，参考资料：https://github.com/KRISACHAN/front-end-project/tree/master/learning/regexp-JS
需求：
最终代码： function titleCase(str) {
return str.toLowerCase().replace(/(\s|^)[a-z]/g, item => item.toUpperCase())
}
titleCase("I'm a little tea pot"); |
找出多个数组中的最大数 (Return Largest Numbers in Arrays)
思路：
// 初次解法
Array.map() 最合适
function largestOfFour(arr) {
return arr.map(item => Math.max(...item));
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);结合我们之前那个找出最长单词
// Math.max.apply(null, array)
function largestOfFour(arr) {
return arr.map(item => Math.max.apply(null, item));
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);
// Array.sort((a, b) => b - a)[0]
function largestOfFour(arr) {
return arr.map(item => item.sort((a, b) => b - a)[0]);
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);然后我们可以利用 // Array.reduce() 实现 Array.map() + Math.max()
function largestOfFour(arr) {
return arr.reduce((acc, val) => acc.concat(Math.max(...val)), []);
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);
// 为什么用的是 concat() 而不是 push()
// 因为 concat() 返回的是一个数组，而 push() 返回的是 Array.length
// 使用 push() 的话，我们要手动 return acc 值
// 像这样，不然的话会报错，push is not a function
function largestOfFour(arr) {
return arr.reduce((acc, val) => {
acc.push(Math.max(...val))
return acc
}, []);
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]); |
检查字符串结尾 (Confirm the Ending)
思路：
// 初次解法
function confirmEnding(str, target) {
return target === str.slice(-target.length);
}
confirmEnding("Bastian", "n");上面的是反向截取，如果我们要正向截取呢，那我们要知道从第几位开始。 比较
// slice
function confirmEnding(str, target) {
return target === str.slice(str.length - target.length);
}
confirmEnding("Bastian", "n");
// substr
function confirmEnding(str, target) {
return target === str.substr(str.length - target.length);
}
confirmEnding("Bastian", "n");
// substring
function confirmEnding(str, target) {
return target === str.substr(str.length - target.length);
}
confirmEnding("Bastian", "n");利用正则表达式，这个真没想过！
function confirmEnding(str, target) {
return RegExp(`${target}$`).test(str)
}
confirmEnding("Bastian", "n"); |
重复输出字符串 (Repeat a string repeat a string)
思路一：
function repeat(str, num) {
if (num < 0) return ''
return Array(num).fill(str).join('')
}
repeat("abc", 3);其实嘛，看了博客知道另外一种解法，感觉是我对
function repeat(str, num) {
if (num < 0) return ''
return Array(num + 1).join(str) // 注意：num + 1
}
repeat("abc", 3);思路二：直接用
function repeat(str, num) {
if (num < 0) return ''
return str.repeat(num)
}
const repeat = (str, num) => num > 0 ? str.repeat(num) : ''
repeat("abc", 3); |
截断字符串 (Truncate a string)
题目要求：
思路： function truncate(str, num) {
// num 小于等于3时
if (num < 4) {
return str.slice(0, num) + '...';
}
// num 大于字符串长度时
if (num >= str.length) return str;
return str.slice(0, num - 3) + '...';
}
truncate("A-tisket a-tasket A green and yellow basket", 11);使用三元运算符： function truncate(str, num) {
if (num < str.length) {
return str.slice(0, num > 3 ? num - 3 : num) + '...'
}
return str
}
truncate("A-tisket a-tasket A green and yellow basket", 11)其中 |
猴子吃香蕉, 分割数组 (Chunky Monkey)
题目要求：
解题思路：
// 因为 splice() 会改变原数组的长度，所以可以直接判断数组长度
function chunk(arr, size) {
var a = []
while(arr.length) {
a.push(arr.splice(0, size))
}
return a
}
chunk(["a", "b", "c", "d"], 2);
// 因为 slice() 不会修改原数组长度，所以用变量 i 去计数
function chunk(arr, size) {
var a = []
var i = 0
while(i < arr.length) {
a.push(arr.slice(i, i + size))
i += size
}
return a
}
chunk(["a", "b", "c", "d"], 2);
// 然后 push 和 concat 的区别就是返回值
// push 返回的是 arr.length
// concat 返回的是 一个新数组 |
截断数组 (Slasher Flick)
题目要求：返回一个数组被截断 n 个元素后还剩余的元素，截断从索引 0 开始。 大概意思就是：给你一个数组，和一个数字 n ，然后你返回这个数组从 0 开始删除掉 n 个元素的数组。 立马就可以想到：
// splice 解法
function slasher(arr, howMany) {
// 请把你的代码写在这里
arr.splice(0, howMany)
return arr
}
function slasher(arr, howMany) {
// 去掉多余的 arr
return arr.splice(0, howMany) && arr
}
slasher([1, 2, 3], 2);
function slasher(arr, howMany) {
return arr.slice(howMany)
}
slasher([1, 2, 3], 2);
function slasher(arr, howMany) {
for (let i = 0; i < howMany; i++) {
arr.shift()
}
return arr
}
slasher([1, 2, 3], 2); |
比较字符串 (Mutations)
如果数组第一个字符串元素包含了第二个字符串元素的所有字符，函数返回 true 。 思路：
function mutation(arr) {
const s1 = arr[0].toLowerCase()
const s2 = arr[1].toLowerCase()
let result = true
for (let i of s2) {
if (s1.indexOf(i) === -1) {
result = false
return result
}
}
return result;
}
mutation(["hello", "hey"]);
// 可以不用 result
function mutation(arr) {
const s1 = arr[0].toLowerCase()
const s2 = arr[1].toLowerCase()
for (let i of s2) {
if (s1.indexOf(i) === -1) {
return false
}
}
return true
}
mutation(["hello", "hey"])博客的思路：利用 function mutation(arr) {
var sourceStr = arr[0].toLowerCase();
var targetArr = arr[1].toLowerCase().split("");
var filteredArr = targetArr.filter(function (char) {
return sourceStr.indexOf(char) === -1;
})
return filteredArr.length === 0;
}
// 试一试
function mutation(arr) {
const s = arr[0].toLowerCase()
const a = arr[1].toLowerCase().split('')
return a.every(item => s.indexOf(item) !== -1)
}
// 简洁点
function mutation(arr) {
return arr[1].toLowerCase().split('').every(item => arr[0].toLowerCase().indexOf(item) !== -1)
}
mutation(["hello", "hey"]); |
过滤数组假值 (Falsy Bouncer)
删除数组中的所有假值。 思路： function bouncer(arr) {
return arr.reduce((arr, item) => item ? arr.concat(item) : arr, [])
}
bouncer([7, "ate", "", false, 9]);后面想想，上一题的 function bouncer(arr) {
return arr.filter(item => item)
// 博客里的是用了 !! 去做隐式转换，不知道有没有必要这样做。
// return arr.filter
}
bouncer([7, "ate", "", false, 9]);
// 然后 Boolean 是接受一个参数返回布尔值的构造函数，filter 接受的也是一个函数，该函数返回布尔值。
const bouncer = arr => arr.filter(Boolean) |
摧毁数组 (Seek and Destroy)
// 初次解法
function destroyer(...arr) {
const a1 = arr[0]
const a2 = arr.slice(1)
return a1.reduce((arr, val) => a2.indexOf(val) === -1 ? arr.concat(val) : arr, [])
}
destroyer([1, 2, 3, 1, 2, 3], 2, 3);再理解下题意，发现应该用的是 function destroyer(...arr) {
const a1 = arr[0]
const a2 = arr.slice(1)
return a1.filter(item => a2.indexOf(item) === -1)
}
destroyer([1, 2, 3, 1, 2, 3], 2, 3); |
数组排序并找出元素索引 (Where Do I belong)
题意： 解法一：
note：
function where(arr, num) {
arr.push(num)
arr.sort((a, b) => a - b)
return arr.indexOf(num)
}
where([40, 60], 50);解法二：不去排序，我们去遍历，然后计数 function where(arr, num) {
var count = 0;
for (var i = 0; i < arr.length; i++) {
if (arr[i] < num) {
count++;
}
}
return count;
}
where([40, 60], 50);
// 同样是遍历，只不过用的是 filter
function where(arr, num) {
return arr.filter(item => item < num).length;
}
// 当然你用 map, reduce 也行，map 麻烦一些，其实还是用了遍历 + 计数的方式
const where = (arr, num) => arr.reduce((acc, item) => item > num ? acc.concat(item) : acc, []).length
where([40, 60], 50); |
凯撒密码 (Caesars Cipher)
题意： 需要用到的：
function rot13(str) { // LBH QVQ VG!
var arr = str.split('');
return arr.map(item => /[A-Z]/.test(item) ? String.fromCharCode(item.charCodeAt() % 26 + 65) : item).join('');
}
rot13("SERR PBQR PNZC"); // 你可以修改这一行来测试你的代码
// /[A-Z]/.test(item) 只替换大写字符
// item.charCodeAt() % 26 + 65 只是因为 'A'.charCodeAt() => 65, x % n = [0, n - 1]
function rot13(str) { // LBH QVQ VG!
return str.replace(/[A-Z]/g, char => {
return String.fromCharCode(char.charCodeAt() % 26 + 65)
})
}
rot13("SERR PBQR PNZC"); // 你可以修改这一行来测试你的代码 |
给定范围内的数字总和 (Sum All Numbers in a Range)
题意：给一个数组，然后返回给定范围的数字总和。 例如：[1, 4] => 1+2+3+4=10 返回 10 数学公式解法：n + n+1 + n+2 + ... + m = (n+m)(m-n+1)/2 = (m^2-n^2+n+m)/2 function sumAll(arr) {
var a = arr[0], b = arr[1];
return (Math.abs(a*a - b*b) + a+b) / 2;
}
sumAll([1, 4]);循环叠加解法：首先要判断两数的大小，再循环叠加 function sumAll(arr) {
var a = arr[0], b = arr[1], result = 0;
if (a > b) {
// 交换
[a, b] = [b, a];
}
while(b >= a) {
result += a;
a++;
}
return result;
}
sumAll([1, 4]);博客的另一种解法：生成一个数组[n, n+1, n+2, ... , m]，再遍历求和。 function sumAll(arr) {
var numArr = Array.from({length: Math.abs(arr[0] - arr[1]) + 1}, (_, i) => i + Math.min.apply(null, arr));
return numArr.reduce((prev, next) => prev + next);
}
// 上面每次都要拿一次最小值，其实可以提取出来的
// 也可以用 Array() + Array.fill()
function sumAll(arr) {
var min = Math.min(...arr); // var min = Math.min.apply(null, arr);
var numArr = Array(Math.abs(arr[0] - arr[1]) + 1).fill(min);
return numArr.reduce((acc, val, index) => acc + val + index);
} |
比较两数组差异 (Diff Two Arrays)
题意：比较两个数组，然后返回一个新数组，该数组的元素为两个给定数组中所有独有的数组元素。换言之，返回两个数组的差异。 按照数学上集合来讲就是，两个集合并集减去它们的交集。 function diff(arr1, arr2) {
var sum = [...new Set([...arr1, ...arr2])];
return sum.filter(item => arr1.indexOf(item) === -1 || arr2.indexOf(item) === -1);
}
diff([1, 2, 3, 5], [1, 2, 3, 4, 5]);上面那个感觉有点麻烦，又是拼接数组，又是集合转数组，虽然可以去除，但是看起来复杂了。 可以直接拼接数组再过滤就行了。 function diff(arr1, arr2) {
return arr1.concat(arr2).filter(item => arr1.indexOf(item) === -1 || arr2.indexOf(item) === -1)
}
diff([1, 2, 3, 5], [1, 2, 3, 4, 5]); |
找出对象包含的特定键值对 (Where art thou)
题意：
// 首先返回的是数组，那么用 filter
// 其次是数组的元素里要包含对象的键值 Object.keys(obj) 返回给对对象可枚举属性(key)的字符串数组。
// 为什么是字符串数组，因为对象属性都会转为字符串。
function where(collection, source) {
return collection.filter(item => Object.keys(source).every(key => source[key] === item[key]));
}
where([{ first: "Romeo", last: "Montague" }, { first: "Mercutio", last: null }, { first: "Tybalt", last: "Capulet" }], { last: "Capulet" }); |
句中查找替换 (Search and Replace)
题意：
思路一：
function myReplace(str, before, after) {
var arr = str.split(' ');
if (before.slice(0, 1).charCodeAt() < 91) {
// 判断条件用正则表达式也ok /[A-Z]/.test(before[0])
after = after[0].toUpperCase() + after.slice(1);
}
arr.splice(arr.indexOf(before), 1, after);
return arr.join(' ');
}
myReplace("A quick brown fox jumped over the lazy dog", "jumped", "leaped");思路二：直接字符串替换
function myReplace(str, before, after) {
if (/[A-Z]/.test(before[0])) {
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 配对 (DNA Pairing)
题目意思就是：给你一段残缺的碱基，返回一段碱基对，碱基对有：A => T，C => G 输入：GCG 输出：[["G", "C"], ["C","G"],["G", "C"]] 思路：
// 这样的话，取的时候方便一些
var obj = {
'A': ['A', 'T'],
'T': ['T', 'A'],
'C': ['C', 'G'],
'G': ['G', 'C']
};
// 这样的话就要拼接
var obj = {
A: 'T',
T: 'A',
C: 'G',
G: 'C'
}function pair(str) {
// 这个对象的属性可以不同加引号，它会自动转换为字符串的。
var obj = {
A: ['A', 'T'],
T: ['T', 'A'],
C: ['C', 'G'],
G: ['G', 'C']
};
return str.split('').map(function(item) {
return obj[item];
});
}
pair("GCG");
function pair(str) {
var obj = {
A: 'T',
T: 'A',
C: 'G',
G: 'C'
};
return str.split('').map(function(item) {
return [item, obj[item]];
});
}
pair("GCG"); |
The text was updated successfully, but these errors were encountered: