力扣 430 场周赛-前三题 - JavaScript

力扣 430 场周赛-前三题 - JavaScript

3402. 使每一列严格递增的最少操作次数

解答一

枚举二维数组，时间复杂度$O(n^2)$，空间复杂度$O(1)$

var minimumOperations = function (grid) {
  let reNum = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (i != 0 && grid[i][j] <= grid[i - 1][j]) {
        reNum += grid[i - 1][j] - grid[i][j] + 1
        grid[i][j] = grid[i - 1][j] + 1
      }
    }
  }
  return reNum
}

3403. 从盒子中找出字典序最大的字符串 I

解答一

字典的最大值，也就是基本是长度最长的值，所以我们假设其他分割的字符长度都为 1，字典最大的值的长度为剩余长度，那么我们找这个固定长度的最大值就行了。需要注意的是，如果在结尾处，字典长度小于固定长度的字符串也可能是最大字典值。

时间复杂度$O(n\ast m)$，m 为word.length - (numFriends - 1)，空间复杂度$O(1)$

var answerString = function (word, numFriends) {
  if (numFriends === 1) {
    return word
  }
  let reStr = ''
  let len = word.length - (numFriends - 1)

  for (let i = 0; i < word.length; i++) {
    let temp = ''
    for (let j = 0; j < len; j++) {
      if (word[i + j]) {
        temp += word[i + j]
      }
    }
    if (reStr < temp) {
      reStr = temp
    }
  }
  return reStr
}

3404. 统计特殊子序列的数目

解答一

枚举二维数组寻找所有的nums[p] * nums[r] 和 nums[q] * nums[s]的值，再次枚举寻找符合规则的p、r、q、s的值，时间复杂度$O(n^2\ast U)$，空间复杂度$O(n^2)$，该方法会导致超时。

var numberOfSubsequences = function (nums) {
  let reNum = 0
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      const product = nums[i] * nums[j]
      if (!map.has(product)) {
        map.set(product, [])
      }
      map.get(product).push([i, j])
    }
  }

  map.forEach((pairs) => {
    const n = pairs.length
    if (n > 1) {
      for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
          const [a, b] = pairs[i]
          const [c, d] = pairs[j]
          if (c > a + 1 && c < b - 1 && d > b + 1) {
            reNum++
          }
        }
      }
    }
  })

  return reNum
}

解答二

我们假设四个值是 a、b、c、d，其中 a < b < c < d，按照题目可以转换为$\frac{b}{a}=\frac{c}{d}$，我们可以采用枚举中间值b和c，再枚举左和右的a和d的方式，时间复杂度$O(n^2)$，空间复杂度$O(n^2)$

var numberOfSubsequences = function (nums) {
  const n = nums.length
  let ans = 0
  const cnt = new Map()
  // 枚举 b 和 c
  for (let i = 4; i < n - 2; i++) {
    const b = nums[i - 2]
    // 枚举 a
    for (let j = 0; j < i - 3; j++) {
      const key = nums[j] / b
      cnt.set(key, (cnt.get(key) || 0) + 1)
    }

    const c = nums[i]
    // 枚举 d
    for (let j = i + 2; j < n; j++) {
      ans += cnt.get(nums[j] / c) || 0
    }
  }
  return ans
}