JavaScript算法项目

FreeCodeCamp
,

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");

  • Roman Numeral Converter

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

    我们先找出罗马数字的特征，罗马数字有特殊的字母符号来表示特定的数字（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函数就可以返回转换后的字符串了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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。对于非字母，则不必转换。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    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]]);