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

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

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

解答一

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

var minimumOperations = function (grid) {let reNum = 0for (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] + 1grid[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 = 0const 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.lengthif (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.lengthlet ans = 0const cnt = new Map()// 枚举 b 和 cfor (let i = 4; i < n - 2; i++) {const b = nums[i - 2]// 枚举 afor (let j = 0; j < i - 3; j++) {const key = nums[j] / bcnt.set(key, (cnt.get(key) || 0) + 1)}const c = nums[i]// 枚举 dfor (let j = i + 2; j < n; j++) {ans += cnt.get(nums[j] / c) || 0}}return ans
}