[筆記] LeetCode 刷題記錄 (28,58,67) – 2 @地瓜大的飛翔旅程

章節連結

題目

28. Implement strStr()
58. Length of Last Word
67. Add Binary

歷次 LeetCode 刷題記錄

LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有：Implement strStr、 Length of Last Word 和 Add Binary。

題目

28. Implement strStr()

[連結]：https://leetcode.com/problems/implement-strstr/

/* 1. 先排除邊界情況，如果 needle 根本沒有值，那就回傳 0 
*  2. 運用 String.prototype.indexOf，就可以直接取得 haystack 中有 needle 出現的起始 Index
*/
var strStr = function(haystack, needle) {
    if(needle.length === 0) return 0
    return haystack.indexOf(needle)
};

/* 1. 先排除邊界情況，如果 needle 根本沒有值，那就回傳 0

* 2. 運用 String.prototype.indexOf，就可以直接取得 haystack 中有 needle 出現的起始 Index

var strStr = function(haystack, needle) {

if(needle.length === 0) return 0

return haystack.indexOf(needle)

};

58. Length of Last Word

[連結]：https://leetcode.com/problems/length-of-last-word/

/* 雖然效率不是很好，但也是一開始想到的思路，就先記錄下來
*  1. 將原始字串前後去掉空白，再用 split 分割
*  2. 將目標字串的最後一個元素長度存至 result (如果 words 的長度不是 0 )
*/
var lengthOfLastWord = function(s) {
    let words = s.trim().split(" ")
    let result = 0
    
    if(words.length>0){
        result = words[words.length-1].length    
    }
    
    return result
};

/* 雖然效率不是很好，但也是一開始想到的思路，就先記錄下來

* 1. 將原始字串前後去掉空白，再用 split 分割

* 2. 將目標字串的最後一個元素長度存至 result (如果 words 的長度不是 0 )

var lengthOfLastWord = function(s) {

let words = s.trim().split(" ")

let result = 0

if(words.length>0){

result = words[words.length-1].length

}

return result

};

67. Add Binary

[連結]：https://leetcode.com/problems/add-binary/

/* 運用文字來解題
 *  1. 先將兩個字串都反轉，這樣要實作加法的時候，才會都從最後一位開始加
 *  2. 決定要執行多少次加法，根據最長的字串決定
 *  3-1. 迴圈內，會有 3 個變數：A字串的一位數；B字串的一位數和之前若有進位先 push 進來的一位數
 *  3-2. strA[i] , strB[i], result[i] 為避免 error，以 Number(strA[i] || 0) 的形式，來確保會變成 0
 *  4. 如果 currentSum >= 2，那 result[i] 就會是 %2 的結果，並 .push(1) 當作進位
 *  5. 等 result 生成後，要再反轉回去，就是結果了
*/

var addBinary = function(a, b) {
    let strA = a.split("").reverse().join("");
    let strB = b.split("").reverse().join("");
    let diffLength = strA.length > strB.length ? strA.length : strB.length;
    let result = []
    
    for(let i=0; i<diffLength; i++){
        let numA = Number(strA[i] || 0)
        let numB = Number(strB[i] || 0)
        let currentNum = Number(result[i]||0) + numA +numB
        
        if(currentNum >= 2){
            result[i] = currentNum % 2;
            result.push(1)
        }else{
            result[i] = currentNum
        }
    }

    return result.reverse().join("")
};

/* 此方法不可行，因為數字位數過大，會有 Infinity 問題
var addBinary = function(a, b) {
     let sum = parseInt(a,2) + parseInt(b,2);
     return sum.toString(2);
}

/*此方法在會吃瀏覽器版本，使用時要注意*/
/*BigInt 是新的語法，可以支援 2**53-1 以上的大數，為了將字串理解成 2 進位，所以要加上 "0b"*/
var addBinary = function(a, b) {
    let sum = BigInt(`0b${a}`) + BigInt(`0b${b}`) 
    return sum.toString(2)
}