Basic Algorithm Scripting

Basic Algorithm Scripting

Get Set for our Algorithm Challenges

• 用學過的概念回答開放式問題，練習程序猿思維

• 題目會很難，不要沮喪

• 無法招架就用 Read-Search-Ask 大招

• 準備好就開始吧

Reverse a String

function reverseString(str) {
  str=str.split(""); // str 不會變
  str=str.reverse(); // str 會變化
  str=str.join("");  // str 不會變
  return str;
}

reverseString("hello");

官方解答

• freeCodeCamp Algorithm Challenge Guide: Reverse a String - Guide - freeCodeCamp Forum

function reverseString(str) {
  return str.split('').reverse().join('');
}

Factorialize a Number

function factorialize(num) {
  var temp=1;

  for(i=num; i>0; i--){
    temp=temp*i;
  }
  return temp;
}

factorialize(5);

官方解答

• 用遞歸，函數自己呼叫自己

• freeCodeCamp Algorithm Challenge Guide: Factorialize A Number - Guide - freeCodeCamp Forum

function factorialize(num) {
  if (num === 0) { return 1; }
  return num * factorialize(num-1);
}

factorialize(5);

Check for Palindromes

• 官方解答有三種版本，我的解法偏向第二種

• freeCodeCamp Algorithm Challenge Guide: Check for Palindromes - Guide - freeCodeCamp Forum

• 正規表達式 - JavaScript | MDN

• Check for Palindromes | freeCodeCamp

• Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript

function palindrome(str) {
  // Good luck!

  // 切換成小寫，排除非字母符號，將字串轉成矩陣
  regular = /[A-Za-z0-9]/g;

  var lowerStr = str.toLowerCase();      // 轉成小寫
  var matchStr = lowerStr.match(regular);

  // 比較 i, matcherStr.length -i-1 的字母是否相同
  for (i=0; i<matchStr.length/2; i++){
    if (matchStr[i]!=matchStr[matchStr.length-1-i]){
      return false;
    }
  }

  return true;
}
palindrome("0_0 (: /-\ :) 0-0");

Find the Longest Word in a String

• 官方解答的第二三種作法，對我來說有點不直覺

• 二用了reduce()和math.max()，三用了recursiveness遞歸

• freeCodeCamp Algorithm Challenge Guide: Find the Longest Word in a String - Guide - freeCodeCamp Forum

• 從陣列計算最大和最小值

function findLongestWord(str) {

  var strArray = str.split(" ");
  var strLength=0;

  for(i=0; i<strArray.length; i++){
    if(strArray[i].length>strLength){
      strLength = strArray[i].length;
      console.log("i="+i);
      console.log("strLength="+strLength);
    }
  }

  return strLength;

}

findLongestWord("The quick brown fox jumped over the lazy dog");

我的第二種，用max

function findLongestWord(str) {
  // 请把你的代码写在这里

  strArray = str.split(" ");
  numArray = [];

  for(i=0; i<strArray.length; i++){
    numArray[i]=strArray[i].length;
  }

  biggestLength = Math.max(...numArray);

  return biggestLength;
}

findLongestWord("The quick brown fox jumped over the lazy dog");

Title Case a Sentence

• 想這題，覺得腦袋抽筋

• 官方有三種解法

• 一，用 substr() 取出字串，處理後合併

• 二，map()循環，直接用replace()取代，charAt()抓出字串

• 三，replace()取代，並用正則表達式

• freeCodeCamp Algorithm Challenge Guide: Title Case a Sentence - Guide - freeCodeCamp Forum

return str.toLowerCase()
      .replace(/(^|\s)\S/g, (L) => L.toUpperCase());`

自己的解法，第一種

function titleCase(str) {

  // 轉小寫，將各單字存進矩陣
  LowerStr = str.toLowerCase();
  strArray = LowerStr.split(" ");
  wordArray =[];

  // 把每個字母存進矩陣，並首字轉大寫
  for(i=0; i<strArray.length; i++){
    for(j=0; j<strArray[i].length; j++){
      wordArray[i]=strArray[i].split("");
    }
    wordArray[i][0] = wordArray[i][0].toUpperCase();
  }

  // 將字母合併回單字
  for(i=0; i<wordArray.length; i++){
    wordArray[i] = wordArray[i].join("");
  }

  // 將單字合併回句子
  UpperStr = wordArray.join(" ");

  return UpperStr;
}

titleCase("I'm a little tea pot");

自己的解法，第二種

• JavaScript replace() 方法

• JavaScript substring() 方法

• JavaScript slice() 方法

function titleCase(str) {
  // 请把你的代码写在这里

  // 小寫.分詞
  strArray = str.toLowerCase().split(" ");

  // 取首字大寫，連接其他字
    for(i=0; i<strArray.length; i++){
      strArray[i] = strArray[i].replace(strArray[i].charAt(0), strArray[i].charAt(0).toUpperCase());
    }

    strJoin = strArray.join(" ");

  console.log(strJoin);


  return strJoin;
}

titleCase("I'm a little tea pot");

自己的解法，第三種

• Array.prototype.map() - JavaScript | MDN

function titleCase(str) {
  // 请把你的代码写在这里

  // 小寫.分詞
  strArray = str.toLowerCase().split(" ");

  // 取首字大寫
  upStrArray = strArray.map(function (val){
      return val.replace(val.charAt(0),val.charAt(0).toUpperCase());
  });

    strJoin = upStrArray.join(" ");

  console.log(strJoin);


  return strJoin;
}

titleCase("I'm a little tea pot");

自己的解法，第四種

• 前面 split() 分詞的目的，是為了提取第一個字以便改成大寫。但用這則表達式的話，就能直接抓取每個字的首字

• 箭頭函數如果只執行一行，就不用加 return

• Regular Expression (RegExp) in JavaScript - 石頭閒語

• KingKong Bruce記事: JavaScript - 表單元素 - Regular Expression

function titleCase(str) {
  // 请把你的代码写在这里

  // 取首字大寫
  lowStr = str.toLowerCase();
  var upStr = str.replace(/(^|\s)\S/g, (L) => L.toUpperCase());

  console.log(upStr);

  return upStr;
}

titleCase("I'm a little tea pot");

自己的解法，第五種

• 匿名函數要用 return 回傳

function titleCase(str) {
  // 请把你的代码写在这里

  // 取首字大寫
  lowStr = str.toLowerCase();
  var upStr = lowStr.replace(/(^|\s)\S/g, function(L){
      return L.toUpperCase();
    });

  console.log(upStr);

  return upStr;
}

titleCase("I'm a little tea pot");

Return Largest Numbers in Arrays

• freeCodeCamp Algorithm Challenge Guide: Return largest Numbers in Arrays - Guide - freeCodeCamp Forum

我自己的解法

• 要先宣告變數為矩陣，不然會有問題

• javascript - Uncaught TypeError: Cannot set property '0' of undefined " - Stack Overflow

function largestOfFour(arr) {
  // You can do this!
  var bigArr=[];

  for(i=0; i<arr.length; i++){
      var temp=0;
      for(j=0; j<arr[i].length; j++){
          if(arr[i][j]>temp){
            temp=arr[i][j];
          }
      }
      bigArr[i]=temp;
  }

  console.log(bigArr);
  return bigArr;
}


largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

討論區看到的一個好懂的解法

• Math.max不吃矩陣，所以要加.apply

• 從陣列計算最大和最小值

• javascript - How does the Math.max.apply() work? - Stack Overflow

function largestOfFour(arr) {
  return arr.map(function(a) {
      return Math.max.apply(null, a);
  });
}

 largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

Confirm the Ending

• freeCodeCamp Algorithm Challenge Guide: Confirm the Ending - Guide - freeCodeCamp Forum

• String.prototype.endsWith() - JavaScript | MDN

• 相等比較 - JavaScript | MDN

我的解答

function confirmEnding(str, target) {
  // "Never give up and good luck will find you."
  // -- Falcor

  var strEnd = str.substring(str.length - target.length, str.length);

  return strEnd == target;
}

confirmEnding("Bastian", "n");

官方解答

function confirmEnding(str, target) {
  return str.substr(-target.length) === target;
}

Repeat a string repeat a string

• push 進陣列再 join 成字串的作法好蠢阿阿阿阿阿

• 有人說用 while 比較省時間

• concat

• repeat

• 遞迴

• freeCodeCamp Algorithm Challenge Guide: Repeat a string repeat a string - Guide - freeCodeCamp Forum

function repeatStringNumTimes(str, num) {
  // repeat after me
  var timeStr=[];
  for(i=0; i<num; i++){
    timesStr=timeStr.push(str);
  }
  return timeStr.join("");
}

repeatStringNumTimes("abc", 3);

Truncate a string

• freeCodeCamp Algorithm Challenge Guide: Truncate a String - Guide - freeCodeCamp Forum

• JavaScript取子串方法slice,substr,substring对比表 - Ider - 博客园

自己想的方法

function truncateString(str, num) {
  // Clear out that junk in your trunk
  var dotstr;

  if(num>=str.length){
      dotstr = str;
  } 
  else if(num<3){
      dotstr = str.slice(0,num)+"...";
  }
  else if(num<str.length){
      dotstr = str.slice(0,num-3)+"...";
  }

  console.log(dotstr);
  return dotstr;
}

truncateString("A-tisket a-tasket A green and yellow basket", 11);

官方的進階解答

function truncateString(str, num) {
  if (str.length <= num) {
    return str;
  } else {
    return str.slice(0, num > 3 ? num - 3 : num) + '...';
  }

Chunky Monkey

• freeCodeCamp Algorithm Challenge Guide: Chunky Monkey - Guide - freeCodeCamp Forum

• Array.prototype.slice() - JavaScript | MDN

• Array.prototype.splice() - JavaScript | MDN

自己想到的作法

function chunkArrayInGroups(arr, size) {
  // Break it up.
  var sliceArr = [];

  for(i=0; i<arr.length/size; i++){
      sliceArr.push(arr.slice(i*size, (i+1)*size));
  }

  return sliceArr;

}

chunkArrayInGroups([0, 1, 2, 3, 4, 5, 6, 7, 8], 2);
a= chunkArrayInGroups([0, 1, 2, 3, 4, 5, 6, 7, 8], 2);
console.log(a);

官方進階的解法

• Array.prototype.splice() - JavaScript | MDN

 function chunk(arr, size) {
  // 请把你的代码写在这里
  var spliceArr = [];

  while(arr.length){
    spliceArr.push(arr.splice(0,size));
  }

  return spliceArr;
}

chunk(["a", "b", "c", "d", 1, 2, 3, 4, 5], 2);

Slasher Flick

痾，數組截斷者

• 這題會不會有點簡單，雖然標題我完全看不懂什麼意思

• freeCodeCamp Algorithm Challenge Guide: Slasher Flick - Guide - freeCodeCamp Forum

function slasher(arr, howMany) {
  // it doesn't always pay to be first
  return arr.splice(howMany, arr.length);
}

slasher([1, 2, 3], 2);

Mutations

判斷arr[1]的字母是不是都在arr[0]出現過

• freeCodeCamp Algorithm Challenge Guide: Mutations - Guide - freeCodeCamp Forum

• String.prototype.indexOf() - JavaScript | MDN

我的作法

function mutation(arr) {
  var splitSec = arr[1].toLowerCase().split("");
  var pos = 0;

  for(i=0; i<splitSec.length; i++){
      if(pos!=-1){
          pos = arr[0].toLowerCase().indexOf(splitSec[i]);
          console.log(pos);
          if(pos==-1){
              return false;
          }
      }
      else if(pos==-1){
          return false;
      }
  }

  return true;
}

mutation(["hello", "hey"]);

第二種

function mutation(arr) {
  // 请把你的代码写在这里

  one = arr[0].toLowerCase();
  two = arr[1].toLowerCase();

  for(i=0; i<two.length; i++){
      if(one.indexOf(two[i]) === -1 ){
          return false;
      }
  }

  return true;
}

a = mutation(["hello", "he"]);
console.log(a)

• JavaScript Array.prototype.every() - Guide - freeCodeCamp Forum

先練習 every 的用法

var arr = [true, false, true];

function test(arr){
    return arr.every(function(val){
        return val === true;
    })
}

console.log(test(arr)); // false

自己的寫法

function mutation(arr) {
  // 请把你的代码写在这里

  // 先定義變數，把arr[0]轉成小寫，把arr[1]轉成小寫再分割字母
  var FirStr = arr[0].toLowerCase();
  var SecArr = arr[1].toLowerCase().split("");

  // SecArr 的字母，在FirStr中都有位置(indexOf回傳不是-1)?
  result = SecArr.every( (val) => FirStr.indexOf(val) !== -1 );

  //回傳結果
  console.log(result);
  return result;
}

mutation(["hello", "h"]);

Falsy Bouncer

• 去除 falsy 值，也就是 boolean 值為 false 的值

• freeCodeCamp Algorithm Challenge Guide: Falsy Bouncer - Guide - freeCodeCamp Forum

• Boolean - JavaScript | MDN

• Array.prototype.filter() - JavaScript | MDN

function bouncer(arr) {
  // Don't show a false ID to this bouncer.

  return arr.filter( (val) => Boolean(val) != false );

}

bouncer([7, "ate", "", false, 9]);

留言串看到的解法

function bouncer(arr) {
  var a = [];
  arr.forEach(function(el){
  if(el){
    a.push(el);}});
 return a;}

列舉式的寫法

function badValues(val){  
 return val !== false && val !== null && val !== 0 && val !== "" && val !== undefined && !Number.isNaN(val);   
}

function bouncer(arr) {
  return arr.filter(badValues);  
}

bouncer([1, null, NaN, 2, undefined]);

Seek and Destroy

從矩陣中移除後面參數出現的東西

• 參數物件，第一次聽到這個東西

• Arguments object - JavaScript | MDN

• freeCodeCamp Algorithm Challenge Guide: Seek and Destroy - Guide - freeCodeCamp Forum

function destroyer(arr) {
  // Remove all the values

  // 先拿到參數矩陣，再另存參數一矩陣
  var args = Array.from(arguments);
  var arr0 = args.shift(); //arr0等於參數一，args等於其他的參數

  // 排除arr0 中含有 agrs 的內容
  // callback 函數有三個參數，當前值，目錄，與要篩選的矩陣
  // 如果args[i]==val，回傳 false，代表從arr0篩除
   return arr0.filter(function(val, index, arr0){

    var result = true;

    // 如果有一個
    for(i=0; i<args.length; i++){
       if (args[i]===val){
         result = false;
       }
     }
     return result;

   });
}

a = destroyer([1, 2, 3, 1, 2, 3], 2, 3);
console.log(a)

其他解法

var args = Array.prototype.slice.call(arguments, 1);

return arr.filter(function(val){ return args.every(x => x !== val); });

其他解法

function destroyer(arr) {
    var filterList = [];

    for (var i = 1; i < arguments.length; i++) {
        filterList.push(arguments[i]);
    }

    return arr.filter(function(val) {
        return filterList.indexOf(val) < 0;
    });
}

destroyer([1, 2, 3, 1, 2, 3], 2, 3);

其他解法

function destroyer(arr) {
 var args = Array.prototype.slice.call(arguments, destroyer.length); 

  return arr.reduce((acc, item) => {
         if (!args.includes(item)) { 
            acc.push(item);
         }  
         return acc;

 }, []);

官方解法一

function destroyer(arr) {
  var args = Array.prototype.slice.call(arguments);

  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < args.length; j++) {
      if (arr[i] === args[j]) {
        delete arr[i];
      }
    }
  }
  return arr.filter(Boolean);

官方解法二

function destroyer(arr) {
  var args = Array.from(arguments).slice(1);
  return arr.filter(function(val) {
    return !args.includes(val);
  });
}

Where do I belong

• freeCodeCamp Algorithm Challenge Guide: Where do I Belong - Guide - freeCodeCamp Forum

我的解法

• 一開始忘記 sort 的特性，做了許多白工

• Array.prototype.sort() - JavaScript | MDN

function getIndexToIns(arr, num) {
  // Find my place in this sorted array.

  arr.push(num);
  arr.sort((a,b)=>a-b);

  return arr.indexOf(num);

}

getIndexToIns([2, 5, 10], 15);

官方的中等作法

• Array.prototype.findIndex() - JavaScript | MDN

function getIndexToIns(arr, num) {
  // sort and find right index
  var index = arr.sort((curr, next) => curr > next)
    .findIndex((currNum)=> num <= currNum);
  // Returns proper answer
  return index === -1 ? arr.length : index;
}

getIndexToIns([40, 60], 500);

官方的進階作法

• Method Chaining in JavaScript | Gregory Schier

• Array.prototype.concat() - JavaScript | MDN

function getIndexToIns(arr, num) {

return arr.concat(num).sort((a,b) => a-b).indexOf(num);

}

getIndexToIns([1,3,4],2);

Caesars Cipher

• freeCodeCamp Algorithm Challenge Guide: Caesars Cipher - Guide - freeCodeCamp Forum

• 正規表達式 - JavaScript | MDN

• String.prototype.charCodeAt() - JavaScript | MDN

• String.fromCharCode() - JavaScript | MDN

function rot13(str) { // LBH QVQ VG!
  var result="";
  var zAt = "Z".charCodeAt(0);
  var aAt = "A".charCodeAt(0);

  for(i=0; i<str.length; i++){
    if(/\W/.exec(str[i])){
      result = result + str[i];
    }
    else if( (zAt - str.charCodeAt(i)) < 13){
      result = result + String.fromCharCode(str.charCodeAt(i)-13);
    }
    else{
      result = result + String.fromCharCode(str.charCodeAt(i)+13);
    }  
  }

  console.log(result);
  return result;
}

// Change the inputs below to test
rot13("SERR CVMMN!");

官方解答有三種解法

官方解法一

• arr.map.call(str, callback) 用在非 array 的物件(arr本身不重要)

• Array.prototype.map() - JavaScript | MDN

function rot13(str) {
  // Split str into a character array
  return str.split('')
  // Iterate over each character in the array
    .map.call(str, function(char) {
      // Convert char to a character code
      x = char.charCodeAt(0);
      // Checks if character lies between A-Z
      if (x < 65 || x > 90) {
        return String.fromCharCode(x);  // Return un-converted character
      }
      //N = ASCII 78, if the character code is less than 78, shift forward 13 places
      else if (x < 78) {
        return String.fromCharCode(x + 13);
      }
      // Otherwise shift the character 13 places backward
      return String.fromCharCode(x - 13);
    }).join('');  // Rejoin the array into a string
}

官方解法二

• fn.apply(something, array) 可以把矩陣的內容當作參數個別傳入

• 深入浅出妙用 Javascript 中 apply、call、bind - WEB前端 - 伯乐在线

• 【javascript】call 和 apply « 和平，奮鬥，救WEB

• javascript - How does the Math.max.apply() work? - Stack Overflow

• regular.test() 傳回 boolean

• RegExp.prototype.test() - JavaScript | MDN

// Solution with Regular expression and Array of ASCII character codes
function rot13(str) {
  var rotCharArray = [];
  var regEx = /[A-Z]/ ;
  str = str.split("");
  for (var x in str) {
    if (regEx.test(str[x])) {
      // A more general approach
      // possible because of modular arithmetic
      // and cyclic nature of rot13 transform
      rotCharArray.push((str[x].charCodeAt() - 65 + 13) % 26 + 65);
    } else {
      rotCharArray.push(str[x].charCodeAt());
    }
  }
  str = String.fromCharCode.apply(String, rotCharArray);
  return str;
}

// Change the inputs below to test
rot13("LBH QVQ VG!");

第三種解法

• $0 代表正則表達式篩出來的內容，$1 代表內容的第一個被篩出來的部份

• JavaScript String.prototype.replace() - Guide - freeCodeCamp Forum

• javascript - $0 and $1 in Regular Expression - Stack Overflow

• [ JS 进阶 ] test, exec, match, replace - kraaas前端博客 - SegmentFault

function rot13(str) { // LBH QVQ VG!
  return str.replace(/[A-Z]/g, L => String.fromCharCode((L.charCodeAt(0) % 26) + 65));
}