基础javascript算法

终于把FCC的基础javascript算法做完了，来总结一下。

翻转字符串

先把字符串转化成数组，再借助数组的reverse方法翻转数组顺序，最后把数组转化成字符串。

function reverseString(str) {
  var arr = str.split("");
  var arrs = arr.reverse(); 
  var rts = arr.join("");
  return rts;
}
reverseString("hello");

主要用到了

str.split()分割字符串并生成数组。
arr.reverse()反转数组，把第一个转到最后一个，最后一个转到第一个。
arr.join()在数组中每两个元素中加入一个字符串组成新的字符串arr.join("")就是什么都不加入。

计算一个整数的阶乘

这个之前写过了，在这里

检测给定的字符是否是回文

这个之前也写过了，在这里

找到提供的句子中最长的单词，并计算它的长度

function change(a,b) {
  if(a.length > b.length) return -1;
  return 1;
}
function findLongestWord(str) {
  var arr = str.split(" ");
  var newArr = arr.sort(change);
  //return newArr.length;
  return newArr[0].length;
}
findLongestWord("The quick brown fox jumped over the lazy dog");

主要用到了sort排序，详细在这里

确保字符串的每个单词首字母都大写，其余部分小写。

function titleCase(str) {
  var newStr = str.toLowerCase();
  var arr = newStr.split(" ");
  for (var i = 0; i < arr.length; i++) {
    var char = arr[i].charAt(0);
    arr[i] = arr[i].replace(char,function rep(char) {
      return char.toUpperCase();
    });
  }
  var xstr = arr.join(" ");
    return xstr;
}
titleCase("sHoRt AnD sToUt");

用到了str.toLowerCase()，str.replace()和str.toUpperCase()

思路大概是：字符串换成小写，转换成数组。遍历数组找到每个字符串的首字母（用str.charAt()）。然后用str.replace()把首字母替换为大写。在把数组转换为字符串输出。

str.replace()方法：stringObject.replace(regexp/substr,replacement);regexp/substr为需要替换的对象，replacement为替换后的对象，可以为一个函数，比如文中用到的：

1
2
3

arr[i] = arr[i].replace(char,function rep(char) {
     return char.toUpperCase();
   });

返回数组中最大的数

右边大数组中包含了4个小数组，分别找到每个小数组中的最大值，然后把它们串联起来，形成一个新数组。
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]])应该返回[5,27,39,1001]

function change(a,b){
  if (a>b) return -1;
  return 1;
}
function largestOfFour(arr) {
  // You can do this!
  var maxx = [];
  var maxNum = [];
  for(var i = 0; i < arr.length; i++) {
    maxx[i] =  arr[i].sort(change);
    maxNum[i] = maxx[i][0];
  }
  return maxNum;
}
largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

依然用到sort排序。

思路：遍历数组，sort对数组排序，并传到新数组中对应的位置maxx[i] = arr[i].sort(change);然后找到各个数组中最大的数传到另一个数组中maxNum[i] = maxx[i][0];

检查一个字符串(str)是否以指定的字符串(target)结尾

function confirmEnding(str, target) {
  var targetL = target.length;
  var newStr = str.substring(str.length-targetL,str.length); 
  if (newStr == target) return true;
  return false;
}
confirmEnding("He has to give me a new", "name");

思路：截取字符串最后几位，检查是否等于给定的target

重要的事情说3遍！

重复一个指定的字符串 num次，如果num是一个负数则返回一个空字符串。

function repeat(str, num) {
  // repeat after me
  var newStr = str.split(" ");
  if (num < 0) return "";
  else {
    for (var i = 0; i < num; i++) {
      newStr[i] = str;
    }
    return newStr.join("");
  }
}
repeat("abc", 3);

思路：这个其实不难，就是不好想出来，新建一个数组，然后在i<num的时候开始循环，新数组的[i]对应给定的str，这样num是多少，就循环了多少遍，新数组中就有多少个元素。

截断一个字符串！

如果字符串的长度比指定的参数num长，则把多余的部分用…来表示。

切记，插入到字符串尾部的三个点号也会计入字符串的长度。

但是，如果指定的参数num小于或等于3，则添加的三个点号不会计入字符串的长度。

function truncate(str, num) {
  // Clear out that junk in your trunk
  var strSub;
  if (str.length > num) {
    if(num > 3) {
    strSub = str.substring(0,num-3);
      return strSub+"...";
    } else {
    strSub = str.substring(0,num);
      return strSub+"...";
    }
  }
  return str;
}
truncate("A-tisket a-tasket A green and yellow basket", 11);

主要用到了str.substring(start,end),从start处开始截取，到end处截止。
难点在与如果指定的参数num小于或等于3，则添加的三个点号不会计入字符串的长度。
这个要写if..else来判断

把一个数组按照指定的数组大小分割成若干个数组块。

chunk([1,2,3,4],2)=[[1,2],[3,4]];
chunk([1,2,3,4,5],2)=[[1,2],[3,4],[5]];

function chunk(arr, size) {
  // Break it up.
  var num1 = Math.floor(arr.length / size);
  var num2 = arr.length % size;
  var arr2 = [];
  if (num2 === 0) {
  for (var i = 0; i < num1; i++) {
    arr2[i] = arr.slice(i * size,size * (i + 1));
    //return arr2;
    } 
  }else  {
  for (var j = 0; j <= num1; j++) {
    arr2[j] = arr.slice(j * size,size * (j + 1));
    //return arr2;
    }
  }
  return arr2;
}
chunk([0, 1, 2, 3, 4, 5], 4);

用到arr.slice()来切割数组。

思路主要是：

先计算出分成几大段并赋值给num1，再计算出分段后剩余的（用求余计算）并赋值给num2；新建一个数组arr2。
开始判断，如果余数为0，也就是正好分段完没有剩余字符。此时进行遍历并储存切割后的字符
1
2
3
for (var i = 0; i < num1; i++) {
arr2[i] = arr.slice(i * size,size * (i + 1));
}

如果余数不为0，进行另一种赋值

1
2
3

for (var j = 0; j <= num1; j++) {
    arr2[j] = arr.slice(j * size,size * (j + 1));
    }

难点还是在于遍历的同时完成切割后字符的储存，之前一直想直接返回数组，结果只会返回第一个值。后来想了一个方法：新建一个数组，遍历的同时进行新数组第i个赋值，完美。

返回一个数组被截断n个元素后还剩余的元素，截断从索引0开始。

slasher([1, 2, 3], 2)应该返回 [3].
slasher([“burgers”, “fries”, “shake”], 1)应该返回 [“fries”, “shake”].

function slasher(arr, howMany) {
  // it doesn't always pay to be first
  return arr.slice(howMany,arr.length);
}
slasher([1, 2, 3], 2);

这个如果想到了还挺简单的,用arr.clice(),输入两个参数，一个起始位置，一个结束位置，就可以输出了。

如果数组第一个字符串元素包含了第二个字符串元素的所有字符，函数返回true。

mutation([“Mary”, “Army”])应该返回 true.
mutation([“hello”, “neo”])应该返回 false.

function mutation(arr) {
  var rarr = [];
 var str1 = arr[0].toLowerCase();
  var str2 = arr[1].toLowerCase();
  for (var i = 0; i < str2.length; i++) {
    rarr[i] = str1.indexOf(str2[i]);
  }
  var rstr = rarr.join("");
  if (rstr.indexOf("-1") >= 0) {
    return false;
  } return true;
}
mutation(["Mary", "Army"]);

思路：用str.indexOf()找到第二个字符串各个字符在第一个字符串中的位置（找不到为-1）并储存为一个新数组；然后对储存位置的数组进行判断，找到数组中-1（也就是不被字符串1包含的字符）的位置，如果>=0，就意味着位置数组中确实存在值为-1的元素，也就是第二个字符串中有不被第一个字符串包含的字符。返回false.反之如果值为-1的元素在位置数组中的位置为-1，就证明不存在，也就是字符串2中的字符全能在字符串1中找到，此时返回true。

删除数组中的所有假值。

在JavaScript中，假值有false、null、0、""、undefined和NaN

function bouncer(arr) {
  // Don't show a false ID to this bouncer.
  function change(arr) {
    return !(arr === null || arr === false || arr === undefined || arr === 0 || arr === "" || arr !== arr);
  }
  return arr.filter(change);
}
bouncer([false, null, 0, NaN, undefined, ""]);

关于null,undefined,NaN的区别之前写过，点这里跳转

主要用到了arr.filter(callback)，用来返回满足callback函数的值。

实现一个摧毁(destroyer)函数，第一个参数是待摧毁的数组，其余的参数是待摧毁的值。

destroyer([1, 2, 3, 1, 2, 3], 2, 3)应该返回 [1, 1].

destroyer([“tree”, “hamburger”, 53], “tree”, 53)应该返回 [“hamburger”].

function destroyer(arr) {
  // Remove all the values
  var arrDel = [];
  for(var i =1; i<arguments.length; i++) {
    arrDel.push(arguments[i]);
  }
  return arr.filter(function(val) {
                    return arrDel.indexOf(val)<0;
});
}
destroyer([1, 2, 3, 1, 2, 3], 2, 3);

用到arguments.object:arguments 是一个类数组对象。代表传给一个function的参数列表。你可以传递任意数量的参数到该函数，然后该函数会将每个参数作为一个条目来创建一个列表。

比如destroyer(arr)这个函数，只有一个参数，那么如何处理destroyer([1, 2, 3, 1, 2, 3], 2, 3);呢？
没错，[1, 2, 3, 1, 2, 3], 2, 3全部都是arguments这个类数组。可以理解为arguments=[[1, 2, 3, 1, 2, 3], 2, 3]

但是arguments对象并不是一个真正的Array 。它类似于数组，但没有数组所特有的属性和方法，除了 length。例如，它没有 pop 方法。

思路：新建一个储存被删除值的数组arrDel，开始对arguments进行遍历，注意val i = 1;因为不需要对第一个（也就是arr）进行遍历。

然后把arguments各个元素push进arrDel.然后

1 2	return arr.filter(function(val) { return arrDel.indexOf(val)<0;});

先给数组排序，然后找到指定的值在数组的位置，最后返回位置对应的索引。

where([1,2,3,4], 1.5)应该返回 1。因为1.5插入到组[1,2,3,4]后变成[1,1.5,2,3,4]，而1.5对应的索引值就是1。

同理，where([20,3,5], 19) 应该返回 2。因为数组会先排序为 [3,5,20]，19插入到数组[3,5,20]后变成[3,5,19,20]，而19对应的索引值就是2。

function where(arr, num) {
  // Find my place in this sorted array.
  var newArr = arr.concat(num);
  function change(a,b) {
    if (b - a >0) return -1;
    return 1;
  }
  return newArr.sort(change).indexOf(num);
}
where([2, 20, 10], 19);

思路：用arr.concat拼接数组，然后利用sort排序，然后用indexOf返回索引值就可以了。

写一个ROT13函数，实现输入加密字符串，输出解密字符串。

下面我们来介绍风靡全球的凯撒密码Caesar cipher
，又叫移位密码。

移位密码也就是密码中的字母会按照指定的数量来做移位。

一个常见的案例就是ROT13密码，字母会移位13个位置。由’A’ ↔ ‘N’, ‘B’ ↔ ‘O’，以此类推。

写一个ROT13函数，实现输入加密字符串，输出解密字符串。

所有的字母都是大写，不要转化任何非字母形式的字符(例如：空格，标点符号)，遇到这些特殊字符，跳过它们。

rot13(“SERR PBQR PNZC”)应该解码为 “FREE CODE CAMP”

function rot13(str) {
  var newArr=[];
  for(var i=0;i<str.length;i++){
    if(str.charCodeAt(i)<65||str.charCodeAt(i)>90){
      newArr.push(str.charAt(i));
     }else if(str.charCodeAt(i)>77){
       newArr.push(String.fromCharCode(str.charCodeAt(i)-13));
    }else{
      newArr.push(String.fromCharCode(str.charCodeAt(i)+13));
    }
  }
  return newArr.join("");
}
 
// Change the inputs below to test
 rot13("SERR PBQR PNZC");

这个主要考察unicode编码。

charCodeAt()方法返回0到65535之间的整数，代表索引处字符的UTF-16编码单元（在Unicode编码单元表示一个单一的UTF-16编码单元的情况下，UTF-16编码单元匹配Unicode编码单元。否则，比如Unicode 编码单元 > 0x10000 的情况下，只能匹配Unicode代理对的第一个编码单元）。如果你希望得到整点编码值，使用codePointAt()

思路：

26个字母的unicode码在65(A)与90(Z)之间,第13位M(77);
将str通过.charCodeAt()转为unicode编码并放入新数组;
其中非字母形式的字符直接放入.charAt();
后13位字母减去13后放入；
前13位字母加上13后放入；
通过.fromCharCode()转化为字母，将数组转化为字符串；

基础javascript算法就到这了，很多算法虽然写出来了，但是应该不是最优解，但是现在我还想不出来更好的解法。先这样吧，如有错误，欢迎指正。

2016-11-30