Month: May 2020
let gameOfLife = function(board) {
if (!board) return [];
let LIVE = 1,
DEAD = 0,
ALIVE_TO_DEAD = 0b01, // [next state, current state]
ALIVE_TO_ALIVE = 0b11,
DEAD_TO_ALIVE = 0b10,
DEAD_TO_DEAD = 0b00,
maxRow = board.length - 1,
maxCol = board[0].length - 1;
function getAdjacentCount(row, col, valueToCompare) {
let sum = 0;
for (let i = Math.max(row - 1, 0); i <= Math.min(row + 1, maxRow); i++) {
for (let j = Math.max(col - 1, 0); j <= Math.min(col + 1, maxCol); j++) {
if (i === row && j === col) continue;
if (board[i][j] & 1 === valueToCompare) sum = sum + 1;
}
}
return sum;
}
function getNextValue(row, col) {
const val = board[row][col];
let liveNeighbors = getAdjacentCount(row, col, LIVE);
if (val === LIVE) {
// Any live cell with fewer than two live neighbors dies, as if caused by under-population.
// Any live cell with more than three live neighbors dies, as if by over-population..
if (liveNeighbors < 2 || liveNeighbors > 3) {
return ALIVE_TO_DEAD;
}
// Any live cell with two or three live neighbors lives on to the next generation.
return ALIVE_TO_ALIVE;
}
// cell is DEAD
else {
// Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
if (liveNeighbors === 3) {
return DEAD_TO_ALIVE;
}
// no condition
return DEAD_TO_DEAD;
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol;col++) {
board[row][col] = getNextValue(row, col);
}
}
for (let row = 0; row <= maxRow; row++) {
for (let col = 0; col <= maxCol;col++) {
board[row][col] = board[row][col] >> 1;
}
}
};
let gameOfLife = function(board) {
if (!board) return [];
let copy = [],
LIVE = 1,
DEAD = 0,
maxRow = board.length - 1,
maxCol = board[0].length - 1;
function getAdjacentCount(row, col, valueToCompare) {
let sum = 0;
for (let i = Math.max(row - 1, 0); i <= Math.min(row + 1, maxRow); i++) {
for (let j = Math.max(col - 1, 0); j <= Math.min(col + 1, maxCol); j++) {
if (i === row && j === col) continue;
if (copy[i] && copy[i][j] !== undefined) {
if (copy[i][j] === valueToCompare) sum = sum + 1; //?
}
else {
if (board[i][j] === valueToCompare) sum = sum + 1; //?
}
}
}
return sum;
}
function getNextValue(row, col) {
const val = board[row][col];
let liveNeighbors = getAdjacentCount(row, col, LIVE);
if (val === LIVE) {
// Any live cell with fewer than two live neighbors dies, as if caused by under-population.
if (liveNeighbors < 2) {
return DEAD;
}
// Any live cell with more than three live neighbors dies, as if by over-population..
else if (liveNeighbors > 3) {
return DEAD;
}
// Any live cell with two or three live neighbors lives on to the next generation.
return LIVE;
}
// cell is DEAD
else {
// Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
if (liveNeighbors === 3) {
return LIVE;
}
// no condition
return DEAD;
}
}
for (let row = 0; row <= maxRow; row++) {
copy[row] = [];
for (let col = 0; col <= maxCol;col++) {
copy[row][col] = board[row][col];
board[row][col] = getNextValue(row, col);
}
}
};
let plusOne = function(digits) {
let carry = 1;
for (let i = digits.length - 1; i >= 0; i--) {
let sum = digits[i] + carry;
if (sum >= 10) {
digits[i] = 0;
carry = 1;
}
else {
digits[i] = sum;
carry = 0;
}
}
if (carry === 1) digits.unshift(carry);
return digits;
};
let isPalindrome = function(head) {
let slow = head, fast = head, val = [slow.val];
while (fast.next) {
if (fast.next.next) {
fast = fast.next.next;
slow = slow.next;
val.push(slow.val);
}
else {
fast = fast.next;
slow = slow.next;
}
}
while (slow) {
if (slow.val !== val.pop()) {
return false;
}
slow = slow.next;
}
return val.length === 0;
};
Categories
JS Algorithm Course
let isHappy = function(n) {
let visited = {};
function sumOfSquare(num) {
if (visited[num]) return false;
visited[num] = true;
let sum = 0;
while (num > 0) {
let d = num % 10; //?
num = Math.floor(num / 10); //?
sum += d * d;
}
if (sum === 1) {
return true;
}
else {
return sumOfSquare(sum);
}
}
return sumOfSquare(n);
};
class MaxStack {
constructor() {
this.results = [];
this.sorted = [];
}
pop() {
const val = this.results.pop();
this.sorted.splice(this.sorted.lastIndexOf(val), 1);
return val;
}
push(x) {
this.results.push(x);
this.sorted = [...this.results].sort((x, y) => x - y);
}
top() {
return this.results[this.results.length - 1];
}
popMax() {
const val = this.sorted.pop();
this.results.splice(this.results.lastIndexOf(val), 1);
return val;
}
peekMax() {
return this.sorted[this.sorted.length - 1];
}
}
class MinStack {
constructor() {
this.result = [];
this.min = Number.MAX_SAFE_INTEGER;
}
push(x) {
this.result.push(x)
this.min = Math.min(x, this.min);
};
pop() {
let val = this.result.pop()
if (val === this.min) {
this.min = Math.min(...this.result);
}
};
top() {
return this.result[this.result.length - 1];
};
getMin() {
return this.min;
};
}
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;
};