算法基础

发表于 | 分类于 ， ，

算法基础

常用的jsAPI –孤枫_J

介绍

计算机算法是产生特定结果的一系列步骤。要写一个算法，你必须先理解一个特定的问题，然后编写代码去解决它。

将问题化整为零会让你更容易地解决问题。然后你就可以逐一解决这些子问题。例如，如果你要开发一个计算器，不要试图一下子解决整个问题，而是首先考虑怎样获取用户的输入，然后一个一个地实现每一种算术运算，最后实现运算结果的展示。

学习使用 JavaScript 来解决一些基础的算法问题。这会帮助你提升解决问题的能力，并为接下来解决更复杂的问题打下基础。

翻转字符串

反转给出的字符串。

你在反转字符串前可能需要将其切分成字符的数组。

你的结果必须是一个字符串。

笨方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function reverseString(str) {
  var str1 = str.split("");
  var temp;
  for(var i = 0,j = str1.length-1;i<str1.length/2;i++,j--)
  {
    temp = str1[i];
    str1[i] = str1[j];
    str1[j] = temp;
  }
  str = '';
  for(var k = 0;k<str1.length;k++)
    str += str1[k];
  return str;
}
reverseString("hello");

完美简洁版：

1
2
3
function reverseString(str) {
  return str.split('').reverse().join('');
}

先将字符串按每个字符切割，然后反转数组，最后再拼接成字符串。

数字的阶乘

返回一个给定整数的阶乘。

若 n 是一个整数，n 的阶乘就是所有小于等于 n 的正整数的乘积。

n 的阶乘通常用符号 n!来表示。

例如： 5! = 1 * 2 * 3 * 4 * 5 = 120

只有非负整数会被作为函数的输入参数。

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
function factorialize(num) {
  if(num == 0)
    return 1;
  else
  {
    var i = num;
    while(i-->2)
      num *= i;
    return num;
  }  
}

factorialize(5);

递归：

1
2
3
4
5
6
7
8
9
function factorialize(num)
{
	if(num === 0)
		return 1;
	else 
    return num*factorialize(num-1);
}

factorialize(5);

查找字符串中最长的单词

返回给出的句子中最长的单词的长度。

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
function findLongestWordLength(str) {
  var str1 = str.split(' ');
  var max = str1[0].length;
  for(var i = 1; i < str1.length; i++)
  {
    if(max<str1[i].length)
    max = str1[i].length; 
  }
  return max;
}

findLongestWordLength("The quick brown fox jumped over the lazy dog");

方法2：

使用.reduce() 了解.reduce()

1
2
3
4
5
6
function findLongestWordLength(s) {
  return s.split(' ')
    .reduce(function(x, y) {
      return Math.max(x, y.length)
    }, 0);
}

方法3：使用递归，我们检查是否str只剩下1个元素，那是最长的元素，然后返回它。如果第一个元素的长度大于第二个元素的长度（或相等），则删除第二个元素并递归调用function findLongestWord。反之删除第一个再调用。

返回数组中最大的数字

返回一个数组，它要由给出的所有子数组中的最大值组成。简单起见，给出的数组总会包含4个子数组。

最初版：

1
2
3
4
5
6
7
8
9
10
11
function largestOfFour(arr) {
  // You can do this! 
  var newArr = [];
  for(var i = 0;i<arr.length;i++)
  {
    newArr.push(arr[i].reduce((x,y)=>Math.max(x,y),0)); //这个0
  }
  return newArr;
}

largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

报错：largestOfFour([[17, 23, 25, 12], [25, 7, 34, 48], [4, -10, 18, 21], [-72, -3, -17, -10]])应该返回 [25, 48, 21, -3]。

调试发现程序返回的是[25,48,21,0]，困惑怎么会返回0，Math.max()可以使用在正数负数以及小数。再次查看.reduce()的方法发现填加末尾的0，是给定初始值为0，而不是-72，导致出错。不添加初始值则默认为数组第一个元素。

删去0即可ac。

1
newArr.push(arr[i].reduce((x,y)=>Math.max(x,y));

这道题使用.map()方法更为简洁

map() 方法创建一个新数组，其结果是该数组中的每个元素都调用一次提供的函数后的返回值。

1
2
3
4
5
function largestOfFour(arr) {
  return arr.map(function(group){
    return group.reduce((x,y)=>Math.max(x,y));
    })
}

高级：

1
2
3
function largestOfFour(arr) {
  return arr.map(Function.apply.bind(Math.max, null));
}

检查字符串的结尾

检查一个字符串（第一个参数， str）是否以给定的字符串（第二个参数 target）结束。

本题目可以用 ES2015 引入的 .endsWith()方法来解决。但本挑战的目的是使用 JavaScript 的一个 substring 方法。

1
2
3
4
5
6
7
8
9
10
11
12
function confirmEnding(str, target) {
  // "Never give up and good luck will find you."
  // -- Falcor
  var tar = target.length;
  var str1 = str.substring(str.length-tar-1);
  if(str1.indexOf(target)!=-1)
    return true;
  else 
    return false;
}

confirmEnding("Bastian", "n");

也可以使用.slice()方法：

1
2
3
4
5
6
7
8
function confirmEnding(str, target) {
  // "Never give up and good luck will find you."
  // -- Falcor
  
  return str.slice(str.length - target.length) === target;
}

confirmEnding("He has to give me a new name", "name");

重复字符串

将一个给定的字符串（第一个参数， str)重复 num（第二个参数）次。如果 num不是一个正数，返回一个空字符串。

1
2
3
4
5
6
7
8
9
function repeatStringNumTimes(str, num) {
  // repeat after me
  var str1 = '';
  for(var i = 0; i<num ; i++)
    str1 = str1.concat(str);   // str1 += str;
  return str1;
}

repeatStringNumTimes("abc", 3);
1
2
3
4
5
6
7
8
9
//递归版
function repeatStringNumTimes(str, num) {
  if(num < 0)
    return "";
  if(num === 1)
    return str;
  else
    return str + repeatStringNumTimes(str, num - 1);
}
1
2
3
4
//.repeat()版：
function repeatStringNumTimes(str, num) {
    return num > 0 ? str.repeat(num) : '';
}

截断字符串

如果一个字符串（第一个参数）的长度大于给出的值（第二个参数），则截断它并在其后加上 ...。返回被截断的字符串。

1
2
3
4
5
6
7
8
9
function truncateString(str, num) {
  if (str.length > num ) {
    return str.slice(0, num) + '...';
  } 
  else {
    return str;
  }
}
truncateString("A-tisket a-tasket A green and yellow basket", 8);

算法基础：发现者与看护者

请写一个函数来检查一个数组（第一个参数）中的元素，并返回数组中第一个通过校验测试（第二个参数，一个接受一个参数并返回一个布尔值的函数）的元素。如果没有元素通过测试，则返回 undefined。

1
2
3
4
5
6
7
8
9
function findElement(arr, func) {
  let num = 0;
  var arr1 = arr.filter(func); //每个成员执行函数func，返回通过的成员组成的新数组
  if(arr1)
    return arr1[0];
  return undefined;
}

findElement([1, 2, 3, 4], num => num % 2 === 0);

单词首字母大写

将给出的字符串中所有单词的第一个字母变成大写，并返回得到的字符串。请确保其余的字母是小写的。

出于练习的目的，“ the ”“ of ”等虚词的首字母也要大写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//简单易懂
function titleCase(str) {
  str = str.toLowerCase();
  var str1 = str.split(" ");
  var str2='';
  for(var i = 0;i<str1.length;i++)
  {
    str2 += str1[i].substring(0,1).toUpperCase()+str1[i].substring(1)+' ';
  }
  str2 = str2.trim(); //去除最后面的那个空格
  return str2;
}

titleCase("I'm a little tea pot");
1
2
3
4
5
//使用正则表达式
function titleCase(str) {
  return str.toLowerCase().replace(/(^|\s)\S/g, (L) => L.toUpperCase());
}
titleCase("I'm a little tea pot");

slice 和 splice

输入参数为：两个数组和一个索引值。

请利用数组的 slice和 splice方法，将第一个数组中的所有元素依次复制到第二个数组中。

请从第二个数组中索引值为 n的地方开始插入。

返回插入元素后的数组。输入的两个数组在函数执行前后要保持不变。

1
2
3
4
5
6
7
8
9
10
11
function frankenSplice(arr1, arr2, n) {
  var arr3 = arr2.slice();  //复制数组arr2
  for(var j = 0;j<arr1.length;j++)
    {
      arr3.splice(n,0,arr1[j]);  //添加到指定位置
      n++;
    }
  return arr3;
}

frankenSplice([1, 2, 3], [4, 5, 6], 1);

去除数组中的假值

从一个数组中移除所有假值（falsy values）。

JavaScript 中的假值有 false、null、0、""、undefined和 NaN。

提示：请尝试将每一个值转换为一个布尔值（boolean）。

1
2
3
4
5
function bouncer(arr) {
  return arr.filter(Boolean);
}

bouncer([7, "ate", "", false, 9]);

**filter()** 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。

我身在何处

返回数组（第一个参数）被排序后，将一个值（第二个参数）插入到该数组中而使数组保持有序的最小的索引。返回的值应该是一个数字。

例如，getIndexToIns([1,2,3,4], 1.5)应该返回 1因为 1.5 大于 1（索引为 0），但小于 2（索引为 1）。

同样地，getIndexToIns([20,3,5], 19)应该返回 2因为数组被排序后会变成 [3,5,20]，而 19小于 20（索引为 2）且大于 5（索引为 1）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getIndexToIns(arr, num) {
  // Find my place in this sorted array.
  arr.sort(function(a,b){
    return a-b;
  });
  for(var i = 0;i<arr.length;i++)
  {
    if(arr[i]>=num)
      return i;
  }
  return arr.length;
}

getIndexToIns([40, 60], 50);
1
2
3
4
5
//精简高级版
function getIndexToIns(arr, num) {
return arr.concat(num).sort((a,b) => a-b).indexOf(num);//一行
}
getIndexToIns([1,3,4],2);

集合之间的关系

输入参数是一个有两个字符串元素的数组。如果第一个字符串中包含了第二个字符串中的所有字母，则返回 true。

例如，["hello", "Hello"]应该返回 true 因为第一个字符串中包含了第二个字符串中出现的所有字母（忽略大小写）。

而 ["hello", "hey"]应该返回 false 因为第一个字符串 “hello” 没有包含字母 “y”。

最后，["Alien", "line"], 应该返回 true，因为 “line” 中的所有字母都被包含在 “Alien” 中。

1
2
3
4
5
6
7
8
9
10
11
12
function mutation(arr) {
  var a=arr[0].toLowerCase();
  var b=arr[1].toLowerCase();
  for(var i = 0;i<b.length;i++)
  {
    if(a.indexOf(b[i])<0)
    return false;
  }
  return true;
}

mutation(["hello", "hey"]);

​

猴子吃香蕉

写一个函数，将一个数组（第一个参数）分割成一组长度为 size（第二个参数）的数组，然后在一个二维数组中返回这些结果。

1
2
3
4
5
6
7
8
9
10
function chunkArrayInGroups(arr, size) {
  var arr2=[];
  for(var i = 0;i<arr.length;i+=size)
  {
    arr2.push(arr.slice(i,i+size));
  }
  return arr2;
}

chunkArrayInGroups(["a", "b", "c", "d"], 2);