记录

1009 1.  Kth Largest Element in an Array

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
    if (nums == null || nums.length === 0) {throw new Error('Invalid input')}
    return quickSelect(0, nums.length - 1, k);


    function quickSelect (low, high, k) {
        let i = low;
        let j = high - 1;
        let pivot = nums[high];
        while (i <= j) {
            if (nums > pivot) {
                // ;[nums[i], nums[j]] = [nums[j], nums[i]];
                swap(nums, i, j);
                j--;
            } else {
                i++;
            }
        }
        // ;[nums[i], nums[high]] = [nums[high], nums[i]];
        swap(nums, i, high)
        const countBiggerThanPivot = high - i;
        const pivotRank = countBiggerThanPivot + 1;
        if (pivotRank === k) {
            return pivot;
        } else if (k > pivotRank) {
            return quickSelect(low, i - 1, k - pivotRank);
        } else {
            return quickSelect(i + 1, high, k);
        }
    }

};


function swap (nums, i, j) {
    const tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

It seems that leetcode server doesn't handle array destructuring swap very well. Report runtime error that is unable to catch.
Don't know why. It worked on my nodejs environment. [/i][/i][/i][/i][/i][/i][i][i][i][i][i][i]It failed for big dataset: 5000 deep call stack. So I guess it is some kind of bug that appears in this stress test. [/i][/i][/i][/i][/i][/i]
[i][i][i][i][/i][/i][/i][/i]
[i][i][i][i][i][i]Anyway, in this specific situation, sorted, and want the first element in the array, it is not very efficient. So I think a better way is to randomly pick the pivot. [/i][/i][/i][/i][/i][/i]

sicilianee 发表于 2017-10-11 13:24
1009 1.  Kth Largest Element in an Array

/**

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
    if (nums == null || nums.length === 0) {throw new Error('Invalid input')}
    return quickSelect(0, nums.length - 1, k);


    function quickSelect (low, high, k) {
        let i = low;
        let j = high - 1;
        const pivotIndex = Math.floor(Math.random() * (high - low + 1) + low);
        // swap(nums, pivotIndex, high);
        ;[nums[pivotIndex], nums[high]] = [nums[high], nums[pivotIndex]];
        let pivot = nums[high];
        while (i <= j) {
            if (nums[i] > pivot) {
                ;[nums[i], nums[j]] = [nums[j], nums[i]];
                j--;
            } else {
                i++;
            }
        }
        ;[nums[i], nums[high]] = [nums[high], nums[i]];
        const countBiggerThanPivot = high - i;
        const pivotRank = countBiggerThanPivot + 1;
        if (pivotRank === k) {
            return pivot;
        } else if (k > pivotRank) {
            return quickSelect(low, i - 1, k - pivotRank);
        } else {
            return quickSelect(i + 1, high, k);
        }
    }

};


Tried and it worked!

1009 2. Remove Element

/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums === val) {
            count++;
        } else {
            nums[i - count] = nums[i];
        }
    }
    return nums.length - count;
};[/i]
[i]See another solution:[/i]
[i]http://www.cnblogs.com/grandyang/p/4606700.html[/i]

1010 1. Combination Sum

/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
    if (candidates == null || candidates.length === 0) {
        return [];
    }
    const res = [];
    const list = [];
    recurse(0, 0);
    return res;
   
    function recurse (i, sum) {
        if (sum === target) {
            res.push([...list]);
            return;
        }
        if (sum > target) {
            return;
        }
        for (let j = i; j < candidates.length; j++) {
            list.push(candidates[j]);
            recurse(j, sum + candidates[j]);
            list.pop();
        }
    }
};

1010 2. Rotate Image

/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
    if (matrix == null || matrix.length === 0) {
        return matrix;
    }
    const len = matrix.length;
    const limit = Math.floor(len / 2);
    for (let step = 0; step < limit; step++) {
        for (let i = step; i < len - step - 1; i++) { // !!!! no need for the last one, it has been visited cause it is the first one of the next list
            const first = matrix[step][i];
            matrix[step][i] = matrix[len - 1 - i][step];
            matrix[len - 1 - i][step] = matrix[len - 1 - step][len - 1 - i];
            matrix[len - 1 - step][len - 1 - i] = matrix[i][len - 1 - step];
            matrix[i][len - 1 - step] = first;
        }
    }
};

1011 1. Insert Delete GetRandom O(1)

/**
* Initialize your data structure here.
*/
var RandomizedSet = function() {
    this.list = [];
    this.map = new Map(); // num -> index
};

/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
    if (this.map.has(val)) {
        return false;
    } else {
        this.list.push(val);
        this.map.set(val, this.list.length - 1);
        return true;
    }
};

/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
    if (this.map.has(val)) {
        const lastIndex = this.list.length - 1;
        const valIndex = this.map.get(val);
        const lastVal = this.list[lastIndex];
        ;[this.list[lastIndex], this.list[valIndex]] = [this.list[valIndex], this.list[lastIndex]];
        this.map.set(val, lastIndex);
        this.map.set(lastVal, valIndex);
        this.map.delete(val);
        this.list.pop();
        return true;
    } else {
        return false;
    }
};

/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
    const randomIndex = Math.floor(Math.random() * this.list.length);
    return this.list[randomIndex];
};

/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = Object.create(RandomizedSet).createNew()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/

1011 2. Freedom Trail

/**
* @param {string} ring
* @param {string} key
* @return {number}
*/
var findRotateSteps = function(ring, key) {
    if (ring == null || key == null) {return 0}
    const ringLen = ring.length;
    const keyLen = key.length;
    const dp = Array(keyLen + 1).fill().map(() => Array(ringLen).fill(0));
    for (let keyIndex = keyLen - 1; keyIndex >= 0; keyIndex--) {
        for (let ringIndex = 0; ringIndex < ringLen; ringIndex++) {
            dp[keyIndex][ringIndex] = Number.MAX_VALUE;
            for (let nextRingIndex = 0; nextRingIndex < ringLen; nextRingIndex++) {
                if (ring[nextRingIndex] === key[keyIndex]) { // !!!!!! it really happens, use = as comparision
                    const step = Math.abs(nextRingIndex - ringIndex);
                    const minStep = Math.min(step, ringLen - step);
                    dp[keyIndex][ringIndex] = Math.min(dp[keyIndex][ringIndex], dp[keyIndex + 1][nextRingIndex] + minStep);
                }
            }
        }
    }
    return dp[0][0] + keyLen; // !!!! plus the press times
};

难难难

1012 1. Partition Equal Subset Sum

/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
    if (nums == null || nums.length < 2) {
        return false;
    }
    const sum = nums.reduce((a, b) => a + b);
    if (sum % 2 !== 0) {return false}
    const target = sum / 2;
    const dp = Array(target + 1).fill(false); // !!!! undefined is not false
    dp[0] = true;
    for (let num of nums) {
        for (let i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
};

This one is different form other dp problems you have seen in that:
They put numbers in the set one by one. So when you use dp[i], dp[i] doesn't need to be calculated already. For each number you put into the set, you will update all possible dp[i]'s that  might be impacted. This is like react set state, every time you change some state, you update all possible components that might change.

In traditional dp problems, you build dp[i] on dp[i-1] where dp[i-1] has already been calculated.

sicilianee 发表于 2017-10-13 14:59
1012 1. Partition Equal Subset Sum

/**

There is a solution directly using the knapsack problem pattern:
http://blog.csdn.net/liuyue910828/article/details/52792357
Easier to understand

1012 2. House Robber

/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
    if (nums == null || nums.length === 0) {return 0;}
    const dp = Array(nums.length);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    return dp[nums.length - 1];
};