[筆記] LeetCode 刷題記錄 (2,22,621) – 10 @地瓜大的飛翔旅程

章節連結

題目

2. Add Two Numbers
22. Generate Parentheses
621. Task Scheduler

歷次 LeetCode 刷題記錄

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

題目

2. Add Two Numbers

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

/*
* 1. 給定一個新的 Node 為 0，並用 head 變數來儲存一開始的位置
* 2. 宣告一個儲存要進多少位的 carry，並開始移動 list
* 3. 由於 l1,l2 的長度不會一樣，所以要分開加總。當 l1,l2 和 carry 都為 null 或 0 的時候
* 才停止
* 4. 一位一位計算，並將結果推到 list 中
* 5. 最後的結果會像是 "0"12345......，所以要取 head.next 以後的結果才對
*/

var addTwoNumbers = function(l1, l2) {
    let list = new ListNode(0)
    const head = list
    let carry = 0
    
    while(l1 || l2 || carry>0){
        let sum = 0
        if(l1 !== null){
            sum += l1.val
            l1 = l1.next
        }
        if(l2 !== null){
            sum += l2.val
            l2 = l2.next
        }
        sum += carry
        
        list.next = new ListNode(sum % 10)
        carry = parseInt(sum / 10)
        
        list = list.next
    }
    
    return head.next
};

* 1. 給定一個新的 Node 為 0，並用 head 變數來儲存一開始的位置

* 2. 宣告一個儲存要進多少位的 carry，並開始移動 list

* 3. 由於 l1,l2 的長度不會一樣，所以要分開加總。當 l1,l2 和 carry 都為 null 或 0 的時候

* 才停止

* 4. 一位一位計算，並將結果推到 list 中

* 5. 最後的結果會像是 "0"12345......，所以要取 head.next 以後的結果才對

var addTwoNumbers = function(l1, l2) {

let list = new ListNode(0)

const head = list

let carry = 0

while(l1 || l2 || carry>0){

let sum = 0

if(l1 !== null){

sum += l1.val

l1 = l1.next

}

if(l2 !== null){

sum += l2.val

l2 = l2.next

}

sum += carry

list.next = new ListNode(sum % 10)

carry = parseInt(sum / 10)

list = list.next

}

return head.next

};

22. Generate Parentheses

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

/**
 * 重複呼叫的經典題，當左括號的剩餘數量大於右括號，那就繼續添加左括號直到等於 n
 */

/**
 * @param {number} n
 * @return {string[]}
 */

var generateParenthesis = function(n) {
    let result = []
    generateStr(n,n,"",result)
    return result
};

function generateStr(leftCount,rightCount,str,result){
    if(leftCount>rightCount) return;
    if(leftCount === 0 && rightCount === 0){
        result.push(str)
    }else{
        if(leftCount > 0){
            generateStr(leftCount-1,rightCount,str+"(",result)
        }
        if(rightCount > 0){
            generateStr(leftCount,rightCount-1,str+")",result)
        }
    }
}

/**

* 重複呼叫的經典題，當左括號的剩餘數量大於右括號，那就繼續添加左括號直到等於 n

/**

* @param {number} n

* @return {string[]}

var generateParenthesis = function(n) {

let result = []

generateStr(n,n,"",result)

return result

};

function generateStr(leftCount,rightCount,str,result){

if(leftCount>rightCount) return;

if(leftCount === 0 && rightCount === 0){

result.push(str)

}else{

if(leftCount > 0){

generateStr(leftCount-1,rightCount,str+"(",result)

}

if(rightCount > 0){

generateStr(leftCount,rightCount-1,str+")",result)

}

621. Task Scheduler

[連結]：https://leetcode.com/problems/task-scheduler/

/**
 * 1. 若 n 為 0，則回傳 tasks 的長度就好
 * 2. 先取得每個文字的出現頻率、再找出頻率最大值
 * 3. 兩兩相同 task 的間隔為 n+1 ，會出現 頻率最大值-1 次
 * 4. 不完整的末端長度，可由滿足頻率最大值的個數來決定
 */
var leastInterval = function(tasks, n) {
    if(n===0) return tasks.length
    const frequencyMap = tasks.reduce((pre,next)=>{
        pre[next] = pre[next] + 1 || 1
        return pre   
    }
    ,{})
    const maxFrequency = Math.max(...Object.values(frequencyMap))
    const lastRowLength = Object.values(frequencyMap).filter(d=>d===maxFrequency).length
    
    return Math.max(tasks.length, (maxFrequency-1) * (n+1) + lastRowLength)
};