记录

1204 4. Asteroid Collision

/**
* @param {number[]} asteroids
* @return {number[]}
*/
var asteroidCollision = function(asteroids) {
    // check
    // keep a stack
    // if stack has and top is posi, curr is neg, produce the next one as curr,
    if (asteroids == null || asteroids.length === 0) {
        return [];
    }
    const stack = [];
    for (let ast of asteroids) {
        let curr = ast
        while (stack.length > 0 && stack[stack.length - 1] > 0 && curr < 0) {
            const top = stack.pop();
            if (top > -curr) {
                curr = top;
            } else if (top === -curr) {
                curr = 0;
            }
        }
        if (curr) {
            stack.push(curr);
        }
    }
    return stack;
};

1204 5. Equal Tree Partition

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var checkEqualTree = function(root) {
    if (root == null) {return false}
    const set = new Set();
    const allSum = traverse(root); // Note the root val is not added to the set to avoid 0 as the all sum
    if (allSum % 2 === 1) {
        return false;
    } else {
        const half = allSum / 2;
        return set.has(half);
    }
   
   
    function traverse (node) {
        // assume node is not null
        let left = 0;
        let right = 0;
        if (node.left) {
            left = traverse(node.left);
            set.add(left);
        }
        if (node.right) {
            right = traverse(node.right);
            set.add(right);
        }
        return left + right + node.val;
    }
};

1204 6.  Inorder Successor in BST

No duplicates then it is easy

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function(root, p) {
    if (root == null) {return null}
    const val = p.val;
    let prev = null;
    traverse(root);
    return prev;
   
    // assuming no duplicate values
    function traverse (node) {
        if (node == null) {
            return;
        }
        if (val < node.val) {
            prev = node;
            traverse(node.left);
        } else {
            traverse(node.right);
        }
    }
};

1204 7. Find the Celebrity

/**
* Definition for knows()
*
* @param {integer} person a
* @param {integer} person b
* @return {boolean} whether a knows b
* knows = function(a, b) {
*     ...
* };
*/

/**
* @param {function} knows()
* @return {function}
*/
var solution = function(knows) {
    /**
     * @param {integer} n Total people
     * @return {integer} The celebrity
     */
    return function(n) {
        let candidate = 0;
        for (let i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }
        for (let i = 0; i < n; i++) {
            if (i !== candidate) {
                if ( !(knows(i, candidate) && !knows(candidate, i)) ) {
                    return -1;
                }
            }
        }
        return candidate;
    };
};

1204 8. Delete and Earn

/**
* @param {number[]} nums
* @return {number}
*/
var deleteAndEarn = function(nums) {
    // first, get the max of nums
    // create that long + 1 array
    // loop nums and put into corresponding indices
    // init curr, prev 0
    // from 1, update each
    // until you reached the last one
    if (nums == null || nums.length === 0) { // !!! how dare you forget check!!!!
        return 0;
    }
    const max = Math.max(...nums);
    const points = Array(max + 1).fill(0); // !!! if you want to accumulate on it, you need to init it!!!!! Always init it!!!!
    for (let num of nums) {
        points[num] += num;
    }
    let prev = 0;
    let curr = 0;
    for (let i = 1; i <= max; i++) {
        ;[prev, curr] = [curr, Math.max(curr, prev + points[i])];
    }
    return curr;
};

1204 9. Find the Derangement of An Array

/**
* @param {number} n
* @return {number}
*/
var findDerangement = function(n) {
    // 这题其实很好，顺序不重要，那么用掉一个，可以转化成子问题。对于理解递归和divide conquer很有帮助
    // 和坐飞机座位的那道题也有点像。
    const dp = Array(n + 1).fill(0);
    const mod = Math.pow(10, 9) + 7;
    dp[2] = 1;
    for (let i = 3; i <= n; i++) { // !!! need at least 2 els
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod;
    }
    return dp[n];
};

1205 1. My Calendar II

class MyCalendarTwo {

    TreeMap<Integer, Integer> map;
    public MyCalendarTwo() {
        // a treemap, time - value +1, -1
        // each time we book, we get the value
        // try adding it, then loop, if there exists 3 booking, false, restore
        this.map = new TreeMap();
    }
   
    public boolean book(int start, int end) {
        int startVal = this.map.containsKey(start) ? this.map.get(start) : 0;
        startVal++;
        this.map.put(start, startVal);
        int endVal = this.map.containsKey(end) ? this.map.get(end) : 0;
        endVal--;
        this.map.put(end, endVal);
        int count = 0;
        for (Integer value : this.map.values()) {
            count += value;
            if (count >= 3) {
                this.map.put(start, startVal - 1);
                this.map.put(end, endVal + 1);
                return false;
            }
        }
        return true;
    }
}

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

1205 2. Design Phone Directory


题目并没有要求要随机。是任意。就是随便怎么样都可以。

/**
* Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory.
* @param {number} maxNumbers
*/
var PhoneDirectory = function(maxNumbers) {
    this.list = [];
    this.set = new Set();
    for (let i = 0; i < maxNumbers; i++) {
        this.list.push(i);
    }
};

/**
* Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available.
* @return {number}
*/
PhoneDirectory.prototype.get = function() {
    if (this.list.length > 0) {
        const num = this.list.pop();
        this.set.add(num);
        return num;
    } else {
        return -1;
    }
};

/**
* Check if a number is available or not.
* @param {number} number
* @return {boolean}
*/
PhoneDirectory.prototype.check = function(number) {
    return !this.set.has(number);
};

/**
* Recycle or release a number.
* @param {number} number
* @return {void}
*/
PhoneDirectory.prototype.release = function(number) {
    // !!! need to check whether we need to release
    if (this.set.has(number)) {
        this.set.delete(number);
        this.list.push(number);
    }
};

/**
* Your PhoneDirectory object will be instantiated and called as such:
* var obj = Object.create(PhoneDirectory).createNew(maxNumbers)
* var param_1 = obj.get()
* var param_2 = obj.check(number)
* obj.release(number)
*/

1205 3. Convex Polygon

/**
* @param {number[][]} points
* @return {boolean}
*/
var isConvex = function(points) {
    if (points == null || points.length < 3) {
        return false;
    }
    points.push(points[0], points[1]); // !!!! 1. need two more!!!
    let prev = 0; // !!! 0 is a good trick because has no sign
    for (let i = 0; i + 2 < points.length; i++) {
        const curr = crossProduct(points[i], points[i + 1], points[i + 2]);
        if (curr !== 0) { // !!!! 2. if on the same line, ignore
            if (curr * prev < 0) {
                return false;
            } else {
                prev = curr;
            }
        }
    }
    return true;
};

function crossProduct (p1, p2, p3) {
    // x1y2 - x2y1
    const x1 = p2[0] - p1[0];
    const y1 = p2[1] - p1[1];
    const x2 = p3[0] - p2[0];
    const y2 = p3[1] - p2[1];
    return x1 * y2 - x2 * y1;
}

sicilianee 发表于 2017-12-6 13:06
1205 3. Convex Polygon

/**

Many things to note