- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
请注意:这个问题很长,可能需要一些时间来阅读:
我在编码测试中遇到了这个问题:
Say we have a 0-1 matrix with 2 rows and N columns, given the U=the sum of upper row, and the L=the sum of low row, and int[] C= the array containing the sum of each column, return the String representation of the matrix. If there are more than one, return any of them. If no matrix satisfies, return "IMPOSSIBLE".
示例1:
U=3,L=2,C=[2,1,1,0,1] return String="11100,10001"(two rows are seperated by ",")
通过以下方法,我得到了 50% 的正确率和 14% 的速度:
我的想法:
- if U+L != the sum of elements in C, return "IMPOSSIBLE";
- otherwise, initilize the matrix with 0, and use a for loop to visit each element in C:
if C[i]==2, set elements in each row with 1;
if C[i]==0 set elements in each row with 0;
if C[i]==1 && 0<U, set element in upper row with 1 and element in low row with 0, and U--,
otherwise, set element in upper row with 0 and element in low row with 1;- finally we visit each elemenet in the matrix to get the result String(with StringBuilder.append()).
有人可以帮我改进吗?想了很久也想不出更好的解决办法。我认为这个解决方案应该是 100% 正确的,并且 O(N)
应该是最小时间复杂度,其中 N
是矩阵元素的总数。
----更新:
class Solution {
public String solution(int U, int L, int[] C) {
// write your code in Java SE 8
int N=C.length;
int colSum=0;
for(int i=0;i<N;i++){
colSum+=C[i];
}
if(colSum!=U+L){
return "IMPOSSIBLE";
}
String[] upRow=new String[N];
String[] lowRow=new String[N];
for(int i=0;i<N;i++){
if(C[i]==2){
upRow[i]="1";
lowRow[i]="1";
U--;
L--;
}else if(C[i]==0){
upRow[i]="0";
lowRow[i]="0";
}else{
if(0<U){
upRow[i]="1";
lowRow[i]="0";
U--;
}else{
upRow[i]="0";
lowRow[i]="1";
}
}
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<N;i++){
sb.append(upRow[i]);
}
sb.append(",");
for(int i=0;i<N;i++){
sb.append(lowRow[i]);
}
return sb.toString();
}
}
最佳答案
基于评论的解决方案:
public static String check(int[] c, int u, int l) {
// decrease the sum of upper and lower rows by the number of sum 2 columns
int twos = (int) Arrays.stream(c).filter(a -> a == 2).count();
u -= twos;
l -= twos;
StringBuilder upper = new StringBuilder();
StringBuilder lower = new StringBuilder();
for (int a : c) {
switch (a) {
// sum was already decreased, just add 1 to each row
case 2:
upper.append('1');
lower.append('1');
break;
// first put 1 in the upper row and decrease it's sum until it reaches 0 then switch to lower row
case 1:
if (u > 0) {
upper.append('1');
lower.append('0');
u--;
} else {
upper.append('0');
lower.append('1');
l--;
}
break;
case 0:
upper.append('0');
lower.append('0');
}
}
// if and only if the sum of both rows is now 0 a solution was found otherwise return "IMPOSSIBLE"
return u == 0 && l == 0 ? upper.toString() + "," + lower.toString() : "IMPOSSIBLE";
}
在到达结尾之前可以知道如果u
或l
小于0
则无解,并且可以添加检查以代码为例:
if (u < 0 || l < 0)
return "IMPOSSIBLE";
可以添加在for
循环之前。并且可以在循环中添加更多检查。在现实世界中,它可能会使代码变慢或变快,具体取决于许多因素(分支预测、更有可能或不可能......)。它不会改变复杂性。
关于java - 根据行和列和恢复0-1矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60461441/
假设我有两个矩阵,每个矩阵有两列和不同的行数。我想检查并查看一个矩阵的哪些对在另一个矩阵中。如果这些是一维的,我通常只会做 a %in% x得到我的结果。 match似乎只适用于向量。 > a
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 9 个月前。 Improv
我只处理过 DirectX 矩阵 我读过一些文章,说不能将 DirectX 矩阵数学库用于 openGL 矩阵。 但我也读过,如果你的数学是一致的,你可以获得类似的结果。那只会让我更加困惑。 任何人都
我编写了一个C++代码来解决线性系统A.x = b,其中A是一个对称矩阵,方法是首先使用LAPACK(E)对角矩阵A = V.D.V^T(因为以后需要特征值),然后求解x = A^-1.b = V^T
我遇到了问题。我想创建二维数组 rows=3 cols=2我的代码如下 int **ptr; int row=3; int col=2; ptr=new int *[col]; for (int i=
我有一个 3d mxnxt 矩阵,我希望能够提取 t 2d nxm 矩阵。在我的例子中,我有一个 1024x1024x10 矩阵,我想要 10 张图像显示给我。 这不是 reshape ,我每次只需要
我在 MATLAB 中有一个 3d 矩阵 (n-by-m-by-t) 表示一段时间内网格中的 n-by-m 测量值.我想要一个二维矩阵,其中空间信息消失了,只剩下 n*m 随着时间 t 的测量值(即:
作为一个简化的示例,我有一个 3D numpy 矩阵,如下所示: a = np.array([[[1,2], [4,np.nan], [7,
作为一个简化的示例,我有一个 3D numpy 矩阵,如下所示: a = np.array([[[1,2], [4,np.nan], [7,
使用 eigen2 , 并给定一个矩阵 A a_0_0, a_0_1, a_0_2, ... a_1_0, a_1_0, a_1_2, ... ... 和一个矩阵B: b_0_0, b_0_1, b_
我想知道如何获得下面的布局。 在中型和大型设备上,我希望有 2 行和 2 列的布局(2 x 2 矩阵)。 在小型(和超小型)设备上或调整为小型设备时,我想要一个 4 行和 1 列的矩阵。 我将通过 a
有什么方法可以向量化以下内容: for i = 1:6 te = k(:,:,:,i).*(c(i)); end 我正在尝试将 4D 矩阵 k 乘以向量 c,方法是将其
如何从填充有 1 和 0 的矩阵中抽取 n 个随机点的样本? a=rep(0:1,5) b=rep(0,10) c=rep(1,10) dataset=matrix(cbind(a,b,c),nrow
我正在尝试创建一个包含 X 个 X 的矩阵。以下代码生成从左上角到右下角的 X 对 Angular 线,而不是从右上角到左下角的 X 对 Angular 线。我不确定从哪里开始。是否应该使用新变量创建
我想在 python 中创建一个每行三列的矩阵,并能够通过任何一行对它们进行索引。矩阵中的每个值都是唯一的。 据我所知,我可以设置如下矩阵: matrix = [["username", "name"
我有点迷茫 我创建了一个名为 person 的类,它具有 age 和 name 属性(以及 get set 方法)。然后在另一个类中,我想创建一个 persons 数组,其中每个人都有不同的年龄和姓名
我有 n 个类,它们要么堆叠,要么不堆叠。所有这些类都扩展了同一个类 (CellObject)。我知道更多类将添加到此列表中,我想创建一种易于在一个地方操纵“可堆叠性”的方法。 我正在考虑创建一个矩阵
我有一个包含 x 个字符串名称及其关联 ID 的文件。本质上是两列数据。 我想要的是一个格式为 x x x 的相关样式表(将相关数据同时作为 x 轴和 y 轴),但我想要 fuzzywuzzy 库的函
机器学习与传统编程的一个重要区别在于机器学习比传统编程涉及了更多的数学知识。不过,随着机器学习的飞速发展,各种框架应运而生,在数据分析等应用中使用机器学习时,使用现成的库和框架成为常态,似乎越来越不需
当我在 julia 中输入这个错误跳转但我不知道为什么,它应该工作。/ julia> A = [1 2 3 4; 5 6 7 8; 1 2 3 4; 5 6 7 8] 4×4 Array{Int64,
我是一名优秀的程序员,十分优秀!