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的數(shù)字三次比下面多匹配一個括號苛聘，左右括號分別需要加上轉(zhuǎn)義字符\
  // \d{3}匹配一個0-9的數(shù)字三次
  //\s?表示空白字符匹配0次或1次
  //[\s\-]?表示空格或者連字符-匹配0次或1次
  //\d{4}$表示已4位數(shù)字結(jié)尾($)
  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

創(chuàng)建一個函數(shù)，接受兩個或多個數(shù)組忠聚，返回所給數(shù)組的 對等差分(symmetric difference) (△ or ⊕)數(shù)組.

給出兩個集合 (如集合 A = {1, 2, 3} 和集合 B = {2, 3, 4}), 而數(shù)學(xué)術(shù)語 "對等差分" 的集合就是指由所有只在兩個集合其中之一的元素組成的集合(A △ B = C = {1, 4}). 對于傳入的額外集合 (如 D = {2, 3}), 你應(yīng)該安裝前面原則求前兩個集合的結(jié)果與新集合的對等差分集合 (C △ D = {1, 4} △ {2, 3} = {1, 2, 3, 4}).
參考鏈接
方法一:

function getSym(arr1, arr2) {
    // 得到在第一個數(shù)組设哗，但不在第二個數(shù)組中的元素
    var result = arr1.filter(function(e) {
        return arr2.indexOf(e) === -1;
    });

    // 得到在第二個數(shù)組，但不在第以個數(shù)組中的元素
    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

設(shè)計一個收銀程序 checkCashRegister() 两蟀，其把購買價格(price)作為第一個參數(shù) , 付款金額 (cash)作為第二個參數(shù), 和收銀機中零錢 (cid) 作為第三個參數(shù).

cid 是一個二維數(shù)組网梢，存著當(dāng)前可用的找零.

當(dāng)收銀機中的錢不夠找零時返回字符串 "Insufficient Funds". 如果正好則返回字符串 "Closed".

否則, 返回應(yīng)找回的零錢列表,且由大到小存在二維數(shù)組中.

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

依照一個存著新進貨物的二維數(shù)組，更新存著現(xiàn)有庫存(在 arr1 中)的二維數(shù)組. 如果貨物已存在則更新數(shù)量 . 如果沒有對應(yīng)貨物則把其加入到數(shù)組中赂毯，更新最新的數(shù)量. 返回當(dāng)前的庫存數(shù)組战虏，且按貨物名稱的字母順序排列.

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

把一個字符串中的字符重新排列生成新的字符串，返回新生成的字符串里沒有連續(xù)重復(fù)字符的字符串個數(shù).連續(xù)重復(fù)只以單個字符為準

例如, aab 應(yīng)該返回 2 因為它總共有6中排列 (aab, aab, aba, aba, baa, baa), 但是只有兩個 (aba and aba)沒有連續(xù)重復(fù)的字符 (在本例中是 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

讓日期區(qū)間更友好党涕！

把常見的日期格式如：YYYY-MM-DD 轉(zhuǎn)換成一種更易讀的格式烦感。

易讀格式應(yīng)該是用月份名稱代替月份數(shù)字，用序數(shù)詞代替數(shù)字來表示天 (1st 代替 1).

記住不要顯示那些可以被推測出來的信息: 如果一個日期區(qū)間里結(jié)束日期與開始日期相差小于一年遣鼓，則結(jié)束日期就不用寫年份了啸盏；在這種情況下，如果月份開始和結(jié)束日期如果在同一個月骑祟，則結(jié)束日期月份也不用寫了回懦。

另外, 如果開始日期年份是當(dāng)前年份，且結(jié)束日期與開始日期小于一年次企，則開始日期的年份也不用寫怯晕。

例如:

包含當(dāng)前年份和相同月份的時候，makeFriendlyDates(["2017-01-02", "2017-01-05"]) 應(yīng)該返回 ["January 2nd","5th"]

不包含當(dāng)前年份缸棵，makeFriendlyDates(["2003-08-15", "2009-09-21"]) 應(yīng)該返回 ["August 15th, 2003", "September 21st, 2009"]舟茶。

請考慮清楚所有可能出現(xiàn)的情況，包括傳入的日期區(qū)間是否合理堵第。對于不合理的日期區(qū)間吧凉，直接返回 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; //判斷在一年以內(nèi)返回true
        else return d2[2] < d1[2] ? true : false; //判斷是否在一年以內(nèi)
      }  
    }  
  };  
  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){  //開始年份為當(dāng)前年份 
      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

用下面給定的方法構(gòu)造一個對象.

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

所有有參數(shù)的方法只接受一個字符串參數(shù).

所有的方法只與實體對象交互.

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

返回一個數(shù)組，其內(nèi)容是把原數(shù)組中對應(yīng)元素的平均海拔轉(zhuǎn)換成其對應(yīng)的軌道周期.

原數(shù)組中會包含格式化的對象內(nèi)容踏志，像這樣 {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

有一個能力數(shù)組[7,9,11,13,15]阀捅，按照最佳組合值為20來計算，只有7+13和9+11兩種組合针余。而7在數(shù)組的索引為0饲鄙，13在數(shù)組的索引為3凄诞，9在數(shù)組的索引為1，11在數(shù)組的索引為2忍级。
所以我們說函數(shù)：pairwise([7,9,11,13,15],20) 的返回值應(yīng)該是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);