JavaScript算法项目

发表于 2018-07-11 更新于 2018-08-07 分类于 FreeCodeCamp 阅读次数： Disqus：

JS算法项目是5道题目，没有具体的知识点讲解，我把题目的解答和思路放在下面：

Introduction to the JavaScript Algorithms and Data Structures Projects

Palindrome Checker 测试回文

题干：测试字符串从左到右与从右到左是否是一致的（需要提前筛除掉-/等特殊符号）

这题比较简单，先把字符串转换成小写字母（题目规定忽略大小写差异），切分成数组，因为数组可以使用reverse()方法直接调转顺序，这里用split("")切分，方便后一步筛选特殊符号，然后利用filter()方法，用正则/[a-z0-9]/把可以接受的字符筛选出来，再将正反两个顺序的数组用join()方法连接起来比较就好了。
1
2
3
4
5
function palindrome(str) {
let arr = str.toLowerCase().split("").filter(ele => (/[a-z0-9]/).test(ele));
return arr.join("") === arr.reverse().join("");
}
palindrome("eye");

题干：将阿拉伯数字转换成罗马数字

我们先找出罗马数字的特征，罗马数字有特殊的字母符号来表示特定的数字（1， 5， 10， 50， 100， 500， 1000），这里只需要计算到最高3999。这些符号累加的结果等于阿拉伯数字，但是写的顺序要注意，如果较小的单位在较大单位的左边，则表示减去这个较小单位，如果在右边就是加上较小单位。

我采取的方法是先创建一个Roman对象来保存各个级别的对应字母，然后创建repeat函数来规定字母怎么排列。这里以5作为切换的标准，1, 10, 100, 1000这4个级别上都是1-3个单位写作累加unit unit unit类似III或者XXX，如果是4个单位就是表示5倍单位的字母左边加上较小单位，如IV或XL,5个单位的则是对应级别中数组的第二个元素，如V, L,D，如果是6-8个单位则是表示5倍单位的字母右边累计添加表示1倍单位的字母，最后表示9个单位则是10倍单位在左边加上一倍单位。

找到这个规律之后，找到每个级别的数字，Math.floor(num / unit)，再调用repeat函数就可以返回转换后的字符串了。

function convertToRoman(num) {
	let Roman = {
		1: ["I", "V"],
		10: ["X", "L"],
		100: ["C", "D"],
		1000: ["M"]
	}
	let result = "";
	let repeat = function(times, prop) {
		let roman = Roman[prop];
		let addStr;
		if(times <= 3) {
			addStr = new Array(times).fill(roman[0]).join("");
			result += addStr;
		} else if (times === 4) {
			addStr = roman[0] + roman[1];
			result += addStr;
		} else if (times === 5) {
			result += roman[1];
		} else if (times < 9) {
			addStr = roman[1] + new Array(times-5).fill(roman[0]).join("");
			result += addStr;
		} else if (times === 9) {
			addStr = roman[0] + Roman[prop * 10][0];
			result += addStr;
		}
		return result;
	}
	repeat(Math.floor(num / 1000), 1000);
	repeat(Math.floor((num % 1000) /100), 100);
	repeat(Math.floor(num % 100 / 10), 10);
	repeat(num % 10, 1);
	return result;
}
convertToRoman(36);

Caesars Cipher

题干：凯撒密码

凯撒密码是一个很简单的编码方式，即字母对应编码为字母本身Unicode编码+13的字母。这里有一个小坑是，如果统一加13，小于65或者大于90对应的字母在26个大写字母之外，所以需要判断一下字母的大小，如果字母的编码本身大于77，则编码-13，如果小于77，则编码+13。对于非字母，则不必转换。

function rot13(str) { // LBH QVQ VG!
    let result = str.split("").map(val => {
   	if(val.charCodeAt() < 65 || val.charCodeAt() > 90) {
   		return val;
   	} else {
   		return val.charCodeAt() > 77? String.fromCharCode(val.charCodeAt() - 13): String.fromCharCode(val.charCodeAt() + 13)
   	}
   }).join("");
   return result;
}

// Change the inputs below to test
rot13("SERR PBQR PNZC");

Telephone Number Validator

题干：检测电话号码是否有效

这题就是利用正则表达式来检测字符串。字符串开头可以是1或者1加上空格，之后是3个数字，这3个数字前后可以有一对括号，但是括号必须完整，之后是3个数组，再之后是4个数字，3组数字之间可以是空格，也可以是短横线，还可以没有分隔符，字符串前后不能再有其他的内容。所以按照这个思路很容易写出这个表达式。
1
2
3
4
5
6
function telephoneCheck(str) {
let re = /^(1|1\s)?([0-9]{3}|$[0-9]{3}$)(\s|-)?[0-9]{3}(\s|-)?[0-9]{4}$/;
return re.test(str);
}

telephoneCheck("555-555-5555");

Cash Register

题干：模拟自动收银机返回找零钱的数组

这题和转换罗马数字那题有一点类似，就是使用对象会很方便。这题把所有的单位和单位指代的价格对应起来，放在一个对象中。

首先判断需要找零的钱和收银机里钱的关系，如果找零正好等于收银机的前，则返回原数组，且status是CLOSED，如果找零大于收银机里的钱，则返回零钱不够INSUFFICIENT FUNDS，如果零钱够，则需要判断返回的数组，这里我让cid中的每一位去和零钱比较，如果单位比change大，则不必返回这一部分，如果单位比change小或者相等，则判断返回多少Math.floor(change / unit)，在遍历完成后检查change是否为零，为零表示收银机里的钱可以合适地找给顾客，如果不为零，则说明对应的单位无法满足正好加起来等于找零。

需要注意一个坑是，JavaScript在做浮点运算的时候回出现多位小数的bug，非常坑。这里我采取的方法是toFixed(2)，但是另一个需要注意的是，toFixed方法会返回一个字符串，所以无法直接合其他的数字比较，如果需要比较，得parseFloat。

function checkCashRegister(price, cash, cid) {
  var change = cash - price;
  let money = {
  	"ONE HUNDRED": 100,
  	"TWENTY": 20,
  	"TEN": 10,
  	"FIVE": 5,
  	"ONE": 1,
  	"QUARTER": 0.25,
  	"DIME": 0.1,
  	"NICKEL": 0.05,
  	"PENNY": 0.01 
  };
  let drawer = parseFloat(cid.reduce((acc, cur) => acc + cur[1], 0).toFixed(2));
  if(change > drawer) {
  	return {status: "INSUFFICIENT_FUNDS", change:[]};
  } else if (change === drawer) {
  	return {status: "CLOSED", change: cid};
  } else {
  	let cashArr = [];
  	cid.reverse().map(val => {
  		let unit = money[val[0]];
  		let cache = Math.floor(change/unit);
  		if(cache > 0) {
  			if(cache * unit >= val[1]) {
  				cashArr.push(val);
          change = (change - val[1]).toFixed(2);
  			} else {
  				cashArr.push([val[0], cache * unit]);
  				change = (change - cache * unit).toFixed(2);
  			}
  		} 
  	})
  	if(eval(change) === 0) {
  		return {status: "OPEN", change: cashArr};
  	} else {
  		return {status: "INSUFFICIENT_FUNDS", change:[]};
  	}
  }
}
checkCashRegister(19.5, 20, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.1], ["QUARTER", 4.25], ["ONE", 90], ["FIVE", 55], ["TEN", 20], ["TWENTY", 60], ["ONE HUNDRED", 100]]);