记录

1107 2. Unique Substrings in Wraparound String

/**
* @param {string} p
* @return {number}
*/
var findSubstringInWraproundString = function(p) {
    if (p == null || p.length === 0) {
        return 0;
    }
    let len = 0;
    const dict = {};
    for (let i = 0; i < p.length; i++) {
        if (i > 0 && (p.charCodeAt(i) - p.charCodeAt(i - 1) === 1 || p.charCodeAt(i - 1) - p.charCodeAt(i) === 25)) {
            len++;
        } else {
            len = 1;
        }
        dict[p[i]] = dict[p[i]] || 0;
        dict[p[i]] = Math.max(dict[p[i]], len);
    }
    return Object.values(dict).reduce((a, b) => a + b);
};

1107 3. Partition List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
    if (head == null) {
        return null;
    }
    const lessDummy = new ListNode(0);
    const greaterDummy = new ListNode(0);
    lessDummy.next = head;
    let prev = lessDummy;
    let greaterPrev = greaterDummy;
    while (prev.next != null) {
        if (prev.next.val < x) {
            prev = prev.next;
        } else {
            const next = prev.next.next;
            const node = prev.next;
            prev.next = next;
            greaterPrev.next = node;
            node.next = null;
            greaterPrev = greaterPrev.next;
        }
    }
    prev.next = greaterDummy.next;
    return lessDummy.next;
};

1107 4. Rectangle Area

/**
* @param {number} A
* @param {number} B
* @param {number} C
* @param {number} D
* @param {number} E
* @param {number} F
* @param {number} G
* @param {number} H
* @return {number}
*/
var computeArea = function(A, B, C, D, E, F, G, H) {
    const area1 = (C - A) * (D - B);
    const area2 = (G - E) * (H - F);
    const leftX = Math.max(A, E);
    const rightX = Math.min(G, C);
    const downY = Math.max(B, F);
    const upY = Math.min(D, H);
    let overlap = 0;
    if (leftX < rightX && downY < upY) {
        overlap = (rightX - leftX) * (upY - downY);
    }
    return area1 + area2 - overlap;
};

1107 5. Baseball Game

/**
* @param {string[]} ops
* @return {number}
*/
var calPoints = function(ops) {
    if (ops == null || ops.length === 0) {
        return 0;
    }
    let newOps = [];
    for (let op of ops) {
        if (op === 'C') {
            newOps.pop();
        } else {
            newOps.push(op);
        }
    }
    const values = [];
    for (let op of newOps) {
        const len = values.length;
        if (op === '+') {
            const value = values[len - 1] + values[len - 2];
            values.push(value);
        } else if (op === 'D') {
            values.push(values[len - 1] * 2);
        } else {
            values.push(Number.parseInt(op, 10));
        }
    }
    return values.reduce((a, b) => a + b);
};

sicilianee 发表于 2017-11-8 12:35
1107 5. Baseball Game

/**

没有必要过两遍，直接过一遍。
因为我们有一个values数组，我们每次操作的是这个values数组。

1107 6. Course Schedule

/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
    // check
    // build adjacency list, also build the inDegree dict
    // loop and put all inDegree 0 nodes into q
    // bfs the q,
    // get one 0-node, cut all edges using the adjacency list and update inDegree dict
    // after bfs, check all nodes to see if inDegree all goes to 0
    if (numCourses <= 0 || prerequisites == null || prerequisites.length === 0) {return true}
    const g = Array(numCourses).fill().map(() => Array());
    const dict = {};
    for (let edge of prerequisites) {
        g[edge[1]].push(edge[0]);
        dict[edge[0]] = dict[edge[0]] || 0;
        dict[edge[0]]++;
    }
    const q = [];
    // !!!! not all nodes are in the dict, if they are not connected or don't have inDgree, they are not even in the dict, so we loop all nodes, not only the dict
    for (let i = 0; i < numCourses; i++) {
        dict = dict[i] || 0;
        if (dict[i] === 0) {
            q.push(i); // !!!! you push i, not dict[i]  !!!!
        }
    }
    while (q.length > 0) {
        const size = q.length;
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            const tos = g[node];
            for (let to of tos) {
                dict[to]--;
                if (dict[to] === 0) {
                    q.push(to);
                }
            }
        }
    }
    for (let i = 0; i < numCourses; i++) {
        if (dict[i] !== 0) {
            return false;
        }
    }
    return true;
};[/i][/i][/i][/i][i][i][/i][/i]
这种错误实在是很难找

1107 7. Construct Binary Tree from Preorder and Inorder Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
    if (preorder == null || preorder.length === 0 || inorder == null || inorder.length === 0) {
        return null;
    }
    return recurse(0, preorder.length - 1, 0, preorder.length - 1);
   
    function recurse (i, j, m, n) {
        if (i > j) { // !!!!!! i > j, not i < j, as the invalid condition
            return null;
        }
        if (i === j) {
            return new TreeNode(preorder[i]);
        }
        const rootVal = preorder[i];
        let k;
        for (k = m; k <= n; k++) {
            if (inorder[k] === rootVal) {
                break;
            }
        }
        const left = recurse(i + 1, k - m + i, m, k - 1);
        const right = recurse(k - m + i + 1, j, k + 1, n);
        const self = new TreeNode(rootVal);
        self.left = left;
        self.right = right;
        return self;
    }
};

1107 8. Construct Binary Tree from Inorder and Postorder Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
    if (inorder == null || inorder.length === 0 || postorder == null || postorder.length === 0) {
        return null;
    }
    return recurse(0, inorder.length - 1, 0, inorder.length - 1);
   
    function recurse (i, j, m, n) {
        console.log(i, j, m, n)
        if (i > j) {
            return null;
        }
        if (i === j) {
            return new TreeNode(inorder[i]);
        }
        const rootVal = postorder[n];
        let k;
        for (k = i; k <= j; k++) {
            if (inorder[k] === rootVal) {
                break;
            }
        }
        const leftSize = k - i;
        const rightSize = j - k;
        const left = recurse(i, k - 1, m, m + leftSize - 1); // !!!! need to -1 for end index
        const right = recurse(k + 1, j, n - 1 - rightSize + 1, n - 1); // !!! same here needs to + 1
        const self = new TreeNode(rootVal);
        self.left = left;
        self.right = right;
        return self;
    }
};

1108 1.  Palindromic Substrings


/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    const len = s.length;
    let count = 0;
    const dp = Array(len).fill().map(() => Array(len));
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            if (i === j) {
                dp[i][j] = true;
            } else if (j === i + 1) {
                dp[i][j] = s[i] === s[j];
            } else {
                if (s[i] === s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
            if (dp[i][j]) {
                count++;
            }
        }
    }
    return count;
};

1108 2. Erect the Fence

/**
* Definition for a point.
* function Point(x, y) {
*     this.x = x;
*     this.y = y;
* }
*/
/**
* @param {Point[]} points
* @return {Point[]}
*/
var outerTrees = function(points) {
    if (points == null || points.length === 0) {
        return [];
    }
    points.sort((a, b) => a.x - b.x !== 0 ? a.x - b.x : a.y - b.y);
    const list = [];
    for (let i = 0; i < points.length; i++) {
        while (list.length >= 2 && orientation(list[list.length - 2], list[list.length - 1], points[i]) < 0) {
            list.pop();
        }
        list.push(points[i]);
    }
    list.pop(); // !!!! this one is needed not only for deduplication, but also because it breaks the order !!!!
    for (let i = points.length - 1; i >= 0; i--) { // !!!!! finally !!!!! the second one you are looping the list, you should be looping the points !!!!1
        while (list.length >= 2 && orientation(list[list.length - 2], list[list.length - 1], points[i]) < 0) {
            list.pop();
        }
        list.push(points[i]);
    }
    // list.pop(); // this is just for dedup, we could remove it
    // !!!!! it could have duplicate ones, we must remove dup
    // we actually need a set like in java, but no built-in way to do it in js
    const dict = {};
    list.forEach(item => {
        const key = `${item.x}:${item.y}`;
        dict[key] = item;
    });
    return Object.values(dict)
};



function orientation (p, q, r) {
    return (q.x - p.x) * (r.y - q.y) - (r.x - q.x) * (q.y - p.y);
}