力扣第 387 場周賽解題報告 | 珂學家 | 離散化樹狀數組 + 模擬場

前言

整體評價

手速場+模擬場，思路和解法都蠻直接的。

所以搞點活

如果T2，如果不固定左上角，批量查詢某個點為左上角，求滿足總和 $\le k$ 的子矩陣個數
如果T2，如果不固定左上角，求總和 $\le k$ 的子矩陣個數
如果T3, 數值不局限于0,1,2, 求最小操作數

A. 將元素分配到兩個數組中 I

思路: 模擬

模擬即可，沒啥可說的。

class Solution {public int[] resultArray(int[] nums) {List<Integer> r1 = new ArrayList<>(List.of(nums[0]));List<Integer> r2 = new ArrayList<>(List.of(nums[1]));for (int i = 2; i < nums.length; i++) {if (r1.get(r1.size() - 1) > r2.get(r2.size() - 1)) {r1.add(nums[i]);} else {r2.add(nums[i]);}}r1.addAll(r2);return r1.stream().mapToInt(Integer::valueOf).toArray();}
}

B. 元素和小于等于 k 的子矩陣的數目

思路: 二維前綴和 + 枚舉

因為固定左上角，所以子矩陣的個數為 $n ? m$

前綴和預處理, $O (n ? m)$

枚舉子矩陣為, $O (n ? m)$

class Solution {public int countSubmatrices(int[][] grid, int k) {int h = grid.length, w = grid[0].length;long[][] pre = new long[h + 1][w + 1];for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + grid[i][j];}}int res = 0;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (pre[i + 1][j + 1] <= k) {res ++;}}}return res;}
}

思考:

如果左上角并不固定，而且以任意點出發，求滿足要求的子矩陣數？而且這個查詢量不小？

那面對這個問題，該如何求解呢?

感覺一次查詢，可以從 $O (n ? m) 優化為 O (n + m)$ ，就是從右上點出發，逐漸收斂到左下。

C. 在矩陣上寫出字母 Y 所需的最少操作次數

思路: 模擬 + 枚舉組合

唯一可以增加難度的是，不限定數值范圍

不過這也才基本的nlargest問題

class Solution {boolean isJudge(int y, int x, int n) {if (y == x && y <= n / 2) {return true;}if (y + x == n - 1 && y <= n / 2) {return true;}if (y >= n / 2 && x == n / 2) {return true;}return false;}public int minimumOperationsToWriteY(int[][] grid) {int n = grid.length;int[] ys = new int[3];int[] nys = new int[3];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int id = grid[i][j];if (isJudge(i, j, n)) {ys[id]++;} else {nys[id]++;}}}// 枚舉即可int res = n * n;int totYs = n/2 + n/2 + n/2 + 1;int totNys = n * n - totYs;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (i != j) {res = Math.min(res, (totYs - ys[i]) + (totNys - nys[j]));}}}return res;}}

D. 將元素分配到兩個數組中 II

思路：離散化 + 樹狀數組

板子題，而且非常的直接

class Solution {static class BIT {int n;int[] arr;public BIT(int n) {this.n =n;this.arr = new int[n + 1];}int query(int p) {int res = 0;while (p > 0) {res += arr[p];p -= p & -p;}return res;}void update(int p, int d) {while (p <= n) {arr[p] += d;p += p & -p;}}}public int[] resultArray(int[] nums) {List<Integer> arr1 = new ArrayList<>(List.of(nums[0]));List<Integer> arr2 = new ArrayList<>(List.of(nums[1]));// 離散化過程TreeSet<Integer> ts = new TreeSet<>();for (int v: nums) ts.add(v);int ptr = 1;Map<Integer, Integer> idMap = new HashMap<>();for (var k: ts) {idMap.put(k, ptr++);}// 樹狀數組模擬過程BIT bit1 = new BIT(ptr);BIT bit2 = new BIT(ptr);bit1.update(idMap.get(nums[0]), 1);bit2.update(idMap.get(nums[1]), 1);for (int i = 2; i < nums.length; i++) {int v = nums[i];Integer k = idMap.get(v);int cnt1 = bit1.query(ptr) - bit1.query(k);int cnt2 = bit2.query(ptr) - bit2.query(k);if (cnt1 > cnt2 || (cnt1 == cnt2 && arr2.size() >= arr1.size())) {arr1.add(v);bit1.update(k, 1);} else {arr2.add(v);bit2.update(k, 1);} }arr1.addAll(arr2);return arr1.stream().mapToInt(Integer::valueOf).toArray();}
}