leetcode.js

/**
 * https://leetcode.com/problems/integer-to-roman/description/
 * https://en.wikipedia.org/wiki/Roman_numerals
 * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Arithmetic_Operators
 * 
 * @param {number} num
 * @return {string}
 */
function intToRoman(num) {
    var base = {
        1: 'I',
        5: 'V',
        10: 'X',
        50: 'L',
        100: 'C',
        500: 'D',
        1000: 'M'
    };

    var ret = '';

    var from1to9 = function(num) {
        if (num == 1) {
            ret = base[1];
        }
        if (num == 2) {
            ret = base[1] + base[1];
        }
        if (num == 3) {
            ret = base[1] + base[1] + base[1];
        }
        if (num == 4) {
            ret = base[1] + base[5];
        }
        if (num == 5) {
            ret = base[5];
        }
        if (num == 6) {
            ret = base[5] + base[1];
        }
        if (num == 7) {
            ret = base[5] + base[1] + base[1];
        }
        if (num == 8) {
            ret = base[5] + base[1] + base[1] + base[1];
        }
        if (num == 9) {
            // similar pattern as for 400 (CD), 900(CM) - limit number before finite value from base (4 before 5, 9 before 10, 400 before 500)
            ret = base[1] + base[10];
        }

        return ret;
    };


    if (num < 10) {
        ret = from1to9(num);
    }
    if (num == 10) {
        ret = base[10];
    }

    var reminder = num % 10;
    if (reminder == 0) { // X-tens
        // TODO
    } else {
        // reminder is between 1 and 9 // should reuse existed 1-9 algorithm
    }

    return ret;
};

// for (var i = 1; i < 3999; i++) {
//     console.log(intToRoman(i));
// }


//
// =================================
//

/**
 * Find similarity in pattern sequence, and then, check, if str has similar sequence
 *
 * https://en.wikipedia.org/wiki/Bijection
 * http://www.tutorvista.com/content/math/different-types-of-functions/
 * https://commons.wikimedia.org/wiki/Category:Arrow_diagrams_of_mappings
 * 
 * @param {string} pattern
 * @param {string} str
 * @return {boolean}
 */
function wordPattern(pattern, str) {
    var char1 = pattern[0],
        char2 = pattern[1],
        char3 = pattern[2],
        char4 = pattern[3];

    // 010, 100
    var patternSymbolicNumber = '' + Number(char1 == char2) + Number(char2 == char3) + Number(char3 == char4);
    console.log(patternSymbolicNumber);

    var strs = str.split(' ');

    if (pattern.length === strs.length) {
        var setsAreTheSameLength = true;
    }

    var bijectiveFunction = function() {
        // TODO
    }

    var strSymbolicNumber = '' + Number(strs[0] == strs[1]) + Number(strs[1] == strs[2]) + Number(strs[2] == strs[3]);
    console.log(strSymbolicNumber);

    var ret = patternSymbolicNumber == strSymbolicNumber;
    console.log(ret); // WRONG !!!

    return ret;
}

// wordPattern("abba","dog cat cat dog"); // => true // CORRECT
// wordPattern("abba","dog cat cat fish"); // => false // WRONG
// wordPattern("aaaa","dog cat cat dog"); // => false
// wordPattern("abba","dog dog dog dog"); // => false

//
// =================================
//

// https://en.wikipedia.org/wiki/Binary_tree
// https://en.wikipedia.org/wiki/Binary_search_tree
// https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
// 
/**
 * !!!
 * ARRAY BASED VERSION
 * !!!
 * @param {numbers[]} root
 * @return {string[][]}
 */
function printTree(root) {
    //
    // by using console.log(root) it shows TreeNode structured object.
    // but by returning root to output, it shows simple array. Maybe it's Leetcode specific.
    //

    // https://www.quora.com/What-is-the-next-term-of-this-sequence-1-3-7-15-31-63-_
    // Looks like max numbers of child nodes, depends on binary tree height
    // [1] is always on top, and TOTAL number of nodes is ==1==

    // ==3==
    // [1,2]
    // [1,2,3] form triangle
    // 2, 3 under 1 - meaning, every direct closest node has ONLY 2 children, but TOTAL number of nodes is ==3==

    // ==7==
    // [1,2,3,4] forms family Tree/GenealogyTree like view. TOTAL number of nodes is ==7==
    // [1,2,3,4,5]      => ==7==
    // [1,2,3,4,5,6]    => ==7==
    // [1,2,3,4,5,6,7]  => ==7==

    // ==15==
    // [1,2,3,4,5,6,7,8]
    // [1,2,3,4,5,6,7,8,9,10]
    // [1,2,3,4,5,6,7,8,9,10,11]
    // [1,2,3,4,5,6,7,8,9,10,11,12]
    // [1,2,3,4,5,6,7,8,9,10,11,12,13]
    // [1,2,3,4,5,6,7,8,9,10,11,12,13,14]
    // [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    const seq = [1, 3, 7, 15, 31, 63, 127];

    // The column number "n" should always be an odd number.
    // DUMMY way
    // var n = 1;
    // if (!root) { // ARRAY !!!!
    //     return [];
    // } else if (root.length <= 3) {
    //     n = 3
    // } else if (root.length > 3 && root.length <= 7) {
    //     n = 7
    // } else if (root.length > 7 && root.length <= 15) {
    //     n = 15;
    // }

    var computeBinaryTreeWidth = function(inputData) {
        let foundN;
        for (var i = 0; i < seq.length - 1; i++) {
            if (inputData.length >= seq[i] && inputData.length <= seq[i + 1]) {
                foundN = seq[i + 1]; // because maximum (bigger)
                break
            }
        }

        return foundN;
    }
    var n = computeBinaryTreeWidth(root);

    //
    // First we need to fin WIDTH "n", because it will help to define HEIGHT "m" - number of "returns from right tree to left tree"
    // 
    var computeBinaryTreeHeight = function(nValue) {
        let foundM = seq.indexOf(nValue) + 1; // because JS indexing started from 0, and we need just natural numbers seq (1,2,3,4,5....).

        return foundM;
    }
    var m = computeBinaryTreeHeight(n);

    console.log(root, m, n);
    var print2dArray = function(m, n, inputData) {
        let mainArr = new Array(m);

        let middleOfRowIndex = Math.ceil(n / 2) - 1; // again due to JS array indexing from 0
        // console.log(middleOfRowIndex);

        for (var i = 0; i < mainArr.length; i++) {
            let rowArr = new Array(n);
            for (var j = 0; j < rowArr.length; j++) {
                rowArr[j] = "";
            }

            //
            // VERY DUMMY
            if (i == 0) {
                rowArr[middleOfRowIndex] = '' + inputData[0];
            }
            if (i == 1) {
                rowArr[0] = '' + inputData[1];
            }
            // VERY DUMMY
            // 

            mainArr[i] = rowArr;
        }

        return mainArr;
    }

    var arr = print2dArray(m, n, root);

    console.log(arr, JSON.stringify(arr));
    return arr;
};

var inputData = [1, 2];
// var inputData = [1, 2, 3];
// var inputData = [1, 2, 3, 4];
// var inputData = [1, 2, 3, 4, 5, 6, 7,8,9];
// printTree(new TreeNode(1));
printTree(inputData);


// Definition for a binary tree node.
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * !!!
 * TreeNode BASED VERSION
 * !!!
 * @param {TreeNode} root - examples => ./treeExamples.js
 * @return {string[][]}
 */
function printTree2(root) {


}


//
// =================================
//

old_tasks.js

function rotateArray() {
    var arr = [
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5],
        [1, 2, 3, 4, 5]
    ];

    /**
	 *   - output - rotated by 1
	 1 1 2 3 4 
	 1 2 2 3 5
	 1 2 3 4 5
	 1 3 4 4 5
	 2 3 4 5 5 
	 */
    var applyRotattion = function(arr) {

        return arr;
    };

    var rotatedArray = applyRotattion(arr);

    console.log(rotatedArray);
}

// rotateArray();


/**
 * 100100100111010 - input
 * 011011011000101 - output
 * 
 */
function invertBits() {
    var input = 100100100111010;

    var output;

    console.log(output);
}

// invertBits();


/**
Dynamic programming 
https://www.hackerrank.com/challenges/ctci-coin-change/problem
 */
function changeCoins() {

}

/**

Minimum Moves to Equal Array Elements II My SubmissionsBack to Contest
User Accepted: 541
User Tried: 653
Total Accepted: 561
Total Submissions: 1588
Difficulty: Medium
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, 
where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array's length is at most 10,000.

Example:

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]
 */


// https://en.wikipedia.org/wiki/Dynamic_programming
// For example, in the coin change problem of finding the minimum number of coins of given denominations 
// needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an 
// optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount. 
// In contrast, a greedy algorithm might treat the solution as a sequence of coins, starting from the given amount and at each step 
// subtracting the largest possible coin denomination that is less than the current remaining amount. If the coin denominations are 1,4,5,15,20 
// and the given amount is 23, 
// this greedy algorithm gives a non-optimal solution of 20+1+1+1, while the optimal solution is 15+4+4.

function task5() {

}



function contest() {

    }
    // contest();


// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find
function isPrime(element, index, array) {
    var start = 2;
    while (start <= Math.sqrt(element)) {
        if (element % start++ < 1) {
            return false;
        }
    }
    return element > 1;
}

// console.log([4, 6, 8, 12].find(isPrime)); // undefined, not found
// console.log([4, 5, 8, 12].find(isPrime)); // 5

treeNodeExamples.js

[1, 2] => TreeNode {
    val: 1,
    right: null,
    left: TreeNode {
        val: 2,
        right: null,
        left: null
    }
}

[1, 2, 3] => TreeNode {
    val: 1,
    right: TreeNode {
        val: 3,
        right: null,
        left: null
    },
    left: TreeNode {
        val: 2,
        right: null,
        left: null
    }
}

[
    ["","1",""],
    ["2","","3"]
]

[1, 2, 3, 4] => TreeNode {
    val: 1,
    right: TreeNode {
        val: 3,
        right: null,
        left: null
    },
    left: TreeNode {
        val: 2,
        right: null,
        left: TreeNode {
            val: 4,
            right: null,
            left: null
        }
    }
}


[
    ["","","","1","","",""],
    ["","2","","","","3",""],
    ["4","","","","","",""]
]



[1, 2, 3, "", 4, "", 5] => TreeNode {
    val: 1,
    right: TreeNode {
        val: 3,
        right: TreeNode {
            val: 5,
            right: null,
            left: null
        },
        left: TreeNode {
            val: 0,
            right: null,
            left: null
        }
    },
    left: TreeNode {
        val: 2,
        right: TreeNode {
            val: 4,
            right: null,
            left: null
        },
        left: TreeNode {
            val: 0,
            right: null,
            left: null
        }
    }
}

[
    ["","","","1","","",""],
    ["","2","","","","3",""],
    ["","","4","","","","5"]
]