FCC高级算法题

Validate US Telephone Numbers

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

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

555-555-5555
(555)555-5555
(555) 555-5555
555 555 5555
5555555555
1 555 555 5555
在本节中你会看见如 800-692-7753 or 8oo-six427676;laskdjf这样的字符串. 你的任务就是验证前面给出的字符串是否是有效的美国电话号码. 区号是必须有的. 如果字符串中给出了国家代码, 你必须验证其是 1. 如果号码有效就返回 true ; 否则返回 false.

function telephoneCheck(str) {
  var reg=/^1? ?(\d{3}|\(\d{3}\))[ -]?\d{3}[ -]?\d{4}$/;
  var res=reg.test(str);
  return res;
}

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 sym(args) {
  var newArgs = Array.prototype.slice.call(arguments);//转化数组
  function diff(arr1,arr2){
    //闭包函数
    arr1 = Array.from(new Set(arr1));
    arr2 = Array.from(new Set(arr2));//对参数进行去重
    var counter = arr2.length;
    for(i = 0;i<arr1.length;i++){
      counter --;
      arr2 = arr2.filter(function(val){
        return val !== arr1[i];
      });//遍历arr2，并返回arr2不与arr1重复的元素
     if(counter<arr2.length){
       arr2.push(arr1[i]);//将arr1中不与arr2重复的元素添加进arr2中
       counter = arr2.length;
     }else{
       continue;
     }
    }
    return arr2;
  }
 for(x = 0;x<newArgs.length-1;x++){
   newArgs[x+1] = diff(newArgs[x],newArgs[x+1]);//对newArgs数组进行遍历
 }
  return newArgs[newArgs.length-1];
}
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);

Exact Change

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

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

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

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

本题代码来自fcc的wiki

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}
];
function checkCashRegister(price, cash, cid) {
  var change = cash - price;
// 遍历cid数组获得一个带有目前零钱总数和各零钱数额的register对象
  var register = cid.reduce(function(acc, curr) {
    acc.total += curr[1];
    acc[curr[0]] = curr[1];
    return acc;
  }, {total: 0});
//零钱正好找完
  if (register.total === change) {
    return 'Closed';
  }
// 零钱不够了
  if (register.total < change) {
    return 'Insufficient Funds';
  }
// 遍历denom数组
  var change_arr = denom.reduce(function(acc, curr) {
    var value = 0;
    // while该面值零钱仍有余额
    // 面值应当小于或等于找零
    while (register[curr.name] > 0 && change >= curr.val) {
      change -= curr.val;
      register[curr.name] -= curr.val;
      value += curr.val;
// 消除浮点数误差
      change = Math.round(change * 100) / 100;
    }
    if (value > 0) {
        acc.push([ curr.name, value ]);
    }
    return acc;
  }, []); // Initial value of empty array for reduce
// change_arr数组若没有元素或者无法找尽零钱，返回零钱不够了
  if (change_arr.length < 1 || change > 0) {
    return "Insufficient Funds";
  }
// Here is your change, ma'am.
  return change_arr;
}
// test here
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]]);

Inventory Update

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

function updateInventory(arr1, arr2) {
    arr1.forEach(function(v,ind,a){
      for(i=0;i<arr2.length;i++){
        if(arr2[i][1] == v[1]){
          v[0] +=arr2[i][0];
        }
      }
    });
  for(i=0;i<arr1.length;i++){
    arr2 = arr2.filter(function(val){
      return val[1] !== arr1[i][1];
    });
  }
    var newArr = arr1.concat(arr2);
  newArr.sort(function(a,b){
    return a[1].charCodeAt(0)-b[1].charCodeAt(0);
  });
  return newArr;
}
// Example inventory lists
updateInventory([[21, "Bowling Ball"], [2, "Dirty Sock"], [1, "Hair Pin"], [5, "Microphone"]], [[2, "Hair Pin"], [3, "Half-Eaten Apple"], [67, "Bowling Ball"], [7, "Toothpaste"]]);

No repeats please

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

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

function permAlone(str) {
  var reg = /(.)\1+/g;//正则
  var newArr = str.split('');
  var r = [];
  var num = str.length;
  (function f(t,a,n){
    if(n===0){
      return r.push(t);
    }
    for(var i=0;i<a.length;i++){
      f(t.concat(a[i]),a.slice(0,i).concat(a.slice(i+1)),n-1);
    }
  })([],newArr,num);//对数组进行全排列
  var res = r.map(function(val){
    return val.join('');
  });
  res = res.filter(function(val){
    return !val.match(reg);
  });//匹配正则
  return res.length;
}
permAlone('aab');

Friendly Date Ranges

让日期区间更友好！

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

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

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

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

例如:

makeFriendlyDates([“2016-07-01”, “2016-07-04”]) 应该返回 [“July 1st”,”4th”]

makeFriendlyDates([“2016-07-01”, “2018-07-04”]) 应该返回 [“July 1st, 2016”, “July 4th, 2018”].

function makeFriendlyDates(arr) {
  var Month = ["", "January", "February", "March", "April", "May", "June",
        "July", "August", "September", "October", "November", "December"
      ],//月份转换数组
      result = [];
  function test(dateStr) {
    dateStr = parseInt(dateStr,10);
    switch (dateStr) {
      case 1:
        dateStr += 'st';
        break;
      case 2:
        dateStr += 'nd';
        break;
      case 3:
        dateStr += 'rd';
        break;
      default:
        dateStr += 'th';
        break;
    }
    return dateStr;
}//日期转换
  var date1 = test(arr[0].substr(-2)),
      date2 = test(arr[1].substr(-2)),
      arr1 = arr[0].split('-'),
      arr2 = arr[1].split('-'),
      year = arr2[0]-arr1[0],
      month = arr2[1]-arr1[1],
      date = arr2[2]-arr1[2],
      month1 = arr[0].substr(5,2),
      month2 = arr[1].substr(5,2),
      year1 = arr[0].substr(0,4),
      year2 = arr[1].substr(0,4);
    switch(year){
      case 0:
        if(month ==11 && date == 30){
          //同年01-01和12-31
          result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1,Month[parseInt(month2,10)]+' '+date2+', '+year2);
        }else if(month === 0){
          if (date !== 0){
            //同年同月不同日
            result.push(Month[parseInt(month1,10)]+' '+date1,date2);
          }else{
            //同年同月同日
             result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1);
          }
        }else{
          //同年不同月
          result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1,Month[parseInt(month2,10)]+' '+date2);
        }
        break;
      case 1:
        if((month === 0 && date == -1)||month >0){
          //差一年整
          result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1,Month[parseInt(month2,10)]+' '+date2);
        }else if(month === 0 && date > -1){
          //差一年同月，大于一年
          result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1,Month[parseInt(month2,10)]+' '+date2+', '+year2);
        }else{
          //差一年，大于一年
          result.push(Month[parseInt(month1,10)]+' '+date1,Month[parseInt(month2,10)]+' '+date2);
        }
        break;
      default:
       result.push(Month[parseInt(month1,10)]+' '+date1+', '+year1,Month[parseInt(month2,10)]+' '+date2+', '+year2);
}
  return result;
}
makeFriendlyDates(["2018-01-01", "2018-12-31"]);

Make a Person

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

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

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

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

思路比较混乱，首先为了避免后面的代码影响到前面获取名字(get****Name)这几行代码，在更改时尽量将改变的数据存储到函数作用域内声明的变量中。

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

Map the Debris

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

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

至于轨道周期怎么求，戳这里 on wikipedia (不想看英文的话可以自行搜索以轨道高度计算轨道周期的公式).

求得的值应该是一个与其最接近的整数，轨道是以地球为基准的.

地球半径是 6367.4447 kilometers, 地球的GM值是 398600.4418, 圆周率为Math.PI

function orbitalPeriod(arr) {
  var GM = 398600.4418;
  var earthRadius = 6367.4447,
      altitude = [];
  for(var i=0;i<arr.length;i++){
    arr[i].orbitalPeriod = Math.round(2*Math.PI*Math.sqrt(Math.pow((earthRadius+arr[i].avgAlt),3)/GM));
    delete arr[i].avgAlt;
  }
  return arr;
}
orbitalPeriod([{name : "sputnik", avgAlt : 35873.5553}]);

Pairwise（找到你的另一半）

都说优秀的程序员擅长面向对象编程，但却经常找不到另一半，这是为什么呢？因为你总是把自己局限成为一个程序员，没有打开自己的思维。

这是一个社群的时代啊，在这里你应该找到与你有相同价值观但又互补的另一半。

譬如：你编程能力强，估值11分，如果以20分为最佳情侣来计算，你应该找一个设计能力强，估值为9分的女生。

那么当你遇到一个设计能力为9分的女生，千万别犹豫，大胆去表白。千万别以为后面的瓜比前面的甜哦。

举个例子：有一个能力数组[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 a = arr.reduce(function(acc,curr,ind,array){
    for(var i=ind+1;i<array.length;i++){
      if(array[ind] + array[i] == arg){
        array[ind] = array[i] = NaN;
        return acc+i+ind;
      }
    }
    return acc;
  },0);
  return a;
}
pairwise([1, 3, 2, 4], 4);