let twoSumLessThanK = function(A, K) {
let max = -1, start = 0, end = A.length - 1;
A.sort((a, b) => b - a); //?
while (start < end) {
let sum = A[start] + A[end];
if (sum < K) {
max = Math.max(sum, max);
end--;
}
else {
start++;
}
}
return max;
};
Author: Ron
if (!grid || !grid.length) return 0;
let numRows = grid.length,
numCols = grid[0].length,
LAND = 1, VISITED = 2;
function markAndVisit(row, col, island = [], level = 0) {
if (grid[row][col] === LAND) {
grid[row][col] = VISITED;
island.push('X' + level);
// up
if (row > 0 && grid[row - 1][col] === LAND) {
island.push('U' + level);
markAndVisit(row - 1, col, island, level + 1);
}
// down
if (row < numRows - 1 && grid[row + 1][col] === LAND) {
island.push('D' + level);
markAndVisit(row + 1, col, island, level + 1);
}
// left
if (col > 0 && grid[row][col - 1] === LAND) {
island.push('L' + level);
markAndVisit(row, col - 1, island, level + 1);
}
// right
if (col < numCols - 1 && grid && grid[row][col + 1] === LAND) {
island.push('R' + level);
markAndVisit(row, col + 1, island, level + 1);
}
}
return island;
}
let islands = new Set();
for (let row = 0; row < numRows;row++) {
for (let col = 0; col < numCols;col++) {
if (grid[row][col] === LAND) {
let island = markAndVisit(row, col);
// console.log(island);
if (island.length) islands.add(island.join(''));
}
}
}
// console.table(grid);
return islands.size;
let reorganizeString = function(S) {
let chars = {}, max = 0;
for(let i = 0; i < S.length;i++) {
if (chars[S[i]]) {
chars[S[i]] = chars[S[i]] + 1;
max = Math.max(chars[S[i]], max);
}
else {
chars[S[i]] = 1;
}
}
console.log(max, Math.floor((S.length + 1) / 2));
if (max > (S.length + 1) / 2) {
return "";
}
let result = [], index = 0;
const keys = Object.keys(chars).sort((a, b) => chars[b] - chars[a]); //?
while (keys.length) { //?
const key = keys.shift(); //?
result[index] = key;
if (chars[key] - 1 > 0) {
chars[key] = chars[key] - 1;
keys.unshift(key); //?
}
index += 2; //?
if (index >= S.length) {
index = 1;
}
}
return result.join('');
};
let prisonAfterNDays = function(cells, N) {
let cache = {},
counter = 1,
cycle = false,
len = 8;
let dup = [...cells];
function getNextCycle(data) {
let lastCycle = data[1];
let cycleDays = counter - lastCycle;
console.log(lastCycle, cycleDays);
let nextCycle = N - ((N - lastCycle) % cycleDays); //?.
// let nextCycle = counter; //?
// while (nextCycle + counter < N) {
// nextCycle = nextCycle += cycleDays;
// }
return nextCycle; //?
}
while(counter <= N) {
let key = dup.join(''),
data = cache[key],
row = [];
if (data && !cycle) {
cycle = true;
counter = getNextCycle(data);
}
if (data) {
dup = data[0];
counter++; //?
}
else {
for (let i = 0; i < len; i++) {
row[i] = dup[i - 1] === dup[i + 1] ? 1 : 0;
}
cache[key] = [[...row], counter];
dup = cache[key][0];
counter++; //?
}
}
return dup;
};
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;
}
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);
}
let mergeSort = function(numbers) {
function mergeSort(arr) {
if (arr.length === 1) return arr;
let center = Math.floor(arr.length / 2);
let left = arr.slice(0, center);
let right = arr.slice(center);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let results = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
results.push(left.shift());
}
else {
results.push(right.shift());
}
}
return [...results, ...left, ...right];
}
return mergeSort(numbers);
}
Categories
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
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;
};