LeetCode] 每周游戏 #387本周游戏 #387
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 。
复杂度:O(N)
class Solution {
public int[] resultArray(int[] nums) {
int n = nums.length;
List<Integer> l1 = new ArrayList();
List<Integer> l2 = new ArrayList();
l1.add(nums[0]);
l2.add(nums[1]);
for(int i=2; i<n; 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 i=0; i<l1.size(); i++) {
res[idx] = l1.get(i);
idx ++;
}
for(int i=0; i<l2.size(); i++) {
res[idx] = l2.get(i);
idx ++;
}
return res;
}
}
3070. 元素和小于等于 k 的子矩阵的数目
给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。
返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的
数目
。
思路:二维数组前缀和
复杂度:O(N*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 i=0; i<m; i++) {
int s = 0;
for(int j=0; j<n; j++) {
s = s + grid[i][j];
dp[i][j] = s;
if(i-1>=0) {
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不相等。
复杂度:O(NN)
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 i=0; i<=n/2; i++) {
vis[i][i] = true;
}
int idx = n/2;
for(int j=n/2; j<n; j++) {
vis[idx][j] = true;
idx --;
}
idx = n/2;
for(int i=n/2; i<n; i++) vis[i][idx]=true;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(vis[i][j]) {
y[grid[i][j]] ++;
} else {
ny[grid[i][j]] ++;
}
}
}
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// System.out.print(vis[i][j] +" ");
// }
// System.out.println(" ");
// }
//
// for(int j=0; j<3; j++) {
// System.out.print(y[j] +" ");
// }
int ans = n*n;
for(int i=0; i<3; i++) {
for(int j=0; j<3; 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的数量,则gc=n-sum[1,i]
复杂度:O(NlogN)
class Fenwick {
public final int[] tree;
public Fenwick(int n) {
tree = new int[n];
}
public void add(int idx) {
while(idx<tree.length) {
tree[idx] ++;
idx += idx & -idx;
}
}
public int sum(int i) {
int res =0;
while(i>0) {
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(n+1);
Fenwick tb = new Fenwick(n+1);
List<Integer> a = new ArrayList();
List<Integer> 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 i=2; i<n; i++) {
// 找到对应的映射
int v1 = Arrays.binarySearch(sorted, nums[i]) +1;
int gc1 = a.size() - ta.sum(v1);
int gc2 = b.size() - tb.sum(v1);
if(gc1>gc2 || gc1==gc2 && 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 i=0; i<n; i++) {
res[i] = a.get(i);
}
return res;
}
}
上一篇: 反应模态箱设计 (V) 主体设计