Freecodecamp 高级算法题

1. Validate US Telephone Numbers

如果传入字符串是一个有效的美国电话号码，则返回 true.

用户可以在表单中填入一个任意有效美国电话号码. 下面是一些有效号码的例子(还有下面测试时用到的一些变体写法):

555-555-5555
(555)555-5555
(555) 555-5555
555 555 5555
5555555555
1 555 555 5555

function telephoneCheck(str) {
  //^1?表示以1开头，1匹配0次或1次
  //\(\d{3}\)匹配（一个0-9的数字三次比下面多匹配一个括号，左右括号分别需要加上转义字符\
  // \d{3}匹配一个0-9的数字三次
  //\s?表示空白字符匹配0次或1次
  //[\s\-]?表示空格或者连字符-匹配0次或1次
  //\d{4}$表示已4位数字结尾($)
  var regex = /^(1?\s?)?(\(\d{3}\)|\d{3})[\s\-]?(\d{3})[\s\-]?(\d{4})$/g;
  return regex.test(str);
}

telephoneCheck("1 555 555 5555");

2. Symmetric Difference

创建一个函数，接受两个或多个数组，返回所给数组的 对等差分(symmetric difference) (△ or ⊕)数组.

给出两个集合 (如集合 A = {1, 2, 3} 和集合 B = {2, 3, 4}), 而数学术语 "对等差分" 的集合就是指由所有只在两个集合其中之一的元素组成的集合(A △ B = C = {1, 4}). 对于传入的额外集合 (如 D = {2, 3}), 你应该安装前面原则求前两个集合的结果与新集合的对等差分集合 (C △ D = {1, 4} △ {2, 3} = {1, 2, 3, 4}).
参考链接
方法一:

function getSym(arr1, arr2) {
    // 得到在第一个数组，但不在第二个数组中的元素
    var result = arr1.filter(function(e) {
        return arr2.indexOf(e) === -1;
    });

    // 得到在第二个数组，但不在第以个数组中的元素
    result.concat(arr2.filter(function(e) {
        return arr1.indexOf(e) === -1;
    }))
    
    // 去重
    return result.filter(function(e, i) {
        return result.indexOf(e) === i;
    })
}

方法二：

/*jshint esversion: 6 */
function sym(args) {
 var arr = Array.from(arguments); 
  return arr.reduce((arr1,arr2)=>{
   return arr1.concat(arr2).filter(val=>{
     return arr1.indexOf(val) == -1 || arr2.indexOf(val) ==-1; 
   }).filter((val, index, arr) => {
      return arr.indexOf(val) === index;
    });
  });
}

sym([1, 2, 3], [5, 2, 1, 4]);

2. Exact Change

设计一个收银程序 checkCashRegister() ，其把购买价格(price)作为第一个参数 , 付款金额 (cash)作为第二个参数, 和收银机中零钱 (cid) 作为第三个参数.

cid 是一个二维数组，存着当前可用的找零.

当收银机中的钱不够找零时返回字符串 "Insufficient Funds". 如果正好则返回字符串 "Closed".

否则, 返回应找回的零钱列表,且由大到小存在二维数组中.

function checkCashRegister(price, cash, cid) {
  var denom = [
  { name: 'ONE HUNDRED', val: 100.00},
  { name: 'TWENTY', val: 20.00},
  { name: 'TEN', val: 10.00},
  { name: 'FIVE', val: 5.00},
  { name: 'ONE', val: 1.00},
  { name: 'QUARTER', val: 0.25},
  { name: 'DIME', val: 0.10},
  { name: 'NICKEL', val: 0.05},
  { name: 'PENNY', val: 0.01}
];
  var change = cash - price;
  var totalCid = cid.reduce(function(acc,curr){
    acc.total += curr[1];
    acc[curr[0]] = curr[1];
    return acc;
  },{total:0});
  
  if (totalCid.total === change) {
    return 'Closed';
  }

  if (totalCid.total < change) {
    return 'Insufficient Funds';
  }  
  
  var change_arr = denom.reduce(function(acc,curr){
    var value=0;
    while(totalCid[curr.name]>0 && change>=curr.val){
      change-=curr.val;
      totalCid[curr.name]-=curr.val;
      value += curr.val;
      change = Math.round(change * 100) / 100;
    }
    if(value>0){
      acc.push([ curr.name, value ]);
    }
    return acc;
  },[]);
  
  if (change_arr.length < 1 || change > 0) {
    return "Insufficient Funds";
  }
  return change_arr;
}

// 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", 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]]);

3. Inventory Update

依照一个存着新进货物的二维数组，更新存着现有库存(在 arr1 中)的二维数组. 如果货物已存在则更新数量 . 如果没有对应货物则把其加入到数组中，更新最新的数量. 返回当前的库存数组，且按货物名称的字母顺序排列.

function updateInventory(arr1, arr2) {
  for(var i=0;i<arr2.length;i++){
      var foundMatch = false;
      for(var k=0;k<arr1.length;k++){
        if(arr1[k][1].indexOf(arr2[i][1])!== -1){
          arr1[k][0] += arr2[i][0];
          foundMatch = true;
        }
        
      }
      
  if (foundMatch === false) {
      arr1.push(arr2[i]);} 
    }
    arr1.sort(function(a,b){
      if(a[1]<b[1]){
        return -1;
      }
      return 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(curInv, newInv);

4. No repeats please

把一个字符串中的字符重新排列生成新的字符串，返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准

例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa), 但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a).

function permAlone(str) {
  var arr = str.split('');
  var result = 0;
  
  function swap(a,b){
    var tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
  }
  
  
  function generate(n){
    var regex = /([a-z])\1+/;
    
    if(n===1 && !regex.test(arr.join(''))){
      result++;
    }else{
      for(var i=0;i!==n;i++){
        generate(n-1);
        swap(n%2 ? 0:i,n-1);
      }
    }
  }
  
  generate(arr.length);
  return result;
  
  
}

permAlone('aab');

5. Friendly Date Ranges

让日期区间更友好！

把常见的日期格式如：YYYY-MM-DD 转换成一种更易读的格式。

易读格式应该是用月份名称代替月份数字，用序数词代替数字来表示天 (1st 代替 1).

记住不要显示那些可以被推测出来的信息: 如果一个日期区间里结束日期与开始日期相差小于一年，则结束日期就不用写年份了；在这种情况下，如果月份开始和结束日期如果在同一个月，则结束日期月份也不用写了。

另外, 如果开始日期年份是当前年份，且结束日期与开始日期小于一年，则开始日期的年份也不用写。

例如:

包含当前年份和相同月份的时候，makeFriendlyDates(["2017-01-02", "2017-01-05"]) 应该返回 ["January 2nd","5th"]

不包含当前年份，makeFriendlyDates(["2003-08-15", "2009-09-21"]) 应该返回 ["August 15th, 2003", "September 21st, 2009"]。

请考虑清楚所有可能出现的情况，包括传入的日期区间是否合理。对于不合理的日期区间，直接返回 undefined 即可

let makeFriendlyDates = arr => {  
  const months = {"01" : "January","02" : "February","03" : "March", "04" : "April","05" : "May", "06" : "June", "07" : "July","08" : "August", "09" : "September","10" : "October", "11" : "November","12" : "December"  };  
  let date1 = arr[0].split("-"); 
  let date2 = arr[1].split("-");
  let date = new Date();  
  let dateChange = day => {  
    if(day[0] === "0"){  
      day = day.substr(1);  
      if(day === "1") return day + "st";  //01->1st
      if(day === "2") return day + "nd";  //02->2nd
      if(day === "3") return day + "rd";  //03->3rd
      else return day + "th";  
    }  
    else{  
      if(day.substr(1,1) === "1" && day.substr(0,1) === "2") return day + "st";  //21->21st
      if(day.substr(1,1) === "1" && day.substr(0,1) === "3") return day + "st";  //31->31st
      if(day.substr(1,1) === "2" && day.substr(0,1) === "2") return day + "nd";  //22->22nd
      if(day.substr(1,1) === "3" && day.substr(0,1) === "2") return day + "rd";  //23->23rd
      else return day + "th";   
    }    
  };  
  let sameYear = (d1, d2) => {  
    if(d2[0] - d1[0] > 1) return false;  
    else{  
      if(d1[0] === d2[0]) return true;   
      else{  //判断相减为1的时候
        if(d2[1] > d1[1]) return false;  
        if(d2[1] < d1[1]) return true; //判断在一年以内返回true
        else return d2[2] < d1[2] ? true : false; //判断是否在一年以内
      }  
    }  
  };  
  if (sameYear(date1, date2)) { 
    if(date1[0] === date2[0]){  
      if(date1[1] === date2[1]){  //月份相同 
        if(date1[2] === date2[2]){  //日期相同
          let dateArr = [];  
          dateArr.push(months[date1[1]] + " " + dateChange(date1[2]) + ", " + date1[0]);  
          return dateArr;  
        }else{  
          let dateArr = [];  
          dateArr.push(months[date1[1]] + " " + dateChange(date1[2]));  
          dateArr.push(dateChange(date2[2]));  
          return dateArr;  
        }  
      }
      else{  //月份不同
        let dateArr = [];  
        dateArr.push(months[date1[1]] + " " + dateChange(date1[2]));  
        dateArr.push(months[date2[1]] + " " + dateChange(date2[2]));  
        return dateArr;  
      }  
    }  
    if(date1[0] == date.getFullYear() - 2){  //开始年份为当前年份 
      let dateArr = [];  
      dateArr.push(months[date1[1]] + " " + dateChange(date1[2]));  
      dateArr.push(months[date2[1]] + " " + dateChange(date2[2]));  
      return dateArr;  
    }  
    else{  
      let dateArr = [];  
      dateArr.push(months[date1[1]] + " " + dateChange(date1[2]) + ", " + date1[0]);  
      dateArr.push(months[date2[1]] + " " + dateChange(date2[2]));  
      return dateArr;  
    }  
  }    
  if (date2[0] > date1[0]){  //不同年且d2比d1大时
    let dateArr = [];  
    dateArr.push(months[date1[1]] + " " + dateChange(date1[2]) + ", " + date1[0]);  
    dateArr.push(months[date2[1]] + " " + dateChange(date2[2]) + ", " + date2[0]);  
    return dateArr;  
  }  
};  
makeFriendlyDates(["2017-07-12", "2018-06-13"]);

6. Make a Person

用下面给定的方法构造一个对象.

方法有 getFirstName(), getLastName(), getFullName(), setFirstName(first), setLastName(last), and setFullName(firstAndLast).

所有有参数的方法只接受一个字符串参数.

所有的方法只与实体对象交互.

var Person = function(firstAndLast) {
  var fullName = firstAndLast;
  
  
  this.getFirstName=function(){
    return fullName.split(' ')[0];
  };
  
  this.getLastName=function(){
    return fullName.split(' ')[1];
  };
  
  this.getFullName=function(){
    return fullName;
  };
  
  this.setFirstName=function(first){
    fullName =  first+' '+ fullName.split(' ')[1];
  };
  
  this.setLastName=function(last){
    fullName =  fullName.split(' ')[0]+' '+ last;
  };
  this.setFullName=function(firstAndLast){
    fullName = firstAndLast;
  };
    return fullName;
};

var bob = new Person('Bob Ross');
bob.getFullName();

7. Map the Debris

返回一个数组，其内容是把原数组中对应元素的平均海拔转换成其对应的轨道周期.

原数组中会包含格式化的对象内容，像这样 {name: 'name', avgAlt: avgAlt}.

function orbitalPeriod(arr) {
  var GM = 398600.4418;
  var earthRadius = 6367.4447;
  
  arr.forEach(function(item){
    item.orbitalPeriod=Math.round(2*Math.PI*Math.sqrt(Math.pow(earthRadius+item.avgAlt,3)/GM));
    delete item.avgAlt;
  });
  return arr;
}

orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);

9. Pairwise

有一个能力数组[7,9,11,13,15]，按照最佳组合值为20来计算，只有7+13和9+11两种组合。而7在数组的索引为0，13在数组的索引为3，9在数组的索引为1，11在数组的索引为2。
所以我们说函数：pairwise([7,9,11,13,15],20) 的返回值应该是0+3+1+2的和，即6。

function pairwise(arr, arg) {
  var sum=0;
  var pairArr = arr.slice();
  for(var i=0;i<pairArr.length;i++){
    for(var j=i+1;j<pairArr.length;j++){
      if(pairArr[i]+pairArr[j]===arg){
        sum+=i+j;
        pairArr[i] = pairArr[j] = NaN;
        break;
      }
    }
  }
  return sum;
}

pairwise([1,4,2,3,0,5], 7);