class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = {};
this.keys = [];
};
get(key) {
// if value is already in the cache,
// reorder keys array and put the key on the end of queue
let val = this.cache[key];
if (val !== undefined) {
this.keys.splice(this.keys.indexOf(key), 1);
this.keys.push(key);
return val;
}
return -1;
};
put(key, value) {
let obj = this.cache[key];
// if key is already in the cache
// remove key so we can add it on the end later
if (obj !== undefined) {
this.keys.splice(this.keys.indexOf(key), 1);
}
// if adding key is already over the capacity
// we are going to remove the first item on the keys
if (obj === undefined && this.keys.length === this.capacity) {
const oldKey = this.keys.shift(); //?
delete this.cache[oldKey]; //?
}
// add key to the keys, this is either an existing key or a new key
this.keys.push(key); //?
this.cache[key] = value;
}Tag: leetcode
let reorderLogFiles = function(logs) {
let alpha = [],
numbers = [];
const isNumber = (str) => {
const [, content] = str.split(' ');
return content.match(/\d+/);
}
const getBody = (str) => {
return str.substring(str.indexOf(' ') + 1);
}
// separate alpha from numbers
logs.forEach(log => {
if (isNumber(log)) {
numbers.push(log);
}
else {
alpha.push(log);
}
});
let comparator = (x, y) => {
let compareResult = getBody(x).localeCompare(getBody(y));
if (compareResult === 0) {
return x.localeCompare(y);
}
return compareResult;
}
return [...alpha.sort(comparator), ...numbers];
};
Categories
Oranges Rotting
let orangesRotting = function(grid) {
const FRESH = 1,
ROTTEN = 2,
VISITED = -1;
let rotten = [],
totalFresh = 0,
totalEmpty = 0,
total = 0;
function getAdjacents(row, col) {
let result = [];
// check top
if (row > 0 && grid[row -1][col] === FRESH) {
grid[row -1][col] = VISITED;
result.push([row - 1, col]);
}
// check bottom
if (row < grid.length - 1 && grid[row + 1][col] === FRESH) {
grid[row +1][col] = VISITED;
result.push([row + 1, col]);
}
// check left;
if (col > 0 && grid[row][col - 1] === FRESH) {
grid[row][col - 1] = VISITED;
result.push([row, col - 1]);
}
// check right
if (col < grid[row].length - 1 && grid[row][col + 1] === FRESH) {
grid[row][col + 1] = VISITED;
result.push([row, col + 1]);
}
return result;
}
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
const data = grid[i][j];
if (data === ROTTEN) {
rotten.push(...getAdjacents(i, j));
}
else if (data === FRESH || data === VISITED) {
totalFresh++;
}
else {
totalEmpty++;
}
total++;
}
}
totalFresh -= rotten.length;
let minute = 0;
while (rotten.length) {
let len = rotten.length;
while (len --> 0) {
let point = rotten.pop();
let [row, col] = point;
grid[row][col] = ROTTEN;
rotten.unshift(...getAdjacents(row, col));
}
totalFresh -= rotten.length;
minute++;
}
if (total === totalEmpty) return 0;
let hasFreshOranges = totalFresh > 0;
if (hasFreshOranges) return -1;
return minute;
};
Categories
Decode String
let decodeString = function(str) {
if (str.indexOf("[") < 0) {
return str;
}
let openingIndex = [];
let newStr = "";
for (let i = 0; i < str.length; i++) {
if (str[i] === "[") {
openingIndex.push(i);
newStr += str[i];
}
else if (str[i] === "]") {
let opening = openingIndex.pop();
let allMultipliers = str.substring(0, opening).match(/\d+/g);
let multiplier = allMultipliers[allMultipliers.length - 1];
let data = str.substring(opening + 1, i);
if (data.indexOf("[") < 0) {
newStr = newStr.substring(0, newStr.lastIndexOf("[") - multiplier.length) + data.repeat(multiplier);
console.log({opening, multiplier, data, newStr});
}
else {
newStr += str[i];
}
}
else {
newStr += str[i];
}
}
return decodeString(newStr);
};
Categories
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
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
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;
}
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;
}
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)
}
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;
}