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;
};
Tag: leetcode
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;
};
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 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 uniquePathsWithObstacles = function(obstacleGrid) {
if (!obstacleGrid || !obstacleGrid.length) return 0;
function markNextRowsAsZero(col) {
for (let i = col; i < maxCol; i++) {
obstacleGrid[0][i] = 0;
}
}
function markNextColumnsAsZero(row) {
for (let i = row; i < maxRow; i++) {
obstacleGrid[i][0] = 0;
}
}
let maxRow = obstacleGrid.length,
maxCol = obstacleGrid[0].length,
OBSTACLE = 1, VISITED = -1;
// first block is obstacle return 0;
if (obstacleGrid[0][0] === OBSTACLE) {
return 0;
}
// mark all first rows as either 1 or zero
for (let col = 0; col < maxCol;col++) {
if (obstacleGrid[0][col] === OBSTACLE) {
markNextRowsAsZero(col);
break;
}
else {
obstacleGrid[0][col] = 1;
}
}
// mark all first columns as either 1 or zero
for (let row = 1; row < maxRow;row++) {
if (obstacleGrid[row][0] === OBSTACLE) {
markNextColumnsAsZero(row);
break;
}
else {
obstacleGrid[row][0] = 1;
}
}
for (let row = 1; row < maxRow;row++) {
for (let col = 1; col < maxCol;col++) {
if (obstacleGrid[row][col] === OBSTACLE) {
obstacleGrid[row][col] = 0;
}
else {
obstacleGrid[row][col] =
obstacleGrid[row - 1][col] +
obstacleGrid[row][col - 1];
}
}
}
return obstacleGrid[maxRow - 1][maxCol - 1];
};