[筆記] LeetCode 刷題記錄 (13,20,38) – 1 @地瓜大的飛翔旅程

章節連結

題目

13. Roman to Integer
20. Valid Parentheses
38. Count and Say

歷次 LeetCode 刷題記錄

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

題目

13. Roman to Integer

[連結]：https://leetcode.com/problems/roman-to-integer/

/* 1. 先將所有的可能的文字組合和其對應數字都列出
*  2. 造出文字和數字相對應的兩個 Array
*  3. 遍歷整個文字迴圈，當字串有發現對應的文字時，將對應的數字加入結果，同時把字串中對應的文字給覆蓋掉
*/
var romanToInt = function(s) {
    const romanNumbers = {
        "M": 1000, 
        "CM": 900,
        "D": 500,
        "CD": 400,
        "C":100,
        "XC":90,
        "L":50,
        "XL":40,
        "X":10,
        "IX":9,
        "V":5,
        "IV":4,
        "I":1
    }
    const romans = Object.keys(romanNumbers)
    const numbers= Object.values(romanNumbers)
    let result = 0
    
    for(let i=0;i<romans.length;i++){
        while(s.indexOf(romans[i]) === 0){
            result += numbers[i]
            s = s.replace(romans[i],"")
        }
    }
    
    return result
};

/* 1. 先將所有的可能的文字組合和其對應數字都列出

* 2. 造出文字和數字相對應的兩個 Array

* 3. 遍歷整個文字迴圈，當字串有發現對應的文字時，將對應的數字加入結果，同時把字串中對應的文字給覆蓋掉

var romanToInt = function(s) {

const romanNumbers = {

"M": 1000,

"CM": 900,

"D": 500,

"CD": 400,

"C":100,

"XC":90,

"L":50,

"XL":40,

"X":10,

"IX":9,

"V":5,

"IV":4,

"I":1

}

const romans = Object.keys(romanNumbers)

const numbers= Object.values(romanNumbers)

let result = 0

for(let i=0;i<romans.length;i++){

while(s.indexOf(romans[i]) === 0){

result += numbers[i]

s = s.replace(romans[i],"")

}

return result

};

20. Valid Parentheses

[連結]：https://leetcode.com/problems/valid-parentheses/

/* 雖然效率不是很好，但也是一開始想到的思路，就先記錄下來
*  1. 將成對的字串列表，放到一個 Array 名為 params 中
*  2. 反覆進行 removeParams 的函式，把要檢驗的字串傳入。若最後檢驗的字串經由層層摘除後，還有剩餘，那就表示有不合法的input
*  removeParams 函式的思路：
*  遍歷 params 裡的三個字串，跟檢驗的字串進行比對，如果有比對到的，那就把對應的字串以""取代
*  同時，用一個計數器來記錄沒有比對成功的次數
*  如果這個次數不是 3 ，那麼將計數器歸 0，並再次呼叫回傳 removeParams(s)
*  若次數為 3 ，表示能取代成空白的都取代掉了，如果 s 還有值，那就表示 input 不合法。
*/
var isValid = function(s) {
    const params = ["()","[]","{}"]
    if(!s) return true
    
    let result = removeParams(s)
    
    function removeParams(s){
        let noParamCount = 0

        for(let i=0; i<params.length;i++){
            if(s.indexOf(params[i])>-1){
                s = s.replace(params[i],"")
            }else{
                noParamCount ++
            }
        }
        
        if(noParamCount === 3){
            return s ? false : true
        }else{
            noParamCount = 0
            return removeParams(s)
        }
    }
    
    return result
};

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

* 1. 將成對的字串列表，放到一個 Array 名為 params 中

* 2. 反覆進行 removeParams 的函式，把要檢驗的字串傳入。若最後檢驗的字串經由層層摘除後，還有剩餘，那就表示有不合法的input

* removeParams 函式的思路：

* 遍歷 params 裡的三個字串，跟檢驗的字串進行比對，如果有比對到的，那就把對應的字串以""取代

* 同時，用一個計數器來記錄沒有比對成功的次數

* 如果這個次數不是 3 ，那麼將計數器歸 0，並再次呼叫回傳 removeParams(s)

* 若次數為 3 ，表示能取代成空白的都取代掉了，如果 s 還有值，那就表示 input 不合法。

var isValid = function(s) {

const params = ["()","[]","{}"]

if(!s) return true

let result = removeParams(s)

function removeParams(s){

let noParamCount = 0

for(let i=0; i<params.length;i++){

if(s.indexOf(params[i])>-1){

s = s.replace(params[i],"")

}else{

noParamCount ++

}

if(noParamCount === 3){

return s ? false : true

}else{

noParamCount = 0

return removeParams(s)

}

return result

};

38. Count and Say

[連結]：https://leetcode.com/problems/count-and-say/

/* 從 n = 1 逐步延展到 n = 30
*  當 n = 2 時，是看 n = 1 時的字串來決定。可以用 two pointer 的想法來處理
*  若 n = 1 ，那直接回傳 "1"
*  接著由 1 ~ n-1 進行迴圈，每次得到的新字串都由前一個傳入的字串決定
*  generateStr 函式裡面有兩個指針：左邊的指針先固定在 0 ，右邊的指針則由 1 開始往右直到最後的 string 可以被考慮到 
*  如果右邊的指針數字不等於左邊的指針數字，那表示就會有 i-pointer 個某數字 string[pointer]
*  接著把左邊的 pointer 換成 i 的位置，重新再算
*/
var countAndSay = function(n) {
    if(n<=1) return "1";
    
    let result = "1";
    
    for(let i=1; i<n;i++){
        result = generateStr(result)
    }
    
    function generateStr(string){
        let pointer = 0
        let result = ""
        
        for(let i=1; i<=string.length;i++){
            if(string[i] !== string[pointer]){
                let length = i - pointer
                result += length + string[pointer]
                pointer = i
            }
        }

        return result
    }
    
    return result
};