记录

sicilianee 发表于 2017-11-15 11:58
Previous dates are wrong

1114 1. Populating Next Right Pointers in Each Node II

好题。思考

1114 2. Largest Divisible Subset

/**
* @param {number[]} nums
* @return {number[]}
*/
var largestDivisibleSubset = function(nums) {
    if (nums == null || nums.length === 0) {
        return [];
    }
    nums.sort((a, b) => a - b);
    const len = nums.length;
    const dp = Array(len).fill(1);
    const froms = Array(len).fill(-1);
    let maxLen = 1;
    let maxIndex = 0;
    for (let i = 0; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) { // !!! if we have only one element, this won't even execute. so maxLen and maxIndex
            // should consider that and start with the first one
            if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                froms[i] = j;
                if (dp[i] > maxLen) {
                    maxLen = dp[i];
                    maxIndex = i;
                }
            }
        }
    }
    // backtrack
    console.log(maxLen)
    console.log(maxIndex)
    const res = [];
    for (let i = maxIndex; i != -1; i = froms[i]) {
        res.push(nums[i]);
    }
    return res;
};

1114 2. Largest Divisible Subset

/**
* @param {number[]} nums
* @return {number[]}
*/
var largestDivisibleSubset = function(nums) {
    if (nums == null || nums.length === 0) {
        return [];
    }
    nums.sort((a, b) => a - b);
    const len = nums.length;
    const dp = Array(len).fill(1);
    const froms = Array(len).fill(-1);
    let maxLen = 1;
    let maxIndex = 0;
    for (let i = 0; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) { // !!! if we have only one element, this won't even execute. so maxLen and maxIndex
            // should consider that and start with the first one
            if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                froms[i] = j;
                if (dp[i] > maxLen) {
                    maxLen = dp[i];
                    maxIndex = i;
                }
            }
        }
    }
    // backtrack
    console.log(maxLen)
    console.log(maxIndex)
    const res = [];
    for (let i = maxIndex; i != -1; i = froms[i]) {
        res.push(nums[i]);
    }
    return res;
};

sicilianee 发表于 2017-11-15 12:32
1114 2. Largest Divisible Subset

/**

关键是每次找下一个只用找刚刚找到的最大的，因为一个set里面，能够整除最大的， 其他比他小的你也一定能够整除，有传递性。这就给用dp解题创造了条件。

1114 3. Unique Paths II

/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length === 0 || obstacleGrid[0].length === 0) {
        return 0;
    }
    const rowLen = obstacleGrid.length;
    const colLen = obstacleGrid[0].length;
    const dp = Array(rowLen).fill().map(() => Array(colLen).fill(0));
    dp[0][0] = obstacleGrid[0][0] === 1 ? 0 : 1; // !!!! what if the first one is obstacle ???
    const moves = [[-1, 0], [0, -1]]
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (obstacleGrid[i][j] !== 1) {
                for (let move of moves) {
                    // get prev index
                    const x = i + move[0];  // !!!! it is move, not moves, again variable mix
                    const y = j + move[1];
                    if (x >= 0 && x < rowLen && y >= 0 && y < colLen) {
                        dp[i][j] += dp[x][y]
                    }
                }  
            }

        }
    }
    return dp[rowLen - 1][colLen - 1];
};

1114 4. Unique Binary Search Trees II

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
    if (n < 1) {return []}
    return recurse(1, n);
   
    function recurse (start, end) {
        if (start > end) { // !!!! not the first time, you need to provide the reverse condition !!!
            return [null];
        }
        const res = [];
        for (let i = start; i <= end; i++) {
            const leftArr = recurse(start, i - 1);
            const rightArr = recurse(i + 1, end);
            for (let leftNode of leftArr) {
                for (let rightNode of rightArr) {
                    const self = new TreeNode(i);
                    self.left = leftNode;
                    self.right = rightNode;
                    res.push(self);
                }
            }
        }
        return res;
    }
   
};

1114 5.  Longest Uncommon Subsequence II

/**
* @param {string[]} strs
* @return {number}
*/
var findLUSlength = function(strs) {
    // 这题的关键在于知道， 答案肯定是strs中间的一个串，不会是某一个串的字串。
    // 因为可以反证法，如果一个串的子串不是别人的子串， 而这个串是某个的字串，是会推出矛盾的：一个串是别人的字串，那他的
    // 所有子串都是别人的子串。
    strs.sort((a, b) => b.length - a.length);
    for (let i = 0; i < strs.length; i++) {
        const str = strs[i];
        let good = true;
        for (let j = 0; j < strs.length; j++) {
            if (i !== j) {
                const aStr = strs[j];
                if (check(str, aStr)) {
                    good = false;
                    break;
                }
            }
        }
        if (good) {
            return str.length;
        }
    }
    return -1;
   
    function check (str, aStr) {
        console.log(str, aStr)
        let i = 0;
        let j = 0;
        while (i < str.length && j < aStr.length) {
            if (str[i] === aStr[j]) { // !!!! aStr, you write str, variable mix, again !!!! how to avoid this !!! ?
                i++;
                j++;
            } else {
                j++;
            }
        }
        console.log(i, j)
        console.log(i === str.length)
        return i === str.length;
    }
   
};

1114 6. Search for a Range

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
    if (nums == null || nums.length === 0) {
        return [-1, -1];
    }
    // binary search start
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (target <= nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    const start = left;
    if (nums[left] !== target) {return [-1, -1];}
    // binary search end
    left = start;
    right = nums.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (target < nums[mid]) {
            right = mid - 1;
        } else { // 实际上不可能大于了， 就是等于
            left = mid + 1;
        }
    }
    return [start, right];
   
};

1114 7. Minimum Size Subarray Sum

/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
    if (nums == null || nums.length === 0) {return 0;}
    let left = -1;
    let right = -1
    let sum = 0;
    let min = Infinity;
    while (right < nums.length && left < nums.length) {
        if (sum >= s) {
            const len = right - left;
            min = Math.min(len, min);
            left++;
            sum -= nums[left];
        } else {
            right++;
            sum += nums[right];
        }
    }
    return min === Infinity ? 0 : min;
};
// follow up 没看

1114 8. 3Sum Closest

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
    if (nums == null || nums.length < 3) {
        throw new Error();
    }
    nums.sort((a, b) => a - b);
    let sum = nums[0] + nums[1] + nums[2];
    let diff = Math.abs(sum - target);
    for (let i = 0; i + 2 < nums.length; i++) {
        const val = nums[i];
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            const newSum = val + nums[left] + nums[right];
            const newDiff = Math.abs(newSum - target);
            if (newDiff < diff) {
                diff = newDiff;
                sum = newSum;
            }
            if (newSum > target) {
                right--;
            } else if (newSum < target) {
                left++;
            } else {
                return newSum;
            }
        }
    }
    return sum;
};