记录

1125 9. Flood Fill

/**
* @param {number[][]} image
* @param {number} sr
* @param {number} sc
* @param {number} newColor
* @return {number[][]}
*/
var floodFill = function(image, sr, sc, newColor) {
    if (image == null || image.length === 0) {return image};
    const rowLen = image.length;
    const colLen = image[0].length;
    const color = image[sr][sc];
    const visited = Array(rowLen).fill().map(() => Array(colLen).fill(false));
    fill(sr, sc, color);
    return image; // !!!! return it
   
    // !!!! again, the visited problem, infinite loop
    function fill (i, j, color) {
        if (i < 0 || i >= rowLen) {return}
        if (j < 0 || j >= colLen) {return}
        if (visited[i][j]) {return} // !!! you need to put it here, see below
        if (image[i][j] === color) {
            image[i][j] = newColor;
            visited[i][j] = true;

            // !!! these shall only execute when the current one is true
            const moves = [[0, -1], [0, 1], [-1, 0], [1, 0]];
            for (let move of moves) {
                const x = i + move[0];
                const y = j + move[1];
                fill(x, y, color); // !!! not here because you test the validity of indices in the beginning
            }
        }

    }
};

这题还要再不断练。

1125 10. Sentence Similarity

/**
* @param {string[]} words1
* @param {string[]} words2
* @param {string[][]} pairs
* @return {boolean}
*/
var areSentencesSimilar = function(words1, words2, pairs) {
    if (words1.length !== words2.length) {return false}
    const map = new Map();
    const addItem = (key, val) => {
        const set = map.get(key) || new Set();
        set.add(val);
        map.set(key, set);
    }
    for (let pair of pairs) {
        addItem(pair[0], pair[1]);
        addItem(pair[1], pair[0]);
    }
    for (let i = 0; i < words1.length; i++) {
        if (!(   words1[i] === words2[i] ||
            map.has(words1[i]) && map.get(words1[i]).has(words2[i])
        )) {return false;}
    }
    return true;
};

1125 11. Plus One Linked List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var plusOne = function(head) {
    let newHead = reverse(head);
    let node = newHead;
    let carry = 1;
    let prev = null;
    while (node != null) {
        const sum = node.val + carry;
        node.val = sum % 10;
        carry = Math.trunc(sum / 10);
        prev = node;
        node = node.next;
    }
    if (carry > 0) {
        const newNode = new ListNode(carry);
        prev.next = newNode;
    }
    return reverse(newHead);
   
};

function reverse (head) {
    const stack = [];
    let node = head;
    while (node != null) {
        stack.push(node);
        node = node.next;
    }
    const dummy = new ListNode(0);
    node = dummy;
    while (stack.length > 0) {
        const next = stack.pop();
        node.next = next;
        node = next;
    }
    // !!! the last null
    node.next = null;
    return dummy.next;
}



要再做，有很多文章可以做。

1125 12. Design Hit Counter

/**
* Initialize your data structure here.
*/
var HitCounter = function() {
    this.q = [];
};

/**
* Record a hit.
        @param timestamp - The current timestamp (in seconds granularity).
* @param {number} timestamp
* @return {void}
*/
HitCounter.prototype.hit = function(timestamp) {
    this.q.push(timestamp);
};

/**
* Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity).
* @param {number} timestamp
* @return {number}
*/
HitCounter.prototype.getHits = function(timestamp) {
    const start = timestamp - 300; // exclusive
    while (this.q.length > 0 && this.q[0] <= start) {
        this.q.shift(); // !!! note calls are chronological order, so no previous timestamp will be used
    }
    return this.q.length;
};

/**
* Your HitCounter object will be instantiated and called as such:
* var obj = Object.create(HitCounter).createNew()
* obj.hit(timestamp)
* var param_2 = obj.getHits(timestamp)
*/

1125 13. Nested List Weight Sum II

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
*     Return true if this NestedInteger holds a single integer, rather than a nested list.
*     @return {boolean}
*     this.isInteger = function() {
*         ...
*     };
*
*     Return the single integer that this NestedInteger holds, if it holds a single integer
*     Return null if this NestedInteger holds a nested list
*     @return {integer}
*     this.getInteger = function() {
*         ...
*     };
*
*     Set this NestedInteger to hold a single integer equal to value.
*     @return {void}
*     this.setInteger = function(value) {
*         ...
*     };
*
*     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
*     @return {void}
*     this.add = function(elem) {
*         ...
*     };
*
*     Return the nested list that this NestedInteger holds, if it holds a nested list
*     Return null if this NestedInteger holds a single integer
*     @return {NestedInteger[]}
*     this.getList = function() {
*         ...
*     };
* };
*/
/**
* @param {NestedInteger[]} nestedList
* @return {number}
*/
var depthSumInverse = function(nestedList) {
    // first, find the max depth
    // then, start from root is max depth, we just decrease at each level
    let depth = getDepth(nestedList);
    let sum = 0;
    addUp(nestedList, depth);
    return sum;
   
    function addUp (list, depth) {
        for (let el of list) {
            if (el.isInteger()) {
                sum += el.getInteger() * depth;
            } else {
                addUp(el.getList(), depth - 1);
            }
        }
    }
   
    // what about nested empty list?
    function getDepth (list) {
        if (list == null || list.length === 0) {return 0}
        let max = 1;
        for (let el of list) {
            if (!el.isInteger()) {
                const depth = getDepth(el.getList()) + 1;
                max = Math.max(depth, max);
            }
        }
        return max;
    }
};

1126 1. Squirrel Simulation

/**
* @param {number} height
* @param {number} width
* @param {number[]} tree
* @param {number[]} squirrel
* @param {number[][]} nuts
* @return {number}
*/
var minDistance = function(height, width, tree, squirrel, nuts) {
    // !!! 不是直接找最近的nut， 要建模
    // for each nut, the distance would be twice the treeDis originally
    // use as first nut, it becomes treeDis + squirrelDis. Looking for what you saved!
    // what you saved is: 2 * treeDis - (treeDis + squirrelDis) = treeDis - squirrelDis
    // save most is what you want.
    let maxSave = -Infinity;
    let sum = 0;
    for (let nut of nuts) {
        sum += distance(tree, nut) * 2;
        const saved = distance(tree, nut) - distance(squirrel, nut);
        maxSave = Math.max(saved, maxSave);
    }
    return sum - maxSave;
};

function distance ([x1, y1], [x2, y2]) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

1126 2. Sparse Matrix Multiplication

/**
* @param {number[][]} A
* @param {number[][]} B
* @return {number[][]}
*/
var multiply = function(A, B) {
    if (A == null || A.length === 0 || B == null || B.length === 0) {return []}
    const rowLen = A.length;
    const colLen = B[0].length;
    const C = Array(rowLen).fill().map(() => Array(colLen).fill(0));
    for (let i = 0; i < rowLen; i++) {
        for (let k = 0; k < A[0].length; k++) {
            if (A[i][k] !== 0) {
                for (let j = 0; j < colLen; j++) {
                    if (B[k][j] !== 0) {
                        C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
    }
    return C;
};

1126 3.  Zigzag Iterator

/**
* @constructor
* @param {Integer[]} v1
* @param {Integer[]} v1
*/
var ZigzagIterator = function ZigzagIterator(v1, v2) {
    this.matrix = [v1, v2];
    this.row = 0; // !!! 0, 0 could already be empty
    this.col = 0;
    if (v1.length === 0) {
        this.row = 1;
    }
};


/**
* @this ZigzagIterator
* @returns {boolean}
*/
ZigzagIterator.prototype.hasNext = function hasNext() {
    return !(this.col >= this.matrix[this.row].length)
};

/**
* @this ZigzagIterator
* @returns {integer}
*/
ZigzagIterator.prototype.next = function next() {
    if (!this.hasNext()) {throw new Error('No next')}
    const val = this.matrix[this.row][this.col];
    const limit = Math.min(this.matrix[0].length, this.matrix[1].length);
    if (this.col < limit) {
        if (this.row === 0) {
            this.row = 1;
        } else {
            this.row = 0;
            this.col++;
            if (this.col >= this.matrix[0].length) {
                this.row = 1;
            }
        }
    } else {
        this.col++;
    }
    return val;
};

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

sicilianee 发表于 2017-11-27 11:51
1126 3.  Zigzag Iterator

/**

太蠢了， 这两个方法比较好：
http://www.cnblogs.com/grandyang/p/5212785.html

1126 4. Ternary Expression Parser

/**
* @param {string} expression
* @return {string}
*/
var parseTernary = function(expression) {
    if (!expression.includes('?')) {return expression}
    const cond = expression[0] === 'T';
    let count = 0;
    // T?T?2:1:3
    for (let i = 1; i < expression.length; i++) {
        if (expression[i] === '?') {
            count++;
        } else if (expression[i] === ':') {
            count--;
            if (count === 0) {
                const left = expression.slice(2, i);
                const right = expression.slice(i + 1);
                return cond ? parseTernary(left) : parseTernary(right);
            }
        }
    }
    throw new Error('invalid input')
};


http://blog.csdn.net/shiyang6017/article/details/52901396
http://hongzheng.me/leetcode/leetcode-439-ternary-expression-parser/
两种方法，第一种实际上类似于reverse polish notation, 但是原po的解法没有考虑数字连续的情况，lc没有测这种情况。但是原理是不变的，可以先把所有input过一遍清理一遍。但是另外一个问题是，第一种解法不能够short circuit，必须要算出所有的表达式的值。