记录

1105 8. Max Sum of Rectangle No Larger Than K

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        // check
        // find max of row, col, assume row
        // loop start row
        // loop end row
        // sum in between using dp
        // for 1-d sum, loop k, sum so far, add prev sum to treeSet, using ceil to get possible values
        // and update max
        // move on to next
        // until ret
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        boolean colBigger = colLen >= rowLen;
        if (!colBigger) {
            rowLen = matrix[0].length;
            colLen = matrix.length;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < rowLen; i++) {
            int[] sum = new int[colLen];
            for (int j = i; j < rowLen; j++) {
                TreeSet<Integer> set = new TreeSet();
                set.add(0);
                int value = 0;
                for (int m = 0; m < colLen; m++) {
                    sum[m] = sum[m] + (colBigger ? matrix[j][m] : matrix[m][j]); // !!! precedence?
                    value = value + sum[m];
                    Integer rest = set.ceiling(value - k); // !!! must be Integer to incluce null
                    if (rest != null) {
                        max = Math.max(max, value - rest);
                    }
                    // !!!!! you forgot to add the new value!!!!
                    set.add(value);
                }
            }
        }
        return max;
    }
}

1105 9. Sliding Window Maximum

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
    //key: 当一个数进入一直到他被移除的全过程中，比他小的数永远不可能成为最大值。而他前面的数会比他先移除，所以当一个数
    // 移入，我们可以把前面所有小于他的数移除。
    if (nums == null || nums.length === 0) {
        return [];
    }
    const dq = [];
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        // add the current num into the q, q is descending
        // if i >= k && the num to remove is the max, remove it from the q
        // update the max for the current one, go on to the next round
        const num = nums[i];
        while (dq.length > 0 && dq[dq.length - 1] < num) {
            dq.pop();
        }
        dq.push(num);
        if (i >= k && nums[i - k] === dq[0]) {
            // !!! because we need to remove the last one from the window (q), we get the last one from
            // the nums, and if it is not the current max, it should not be in the q. if it is the current max, we should remove it
            dq.shift();
        }
        if (i >= k - 1) {
            res.push(dq[0]);
        }
    }
    return res;
};

All the answers online seem to store the index instead of the value. I don't see why we need to do that. I just store the values. It passed the oj but need to think through a bit whether it is correct or not.

1106 1. Judge Route Circle


/**
* @param {string} moves
* @return {boolean}
*/
var judgeCircle = function(moves) {
    let x = 0;
    let y = 0;
    for (let move of moves) {
        switch (move) {
            case 'L':
                y--;
                break;
            case 'R':
                y++;
                break;
            case 'U':
                x--;
                break;
            case 'D':
                x++;
                break;
            default:
                throw new Error('No such move');
        }
    }
    return x === 0 && y === 0;
};

1106 2. Word Pattern

/**
* @param {string} pattern
* @param {string} str
* @return {boolean}
*/
var wordPattern = function(pattern, str) {
    if (pattern == null || pattern.length === 0 || str == null || str.length === 0) {
        return false;
    }
    const patterns = pattern.split('');
    const strs = str.split(' ');
    if (patterns.length != strs.length) {
        return false;
    }
    const dict = {};
    const set = new Set();
    for (let i = 0; i < patterns.length; i++) {
        const p = patterns[i];
        if (dict[p]) {
            if (dict[p] !== strs[i]) {
                return false;
            }
        } else {
            if (set.has(strs[i])) {
                return false;
            }
            set.add(strs[i]);
            dict[p] = strs[i];
        }
    }
    return true;
};

Need to checkout the two hashMap solution

1106 3. Add Binary

/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {
    if (a == null || a.length === 0) {
        return b;
    }
    if (b == null || b.length === 0) {
        return a;
    }
    const aList = a.split('').map(str => Number.parseInt(str, 10)).reverse();
    const bList = b.split('').map(str => Number.parseInt(str, 10)).reverse();
    const len = Math.max(aList.length, bList.length);
    let carry = 0;
    const res = [];
    for (let i = 0; i < len; i++) {
        const aNum = aList[i] ? aList[i] : 0;
        const bNum = bList[i] ? bList[i] : 0;
        const sum = aNum + bNum + carry;
        carry = sum >= 2 ? 1 : 0;
        res[i] = sum >= 2 ? sum - 2 : sum;
    }
    if (carry !== 0) {
        res[len] = 1;
    }
    res.reverse();
    return res.join('');
};

1106 4. Longest Univalue Path

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var longestUnivaluePath = function(root) {
    if (root == null) {
        return 0;
    }
    let res = 0;
    recurse(root);
    return res;
   
    function recurse (node) {
        if (node == null) {return 0;}
        let left = recurse(node.left);
        let right = recurse(node.right);
        left = node.left && node.left.val === node.val ? left + 1 : 0;
        right = node.right && node.right.val === node.val ? right + 1 : 0;
        res = Math.max(res, left + right);
        return Math.max(left, right);
    }
};

1106 5. Remove Linked List Elements

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
    if (head == null) {
        return head;
    }
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    while (prev.next != null) {
        if (prev.next.val === val) {
            prev.next = prev.next.next; // !!! should not move prev when you removed a note, since the next node will be a new node and you haven't visited it yet. !!!!
        } else {
            prev = prev.next; // !!!! only do this when you did not remove any
        }
    }
    return dummy.next;
};

1106 6. Ugly Number II

/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function(n) {
    if (n <= 0) {return null;}
    if (n === 1) {
        return 1;
    }
    const list = [1];
    let index2 = 0;
    let index3 = 0;
    let index5 = 0;
    let count = 1;
    while (count < n) {
        const val2 = list[index2] * 2;
        const val3 = list[index3] * 3;
        const val5 = list[index5] * 5;
        const min = Math.min(val2, val3, val5);
        list.push(min);
        count++;
        if (min === list[index2] * 2) {
            index2++;
        }
        if (min === list[index3] * 3) {
            index3++;
        }
        if (min === list[index5] * 5) {
            index5++;
        }
    }
    return list[list.length - 1];
};

1106 7. 01 Matrix

/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var updateMatrix = function(matrix) {
    if (matrix == null || matrix.length === 0 || matrix[0].length === 0) {
        return matrix;
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const res = Array(rowLen).fill().map(() => Array(colLen).fill(-1));
    const q = [];
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (matrix[i][j] === 0) {
                res[i][j] = 0;
                q.push([i, j]);
            }
        }
    }
    const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    while (q.length > 0) {
        const size = q.length;
        const level = [];
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            const val = res[node[0]][node[1]]; // !!!! note how the value is accessed, two levels of []
            // four directions, if not visited, visit it and push it into the q
            for (let move of moves) {
                const x = node[0] + move[0];
                const y = node[1] + move[1];
                if (x >= 0 && x < rowLen && y >= 0 && y < colLen && res[x][y] < 0) {
                    res[x][y] = val + 1;
                    q.push([x, y]);
                }
            }
        }
        q.push(...level);
    }
    return res;
};

1107 1.  Trim a Binary Search Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} L
* @param {number} R
* @return {TreeNode}
*/
var trimBST = function(root, L, R) {
    // !!!! cannot just decide on left, go right it will increase
    // seems like we need to construct a new tree.
    if (root == null) {
        return null;
    }
    if (root.val < L) {
        return trimBST(root.right, L, R);
    }
    if (root.val > R) {
        return trimBST(root.left, L, R);
    }
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;
};