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)
}
function fib(n) {
if(n === 0) return 0;
if(n <= 2) return 1;
let x = 1, y = 2;
for(let i = 3; i < n; i++) {
let oldX = x;
x = y;
y = y + oldX; /*?.*/
}
return y;
}
let numIslands = function(matrix) {
if (!matrix.length) return 0;
let land = 1, visited = 'X',
counter = 0,
maxRow = matrix.length - 1,
maxCol = matrix[0].length - 1;
function exploreAndMark(row, col) {
if (row < 0 || col < 0 || row > maxRow || col > maxCol) {
return;
}
if (matrix[row][col] === land) {
matrix[row][col] = visited;
// explore up
exploreAndMark(row - 1, col);
// explore down
exploreAndMark(row + 1, col);
// explore left
exploreAndMark(row, col - 1);
// explore right
exploreAndMark(row, col + 1);
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol; col++) {
if (matrix[row][col] === land) {
counter++;
exploreAndMark(row, col);
}
}
}
return counter;
}
let secondHighest = function(arr1, arr2) {
if (arr1.length === 1 && arr2.length === 1) {
return Math.min(arr1[0], arr2[0]);
}
else if (arr1.length === 0 && arr2.length === 2) {
return Math.min(arr2[0], arr2[1]);
}
else if (arr2.length === 0 && arr1.length === 2) {
return Math.min(arr1[0], arr1[1]);
}
let mid1 = Math.ceil((arr1.length / 2) - 1)
let mid2 = Math.ceil((arr2.length / 2) - 1);
if (arr1[mid1] <= arr2[mid2]) {
arr1 = arr1.slice(mid1 + 1);
arr2 = arr2.slice(mid2);
}
else {
arr1 = arr1.slice(mid1);
arr2 = arr2.slice(mid2 + 1);
}
return secondHighest(arr1, arr2);
}
function twoSum(nums, target) {
let result = [],
cache = {};
for (let i = 0; i < nums.length; i++) {
let x = target - nums[i];
if (cache[x] !== undefined) {
result.push([cache[x], i]);
}
cache[nums[i]] = i;
}
return result;
};
function validParenthesis(str) {
let closingMap = {
')' : '(',
']' : '[',
'}' : '{'
}
let chars = [];
for(let i = 0; i < str.length; i++) {
if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
chars.push(str[i]);
}
else {
let compare = chars.pop();
if (closingMap[str[i]] !== compare) return false;
}
}
return chars.length === 0;
}
function binarySearch(arr, n, start = 0, end = arr.length) {
let mid = Math.floor((end + start) / 2);
if (arr[mid] === n) return mid;
if (start < end - 1) {
if (n > arr[mid]) {
return binarySearch(arr, n, mid, end);
} else {
return binarySearch(arr, n, start, mid);
}
}
return -1;
}