记录

1111 10. Range Sum Query - Immutable

/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
    this.cache = [];
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        this.cache[i] = sum;
    }
};

/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
    return i === 0 ? this.cache[j] : this.cache[j] - this.cache[i - 1];
};

/**
* Your NumArray object will be instantiated and called as such:
* var obj = Object.create(NumArray).createNew(nums)
* var param_1 = obj.sumRange(i,j)
*/

做了10道easy... 纯找感觉。该做几道hard了。

1111 11. Remove Boxes

/**
* @param {number[]} boxes
* @return {number}
*/
var removeBoxes = function(boxes) {
    if (boxes == null || boxes.length === 0) {
        return 0;
    }
    const len = boxes.length;
    // excited!
    const dp = Array(len).fill().map(() => Array(len).fill().map(() => Array(len).fill(0)));
    for (let range = 1; range <= len; range++) {
        for (let i = 0; i + range - 1 < len; i++) {
            const j = i + range - 1;
            const kLimit = i;
            for (let k = 0; k <= kLimit; k++) { // !!! can equal !!!!
                if (i === j) {
                    dp[i][j][k] = (k + 1) * (k + 1);
                } else {
                    // take ith alone
                    const one = (k + 1) * (k + 1) + dp[i + 1][j][0];
                    // combine i with some other el that is same with i after i
                    // first, find all el indeces that is same with i and after i
                    // loop them one by one, take the max
                    let two = 0;
                    for (m = i + 1; m <= j; m++) {
                        if (boxes[m] === boxes[i]) {
                            const mid = m === i + 1 ? 0 : dp[i + 1][m - 1][0];
                            const val = mid + dp[m][j][k + 1];
                            two = Math.max(val, two);
                        }
                    }
                    dp[i][j][k] = Math.max(one, two);
                }
            }
        }
    }
    return dp[0][len - 1][0];
};

Holy shit!
3d dp, might be the first time I encountered this pattern. 爽歪歪。

1112 1. Can Place Flowers

/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function(flowerbed, n) {
    if (n === 0) {return true;}
    if (flowerbed == null || flowerbed.length === 0) {
        return false;
    }
    let count = 0;
    flowerbed.forEach((val, i) => {
        const prev = i === 0 ? true : flowerbed[i - 1] === 0;
        const next = i === flowerbed.length - 1 ? true : flowerbed[i + 1] === 0;
        if (prev && next && val === 0) {
            flowerbed[i] = 1;
            count++;
        }
    });
    return count >= n;
};

没有那么多变化，解是可以固定推出来的，不是一个dp题。

1112 2. Nth Digit

/**
* @param {number} n
* @return {number}
*/
var findNthDigit = function(n) {
    let count = 0;
    let sum = 0;
    let prevSum = 0;
    while (n > sum) {
        // 关键不在do while还是while，而是更新变量的顺序，先更新再visit还是先visit再更新
        count++;
        prevSum = sum;
        sum += 9 * Math.pow(10, count - 1) * count;
    }
    const rem = n - prevSum;
    // 这个错位的技巧需要掌握， 多练
    const countWhole = Math.floor((rem - 1) / count);
    const num = Math.pow(10, count - 1) + countWhole;
    const digit = (rem - 1) % count; // 0123
    const str = String(num)[digit];
    return Number.parseInt(str, 10);
};

蛮多tricky的技巧，这题应当多练

1112 3. Min Stack

/**
* initialize your data structure here.
*/
var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
    // !!!! minStack could be empty at this time !!!!
    let min;
    if (this.minStack.length > 0) {
        min = Math.min(x, this.minStack[this.minStack.length - 1]);
    } else {
        min = x;
    }
    this.stack.push(x);
    this.minStack.push(min);
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {
    this.minStack.pop();
    this.stack.pop();
};

/**
* @return {number}
*/
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
    if (this.minStack.length === 0) {
        return null;
    }
    return this.minStack[this.minStack.length - 1];
};

/**
* Your MinStack object will be instantiated and called as such:
* var obj = Object.create(MinStack).createNew()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/

1112 4.  Heaters

/**
* @param {number[]} houses
* @param {number[]} heaters
* @return {number}
*/
var findRadius = function(houses, heaters) {
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    let i = 0;
    let res = 0;
    for (let house of houses) {
        while (i < heaters.length && heaters + heaters[i + 1] <= house * 2) {
            i++;
        }
        res = Math.max(res, Math.abs(heaters[i] - house));
    }
    return res;
};

这个解法好叼。膜拜 ！
http://starllap.space/2017/02/12/Leetcode-475-Heaters/[/i]
不过优化的话会不会有牛逼的数据结构？这题看起来有点像range sum query一类的。以后研究一下。

1112 5. Reverse Bits

/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
var reverseBits = function(n) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        const bit = n & 1;
        res = (res << 1) + bit;
        n = n >>> 1;
    }
    return (res >>> 0); // !!! Well.... its javascript.... no unsigned int. If we want to read it as unsigned, we do >>>
};

Follow up 怎么解？
https://segmentfault.com/a/1190000003483740
研究下这个解法。

1112 6. Shortest Unsorted Continuous Subarray

/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let max = nums[0];
    let end = 0;
    for (let i = 0; i < nums.length; i++) {
        max = Math.max(max, nums[i]);
        if (max > nums[i]) {
            end = i;
        }
    }
    // !!!! note your original idea is incorrect because you also need to consider the reverse direction.
    let len = nums.length;
    let min = nums[len - 1];
    let start = len - 1;
    for (let i = len - 1; i >= 0; i--) {
        min = Math.min(min, nums[i]);
        if (min < nums[i]) {
            start = i;
        }
    }
    return start < end ? end - start + 1 : 0; // !!! no equal, when only a single element, no need for sorting
};

1112 7.  Implement strStr()

/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
    // check
    // !!!!! naive解法还需要一个优化才能过：当长度不够needle长度就停止搜索。
    if (needle.length === 0) {return 0;}
    const len = needle.length;
    for (let i = 0; i + len - 1 < haystack.length; i++) {
        if (haystack[i] === needle[0]) {
            let valid = true;
            for (let j = 0; j < len; j++) {
                if (needle[j] !== haystack[i + j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {return i;}
        }
    }
    return -1;
};