let fizzBuzz = function(n) {
let result = [];
for (let i = 1; i <= n; i++) {
if (i % 3 === 0 && i % 5 === 0) {
result.push("FizzBuzz");
}
else if (i % 3 === 0) {
result.push("Fizz");
}
else if (i % 5 === 0) {
result.push("Buzz");
}
else {
result.push('' + i);
}
}
return result;
};
Author: Ronald
let longestCommonPrefix = function(strs) {
if (!strs.length) return '';
let index = 0, curr = '';
for (;;)
{
for (let i = 0; i < strs.length; i++) {
if (strs[i].length <= index) {
return strs[0].substring(0, index); //?
}
if (curr === '') curr = strs[i][index];
if (curr !== strs[i][index]) {
return strs[0].substring(0, index);
}
if (i === strs.length - 1) {
curr = '';
index++
}
}
}
return '';
};
let generate = function(numRows) {
if (numRows === 0) return [];
let result = [];
for (let i = 1; i <= numRows;i++) {
let row = [];
for (let j = 0; j < i; j++) {
if (j === 0 || j === i - 1) {
row[j] = 1;
}
else {
row[j] = result[i - 2][j - 1] + result[i - 2][j];
}
}
result.push(row);
}
return result;
};
let isPalindrome = function(s) {
let start = 0, end = s.length - 1, regex = /\w/i;
while (start < end) {
if (!s[start].match(regex)) {
start++;
}
else if (!s[end].match(regex)) {
end--;
}
else {
if (s[start].toLowerCase() !== s[end].toLowerCase()) return false;
start++;
end--;
}
}
return true;
}
let romanToInt = function(s) {
if (!s) return 0;
let mapping = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
let result = 0;
for (let i = s.length - 1; i >= 0;) {
if (mapping[s[i]] > mapping[s[i - 1]]) {
result += mapping[s[i]] - mapping[s[i - 1]];
i -= 2;
}
else {
result += mapping[s[i]];
i -= 1;
}
}
return result;
}
let mostVisitedPattern = function(username, timestamp, website) {
let map = new Map();
for (let i = 0; i < username.length; i++) {
if (map.has(username[i])) {
map.get(username[i]).push([website[i], timestamp[i]]);
}
else {
map.set(username[i], [[website[i], timestamp[i]]]);
}
}
// get all possibilites
let visitedPattern = {};
let possibilityMap = new Map();
for(let [user, visits] of map.entries()) {
visitedPattern[user] = {};
const value = visits.sort((a, b) => a[1] - b[1]).map(([a]) => a);
if ( value.length < 3) continue;
for (let i = 0; i < value.length - 2; i++) {
for (let j = i + 1; j < value.length - 1; j++) {
for (let k = j + 1; k < value.length; k++) {
let key = `${value[i]},${value[j]},${value[k]}`;
if(possibilityMap.has(key)) {
if(!visitedPattern[user][key]) {
possibilityMap.set(key, possibilityMap.get(key) + 1);
visitedPattern[user][key] = 1;
}
}
else {
possibilityMap.set(key, 1);
visitedPattern[user][key] = 1;
}
}
}
}
}
const result = [...possibilityMap];
return result.sort((a, b) => {
if(a[1] < b[1]) {
return 1;
}
else if (a[1] > b[1]) {
return -1;
}
return a[0].localeCompare(b[0]);
}).map(arr => arr[0]).shift().split(','); //?
// result.pop(); //?
// .map(arr => arr[0]).pop().split('|'); //?
};
Categories
Is Subtree
let isSubtree = function(mainTree, subTree) {
function isSame(left, right) {
if (left === right) return true;
if (left === null && right !== null) return false;
if (left !== null && right === null) return false;
if (left.val !== right.val) return false;
return isSame(left.left, right.left)
&& isSame(left.right, right.right);
}
if (mainTree === subTree) return true;
if (!mainTree) return false;
if (isSame(mainTree, subTree)) return true;
return isSubtree(mainTree.left, subTree) || isSubtree(mainTree.right, subTree);
};
let suggestedProducts = function(products, searchWord) {
products.sort();
let result = [];
for(let i = 0; i < searchWord.length; i++) {
products = products.filter(p => p[i] === searchWord[i]);
result.push(products.slice(0, Math.min(3, products.length)));
}
return result; //?
};
let suggestedProducts = function(products, searchWord) {
const MAX_RESULT_COUNT = 3;
let root = {
children: {}
};
function addToNode(word, index, node) {
if (index >= word.length) {
node.end = true;
return;
}
//
const child = node.children[word[index]];
if (child) {
addToNode(word, index + 1, child);
}
else {
let child = {val: word[index], parent: node, children: {}};
node.children[word[index]] = child;
addToNode(word, index + 1, child);
}
}
function getWord(leaf) {
let node = leaf;
let str = '';
while (node) {
if (node.val) str = node.val + str; //?
node = node.parent; //?
}
return str; //?
}
function searchProducts(searchString) {
let words = [];
let nodes = [...Object.entries(root.children)], len = searchString.length;
while (nodes.length) {
let currentNodeLength = nodes.length;
while (currentNodeLength > 0) {
currentNodeLength--;
const node = nodes.pop();
const [key, val] = node;
if (len > 0 && key === searchString[searchString.length - len]) {
nodes.unshift(...Object.entries(val.children));
if (len === 1 && val.end) {
words.push(getWord(val));
}
} else if (len <= 0) {
if (val.end) words.push(getWord(val));
nodes.unshift(...Object.entries(val.children));
}
}
len--;
}
return words.sort().slice(0, Math.min(MAX_RESULT_COUNT, words.length));
}
for(let product of products) {
addToNode(product, 0, root);
}
let result = [];
for (let i = 0; i < searchWord.length; i++) {
result.push(searchProducts(searchWord.substring(0, i + 1))); //?
}
return result; //?
};
Categories
Search Matrix
let searchMatrix = function(matrix, target) {
if(!matrix.length) return false;
function search(startRow, endRow, startCol, endCol) {
console.log(startRow, endRow, startCol, endCol);
let midRow = Math.floor((startRow + endRow) / 2); //?
let midCol = Math.floor((startCol + endCol) / 2); //?
if (startRow < endRow && startCol < endCol) {
const midValue = matrix[midRow][midCol]; //?
if(midValue === target) {
return true;
}
if (midValue < target) {
return search(midRow + 1, endRow, startCol, endCol)
|| search(startRow, endRow, midCol + 1, endCol);
}
else {
return search(startRow, midRow, startCol, endCol)
|| search(startRow, endRow, startCol, midCol);
}
}
return false;
}
return search(0, matrix.length, 0, matrix[0].length);
};