记录

0607 2. Jump Game II

TLE:

/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
  const dp = nums.map(() => 0)
  for (let i = nums.length - 2; i >= 0; i--) {
    const num = nums[i]
    const j = i + num
    let min = Infinity
    for (let index = i + 1; index <= Math.min(j, nums.length - 1); index++) { // !!! cannot exceed length - 1
      min = Math.min(min, dp[index])
    }
    dp[i] = min + 1
  }
  return dp[0]
};

console.log(jump([2,3,1,1,4]) === 2)

sicilianee 发表于 2018-6-8 12:07
0607 2. Jump Game II

TLE:

/**
* @param {number[]} nums
* @return {number}
*/
var jump = function(nums) {
  if (nums.length < 2) { // !!! only one el case
    return 0
  }
  let step = 1
  let i = 0
  let j = nums[0]
  while (true) {
    if (j >= nums.length - 1) { // !!! the last one is length - 1, not length
      return step
    }
    let maxReach = j
    for (let k = i + 1; k <= j; k++) {
      const reach = k + nums[k]
      maxReach = Math.max(reach, maxReach)
    }
    i = j
    j = maxReach
    step++
  }
};

0607 3. Palindrome Partitioning II

1. counter example for greedy:

9876543212345678909876543211234

2. TLE:

/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
  const len = s.length
  const map = new Map()
  return find(0)

  // from i to end, inclusive, the min cut
  function find (i) {
    if (map.has(i)) {
      return map.get(i)
    }
    if (isPalindrome(s.slice(i))) {
      return 0
    }
    let cut = Infinity
    for (let j = i; j < len; j++) {
      // take from i till j
      if (isPalindrome(s.slice(i, j + 1))) {
        // take the first half, query the second half, combine the number
        cut = Math.min(cut, 1 + find(j + 1))
      }
    }
    map.set(i, cut)
    return cut
  }
};

function isPalindrome (str) {
  return str === [...str].reverse().join('')
}

console.log(minCut('aab') === 1)

sicilianee 发表于 2018-6-8 13:32
0607 3. Palindrome Partitioning II

1. counter example for greedy:

Same approach converted to DP, still TLE

/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
  // let's try a dp solution
  const len = s.length
  const dp = Array(len + 1).fill(Infinity)
  dp[len] = -1
  dp[len - 1] = 0
  for (let i = len - 2; i >= 0; i--) {
    for (let j = i; j < len; j++) { // !!! start from i, not i + 1
      const str = s.slice(i, j + 1)
      if (isPalindrome(str)) {
        const curr = 1 + dp[j + 1]
        dp[i] = Math.min(curr, dp[i])
      }
    }
  }
  return dp[0]
};

function isPalindrome (str) {
  return str === [...str].reverse().join('')
}

console.log(minCut('aab') === 1)
console.log(minCut('ab') === 1)

sicilianee 发表于 2018-6-9 09:56
Same approach converted to DP, still TLE

/**

AC



/**
* @param {string} s
* @return {number}
*/
var minCut = function(s) {
  // let's first build the palindrome table then work on the problem
  const len = s.length
  const table = Array(len).fill()
    .map(() => Array(len).fill(false))
  for (let i = 0; i < len; i++) {
    table[i][i] = true
  }
  for (let step = 2; step <= len; step++) {
    for (let i = 0; i + step - 1 < len; i++) {
      const j = i + step - 1
      if (s[i] === s[j] &&
        ( i + 1 > j - 1 || table[i + 1][j - 1])
      ) {
        table[i][j] = true
      }
    }
  }
  // now we have the table
  const dp = Array(len + 1).fill(Infinity)
  dp[len] = -1
  dp[len - 1] = 0
  for (let i = len - 2; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (table[i][j]) {
        dp[i] = Math.min(dp[i], 1 + dp[j + 1])
      }
    }
  }
  return dp[0]
};

function isPalindrome (str) {
  return str === [...str].reverse().join('')
}

console.log(minCut('aab') === 1)
console.log(minCut('ab') === 1)

sicilianee 发表于 2018-6-9 10:18
AC

The problem self we use dp to solve.
The palindrome check in each iteration has unnecessary repetition so we can use dp to build a table to resolve that.

sicilianee 发表于 2018-6-9 10:20
The problem self we use dp to solve.
The palindrome check in each iteration has unnecessary repet ...

They have a very smart and delicate dp solution which, only takes O(n) space. They don't need the palindrome check.

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }
};

sicilianee 发表于 2018-6-9 11:11
They have a very smart and delicate dp solution which, only takes O(n) space. They don't need the  ...

Very delicate and smart dp dependency handling. Ensured whatever used is already calculated.

0609 1. Maximum Average Subarray II

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
    // !!! READ the NOTES and CONSTRAINTS carefully. They might convey very important information
    // They might make the problem completely different.
    // like this problem, they don't need an exact answer, could be approximation with error,
    // it is then a completely different problem then.
    // 这题如果不是近似，则二分法复杂度就不是logn了。一般的exact二分法都会限制变量为整数，这样二分法仍是logn

    // setup left, right, error, prev val
    // while error, start loop, get mid as val, check with error, return if good
    // check mid big or small, set up new left right
    let left = Math.min(...nums)
    let right = Math.max(...nums)
    let prev = right
    while (true) {
      const mid = left + (right - left) / 2
      if (Math.abs(mid - prev) < 0.00001) {
        return mid
      }
      //
      if (canReach(nums, mid, k)) {
        // can go bigger
        left = mid
      } else {
        // shall go smaller
        right = mid
      }
      prev = mid // !!! f*** this is important
    }
    return undefined
};

// can at least k nums from nums reach avg?
function canReach (nums, avg, k) {
  nums = nums.map(num => num - avg)
  let sum = 0, preSum = 0, preMin = 0
  for (let i = 0; i < k; i++) {
    sum += nums[i]
  }
  if (sum >= 0) {
    return true
  }
  for (let i = k; i < nums.length; i++) {
    sum += nums[i]
    preSum += nums[i - k]
    preMin = Math.min(preSum, preMin)
    if (sum >= preMin) {
      return true
    }
  }
}

console.log(findMaxAverage([1,12,-5,-6,50,3], 4))

sicilianee 发表于 2018-6-10 07:03
0609 1. Maximum Average Subarray II

/**

Key is:

1. read the requirement, they allow error, not exact, consider binary search
2. how to determine if k els from an array can reach avg? Key is as element added one by one, subtract the avg one by one. That transformed to a subtracted by avg array, and to the accumulative array of the subtracted array.