记录

1121 4. Evaluate Reverse Polish Notation

/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
    // check
    // keep a stack, for nums
    // for each token, if is num, push to stack, if is operator, get two from stack and calc, don't have two error, then
    // push back to stack, until end, stack should be empty
    if (tokens == null || tokens.length === 0) {
        return 0;
    }
    const stack = [];
    for (let token of tokens) {
        if (['+', '-', '*', '/'].includes(token)) {
            const second = stack.pop();
            const first = stack.pop();
            if (token === '+') {
                stack.push(first + second);
            } else if (token === '-') {
                stack.push(first - second);
            } else if (token === '*') {
                stack.push(first * second);
            } else {
                stack.push(Math.trunc(first / second)); // !!!! trunc not floor if you have negative, the second time you met this. Well, why not just use trunc instead of floor?
            }
        } else {
            stack.push(Number.parseInt(token, 10));
        }
    }
    return stack[0];
};

1121 5.  Water and Jug Problem

/**
* @param {number} x
* @param {number} y
* @param {number} z
* @return {boolean}
*/
var canMeasureWater = function(x, y, z) {
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    const aGcd = gcd(x, y);
    if (aGcd === 0) {return z === 0} // !!!!! 0, 0, 0
    return z % aGcd === 0 && x + y >= z;
   
};

两步转换，证明也不难。

1121 6. Multiply Strings

/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function(num1, num2) {
    // check
    // reverse 1 and 2
    // loop 1 and 2, i and j,
    // for each i, we create a list, and as we loop j, we calc el of the list considering carry
    // after each i, we add the list to global list
    // in the end, we reverse and concatenate global list
    if (num1 == null || num1.length === 0 || num2 == null || num2.length === 0) {throw new Error('Invalid input')}
    // !!!!! you didn't f***ing reverse them !!!! ???? sad
    num1 = num1.split('').reverse().join('');
    num2 = num2.split('').reverse().join('');
    const list = [];
    for (let i = 0; i < num1.length; i++) {
        const numi = num1[i].charCodeAt(0) - '0'.charCodeAt(0);
        let carry = 0;
        for (let j = 0; j < num2.length; j++) {
            const numj = num2[j].charCodeAt(0) - '0'.charCodeAt(0);
            const res = numi * numj + carry + (list[i + j] || 0);
            carry = Math.trunc(res / 10);
            list[i + j] = res % 10;
        }
        if (carry > 0) {list.push(carry)}
    }
    list.reverse();
    while (list.length !== 1 && list[0] === 0) {
        list.shift();
    }
    return list.join('');
};

1122 1. Count Complete Tree Nodes

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
    // check
    // go left, find left depth
    // go right, find right depth
    // if not equal, get left and right, plust one
    // if equal, is a perfect tree, just calculate
    if (root == null) {
        return 0;
    }
    let node = root;
    let leftCount = 0;
    while (node != null) {
        leftCount++;
        node = node.left;
    }
    node = root;
    let rightCount = 0;
    while (node != null) {
        rightCount++;
        node = node.right;
    }
    return leftCount === rightCount
        ? (1 << leftCount) - 1
        : countNodes(root.left) + countNodes(root.right) + 1;
};

1122 2. Accounts Merge

/**
* @param {string[][]} accounts
* @return {string[][]}
*/
var accountsMerge = function(accounts) {
    // check
    // keep emailToId, idToEmail, emailToName
    // loop accounts, put all emails into a set, create emailToName map
    // from that set, create emailToId map, and idToEmail map
    // now for each account, merge them using DSU
    // loop all ids, for each, find the root, create a map rootToArray and get the array, put email into the array
    // after that, loop the array, get name by email and unshift into array
    // return arrays
    if (accounts == null || accounts.length === 0) {
        return [];
    }
    const emailToId = new Map();
    const idToEmail = new Map();
    const emailToName = new Map();
    const set = new Set();
    for (let account of accounts) {
        const name = account[0];
        for (let i = 1; i < account.length; i++) {
            const email = account[i];
            emailToName.set(email, name);
            set.add(email);
        }
    }
    [...set].forEach((email, id) => {
        emailToId.set(email, id);
        idToEmail.set(id, email);
    });
    const len = set.size;
    const dsu = new DSU(len);
    for (let account of accounts) {
        for (let i = 2; i < account.length; i++) {
            const curr = account[i];
            const prev = account[i - 1];
            dsu.union(emailToId.get(curr), emailToId.get(prev));
        }
    }
    const rootToArray = new Map();
    const putAndGet = (map, key, defaultVal) => {
        const val = map.get(key) || defaultVal;
        map.set(key, val);
        return val;
    }
    for (let id of idToEmail.keys()) {
        const root = dsu.findRoot(id);
        const array = putAndGet(rootToArray, root, [emailToName.get(idToEmail.get(root))]);
        array.push(idToEmail.get(id));
    }
    const values = [...rootToArray.values()];
    values.forEach(arr => arr.sort());
    return values;
};

class DSU {
    constructor (len) {
        this.parent = Array(len).fill().map((v, i) => i);
    }
    findRoot (i) {
        if (this.parent[i] !== i) {
            this.parent[i] = this.findRoot(this.parent[i]);
        }
        return this.parent[i];
    }
    union (x, y) {
        this.parent[this.findRoot(x)] = this.findRoot(y);
    }
}

1123 1. Word Search

/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
    // check
    // keep a visited matrix as board
    // loop the board find starting point, if found, check dfs, true just return
    // dfs: four moves, check visited. if reached the last char and the same, return true
    // else return further dfs
    if (word == null || word.length === 0) {
        return true;
    }
    if (board == null || board.length === 0) {
        return false;
    }
    const rowLen = board.length;
    const colLen = board[0].length;
    const wordLen = word.length;
    const visited = Array(rowLen).fill().map(() => Array(colLen).fill(false));
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (dfs(i, j, 0)) {return true;}
        }
    }
    return false;
   
    function dfs (i, j, k) {
        if (i < 0 || i >= rowLen || j < 0 || j >= colLen) {
            return false;
        }
        if (visited[i][j] || board[i][j] !== word[k]) {
            return false;
        }
        if (k === wordLen - 1) { // 1. why we stop at the last element? if we continue, for this specific one we don't have issues, but for some problems where you need to return all cases not just count or booelan, you will have duplicate in that case
            return true;
        }
        visited[i][j] = true;
        const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        for (let move of moves) {
            const x = move[0] + i;
            const y = move[1] + j;
            if (dfs(x, y, k + 1)) {
                return true;
            }
        }
        visited[i][j] = false; // 2. need to backtrack
        return false;
    }
};

1123 2. 4Sum

/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
    // check
    // double loop, put sum, index pair into hashmap
    // loop the sum of the map, get the other value, if exist
    // we have to lists, loop and check each pair of pair, put into set
    // return the set
    if (nums == null || nums.length < 4) {
        return [];
    }
   
    const map = new Map();
    const addItem = (map, key, val) => {
        const list = map.get(key) || [];
        map.set(key, list);
        list.push(val);
    }
   
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            addItem(map, nums[i] + nums[j], [i, j]); // 1. have to use indices here because you cannot use one el twice
        }
    }
   
    const mapSet = new Map();
    const addToSet = (quad) => {
        quad.sort((a, b) => a - b);
        const key = quad.join(':');
        mapSet.set(key, quad);
    }
   
    map.forEach((pairs, sum) => {
        const aTarget = target - sum;
        if (map.has(aTarget)) {
            const aPairs = map.get(aTarget);
            for (let i = 0; i < pairs.length; i++) {
                for (let j = 0; j < aPairs.length; j++) {
                    const merge = [...pairs[i], ...aPairs[j]]; // 2. till here still use index
                    const set = new Set(merge);
                    if (set.size === 4) {
                        addToSet(merge.map(index => nums[index])); // 3. but here has to be value because in the end the duplicate is determined by
                        // values
                    }
                }
            }
        }
    });
    // !!!! what you store is the index, what they want is the actual number
    return [...mapSet.values()];
   
};

1123 3. ZigZag Conversion

/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
    // check
    // row, T = row + row - 2
    // count = ceil(len / T)
    // loop count times, i
    // each time, loop row times, j
    // each row, indexed 0,
    // for j is 0 || row - 1, index, index + 6
    // for j is within, index, index and index + T - j
    if (s == null || s.length === 0) {
        return s;
    }
    if (numRows === 1) {return s} // !!!! The special case !!!
    const T = numRows + numRows - 2;
    const count = Math.ceil(s.length / T);
    let res = '';
    // !!!! which one is the outer loop, and which one is the inner loop !!!!!
    for (let j = 0; j < numRows; j++) {
        for (let i = 0; i < count; i++) {
            const index = j + T * i;
            if (index < s.length) {
                res += s[index];
            }
            if (j !== 0 && j !== numRows - 1) {
                if (index + T - 2 * j < s.length) { // !!! 这个第二个元素的index的计算是难点
                    res += s[index + T - 2 * j];
                }
            }
        }
    }
    return res;
};

1123 4. Coin Change

/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
    // check
    // keep dp, from 0 to amount, build on prev ones
    // return dp amount
    if (amount === 0) {return 0;}
    if (coins == null || coins.length === 0) {
        return -1;
    }
    const dp = Array(amount + 1).fill(Infinity); // !!!!! 1. amount + 1, not coins.length + 1, 2. need to + 1 !!! Need to really think
    dp[0] = 0;
    console.log(dp)
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    console.log(dp);
    return dp[amount] === Infinity ? -1 : dp[amount];
};

1123 5. Spiral Matrix

/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
    // check
    // start loop, each level
    // 4 directions, last 2 needs to check
    if (matrix == null || matrix.length === 0) {
        return [];
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const min = Math.min(rowLen, colLen);
    const count = Math.ceil(min / 2);
    const res = [];
    for (let i = 0; i < count; i++) {
        for (let col = i; col <= colLen - 1 - i; col++) {
            res.push(matrix[i][col]);
        }
        for (let row = i + 1; row <= rowLen - 1 - i; row++) {
            res.push(matrix[row][colLen - 1 - i]);
        }
        if (i !== colLen - 1 - i && i !== rowLen - 1 - i) {
            for (let col = colLen - 1 - i - 1; col >= i; col--) {
                res.push(matrix[rowLen - 1 - i][col]);
            }
            for (let row = rowLen - 1 - i - 1; row > i; row--) {
                res.push(matrix[row][i]);
            }
        }
    }
    return res;
};