gpt4 book ai didi

java - 根据行和列和恢复0-1矩阵

转载 作者:行者123 更新时间:2023-12-02 08:56:23 28 4
gpt4 key购买 nike

请注意:这个问题很长,可能需要一些时间来阅读:

我在编码测试中遇到了这个问题:

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% 的速度:

我的想法:

  1. if U+L != the sum of elements in C, return "IMPOSSIBLE";
  2. 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;
  3. 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";
}

在到达结尾之前可以知道如果ul小于0则无解,并且可以添加检查以代码为例:

if (u < 0 || l < 0)
return "IMPOSSIBLE";

可以添加在for循环之前。并且可以在循环中添加更多检查。在现实世界中,它可能会使代码变慢或变快,具体取决于许多因素(分支预测、更有可能或不可能......)。它不会改变复杂性。

关于java - 根据行和列和恢复0-1矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60461441/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com