记录

1201 1. 3Sum Smaller

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumSmaller = function(nums, target) {
    // check
    // loop the first, get new target
    // left and right
    // each time, sum all, good, get all, left++
    // not good, right-- till good. this is actually for each left get the right and update count
    if (nums == null || nums.length < 3) {
        return 0;
    }
    // !!!!! need to f***ing sort !!!!!!
    nums.sort((a, b) => a - b);
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        const newTarget = target - nums;
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) { // at least 2
            const sum = nums[left] + nums[right];
            if (sum < newTarget) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
};

1201 2.Binary Tree Longest Consecutive Sequence

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var longestConsecutive = function(root) {
    // check
    // check left, right,
    // get bigger one
    let count = 0;
    recurse(root);
    return count; // !! need to return the count
   
    // !!! you need the biggest count, not the count of the root, have to create a helper and count the max
    function recurse (root) {
        if (root == null) {return 0;}
        // !!! for the same reason, even if it doesn't meet the condition, you still need to recurse it because the
        // recurse also serves as traversing !!!!!
        let leftCount = 0;
        let rightCount = 0;
        if (root.left) {
            const leftCountCandidate = recurse(root.left);
            if (root.val - root.left.val === -1) {
                leftCount = leftCountCandidate;
            }
        }
        if (root.right) {
            const rightCountCandidate = recurse(root.right);
            if (root.val - root.right.val === -1) {
                rightCount = rightCountCandidate;
            }
        }
        const selfCount = Math.max(leftCount + 1, rightCount + 1); // !!! var mix
        count = Math.max(count, selfCount);
        return selfCount;
    }

};

1201 3. Sentence Similarity II

/**
* @param {string[]} words1
* @param {string[]} words2
* @param {string[][]} pairs
* @return {boolean}
*/
var areSentencesSimilarTwo = function(words1, words2, pairs) {
    // just a disjoint set union. union-find
    // check
    // check same len
    // create sets from pairs
    // for each word pair, check if is in the same set
    // all good, return
    if (words1 == null || words2 == null || words1.length !== words2.length) {
        return false;
    }
    pairs = pairs || [];
    // map pairs to numbers
    const set = new Set();
    for (let pair of pairs) {
        set.add(pair[0]);
        set.add(pair[1]);
    }
    const strToIndex = new Map([...set.values()].map((str, index) => [str, index]));
    const dSet = new DisjointSet(set.size);
    for (let pair of pairs) {
        dSet.union(strToIndex.get(pair[0]), strToIndex.get(pair[1]));
    }
   
    for (let i = 0; i < words1.length; i++) {
        const word1 = words1[i];
        const word2 = words2[i];
        const good1 = word1 === word2;
        const good2 = set.has(word1) && set.has(word2) && dSet.find(strToIndex.get(word1)) === dSet.find(strToIndex.get(word2));
        if (!(good1 || good2)) {
            return false;
        }
    }
    return true;
};


class DisjointSet { // !!!! no parenthesis for class
    constructor (len) {
        this.parent = Array(len).fill().map((v, i) => i);
    }
    find (x) {
        if (x !== this.parent[x]) {
            return this.find(this.parent[x]);
        } else {
            return x;
        }
    }
    union (x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}

1202 1. Longest Line of Consecutive One in Matrix

/**
* @param {number[][]} M
* @return {number}
*/
var longestLine = function(M) {
    // hori
    // verti
    // diag1
    // diag2
    if (M == null || M.length === 0) {return 0}
    const rowLen = M.length;
    const colLen = M[0].length;
    let maxCount = 0;
    const visit = (val, state) => {
        if (val === 1) {
            state.count++;
            maxCount = Math.max(state.count, maxCount);
        } else {
            state.count = 0;
        }
    }
    for (let i = 0; i < rowLen; i++) {
        const state = {count: 0}
        for (let j = 0; j < colLen; j++) {
            visit(M[i][j], state);
        }
    }
    for (let j = 0; j < colLen; j++) {
        const state = {count: 0}
        let count = 0;
        for (let i = 0; i < rowLen; i++) {
            visit(M[i][j], state);
        }
    }
    let startx = 0;
    let starty = 0
    while (!(startx === rowLen - 1 && starty === colLen - 1)) {
        let x = startx;
        let y = starty;
        const state = {count: 0}
        while (x >= 0 && y < colLen) {
            visit(M[x][y], state);
            x--;
            y++;
        }
        // how to change start and end is the main thing
        if (startx < rowLen - 1) {
            startx++;
        } else {
            starty++;
        }
    }
    startx = rowLen - 1;
    starty = 0;
    while (!(startx === 0  && starty === colLen - 1)) {
        let x = startx;
        let y = starty;
        const state = {count: 0};
        while (x < rowLen && y < colLen) {
            visit(M[x][y], state);
            x++;
            y++;
        }
        if (startx > 0) {
            startx--;
        } else {
            starty++;
        }
    }
    return maxCount;
};

1202 2. Flatten 2D Vector

/**
* @constructor
* @param {Integer[][]} vec2d
*/
var Vector2D = function(vec2d) {
    // check
    if (vec2d == null || vec2d.length === 0) {
        this.invalid = true;
        return; // !!! need to explicitly return to terminate
    }
    this.rowIter = vec2d[Symbol.iterator]();
    this.rowItem = this.rowIter.next();
    this.colIter = this.rowItem.value[Symbol.iterator]();
    this.colItem = this.colIter.next();
};


/**
* @this Vector2D
* @returns {boolean}
*/
Vector2D.prototype.hasNext = function() {
    if (this.invalid) {return false}
    while (this.colItem.done) {
        this.rowItem = this.rowIter.next();
        if (this.rowItem.done) {
            return false;
        } else {
            this.colIter = this.rowItem.value[Symbol.iterator]();
            this.colItem = this.colIter.next();
        }
    }
    return true;
};

/**
* @this Vector2D
* @returns {integer}
*/
Vector2D.prototype.next = function() {
    if (this.hasNext()) {
        // !!! 1. after that, you shall move the current pointer
        const val = this.colItem.value;
        this.colItem = this.colIter.next(); // !!! 2. you should not only call next on the iter, but also update the current value
        return val;
        
    } else {
        throw new Error('Invalid operation');
    }
};

/**
* Your Vector2D will be called like this:
* var i = new Vector2D(vec2d), a = [];
* while (i.hasNext()) a.push(i.next());
*/

1203 1. Verify Preorder Sequence in Binary Search Tree

/**
* @param {number[]} preorder
* @return {boolean}
*/
var verifyPreorder = function(preorder) {
    if (preorder == null || preorder.length === 0) {
        return true;
    }
    const stack = [];
    let min = -Infinity;
    for (let i of preorder) {
        if (i < min) {
            return false;
        } else {
            while (stack.length > 0 && i > stack[stack.length - 1]) { // !!! while not if because will need to pop all elements from the stack
                min = stack.pop();
            }
            stack.push(i);
        }
    }
    return true;
};

1203 2. Strobogrammatic Number II

/**
* @param {number} n
* @return {string[]}
*/
var findStrobogrammatic = function(n) {
    let res = n % 2 === 0 ? [''] : ['0', '1', '8'];
    const size = Math.trunc(n / 2);
    for (let i = 0; i < size; i++) {
        const newRes = [];
        for (let str of res) {
            if (i !== size - 1) {
                newRes.push(`0${str}0`);
            }
            newRes.push(`1${str}1`);
            newRes.push(`8${str}8`);
            newRes.push(`6${str}9`);
            newRes.push(`9${str}6`);
        }
        res = newRes;
    }
    return res;
};

1203 3. Shortest Word Distance II

/**
* @param {string[]} words
*/
var WordDistance = function(words) {
    this.map = new Map();
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const list = this.map.get(word) || [];
        list.push(i);
        this.map.set(word, list);
    }
};

/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
WordDistance.prototype.shortest = function(word1, word2) {
    const list1 = this.map.get(word1);
    const list2 = this.map.get(word2);
    let p1 = 0;
    let p2 = 0;
    let min = Infinity;
    while (p1 < list1.length && p2 < list2.length) {
        min = Math.min(min, Math.abs(list1[p1] - list2[p2]));
        if (list1[p1] < list2[p2]) {
            p1++;
        } else {
            p2++;
        }
    }
    return min;
};

/**
* Your WordDistance object will be instantiated and called as such:
* var obj = Object.create(WordDistance).createNew(words)
* var param_1 = obj.shortest(word1,word2)
*/

1203 4. My Calendar I

class MyCalendar {
    TreeMap<Integer, Integer> map;

    public MyCalendar() {
        this.map = new TreeMap();
    }
   
    public boolean book(int start, int end) {
        Integer prev = this.map.floorKey(start); // !!!! cannot use int because you may have null here
        Integer next = this.map.ceilingKey(start);
        if ((prev == null || this.map.get(prev) <= start ) &&
           (next == null || end <= next) ) {
            this.map.put(start, end);
            return true;
        } else {
            return false;
        }
    }
}

/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/

1023 5. Bomb Enemy

/**
* @param {character[][]} grid
* @return {number}
*/
var maxKilledEnemies = function(grid) {
        if (grid == null || grid.length === 0) {
            return 0;
        }
        const rowLen = grid.length;
        const colLen = grid[0].length;
        const create2d = () => Array(rowLen).fill().map(() => Array(colLen).fill(0));
        const left = create2d();
        const right = create2d();
        const top = create2d();
        const bottom = create2d();
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                const k = colLen - 1 - j;
                if (j === 0) {
                    left[i][j] = 0;
                    right[i][k] = 0;
                } else {
                    // for left
                    if (grid[i][j - 1] === 'W') {
                        left[i][j] = 0;
                    } else if (grid[i][j - 1] === 'E') {
                        left[i][j] = left[i][j - 1] + 1;
                    } else {
                        left[i][j] = left[i][j - 1];
                    }
                    // for right
                    if (grid[i][k + 1] === 'W') {
                        right[i][k] = 0;
                    } else if (grid[i][k + 1] === 'E') {
                        right[i][k] = right[i][k + 1] + 1; // !!! which part + 1
                    } else {
                        right[i][k] = right[i][k + 1];
                    }
                    
                }
            }
        }
        for (let j = 0; j < colLen; j++) {
            for (let i = 0; i < rowLen; i++) {
                if (i === 0) {
                    top[i][j] = 0;
                    bottom[i][j] = 0;
                } else {
                    // for top
                    if (grid[i - 1][j] === 'W') {
                        top[i][j] = 0;
                    } else if (grid[i - 1][j] === 'E') {
                        top[i][j] = top[i - 1][j] + 1;
                    } else {
                        top[i][j] = top[i - 1][j];
                    }
                    // for bottom
                    const k = rowLen - 1 - i; // !!! here it is rowLen not colLen
                    if (grid[k + 1][j] === 'W') {
                        bottom[k][j] = 0;
                    } else if (grid[k + 1][j] === 'E') {
                        bottom[k][j] = bottom[k + 1][j] + 1;
                    } else {
                        bottom[k][j] = bottom[k + 1][j];
                    }
                }
            }
        }
        let max = 0;
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                if (grid[i][j] === '0') {
                    const val = top[i][j] + bottom[i][j] + left[i][j] + right[i][j];
                    max = Math.max(val, max);
                }
            }
        }
        return max;
};