记录

0918 2.  2 Keys Keyboard

/**
* @param {number} n
* @return {number}
*/
var minSteps = function(n) {
    if (n === 1) {return 0;}
    let min = n;
    for (let i = n - 1; i > 1; i--) {
        if (n % i === 0) {
            min = Math.min(minSteps(i) + minSteps(n / i), min)
        }
    }
    return min;
};

0919 1. Random Pick Index

class Solution {
    int[] nums;

    public Solution(int[] nums) {
        this.nums = nums;
    }
   
    public int pick(int target) {
        int count = 0;
        int index = 0;
        for (int i = 0; i < this.nums.length; i++) {
            int num = this.nums[i];
            if (num == target) {
                count++;
                int random = (int) (Math.random() * count);
                if (random == 0) {
                    index = i;
                }
            }
        }
        return index;
    }
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/

0919 2. Burst Balloons

/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function(nums) {
    const len = nums.length;
    nums = [1, ...nums, 1];
    const dp = Array(len + 2).fill().map(() => Array(len + 2).fill(0));
    for (let range = 1; range <= len; range++) {
        for (let i = 1; i + range - 1 <= len; i++) {
            let j = i + range - 1;
            if (range === 1) {
                dp[i][j] = nums[i] * nums[i - 1] * nums[i + 1];
            } else {
                for (let k = i; k <= j; k++) {
                    const value = nums[k] * nums[i - 1] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j];
                    dp[i][j] = Math.max(dp[i][j], value);
                }
            }
        }
    }
    return dp[1][len];
};

0920 1.  Second Minimum Node In a Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findSecondMinimumValue = function(root) {
    if (root == null) {return -1;}
    let second = Number.POSITIVE_INFINITY;
    recurse(root);
    return second === Number.POSITIVE_INFINITY ? -1 : second;
   
    function recurse (node) {
        if (node == null) {
            return;
        }
        if (node.val > root.val) {
            second = Math.min(second, node.val);
        }
        recurse(node.left);
        recurse(node.right);
    }
};

0920 2. Shopping Offers

/**
* @param {number[]} price
* @param {number[][]} special
* @param {number[]} needs
* @return {number}
*/
var shoppingOffers = function(price, special, needs) {
    let wePay = 0;
    for (let i = 0; i < needs.length; i++) {
        wePay += needs[i] * price[i];
    }
    const savings = special.map(specialSet => {
        // const [...nums, specialPrice] = specialSet;  // Rest must be the last in an array
        const nums = specialSet.slice(0, specialSet.length - 1);
        const specialPrice = specialSet[specialSet.length - 1];
        let originalPrice = 0;
        for (let i = 0; i < nums.length; i++) {
            originalPrice += nums[i] * price[i];
        }
        return originalPrice - specialPrice;
    });
    recurse(wePay, 0);
    return wePay;
   
   
    function recurse (pay, i) {
        for (let j = i; j < special.length; j++) {
            const aSpecial = special[j];
            const good = needs.every((need, index) => need >= aSpecial[index]);
            if (good) {
                for (let k = 0; k < needs.length; k++) {
                    needs[k] = needs[k] - aSpecial[k];
                }
                pay = pay - savings[j];
                wePay = Math.min(pay, wePay);
                recurse(pay, i);
                pay = pay + savings[j];
                for (let k = 0; k < needs.length; k++) {
                    needs[k] = needs[k] + aSpecial[k];
                }
            }
        }
    }
};

sicilianee 发表于 2017-9-24 02:52
0920 2. Shopping Offers

/**

// I saw people using the needs list as key to memorize, maybe you could turn it into dp?

Using the function itself to recurse. With this needs, return the min price you will pay. Other input won't change.

0921 1.  Longest Word in Dictionary through Deleting

/**
* @param {string} s
* @param {string[]} d
* @return {string}
*/
var findLongestWord = function(s, d) {
    let word = ''
    d.forEach(aWord => {
        if (validate(s, aWord)) {
            if (aWord.length > word.length || (aWord.length === word.length && aWord < word)) {
                word = aWord;
            }
        }
    });
    return word;
};

function validate (str, word) {
    let i = 0;
    let j = 0;
    while (i < word.length && j < str.length) {
        if (word[i] === str[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    return i === word.length
}

sicilianee 发表于 2017-9-24 03:17
0921 1.  Longest Word in Dictionary through Deleting

/**

Only one pointer i is enough. No need for maintaining j in a while loop fashion since j always increase 1.
Just loop chars of the str and update i in the word.

0921 2. Bulb Switcher

/**
* @param {number} n
* @return {number}
*/
var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n));
};

0922 1. Longest Palindromic Subsequence

/**
* @param {string} s
* @return {number}
*/
var longestPalindromeSubseq = function(s) {
    const len = s.length;
    const dp = Array(len).fill().map(() => Array(len).fill(0));
    for (let step = 1; step <= len; step++) {
        for (let i = 0; i + step - 1 < len; i++) {
            let j = i + step - 1;
            if (step === 1) {
                dp[i][j] = 1;
                continue; // !!!! You either continue or put others in an else statement
            }
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][len - 1];
};