如何建立自己的商城网站,wordpress 时间选择器,杭州信用网官网,html登录注册页面模板前言 整体评价
手速场模拟场#xff0c;思路和解法都蛮直接的。
所以搞点活 如果T2#xff0c;如果不固定左上角#xff0c;批量查询某个点为左上角#xff0c;求满足总和 ≤ k \le k ≤k的子矩阵个数 如果T2#xff0c;如果不固定左上角#xff0c;求总和 ≤ k \le k…
前言 整体评价
手速场模拟场思路和解法都蛮直接的。
所以搞点活 如果T2如果不固定左上角批量查询某个点为左上角求满足总和 ≤ k \le k ≤k的子矩阵个数 如果T2如果不固定左上角求总和 ≤ k \le k ≤k的子矩阵个数 如果T3, 数值不局限于0,1,2, 求最小操作数 A. 将元素分配到两个数组中 I
思路: 模拟
模拟即可没啥可说的。
class Solution {public int[] resultArray(int[] nums) {ListInteger r1 new ArrayList(List.of(nums[0]));ListInteger 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 n * m n∗m
前缀和预处理, O ( n ∗ m ) O(n * m) O(n∗m)
枚举子矩阵为, O ( 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 ) O(n * m) 优化为 O(nm) O(n∗m)优化为O(nm)就是从右上点出发逐渐收敛到左下。 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) {ListInteger arr1 new ArrayList(List.of(nums[0]));ListInteger arr2 new ArrayList(List.of(nums[1]));// 离散化过程TreeSetInteger ts new TreeSet();for (int v: nums) ts.add(v);int ptr 1;MapInteger, 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();}
}写在最后
