记录

sicilianee 发表于 2017-11-9 13:46
1108 2. Erect the Fence

/**

I think we need a better way to handle the use case of set of objects

sicilianee 发表于 2017-11-9 13:47
I think we need a better way to handle the use case of set of objects

/**
* 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 map = new Map(list.map(item => [`${item.x}:${item.y}`, item]));
    return [...map.values()];
};



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

sicilianee 发表于 2017-11-9 13:55
/**
* Definition for a point.
* function Point(x, y) {

The two simpler solutions I can think of now:


const list = [
    {x: 1, y: 2},
    {x: 2, y: 3},
    {x: 3, y: 4}
]

// 1. object dict
const dict = {}
list.forEach(item => {
    const key = `${item.x}:${item.y}`
    dict[key] = item
})
const values = Object.values(dict)

// 2. Map
const map = new Map(list.map(item => [`${item.x}:${item.y}`, item]))
const values = [...map.values()]

1108 3.  Strange Printer

/**
* @param {string} s
* @return {number}
*/
var strangePrinter = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    const len = s.length;
    const dp = Array(len).fill().map(() => Array(len).fill(0));
    for (let range = 1; range <= len; range++) {
        for (let start = 0; start + range - 1 < len; start++) {
            const end = start + range - 1;
            if (start === end) {
                dp[start][end] = 1;
            } else {
                let val = end - start + 1;
                for (let k = start; k < end; k++) {
                    let newVal = dp[start][k] + dp[k + 1][end];
                    if (s[start] === s[k + 1]) {
                        newVal--;
                    }
                    val = Math.min(val, newVal);
                }
                dp[start][end] = val;
            }
        }
    }
    return dp[0][len - 1];
};

实际上没那么难。还是老思路。书影的代码虽然少但是反而是很难看懂，搞得反而好像没法理解。

1109 1. Frog Jump


var canCross = function(stones) {
    const dict = {};
    for (let stone of stones) {
        // !!!!! note you must use set not array cause there might be huge number of duplicates. Try it and log the dict in the end if you don't understand
        dict[stone] = new Set();
    }
    dict[0].add(0);
    for (let stone of stones) {
        for (let step of dict[stone]) {
            for (let k of [step + 1, step, step - 1]) {
                if (k > 0 && dict[stone + k] != null) {
                    dict[stone + k].add(k);
                }
            }
        }
    }
    return dict[stones[stones.length - 1]].size > 0
};


!!! Must use set
Check other solutions.

1109 2. Maximum Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function(nums) {
    if (nums == null || nums.length === 0) {
        return null;
    }
    const max = Math.max(...nums); // !!!! add the ...
    const index = nums.indexOf(max);
    const leftArray = nums.slice(0, index);
    const rightArray = nums.slice(index + 1);
    const self = new TreeNode(max);
    self.left = constructMaximumBinaryTree(leftArray);
    self.right = constructMaximumBinaryTree(rightArray);
    return self;
};

1109 3.  Binary Number with Alternating Bits

/**
* @param {number} n
* @return {boolean}
*/
var hasAlternatingBits = function(n) {
    let prev = null
    while (n > 0) {
        const bit = n & 1;
        if (bit === prev) {
            return false;
        }
        prev = bit;
        n = n >>> 1;
    }
    return true;
};

1109 4. Employee Importance

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        // first, create a map of id => entity
        // then, using the id to find the next subs, push to q, add up the score, until the q is empty
        Map<Integer, Employee> map = new HashMap();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(id);
        int score = 0;
        while (!q.isEmpty()) {
            int aId = q.remove();  // !!!! note java doesn't allow local variable shadowing, not like js !!!!
            // see https://stackoverflow.com/questions/30857753/re-declaring-variables-inside-loops-in-java
            Employee employee = map.get(aId);
            score += employee.importance;
            q.addAll(employee.subordinates);
        }
        return score;
    }
}

1109 5.  1-bit and 2-bit Characters

/**
* @param {number[]} bits
* @return {boolean}
*/
var isOneBitCharacter = function(bits) {
    let res = true;
    const len = bits.length;
    recurse(0);
    return res;
   
    function recurse (i) {
        if (i >= len) {
            return;
        }
        // if (i === len - 1 && bits[i] === 1) {   // !!! that's not valid, shouldn't count
        //     res = false;
        // }
        if (i === len - 2 && bits[i] === 1) {
            res = false;
        }
        if (bits[i] === 0) {
            recurse(i + 1);
        } else {
            recurse(i + 2);
        }
    }
};

sicilianee 发表于 2017-11-10 15:41
1109 5.  1-bit and 2-bit Characters

/**

确实，loop就行了，不用recursion.  看leetcode上答案