Freecodecodecamp(FCC)高级算法汇总.
程序员文章站
2022-04-24 21:56:02
...
高级算法对于我这种渣渣来说,还是挺难的,做的过程中借鉴(抄)了不少网上各位大佬的博客上的东西,甚至有几题是无耻照搬的,而且代码写的非常的乱,各位大佬权当个笑话看看算了.代码风格这个东西真的重要,我自己看自己写的东西都跟看见屎一样的..哈哈哈,本篇文章算做下备份,也算是给后面学习的朋友提供一点思路和建议吧.
希望各位可以考虑许久发现实在不会之后再去借鉴别人的代码.这里面的题对大神来说或许不算什么,对你我这样的算有难度的吧,还是需要考虑,重复码很多遍才能做对的.不然收获真的比较小,比如我,偷了不少东西,然而感觉自己掌握到的并不多.
本人愚钝,代码很乱,很臃肿,可读性差..思维也不是特别好.谨慎阅读…
1.Validate US Telephone Numbers
就一个检测电话号码格式是否正确的代码,主要考察正则表达式,不算特别难,分成三块来解决比较方便.这里错了很久,后来借鉴大佬代码.发现错于没使用检测开头和结尾的符号^和$,错误的使用了匹配模式以及需要注意到()这个虽然成为捕获符号,但是在这里可以作为划分区块的作用
- 国际号码,数字1至多出现一次,并以此开头.
- 区号,三个数字,需要注意中间各种符号至多出现一次.
- 号码,七位,分前三后四,并以此结尾.
function telephoneCheck(str) {
var Reg = /^1?[ -]?(\d{3}|\(\d{3}\))[ -]?\d{3}[ -]?\d{4}$/g;
if(Reg.test(str)){
console.log(str + " 被匹配到" + str.match(Reg).join(""));
return true;}
else{
return false;
}
}2.Symmetric Difference
使用 Array.reduce()方法,对每一个数组元素及其后面的一个数组元素进行对等差分计算.需要注意一下这个方法传入的几个参数,这个参数列表在后面还要用到,我分别用了两个for循环对前后两个数组分别检测,然后push到累加数组里.
function sym(args) {
//需要把args先转变为一个数组.
var arrs=[];
arrs.length=arguments.length;
for(i=0;i<arguments.length;i++){
arrs[i] = arguments[i];
}
if(arrs.length<2){
alert("输入两个以上数组");
}
arrs = arrs.reduce(function(accumulater,currentValue){
var result=[];
for(i=0;i<accumulater.length;i++){
if(!currentValue.includes(accumulater[i]) && !result.includes(accumulater[i]))
result.push(accumulater[i]);
}
for(i=0;i<currentValue.length;i++){
if(!accumulater.includes(currentValue[i])&& !result.includes(currentValue[i]))
result.push(currentValue[i]);
}
console.log(accumulater + "与" + currentValue + "==" + result);
return result;
});
return arrs;
}
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);
3.Exact Change
这题还是比较难的, 当时折磨了我很久(脑子笨是这样的),这个主要是要和现实连接在一起,需要把我们日常生活中找零这个操作用计算机表示出来,其实最主要的一步考虑就是,当前收银台的某一个纸币的面额和当前纸币是否够找的问题.这个代码写的比较乱,看的朋友可能很费神.了解大概思路就好了.
主要需要考虑以下问题
- JS小数的计算有点问题,需要一点技巧转换.百度上有数个方法.(如
Number.toFixed()的使用,或者转化成整数运算后再转化为小数等. - 从面额入手开始考虑,这是最重要的.
- 考虑当前面额与张数和还需找的零钱数目之间的关系.
function checkCashRegister(price, cash, cid) {
var change;
//先得到应该找的数目,然后进行匹配.
//change为应找的数目.change>0继续循环.change=0退出循环,说明已经找尽.循环结束的时候change>0,说明钱不够.
//每循环一次,change就要改变一次. 应该在循环结束的时候进行判定.
//应该建立一个对象,对象里面包含钱币的名称和面额.
change = cash - price; //未找完的钱.
var change1 = change;
var result = []; //应找的钱.
var total = 0;
//钱的对象
var money = {
'PENNY': 0.01,
'NICKEL': 0.05,
'DIME': 0.1,
'QUARTER': 0.25,
'ONE': 1.00,
'FIVE': 5.00,
'TEN': 10.00,
'TWENTY': 20.00,
'ONE HUNDRED': 100.00,
};
//[["TWENTY", 60.00], ["TEN", 20.00], ["FIVE", 15], ["ONE", 1], ["QUARTER", 0.50], ["DIME", 0.20], ["PENNY", 0.04]].
//从大到小开始循环
for (i = 0; i < cid.length; i++)
total += cid[i][1];
console.log(Object.getOwnPropertyNames(money));
for (i = cid.length - 1; i > -1; i--) {
//每次循环中,判断张数,
console.log(money[cid[i][0]]);
console.log("还需找零" + change + "现在面额" + money[cid[i][0]] + "应该找的钱币张数" + Math.floor(change / money[cid[i][0]]) + "现有钱的张数" + cid[i][1] / money[cid[i][0]]);
//如果说当前零钱大于当前面额的时候才会取出当前面额,当前面额多少还要再进行判断.不取出的情况就是当前面额大于钱...
if (change > money[cid[i][0]] && cid[i][1] > 0 && total >= change) {
//x,y分别是张数.
var x = Math.floor(change / money[cid[i][0]]);
var y = cid[i][1] / money[cid[i][0]];
var zhangshu = (x >= y) ? y : x; //这个张数举例说明一下就好了,如果需要找钱80,而目前有3张20或者5张20的情况,取出来的张数是不一样的.
//改变change和当前钱的值,然后push进数组找的钱.
change -= zhangshu * money[cid[i][0]];
cid[i][1] -= zhangshu * money[cid[i][0]];
result.push([cid[i][0], zhangshu * money[cid[i][0]]]);
console.log(x, y, change, result, total, typeof change, cid[i][1]);
change = change.toFixed(2);
}
//不取出的情况直接跳过.
}
//结束取出之后,循环决定.
if (total == change1) {
return 'Closed';
} else if (change > 0) {
return "Insufficient Funds";
}
return result;
}
// Example cash-in-drawer array:
// [["PENNY", 1.01],
// ["NICKEL", 2.05],
// ["DIME", 3.10],
// ["QUARTER", 4.25],
// ["ONE", 90.00],
// ["FIVE", 55.00],
// ["TEN", 20.00],
// ["TWENTY", 60.00],
// ["ONE HUNDRED", 100.00]]
checkCashRegister(19.50, 20.00, [
["PENNY", 0.01],
["NICKEL", 0],
["DIME", 0],
["QUARTER", 0],
["ONE", 1.00],
["FIVE", 0],
["TEN", 0],
["TWENTY", 0],
["ONE HUNDRED", 0]
]);4.Inventory Update
这题相对来说简单的多,注意一下sort() 的用法就好了.
function updateInventory(arr1, arr2) {
// 请保证你的代码考虑到所有情况
//排序的时候需要将普通的二维数组转换为对象数组.
//排序前不能转换,因为一旦转换,将变得难以处理和判断.或者排序之后依然要新建一个数组,调用includes or indexOf函数进行判断,会比较麻烦.
//所以就进行,先取出名字的数字,判断是否存在,push完之后,再进行转换为对象数组,不知道是否有更简单方法.
var curInvName = [];
var curInvObject = [];
for(i=0;i<arr1.length;i++){
curInvName[i] = arr1[i][1];
}
//对于每一个库存元素,进行判断,并转换为对象push进新数组里.
for(i=0;i<arr2.length;i++){
//如果已经存在,更新值.
if(curInvName.indexOf(arr2[i][1])!==-1){
arr1[curInvName.indexOf(arr2[i][1])][0]+=arr2[i][0];
}else{
arr1.push(arr2[i]);
}
//然后push
}
//只能想到这种做法了.
arr1=arr1.sort(function(a,b){
console.log(a[1]<b[1]? -1 : -1);
return a[1]<b[1]? -1 : 1;
});
return arr1;
}
// 仓库库存示例
var curInv = [
[21, "Bowling Ball"],
[2, "Dirty Sock"],
[1, "Hair Pin"],
[5, "Microphone"]
];
var newInv = [
[2, "Hair Pin"],
[3, "Half-Eaten Apple"],
[67, "Bowling Ball"],
[7, "Toothpaste"]
];
updateInventory([[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]], [[2, "Hair Pin"], [3, "Half-Eaten Apple"], [67, "Bowling Ball"], [7, "Toothpaste"]]);
5.No repeats please
- 惭愧,我能想到一个递归的方法,也有了一点自己的思路,然而运行总是堆栈溢出,看来是不可行的,网上有许多大佬的代码,准备回头抄一个回来了.这题的确是高级算法里面最难的一个了.需要好好研究一下.
- 终究是选择照搬了一个源代码,这个递归说来也简单,和日常的思路较为一致.比如说有1.2.3.4四个元素,排列时候是先把1放在第一位,第二个位置之后又是一个数组,当前数组的第一位应该是2,3,4中的某一个,先取2,然后取3,4,此时排列应该为1234,此时index为4,超出了数组长度,结束本次递归,返回上一层,在上一层的的i为3,即此时输出1243,上层的i为4,即到达了尽头,所以返回上上一层.将3作为第一个元素..(以上过程是根据程序来倒推的,我没有实现代码.)
-
比较容易查看的还是使用
console.log将各个步骤打印出来.
调用函数处理1234所得全排列数组.
处理的过程
应该可以大致看出来过程.
function permAlone(str) {
// 匹配重复字符，若匹配出的字符不是空 ，则判断0号索引是否与原字符串相同 ，若相同则该字符串由同一个字符组成
var reg = str.match(/(.)\1+/g);
if(reg!==null && reg[0] === str) {
return 0;
}
var arr = str.split('');
var arrs = [];
//将两元素值对调
function swap(array, i, j)
{
var t = array[i];
array[i] = array[j];
array[j] = t;
}
//全排列递归函数
function fullArray( array , index){
if(index >= array.length)
{
arrs.push(arr.join(''));
}
else {
for( var i = index; i < array.length; i++)
{
console.log(i,index);
swap(array, i, index); //交换两个元素的位置.
fullArray(array , index + 1); //从剩余的数组里面开始进行递归.
swap(array, i, index); //需要还原状态,不然的话状态改变就会改变原来的数组,使得结果出现很大偏差.所做的任何改变都必须是在原数组上的.
}
}
}
fullArray( arr , 0);
//返回没有两字符重复在一起的数量
return arrs.filter(function(str){
return !str.match(/(.)\1+/g);
}).length;
}6.Friendly Date Ranges
这题说实话也不难,我能想到的方法就是做各种 if 判断,尽管这样很麻烦吧,但是也是个方法对不,在写这题的过程中,我不断的想要写出优雅,好看的代码,然而又没有那个能力,所以写完成了这个乱糟糟的样子,可以说是非常混乱了.好像是东补西补凑出来的似的,很难看.
主要需要注意分成三个部分来讨论,年月日,这里我忽略了一个思路就是,年月日是可以从大到小的依次判断的,然而我愚蠢的分为了三个部分分别判断,所以造成了一定的冗杂.
- 年份是否在同一年内,可以使用Date对象的方法来进行判断,因为不怎么熟悉,所以用了一个较笨的方法即结束时间的Date对象-365天是否小于开始时间的方法.
- 月份的改变相对简单,只需要得到月份的数字,然后数字作为索引换成数组元素就好了.
- 日的改变我认为是挺麻烦的,也是中间一大块三元表达式臃肿的原因所在,就是天数需要分为1,2,3的序数词表示和普通数字不一样,又需要考虑11,12,13这三个数字,我没想到特别好的方法,所以用了大段的判断.
- 判断可以参考一个老哥的代码判断,如我这样写感觉很混乱,不知所云,东拼西凑.
即
if(年)
if(月)
if(日)
else
else
elsefunction makeFriendlyDates(arr) {
var monthArr = ["",'January','February','March','April','May','June','July','August','September','October','November','December'];
var dayArr = ["th",'st','nd','rd'];
var oldTime = new Date(arr[0]);
var newTime = new Date(arr[1]);
var result=[];
//2017-01-02
var monthStart = parseInt(arr[0].substr(5,8));
var monthEnd = parseInt(arr[1].substr(5,8));
var yearStart = parseInt(arr[0].substr(0,5));
var yearEnd = parseInt(arr[1].substr(0,5));
var dayStart = parseInt(arr[0].substr(8,10));
var dayEnd = parseInt(arr[1].substr(8,10));
dayStart=(dayStart%10<=3 &&dayStart!==11&dayStart!==12&&dayStart!==13)? (parseInt(arr[0].substr(8,10)) + dayArr[dayStart%10]): dayStart+dayArr[0];
dayEnd=(dayEnd%10<=3&&dayEnd!==11&dayEnd!==12&&dayEnd!==13)? (parseInt(arr[1].substr(8,10)) + dayArr[dayEnd%10]): dayEnd+dayArr[0];
//分年月日三个部分讨论.
//不合
if(yearStart > yearEnd)
return undefined;
newTime.setDate(newTime.getDate()-365);
console.log(newTime);
if(oldTime>newTime){
if(yearStart == yearEnd && monthStart == monthEnd && dayStart == dayEnd){
result[0] = monthArr[monthStart] + " " + dayStart+", "+yearStart;
return result;
}
result[1]=monthArr[monthEnd]+ " " +dayEnd;
if(yearStart ==yearEnd && monthStart == monthEnd)
result[1]=dayEnd;
result[0] = monthArr[monthStart] + " " + dayStart+", "+yearStart;
if(yearStart == 2017 )
result[0] = monthArr[monthStart] + " " +dayStart;
}else{
result[0] = monthArr[monthStart] + " " + dayStart+", "+yearStart;
result[1] = monthArr[monthEnd] + " " + dayEnd + ", " + yearEnd;
}
return result;
}
//判断是否是在本年份.
console.log(makeFriendlyDates(["2016-05-11", "2017-04-04"]));
makeFriendlyDates(["2010-10-23", "2011-10-22"]);7.Make a Person
比较简单的一个应用,当然了,是指在这里简单,闭包还有FCC提供的文档我并没有太过仔细的阅读,我认为还是很重要的.注意this关键字的使用.(其实抄了个代码,因为自己的代码和这个相差无几,但就是过不了,烦死了.)
var Person = function(firstAndLast) {
var firstAndLastarr=firstAndLast.split(" "), firstName=firstAndLastarr[0],
lastName=firstAndLastarr[1];
this.getFirstName=function(){
return firstName;
};
this.getLastName=function(){
return lastName;
};
this.getFullName=function(){
firstAndLastarr[0]=firstName;
firstAndLastarr[1]=lastName;
return firstAndLastarr.join(" ");
};
this.setFirstName=function(first){
firstName=first;
};
this.setLastName=function(last){
lastName=last;
};
this.setFullName=function(firstAndLast){
firstAndLastarr=firstAndLast.split(" ");
firstName=firstAndLastarr[0];
lastName=firstAndLastarr[1];
};
};
var bob = new Person('Bob Ross');
bob.getFirstName();
8.Map the Debris
相对简单,没啥说的,一个数学式子就结束的玩意,我认为这题就是送的.
function orbitalPeriod(arr) {
var GM = 398600.4418;
var earthRadius = 6367.4447;
for(i=0;i<arr.length;i++){
arr[i].orbitalPeriod = Math.round(2 * Math.PI * (Math.sqrt(Math.pow(arr[i].avgAlt + earthRadius,3)/GM)));
delete arr[i].avgAlt;
}
return arr;
}
orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);
9.Pairwise
这题简介有点意思,哈哈哈.不是特别难,但是出了个下策,就是把配对完成的数组元素给直接编程undefined了,感觉有点Low.
function pairwise(arr, arg) {
var result = [];
var result1=0;
var temp;
for(i=0;i<arr.length;i++){
temp = arg-arr[i];
if(arr.indexOf(temp) !== -1 && i !== arr.indexOf(temp)){
result.push(i);
result.push(arr.indexOf(arg-arr[i]));
arr[i] = undefined;
arr[arr.indexOf(temp)]=undefined ;
}
}
if(arr.length===0)
return 0;
result1 = result.reduce(function(a,b){
return a+b;
});
return result1;
}
pairwise([], 100);总而言之,总体难度不是特别难,挺适合我这样的垃圾训练的.大佬们当个笑话看看就行.
上一篇： 235二叉搜索树的最近公共祖先
下一篇： Js 原型对象与原型链(转)