二分查找(对数运算 + 前缀和),滑动窗口:求解《713. 乘积小于 K 的子数组》

2022-05-05 11:58:19

根据对数运算性质将相乘转为求和问题,用前缀和优化。二分查找,滑动窗口,求解《713. 乘积小于 K 的子数组》

对数的运算性质、换底公式和底数与真数互换

对数运算性质 · 相乘

自然对数

以 e 为底的对数

Math.log(x)
func Log(a float64) float64

例题

713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

答案

二分查找

自然对数:相乘 转 求和

var numSubarrayProductLessThanK = function(nums, k) {
  const n = nums.length, sums = new Array(n + 1), target = Math.log(k)
  sums[0] = 0
  let ans = 0
  for (let i = 0; i < n; i++) sums[i + 1] = sums[i] + Math.log(nums[i])
  for (let j = n; j--;) {
    let l = 0, r = j
    while (l <= r) {
      const m = l + r >>> 1
      const sum = sums[j + 1] - sums[m] + 1e-10
      if (sum > target) l = m + 1
      else r = m - 1
    }
    ans += j - l + 1
  }
  return ans
};
func numSubarrayProductLessThanK(nums []int, k int) int {
  n, ans, target := len(nums), 0, math.Log(float64(k))
  sums := make([]float64, n + 1)
  for i := 0; i < n; i++ {
    sums[i + 1] = sums[i] + math.Log(float64(nums[i]))
  }
  for j := n - 1; j >= 0; j-- {
    l, r := 0, j
    for l <= r {
      m := (l + r) >> 1
      sum := sums[j + 1] - sums[m] + 1e-11
      if sum > target {
        l = m + 1
      } else {
        r = m - 1
      }
    }
    ans += j - l + 1
  }
  return ans
}
class Solution {
  function numSubarrayProductLessThanK($nums, $k) {
    $n = count($nums);
    $sums = array_fill(0, $n + 1, 0);
    $target = log($k);
    $ans = 0;
    foreach ($nums as $i => $num) {
      $sums[$i + 1] = $sums[$i] + log($nums[$i]);
    }
    for ($j = $n; $j--;) {
      $l = 0;
      $r = $j;
      while ($l <= $r) {
        $m = $l + $r >> 1;
        $sum = $sums[$j + 1] - $sums[$m] + 1e-10;
        if ($sum > $target) $l = $m + 1;
        else $r = $m - 1;
      }
      $ans += $j - $l + 1;
    }
    return $ans;
  }
}

滑动窗口

var numSubarrayProductLessThanK = function(nums, k) {
  const n = nums.length
  let ans = 0
  for (let j = i = 0, prodcut = 1; j < n; j++) {
    prodcut *= nums[j]
    while (i <= j && prodcut >= k) {
      prodcut /= nums[i]
      i++
    }
    ans += j - i + 1
  }
  return ans
};
func numSubarrayProductLessThanK(nums []int, k int) int {
  product, ans, i := 1, 0, 0
  for j, num := range nums {
    product *= num
    for i <= j && product >= k {
      product /= nums[i]
      i++
    }
    ans += j - i + 1
  }
  return ans
}
class Solution {
  function numSubarrayProductLessThanK($nums, $k) {
    $n = count($nums);
    $product = 1;
    $ans = 0;
    for ($j = $i = 0; $j < $n; $j++) {
      $product *= $nums[$j];
      while ($i <= $j && $product >= $k) {
        $product /= $nums[$i];
        $i++;
      }
      $ans += $j - $i + 1;
    }
    return $ans;
  }
}

代码
5 种方法交换变量,用绝对值和求模标记,用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法:求解《442. 数组中重复的数据》
利用 5 种方法交换变量,用绝对值和求模标记,用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法求解《442. 数组中重复的数据》
代码
双指针合并有序数组:求解《88. 合并两个有序数组》和《面试题 10.01. 合并排序的数组》
双指针合并有序数组(合并数组),注意数组越界不同语言的处理方式。求解《88. 合并两个有序数组》和《面试题 10.01. 合并排序的数组》
代码
二维数组自定义函数排序 + 栈:按二维数组自定义函数升序排序,使用栈合并区间,求解《56. 合并区间》和《剑指 Offer II 074. 合并区间》
按二维数组自定义函数升序排序,使用栈合并区间,求解《56. 合并区间》和《剑指 Offer II 074. 合并区间》