记录

Make up

0822 2. Evaluate Division

/**
* @param {string[][]} equations
* @param {number[]} values
* @param {string[][]} queries
* @return {number[]}
*/
var calcEquation = function(equations, values, queries) {
    if (equations == null || equations.length === 0) {return queries.map(() => -1);}
    const set = new Set();
    equations.forEach(pair => {
        set.add(pair[0]);
        set.add(pair[1]);
    });
    const nameToKey = {};
    [...set].forEach((val, index) => nameToKey[val] = index);
    const len = set.size; // !!!!! not length but size, and it's not a method
    const matrix = Array(len).fill().map(() => Array(len).fill());
    equations.forEach((eq, index) => {
        const value = values[index];
        matrix[nameToKey[eq[0]]][nameToKey[eq[1]]] = value;
        matrix[nameToKey[eq[1]]][nameToKey[eq[0]]] = 1 / value;
    });
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (i === j) {
                matrix[i][j] = 1;
            } else {
                for (let k = 0; k < len; k++) {
                    if (matrix[i][k] && matrix[k][j]) {
                        matrix[i][j] = matrix[i][k] * matrix[k][j];
                    }
                }
            }
        }
    }
    const res = [];
    queries.forEach(q => {
        const key0 = nameToKey[q[0]];
        const key1 = nameToKey[q[1]];
        // !!!!!! could have chars that not exist in the previous set
        let result;
        if (key0 != undefined && key1 != undefined) {
            result = matrix[key0][key1] ? matrix[key0][key1] : -1;
        } else {
            result = -1;
        }
        res.push(result);
    });
    return res;
};

1002 1. Convert a Number to Hexadecimal

/**
* @param {number} num
* @return {string}
*/
var toHex = function(num) {
    if (num === 0) {return '0'} // !!!! special case for 0 since you didn't include it in your loop
    const bits = '0123456789abcdef';
    let res = '';
    while (num !== 0) {
        const four = num & 0xf;
        res = bits[four] + res;
        num = num >>> 4;
    }
    return res;
};

1002 2.  Best Time to Buy and Sell Stock with Cooldown

/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
    if (prices == null || prices.length === 0) {return 0;}
    const hold = Array(prices.length);
    const sold = Array(prices.length);
    hold[0] = -prices[0];
    sold[0] = 0;
    hold[1] = Math.max(-prices[0], -prices[1]); // !!!! NOt simply hold 0
    sold[1] = Math.max(0, hold[0] + prices[1]);
    for (let i = 2; i < prices.length; i++) {
        sold[i] = Math.max(sold[i - 1], prices[i] + hold[i - 1]);
        hold[i] = Math.max(hold[i - 1], -prices[i] + sold[i - 2]);
    }
    const len = prices.length;
    return sold[len - 1];
};

1003 1. Longest Harmonious Subsequence

/**
* @param {number[]} nums
* @return {number}
*/
var findLHS = function(nums) {
    if (nums == null || nums.length === 0) {return 0;}
    const map = new Map();
    nums.forEach(num => {
        let count = map.has(num) ? map.get(num) + 1 : 1;
        map.set(num, count);
    });
    const keys = [...map.keys()].sort((a, b) => a - b);
    let len = 0;
    for (let i = 1; i < keys.length; i++) {
        if (keys[i] - keys[i - 1] === 1) {
            const sum = map.get(keys[i]) + map.get(keys[i - 1]);
            len = Math.max(len, sum);
        }
    }
    return len;
};

1003 2. Happy Number

/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
    const set = new Set();
    while (true) {
        if (n === 1) {
            return true;
        } else {
            if (set.has(n)) {
                return false;
            } else {
                set.add(n);
                n = next(n);  
            }
        }
    }
   
};


function next (num) {
    let sum = 0;
    while (num !== 0) {
        const val = num % 10;
        sum += val * val;
        num = Math.floor(num / 10);
    }
    return sum;
}

Make up

0809 1. Maximum Sum of 3 Non-Overlapping Subarrays

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSumOfThreeSubarrays = function(nums, k) {
    if (nums == null || nums.length === 0) {return [];}
    const sum = [];
    let localSum = 0;
    // !!!! must do it in o(n)
    for (let i = 0; i < nums.length; i++) {
        localSum += nums[i];
        if (i >= k) {
            localSum -= nums[i - k];
        }
        if (i >= k - 1) {
            sum[i - k + 1] = localSum;
        }
        
    }
    console.log(sum)
    const leftMax = [];
    let maxIndex = 0;
    for (let i = 0; i < sum.length; i++) {
        leftMax[i] = maxIndex = sum[i] > sum[maxIndex] ? i : maxIndex; // !!!!! you will also need to update the current max index !!!
    }
    console.log(leftMax);
    const rightMax = [];
    maxIndex = sum.length - 1;
    for (let i = sum.length - 1; i >= 0; i--) {
        rightMax[i] = maxIndex = sum[i] >= sum[maxIndex] ? i : maxIndex;
    }
    let maxTriple;
    for (let j = k; j + 2 * k - 1 < nums.length; j++) { // !!!!! here using sum and using nums have different meaning because they have different length !!!!!
        const i = leftMax[j - k];
        const m = rightMax[j + k];
        if ((j === k) || (sum[i] + sum[j] + sum[m] > sum[maxTriple[0]] + sum[maxTriple[1]] + sum[maxTriple[2]])) {
            maxTriple = [i, j, m];
        }
    }
    return maxTriple;
};

Make up

0809 2. Subtree of Another Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} s
* @param {TreeNode} t
* @return {boolean}
*/
var isSubtree = function(s, t) {
    if (s == null && t == null) {return true;}
    if (s == null || t == null) {return false;} // !!!! still need to guard even if we guard in the other one
    if (isSameTree(s, t)) {
        return true;
    } else {
        if (isSubtree(s.left, t)) { // !!!!! when you have two recursive functions, be careful don't mix them !!!!!
            return true;
        }
        if (isSubtree(s.right, t)) {
            return true;
        }
        return false;
    }
};

function isSameTree (s, t) {
    if (s == null && t == null) {
        return true;
    } else if (s == null || t == null) {
        return false;
    } else {
        const self = s.val === t.val;
        const left = isSameTree(s.left, t.left);
        const right = isSameTree(s.right, t.right);
        return self && left && right;
    }
}

1004 1. Binary Tree Level Order Traversal II

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
    if (root == null) {return []}
    const queue = [root];   // !!!! shit it is not a stack it is a queue!!!!
    const res = [];
    while (queue.length > 0) {
        const level = [];
        const len = queue.length;
        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left) {queue.push(node.left)}
            if (node.right) {queue.push(node.right)}
        }
        res.push(level);
    }
    return res.reverse();
};

1004 2. Binary Tree Postorder Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
    if (root == null) {return []}
    const res = [];
    const stack = [root];
    let last = {}; // !!!! cannot set it to null cause left/right child could be null!!!!
    while (stack.length > 0) {
        const top = stack[stack.length - 1];
        if (!top.left && !top.right || top.left === last || top.right === last) {
            stack.pop();
            res.push(top.val);
            last = top;
        } else {
            if (top.right) {stack.push(top.right)} // !!!! Note right first !!!
            if (top.left) {stack.push(top.left)}
        }
    }
    return res;
};

Make up.

0810 1. Data Stream as Disjoint Intervals

/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
class SummaryRanges {
    List<Interval> list = new ArrayList<Interval>();

    /** Initialize your data structure here. */
    public SummaryRanges() {
    }
   
    public void addNum(int val) {
        Interval interval = new Interval(val, val);
        int index = 0;
        while (index < this.list.size()) {
            Interval curr = this.list.get(index);
            if (val >= curr.start && val <= curr.end) {
                index = -1;
                break;
            } else if (val == curr.end + 1) {
                curr.end = val;
                if (index + 1 < this.list.size()) {
                    Interval next = this.list.get(index + 1);
                    if (curr.end == next.start - 1) { // !!! still have one shift
                        curr.end = next.end;
                        this.list.remove(index + 1);
                    }
                }
                index = -1;
                break;
            } else if (val == curr.start - 1) {
                curr.start = val;
                index = -1;
                break;
            } else if (val < curr.start - 1) {
                break;
            }
            index++;
        }
        if (index != -1) {
            this.list.add(index, interval);
        }
    }
   
    public List<Interval> getIntervals() {
        return this.list;
    }
}

/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* List<Interval> param_2 = obj.getIntervals();
*/
TODO: This solution is brute force. See better solution using treeSet:
http://bookshadow.com/weblog/201 ... disjoint-intervals/