渭南网站建设,wordpress 互动模块,旅游网站专业化建设的要点,在哪个网站有兼职做3069. 将元素分配到两个数组中 I
给你一个下标从 1 开始、包含 不同 整数的数组 nums #xff0c;数组长度为 n 。
你需要通过 n 次操作#xff0c;将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中#xff0c;将 nums[1] 追加到 arr1 。在第二次操作…3069. 将元素分配到两个数组中 I
给你一个下标从 1 开始、包含 不同 整数的数组 nums 数组长度为 n 。
你需要通过 n 次操作将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中将 nums[1] 追加到 arr1 。在第二次操作中将 nums[2] 追加到 arr2 。之后在第 i 次操作中
如果 arr1 的最后一个元素 大于 arr2 的最后一个元素就将 nums[i] 追加到 arr1 。否则将 nums[i] 追加到 arr2 。 通过连接数组 arr1 和 arr2 形成数组 result 。例如如果 arr1 [1,2,3] 且 arr2 [4,5,6] 那么 result [1,2,3,4,5,6] 。
返回数组 result 。 复杂度ON
class Solution {public int[] resultArray(int[] nums) {int n nums.length;ListInteger l1 new ArrayList();ListInteger l2 new ArrayList();l1.add(nums[0]);l2.add(nums[1]);for(int i2; in; i) {int i1 l1.size()-1;int i2 l2.size()-1;if(l1.get(i1) l2.get(i2)) {l1.add(nums[i]);} else {l2.add(nums[i]);}}int[] res new int[n];int idx 0;for(int i0; il1.size(); i) {res[idx] l1.get(i);idx ;}for(int i0; il2.size(); i) {res[idx] l2.get(i);idx ;}return res;}
}3070. 元素和小于等于 k 的子矩阵的数目
给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。
返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的 数目 。 思路二维数组前缀和 复杂度ON*N
class Solution {public int countSubmatrices(int[][] grid, int k) {int m grid.length;int n grid[0].length;int[][] dp new int[m][n];// dp[0][0] grid[0][0];int ans 0;for(int i0; im; i) {int s 0;for(int j0; jn; j) {s s grid[i][j];dp[i][j] s;if(i-10) {dp[i][j] dp[i-1][j];}if(dp[i][j] k) {ans ;}}}return ans;}
}3071. 在矩阵上写出字母 Y 所需的最少操作次数
给你一个下标从 0 开始、大小为 n x n 的矩阵 grid 其中 n 为奇数且 grid[r][c] 的值为 0 、1 或 2 。
如果一个单元格属于以下三条线中的任一一条我们就认为它是字母 Y 的一部分
从左上角单元格开始到矩阵中心单元格结束的对角线。 从右上角单元格开始到矩阵中心单元格结束的对角线。 从中心单元格开始到矩阵底部边界结束的垂直线。 当且仅当满足以下全部条件时可以判定矩阵上写有字母 Y
属于 Y 的所有单元格的值相等。 不属于 Y 的所有单元格的值相等。 属于 Y 的单元格的值与不属于Y的单元格的值不同。 每次操作你可以将任意单元格的值改变为 0 、1 或 2 。返回在矩阵上写出字母 Y 所需的 最少 操作次数。 思路数组y记录Y内区域每种元素出现次数数组ny记录Y外区域每种元素出现次数。则所求问题即为求nn-y[i]-ny[j]的最小值其中i与j不相等。 复杂度ONN
class Solution {public int minimumOperationsToWriteY(int[][] grid) {int n grid.length;int[] y new int[3];int[] ny new int[3];boolean[][] vis new boolean[n][n];for(int i0; in/2; i) {vis[i][i] true;}int idx n/2;for(int jn/2; jn; j) {vis[idx][j] true;idx --;}idx n/2;for(int in/2; in; i) vis[i][idx]true;for(int i0; in; i) {for(int j0; jn; j) {if(vis[i][j]) {y[grid[i][j]] ;} else {ny[grid[i][j]] ;}}}// for(int i0; in; i) {// for(int j0; jn; j) {// System.out.print(vis[i][j] );// }// System.out.println( );// }
// // for(int j0; j3; j) {// System.out.print(y[j] );// }int ans n*n;for(int i0; i3; i) {for(int j0; j3; j) {if(i!j){// System.out.println(n*n-y[i]ny[j]);ans Math.min(ans, n*n-y[i]-ny[j]);} }}return ans;}
}3072. 将元素分配到两个数组中 II
现定义函数 greaterCount 使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中将 nums[1] 追加到 arr1 。在第二次操作中将 nums[2] 追加到 arr2 。之后在第 i 次操作中
如果 greaterCount(arr1, nums[i]) greaterCount(arr2, nums[i]) 将 nums[i] 追加到 arr1 。 如果 greaterCount(arr1, nums[i]) greaterCount(arr2, nums[i]) 将 nums[i] 追加到 arr2 。 如果 greaterCount(arr1, nums[i]) greaterCount(arr2, nums[i]) 将 nums[i] 追加到元素数量较少的数组中。 如果仍然相等那么将 nums[i] 追加到 arr1 。 连接数组 arr1 和 arr2 形成数组 result 。例如如果 arr1 [1,2,3] 且 arr2 [4,5,6] 那么 result [1,2,3,4,5,6] 。
返回整数数组 result 。 思路树型数组。先将数组排序用排序后的数组的序号来缩小数据范围。树型数组的[1,i]表示小于等于i的数量则gcn-sum[1,i] 复杂度ONlogN
class Fenwick {public final int[] tree;public Fenwick(int n) {tree new int[n];}public void add(int idx) {while(idxtree.length) {tree[idx] ;idx idx -idx;}}public int sum(int i) {int res 0;while(i0) {res tree[i];i - i -i;}return res;}
}class Solution {public int[] resultArray(int[] nums) {int[] sorted nums.clone();Arrays.sort(sorted);int n nums.length;Fenwick ta new Fenwick(n1);Fenwick tb new Fenwick(n1);ListInteger a new ArrayList();ListInteger b new ArrayList();a.add(nums[0]);b.add(nums[1]);ta.add(Arrays.binarySearch(sorted, nums[0])1);tb.add(Arrays.binarySearch(sorted, nums[1])1);for(int i2; in; i) {// 找到对应的映射int v1 Arrays.binarySearch(sorted, nums[i]) 1;int gc1 a.size() - ta.sum(v1);int gc2 b.size() - tb.sum(v1);if(gc1gc2 || gc1gc2 a.size()b.size()) {a.add(nums[i]);ta.add(v1);} else {b.add(nums[i]);tb.add(v1);}}for(int num:b) {a.add(num); }int[] res new int[n];for(int i0; in; i) {res[i] a.get(i);}return res;}
}
