Skip to content

Instantly share code, notes, and snippets.

@alundiak

alundiak/leetcode.js

Last active Oct 18, 2017
Embed
What would you like to do?
/**
* 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) {
}
//
// =================================
//
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
[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"]
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment