FCC上的初级算法题

  • A+
所属分类:JavaScript
摘要

核心提示:FCC的算法题一共16道。跟之前简单到令人发指的基础题目相比,难度是上了一个台阶。主要涉及初步的字符串,数组等运算。仍然属于基础的基础,官方网站给出的建议完成时间为50小时,超出了之前所有非项目题目的一倍还多。由此可见它的分量。现将自己的解题过程做个记录,有兴趣的人可以一起来试试。

[摘要]本文是对FCC上的初级算法题的讲解,对学习JavaScript编程技术有所帮助,与大家分享。

核心提示:FCC的算法题一共16道。跟之前简单到令人发指的基础题目相比,难度是上了一个台阶。主要涉及初步的字符串,数组等运算。仍然属于基础的基础,官方网站给出的建议完成时间为50小时,超出了之前所有非项目题目的一倍还多。由此可见它的分量。现将自己的解题过程做个记录,有兴趣的人可以一起来试试。


1.翻转字符串

先把字符串转化成数组,再借助数组的reverse方法翻转数组顺序,最后把数组转化成字符串。
你的结果必须得是一个字符串

functionreverseString(str){
returnstr;
}

reverseString("hello");

思路:
(1)字符串转数组用的是split方法,数组转字符串用join方法

split()方法通过把字符串分割成子字符串来把一个String对象分割成一个字符串数组。参数

当然,你也可以做一个循环把字符串一个个加回去
(2)倒序重排数组用的是reverse方法

解法
varnewStr='';
functionreverseString(str){
vararr=str.split('');//把字符串分割为['h','e','l','l','o']
arr.reverse();//倒序排列数组
newStr=arr.join('');//把数组转为字符串
returnnewStr;//别忘了返回。
}
reverseString("hello");

2.计算一个整数的阶乘

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

functionfactorialize(num){
returnnum;
}

factorialize(5);

思路:用循环,*=做、所需要注意的只是循环起点。

functionfactorialize(num){
vari=1;
varproduct=1;

for(i=1;i<=num;i++){
product*=i;
}
returnproduct;
}

factorialize(5);

3.如果给定的字符串是回文,返回true,反之,返回false

如果一个字符串忽略标点符号、大小写和空格,正着读和反着读一模一样,那么这个字符串就是

注意你需要去掉字符串多余的标点符号和空格,然后把字符串转化成小写来验证此字符串是否为回文。

函数参数的值可以为"racecar""RaceCar""raceCAR"

functionpalindrome(str){
//Goodluck!
returntrue;
}

palindrome("eye");

思路,要转化字符串为无标点的字符串需要两个方法
(1)replace()方法
用于在字符串中用一些字符替换另一些字符,或替换一个与正则表达式匹配的子串。xxx。replace(正则表达式,'xxxx')
(2)转换小写——toLowerCase()

functionpalindrome(str){
//Goodluck!
varnewStr=str.replace(//W+/g,'');//匹配所有非单词的字符,替换为空字符串
newStr=newStr.replace(//_+/g,'');//匹配所有下划线,替换为空字符串
newStr=newStr.toLowerCase();
//转化字符串为小写
vararr1=newStr.split('');

vararr2=arr1.reverse();
varnewStr2=arr2.join('');
//重构倒序的字符串
if(newStr===newStr2){//比较1
returntrue;
}else{
returnfalse;
}
}

一个优化的思路:

functionpalindrome(str){
//Goodluck!
str=str.replace(/[^A-Za-z0-9]/g,'').toLowerCase();
for(vari=0;i<str.length/2;i++){
if(str[i]!==str[str.length-i-1]){
returnfalse;
}
}
returntrue;
}

还有更简单的思路

functionpalindrome(str){
//Goodluck!
varre=/[/W/s_]/gi;
str=str.replace(re,"");
returnstr.toLowerCase()===str.split("").reverse().join("").toLowerCase();
}

palindrome("eye");

4.找到提供的句子中最长的单词,并计算它的长度。

函数的返回值应该是一个数字。
这个没有用什么生疏的方法,split拆分字符串,然后循环判断最长的String.length;

functionfindLongestWord(str){
vararr=str.split('');
varwordLength=0;
for(i=0;i<arr.length;i++){
if(arr[i].length>wordLength){
wordLength=arr[i].length;
LongestWord=arr[i];
}
}
returnwordLength;
}

findLongestWord("Thequickbrownfoxjumpedoverthelazydog");

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

像'the'和'of'这样的连接符同理。
思路,先用split拆分单词,在拆分单词的每个字母,首个字母设置大写,后面的全部设置小写。然后再组合成词,最后再组合为句子。

functiontitleCase(str){
vararr=str.split('');
for(i=0;i<arr.length;i++){
arr2=arr[i].split('');
arr2[0]=arr2[0].toUpperCase();
for(j=1;j<arr2.length;j++){
arr2[j]=arr2[j].toLowerCase();
}

arr[i]=arr2.join('');

}
varnewStr=arr.join('');

returnnewStr;
}

6.右边大数组中包含了4个小数组,分别找到每个小数组中的最大值,然后把它们串联起来,形成一个新数组。

functionlargestOfFour(arr){
//Youcandothis!
returnarr;
}

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

提示:你可以用for循环来迭代数组,并通过arr[i]的方式来访问数组的每个元素。
思路,主要是用了数组排序的方法。

functionlargestOfFour(arr){
//Youcandothis!
varnewArr=[];
for(i=0;i<arr.length;i++){
arr[i].sort(function(a,b){
returnb-a;
});

newArr.push(arr[i][0]);
}
returnnewArr;

}

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

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

如果是,返回true;如果不是,返回false。
思路:主要是用到了substr()方法
substr()方法可在字符串中抽取从start下标开始的指定数目的字符。

varstr="Helloworld!"
document.write(`str.substr(3)`)

输出结果:

loworld!

根据这个方法,可以用String.length来截取想要的部分进行判断。

functionconfirmEnding(str,target){
if(str.substr(str.length-target.length)==target){
returntrue;
}else{
returnfalse;
}
}

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

没什么可说的

functionrepeat(str,num){
//repeatafterme
varstr0=str;
if(num<=0){
return'';
}else{
for(i=0;i<num-1;i++){
str+=str0;
}
returnstr;
}
}

9.截断一个字符串!

如果字符串的长度比指定的参数num长,则把多余的部分用...来表示。
切记,插入到字符串尾部的三个点号也会计入字符串的长度。
但是,如果指定的参数num小于或等于3,则添加的三个点号不会计入字符串的长度。

functiontruncate(str,num){
//Clearoutthatjunkinyourtrunk
returnstr;
}

truncate("A-tisketa-tasketAgreenandyellowbasket",11);

思路:
slice()方法可提取字符串的某个部分,并以新的字符串返回被提取的部分。比如说:

varstr="Hellohappyworld!"
document.write(str.slice(6,17))//输出"happyworld"
functiontruncate(str,num){
//Clearoutthatjunkinyourtrunk
varnewStr='';
if(str.length>num){
if(num<=3){
newStr=str.slice(0,num)+'...';
}else{
newStr=str.slice(0,num-3)+'...';
}
returnnewStr;
}else{
returnstr;
}
}

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

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

functionchunk(arr,size){
//Breakitup.
returnarr;
}

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

如果不用slice做,要对情况做分类讨论:

functionchunk(arr,size){
//Breakitup.
varnewArr=[];
vari=0;
vartempArr=[];
if(arr.length%size!==0){
for(i=0;i<=arr.length;i++){
if(tempArr.length==size){
newArr.push(tempArr);
tempArr=[];
}
if(i==arr.length){
newArr.push(tempArr);
break;
}

tempArr.push(arr[i]);
}

}else{
for(i=0;i<=arr.length;i++){
if(tempArr.length==size){
newArr.push(tempArr);
tempArr=[];
}
tempArr.push(arr[i]);
}
}

而slice方法可以这样实现:

functionchunk(arr,size){
varnewarr=[];
for(vari=0;i<arr.length;i+=size){
newarr.push(arr.slice(i,i+size));
}
returnnewarr;
}

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

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

functionslasher(arr,howMany){
//itdoesn'talwayspaytobefirst
if(howMany===0){
returnarr;
}
arr=arr.splice(howMany,arr.length-1);
returnarr;

}

slasher([1,2,3],2);

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

举例,["hello","Hello"]应该返回true,因为在忽略大小写的情况下,第二个字符串的所有字符都可以在第一个字符串找到。

["hello","hey"]应该返回false,因为字符串"hello"并不包含字符"y"。

["Alien","line"]应该返回true,因为"line"中所有字符都可以在"Alien"找到。

阅读材料
indexOf()方法可返回某个指定的字符串值在字符串中首次出现的位置。

varstr="Helloworld!"
document.write(str.indexOf("Hello")+"<br/>")//0
document.write(str.indexOf("World")+"<br/>")//-1
document.write(str.indexOf("world"))//6

直接的办法

functionmutation(arr){
vara1=arr[0].toLowerCase();
vara2=arr[1].toLowerCase();
if(a1===a2){
returntrue;
}else{
varcount=0;
for(i=0;i<a2.length;i++){
for(j=0;j<a1.length;j++){
if(a2[i]==a1[j]){
count+=1;
}
}
}
if(count>=a2.length){
returntrue;
}else{
returnfalse;
}

}

}

13.删除数组中的所有假值。

JavaScript中,假值有falsenull0""undefinedNaN

functionbouncer(arr){
//Don'tshowafalseIDtothisbouncer.
arr=arr.filter(function(a){
returna
});
returnarr;
}


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

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

思路:要逐步判断arr内的每个参数值,满足一样的删除掉即可,但是在循环内删除会破坏结构,所以可以先替换为一个false,然后再来用filter判断返回出真值。

functiondestroyer(arr){
//Removeallthevalues
for(i=1;i<arguments.length;i++){
for(j=0;j<arr.length;j++){
if(arr[j]==arguments[i]){
arr.splice(j,1,false);//起始项数,要删除的值数,添加项内容
}
}

}
arr=arr.filter(function(a){
returna;
});
returnarr;
}

destroyer([1,2,3,1,2,3],2,3);

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

举例: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

思路:用一个索引值index来标记num本应在数组的位置。在遍历比较之后插入数组。

functionwhere(arr,num){
//Findmyplaceinthissortedarray.
arr.sort(function(a,b){
returna-b;
});


varindex=0;
for(i=0;i<arr.length;i++){
if(arr[i]<num){
index+=1;
}

}
arr.splice(index,0,num);
console.log(arr);
returnindex;
}

where([40,60],50);

16.下面我们来介绍风靡全球的凯撒密码Caesarcipher,又叫移位密码。

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

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

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

所有的字母都是大写,不要转化任何非字母形式的字符(例如:空格,标点符号),遇到这些特殊字符,跳过它们。
思路:
(1)每个字符都有自己的键码,相关的编码可以在<aherf="http://wenku.baidu.com/link?url=WTI3ZhKmXnCrVe-59Ccb5SiCWGddsS1Ch8bGlFsWmS3Sp6bpH2YUScEbUl4bjaZuqZt_yXzk5qIphIJptMyr_-N0p48spQ5pKQMW2j9Many">键码表查到。根据需求:大写字母A-Z的键码为60-90。只要获取每个字符串的键码(String.charCodeAt()方法),回退13位,就可以获得解密后的键码。最后把它输出为相应的字母(String.fromCharCode()方法)。
(2)首先要判断的是:键码60-90闭区间外的字符不予编译。
(3)其次,明文的键码解密之后可能退到不属于大写字母的编码区,比如加密明文为A的时,直接回退再编译就变成了数字3,因此需要给它在此基础上加上大写字母表的个数26。再进行判断。这实现了整个编译区相对于明文区的偏移。

functionrot13(str){//LBHQVQVG!
varnewStr='';
for(i=0;i<str.length;i++){
if(str[i].charCodeAt(0)>90||str[i].charCodeAt(0)<65){
newStr+=str[i];
}else{
varnewStrCode=str[i].charCodeAt(0)-13;
if(newStrCode<65){
newStrCode+=26;
}
newStr+=String.fromCharCode(newStrCode);
}
}
return(newStr);

}
//Changetheinputsbelowtotest
rot13("LBHQVQVG");

题目来源:

FCC中文网:https://www.freecodecamp.cn/

参考资料:

[1]《javascript高级程设计》第4,5,6章。
[2]MOZILLA开发者社区:https://developer.mozilla.org/zh-CN/docs/Web/JavaScript
[3]W3school:http://www.w3school.com.cn/
[4]感谢gitter中文聊天室热心的网友

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: