记录

1017 3. Knight Probability in Chessboard

/**
* @param {number} N
* @param {number} K
* @param {number} r
* @param {number} c
* @return {number}
*/
var knightProbability = function(N, K, r, c) {
    const moves = [[1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2]];
    let dp = Array(N).fill().map(() => Array(N).fill(0));
    dp[r][c] = 1;
    for (let k = 0; k < K; k++) {
        const newDp = Array(N).fill().map(() => Array(N).fill(0));
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                for (let l = 0; l < 8; l++) {
                    const move = moves[l];
                    const moveR = move[0];
                    const moveC = move[1];
                    const ii = i + moveR;
                    const jj = j + moveC;
                    if (ii >= 0 && ii < N && jj >= 0 && jj < N) {
                        newDp[ii][jj] += dp[i][j] / 8;
                    }
                }
            }
        }
        dp = newDp;
    }
    return dp.reduce((sum, row) => sum + row.reduce((i, j) => i + j), 0);
};

Split Array Largest Sum    remains

1017 4. Split Array Largest Sum

/**
* @param {number[]} nums
* @param {number} m
* @return {number}
*/
var splitArray = function(nums, m) {
    // we want to split nums into m groups and minimize the max sum of all groups
    // there exists such a sum*
    // if our sum is still bigger than sum*, we decrease it and it can still split
    // until we reached sum*, we decrease, it cannot split anymore, we increase
    // for each sum, we either can split or not
    // if we can split into m, we decrease sum since sum is the smallest of all pissible ones
    // if we cannot split, we increase sum that's obvious
    // if left is right, we would go smaller, right would change, left is right
    // we must test each and everyone, cause the correct one we might miss, on a bigger one
    // if we test everyone, we must go to a smaller one
    if (nums == null || nums.length === 0) {return 0;}
    const allSum = nums.reduce((a, b) => a + b);
    const oneSum = Math.max(...nums);
    let left = oneSum;
    let right = allSum;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
   
    function canSplit (sum) {
        let count = 0;
        let localSum = 0;
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i];
            if (num > sum) {
                return false;
            }
            if (localSum + num > sum) {
                count++;
                localSum = num;  // !!!! num, and sum!!!!! you got confused, bad variable name!!!
            } else {
                localSum = localSum + num;
            }
        }
        count++;
        // !!!!there is a last one !!!!
        // this occurs when: you do a count and restart inside another loop, when the other loop ends,
        // the last set might not go through the inner count process
        const result =  count <= m;
        return result;
    }
};

1018 1. Super Ugly Number

/**
* @param {number} n
* @param {number[]} primes
* @return {number}
*/
var nthSuperUglyNumber = function(n, primes) {
    if (primes == null || primes.length === 0) {throw new Error('Invalid input')}
    const primeIndices = Array(primes.length).fill(0);
    const nums = [1];
    for (let i = 1; i < n; i++) {
        let min = Number.MAX_VALUE;
        for (let j = 0; j < primes.length; j++) {
            const val = primes[j] * nums[primeIndices[j]];
            min = Math.min(min, val);
        }
        nums[i] = min;
        for (let j = 0; j < primes.length; j++) {
            if (min === primes[j] * nums[primeIndices[j]]) {
                primeIndices[j]++; // !!!! ++???  !!! each one could do, not only ones produced by this one, so it is ++, not assign i to it
            }
        }
    }
    return nums[n - 1];
};

1018 2. Find Peak Element

/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
    if (nums == null || nums.length === 0) {
        throw new Error('Invalid input');
    }
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const prev = mid === 0 ? -Infinity : nums[mid - 1];  // !!!! cannot use Number.MIN_VALUE since Number.MIN_VALUE is the smallest __positive__ value !!!!
        const next = mid === nums.length - 1 ? -Infinity : nums[mid + 1];
        const self = nums[mid];
        if (self > prev && self > next) { // !!!!! it is prev, next, not left, right !!!!! This happend again, similar variable names !!!!
            return mid;
        } else if (self > prev && self < next) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
};

1018 3. Balanced Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
    return recurse(root) >= 0;
    // return depth of the tree if it is balanced, -1 if it is not
    function recurse (node) {
        if (node == null) {return 0;}
        if (node.left == null && node.right == null) {return 1;}
        const left = recurse(node.left);
        const right = recurse(node.right);
        if (left < 0 || right < 0) {return -1;}
        if (Math.abs(left - right) > 1) {return -1;}
        return Math.max(left, right) + 1;
    }
};

1018 4. Max Area of Island

/**
* @param {number[][]} grid
* @return {number}
*/
var maxAreaOfIsland = function(grid) {
    if (grid == null || grid.length === 0) {
        return 0;
    }
    const rowLen = grid.length;
    const colLen = grid[0].length;  // !!!!! rowLen and colLen, not a square !!!
   
    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            count = Math.max(count, dfs(i, j)); // !!!! find max, not sum !!!
        }
    }
    return count;
   
    // return num of connected islands start from this point with current count
    function dfs (i, j) {
        if (i < 0 || i >= rowLen || j < 0 || j >= colLen) {
            return 0;
        }
        if (grid[i][j] !== 1) {
            return 0;
        } else {
            grid[i][j] = -1;
            const left = dfs(i, j - 1);
            const right = dfs(i, j + 1);
            const up = dfs(i - 1, j);
            const down = dfs(i + 1, j);
            return left + right + up + down + 1;
        }
    }
};

Find Mode in Binary Search Tree   
Maximum Average Subarray I   
Maximum Width of Binary Tree   
Zuma Game   

1019 1. Find Mode in Binary Search Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var findMode = function(root) {
    let res = [];
    let max = 0;
    let prevVal = null;
    let count = 0;
    recurse(root);
    return res;
    // !!! how to solve the problem of last round in an iteration? -- we do the operation
    // in every iteration, not just when certain creteria meets
    function recurse (node) {
        // left, mid, right
        if (node == null) {return;}
        recurse(node.left);
        if (node.val === prevVal) {
            count++;
        } else {
            prevVal = node.val;
            count = 1;
        }
        if (count > max) {
            // !!!! need to update max
            max = count;
            res = [node.val];
        } else if (count === max) {
            res.push(node.val);
        }
        recurse(node.right);
    }
};

1019 2.  Find Mode in Binary Search Tree

网上的解法都是给每个node编号，但是这样的解法会overflow：一旦超过32层深，int就overflow了。
if the tree is a right-tilted list, it could easily get to 32 level deep and thus overflow.
不知道有什么好的解决办法
即使用浮点数也很容易越界，因为是指数增长。