记录

next:
Longest Consecutive Sequence   
Kth Smallest Number in Multiplication Table  
Delete Node in a BST   
Game of Life   

1023 1. Game of Life

class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                evolve(board, i, j);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) { // !!! i and j, typo !!!
                board[i][j] = board[i][j] % 2;
            }
        }
    }
   
    private void evolve (int[][] board, int i, int j) {
        int [][] moves = new int[][]{{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
        int count = 0;
        for (int k = 0; k < moves.length; k++) {
            int ii = i + moves[k][0];
            int jj = j + moves[k][1];
            if (ii >= 0 && ii < board.length && jj >= 0 && jj < board[0].length && (board[ii][jj] == 1 || board[ii][jj] == 2)) {
                count++;
            }
        }
        boolean live = board[i][j] == 1;
        if (live && (count < 2 || count > 3)) {
            board[i][j] = 2;
        }
        if (!live && (count == 3)) {
            board[i][j] = 3;
        }
    }
}

1023 2. Delete Node in a BST

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
var deleteNode = function(root, key) {
    // !!! first of all, it's a bst, not just a binary tree
    if (root == null) {
        return null;
    }
    if (root.val < key) {
        root.right = deleteNode(root.right, key);
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else {
        if (root.left == null || root.right == null) {
            root = root.left == null ? root.right : root.left;
        } else {
            let curr = root.right;
            while (curr.left != null) {curr = curr.left}
            root.val = curr.val;
            root.right = deleteNode(root.right, root.val);
        }
    }
    return root;
};

经典题

sicilianee 发表于 2017-10-24 13:06
1023 2. Delete Node in a BST

/**

checkout a general solution for deleting a node in a binary tree:
http://www.cnblogs.com/grandyang/p/6228252.html

1023 3. Kth Smallest Number in Multiplication Table

/**
* @param {number} m
* @param {number} n
* @param {number} k
* @return {number}
*/
var findKthNumber = function(m, n, k) {
    if (m <= 0 || n <= 0) {
        return null;
    }
    let high = m * n;
    let low = 1;
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (enough(mid)) {
            high = mid - 1;   // !!!!! since we do compare only one element, we need to update each aggressively !!! Need to think this through: when there is only one, high == mid == low, and you're not moving. So: if you do compare ===, you never directly assign mid to sth.
        } else {
            low = mid + 1;
        }
    }
    return low;
   
   
    function enough (x) {
        let count = 0;
        for (let i = 1; i <= m; i++) {
            count += Math.min(Math.floor(x / i), n);
        }
        return count >= k;
    }
};

1023 4. Longest Consecutive Sequence

/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
    const set = new Set(nums);
    let max = 0;
    for (let num of nums) {
        let count = 0;
        if (set.has(num)) {
            count++;
            let prev = num - 1;
            while (set.has(prev)) {
                set.delete(prev);
                count++;
                prev--;
            }
            let next = num + 1;
            while (set.has(next)) {
                set.delete(next);
                count++;
                next++;
            }
            max = Math.max(count, max);
        }
    }
    return max;
};

next:
Sum Root to Leaf Numbers   
Trapping Rain Water   
Subsets II   
Populating Next Right Pointers in Each Node   

1024 1. Sum Root to Leaf Numbers

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
    if (root == null) {
        return 0;
    }
    const res = []; // they don't care about duplicates, even simpler
    const list = [];
    dfs(root);
    return res.reduce((prev, next) => prev + next);
   
    function dfs (node) {
        list.push(node.val);
        if (!node.left && !node.right) {
            const sum = list.reduce((memo, val) => memo * 10 + parseInt(val, 10), 0);
            res.push(sum);
            // also here !!!!! before you return, you need to backtrack !!! so better use else instead of return exit
        } else {
            if (node.left) {
                dfs(node.left);
            }
            if (node.right) {
                dfs(node.right);
            }  
        }
        list.pop();
    }
};

1025 1. Trapping Rain Water

/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
    if (height == null || height.length === 0) {
        return 0;
    }
    const left = [];
    const right = [];
    let leftMax = 0;
    for (let i = 0; i < height.length; i++) {
        leftMax = Math.max(leftMax, height[i]);
        left[i] = leftMax;
    }
    let rightMax = 0;
    for (let i = height.length - 1; i >= 0; i--) {
        rightMax = Math.max(rightMax, height[i]);
        right[i] = rightMax;
    }
    let sum = 0;
    for (let i = 0; i < height.length; i++) {
        sum += Math.min(left[i], right[i]) - height[i];
    }
    return sum;
};

1025 2. Subsets II

/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
    // !!!! it is set, not array, order in the set doesn't matter, so you need to sort first!!!!
    if (nums == null || nums.length === 0) {
        return [[]];
    }
    nums.sort((a, b) => a - b);
    const res = [[]];
    const map = new Map();
    for (let num of nums) {
        let start = 0;
        if (map.has(num)) {
            start = map.get(num);
        }
        map.set(num, res.length) // !!!! this should update each time, not only in an else statement !!!!
        const currentLen = res.length; // !!!! if you are changing this length, you cannot use it to loop !!!
        for (let j = start; j < currentLen; j++) {
            const oneArray = res[j];
            const copyOneArray = [...oneArray, num];
            res.push(copyOneArray);
        }
    }
    return res;
};