Category: Leetcode

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
Breadth First Search Leetcode Recursion

Number of Islands

let numIslands = function(matrix) {

    if (!matrix.length) return 0;

    let land = 1, visited = 'X',
        counter = 0,
        maxRow = matrix.length - 1,
        maxCol = matrix[0].length - 1;

    function exploreAndMark(row, col) {
        if (row < 0 || col < 0 || row > maxRow || col > maxCol) {
            return;
        }

        if (matrix[row][col] === land) {
            matrix[row][col] = visited;

            // explore up
            exploreAndMark(row - 1, col);

            // explore down
            exploreAndMark(row + 1, col);

            // explore left
            exploreAndMark(row, col - 1);

            // explore right
            exploreAndMark(row, col + 1);
        }
    }

    for (let row = 0; row <= maxRow; row++) {
        for (let col = 0; col <= maxCol; col++) {
            if (matrix[row][col] === land) {
                counter++;
                exploreAndMark(row, col);
            }
        }
    }

    return counter;
}
Categories
Leetcode

Two Sum

function twoSum(nums, target) {
    let result = [],
        cache = {};
    for (let i = 0; i < nums.length; i++) {
        let x = target - nums[i];
        if (cache[x] !== undefined) {
            result.push([cache[x], i]);
        }
        cache[nums[i]] = i;
    }

    return result;
};
Categories
Leetcode Parenthesis String

Valid Parenthesis

function validParenthesis(str) {

    let closingMap = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }

    let chars = [];
    for(let i = 0; i < str.length; i++) {
        if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
            chars.push(str[i]);
        }
        else {
            let compare = chars.pop();
            if (closingMap[str[i]] !== compare) return false;
        }
    }
    return chars.length === 0;
}
Categories
Binary Tree Leetcode Recursion

Is Same Tree

let isSameTree = function(p, q) {

    if (p === q) return true;
    if (p?.val !== q?.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
Categories
Binary Tree Leetcode Recursion

Invert a Binary Tree

let invertTree = function(root) {

    if (root) {
        const right = root.right;
        root.right = invertTree(root.left)
        root.left = invertTree(right)
        return root;
    }
    return null;
};