Month: May 2020

Categories
Binary Tree Breadth First Search

Level Order Tree Traversal

function levelOrder(root) {

    let queue = [root], result = [];
    function process(node) {
        result.push(node.val);
    }

    while (queue.length) {
        const node = queue.pop();
        process(node);
        if (node.left) queue.unshift(node.left);
        if (node.right) queue.unshift(node.right);
    }

    return result; //?
}
Categories
Leetcode

LinkedList Middle Node

let middleNode = function(head) {
    let slow = head, fast = head;
    while (fast) {
        if (fast.next !== null && fast.next.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        else if (fast.next) {
            slow = slow.next;
            break;
        }
        else {
            break;
        }
    }
    return slow;
};
Categories
Leetcode

Reverse Middle of LinkedList

// m = start of items to reverse, n = end of item to reverse
let reverseBetween = function(head, m, n) {

    let node = head,
        result = [],
        reversed = [],
        counter = 1;

    while (node) {
        let next = node.next;
        if (counter < m) {
            result.push(node); //?
        }
        if (counter >=m && counter <= n) {
            node.next = null;
            reversed.push(node); //?
        }
        else if (counter > n) {
            // all reversals are done
            // drain reversed into result
            while (reversed.length) {
                result.push(reversed.pop()); //?
            }
            result.push(node);
            break;
        }

        counter++;
        node = next;
    }

    // if reversals are done at the end of the linkedlist
    while (reversed.length) {
        result.push(reversed.pop()); //?
    }

    let root = new ListNode(0), tail = root;
    while (result.length) {
        tail.next = result.shift();
        tail = tail.next;
        console.log(tail);
    }

    return root.next; //?
};
Categories
Leetcode

Reverse LinkedList (Iterative)

let reverseLinkedList = function(root) {

    let reverse = new ListNode(0);

    let node = root;
    while (node) {
        let toAdd = node;
        let next = node.next;

        let reversedNext = reverse.next;
        toAdd.next = reversedNext;
        reverse.next = toAdd; //

        node = next;
    }
    return reverse.next;
}
Categories
Leetcode Recursion

Reverse LinkedList (Recursion)

let reverseLinkedList = function(root, reverse = new ListNode(0)) {
    if (root) {
        let toAdd = root;
        let next = root.next;

        let reversedNext = reverse.next;
        toAdd.next = reversedNext;
        reverse.next = toAdd;

        reverseLinkedList(next, reverse);
    }
    return reverse.next;
}
Categories
Dynamic Programming Leetcode Recursion

Fibonacci (Recursion)

function fib(x) {
    let cache = {}
    function fibInternal(n) {
        if(n == 0) return 0;
        if(n <= 2) return 1;
        if (cache[n]) return cache[n];

        const result = fibInternal(n - 1) + fibInternal(n - 2);
        cache[n] = result;
        return result;
    }

    return fibInternal(x)
}
Categories
Leetcode

Fibonacci (Iterative)

function fib(n) {
    if(n === 0) return 0;
    if(n <= 2) return 1;

    let x = 1, y = 2;
    for(let i = 3; i < n; i++) {
        let oldX = x;
        x = y;
        y = y + oldX;  /*?.*/
    }

    return y; 
}
Categories
Leetcode String

Int to Roman

let intToRoman = function(num) {

    const mapping = {
        1000: 'M',
        900:  'CM',
        500:  'D',
        400:  'CD',
        100:  'C',
        90:   'XC',
        50:   'L',
        40:   'XL',
        10:   'X',
        9:    'IX',
        5:    'V',
        4:    'IV',
        1:    'I'
    }

    let result = "";
    for(let divisor of [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]) {
        if (num >= divisor) {
            let quotient = Math.floor(num / divisor);
            result = result + mapping[divisor].repeat(quotient);
            num = num % divisor;
        }
    }

    return result;
}
Categories
Leetcode Recursion String

Look and Say

let lookAndSay = function(nth, number = "1") {
    if (nth === 1) return number;

    let index = 0,
        counter = 1,
        currentNumber = "";

    let result = "";
    while (index < number.length) {
        if (index === 0) {
            currentNumber = number[index];
        }
        else if (currentNumber === number[index]) {
            counter++;
        }
        else if (currentNumber !== number[index]) {
            result = `${result}${counter}${currentNumber}`;//?
            counter = 1;
            currentNumber = number[index];
        }

        index++;
    }

    result = `${result}${counter}${currentNumber}`;//?

    return lookAndSay(--nth, result);
}
Categories
Recursion Sort

Merge Sort

let mergeSort = function(numbers) {

    function mergeSort(arr) {
        if (arr.length === 1) return arr;
        let center = Math.floor(arr.length / 2);
        let left = arr.slice(0, center);
        let right = arr.slice(center);
        return merge(mergeSort(left), mergeSort(right));
    }
    
    function merge(left, right) {
        let results = [];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                results.push(left.shift());
            }
            else {
                results.push(right.shift());
            }
        }

        return [...results, ...left, ...right];
    }

    return mergeSort(numbers);
}