flyingforce
BAN USERcreate two array rowSum[] and colSum[] to indicate the sum of pixel of current row and col, then loop the rowSum, if current rowSum==1, get the pixel col, and check whether the colSum ==1.
The time complexity is O(m*n) Technically at most loop the all the nodes twice.
public class LonelyPixel {
public static int getLonelyPixelCount(int[][] val) {
int[] rowsSum = new int[val.length];
int[] colsSum = new int[val[0].length];
for (int i = 0; i < val.length; i++) {
for (int j = 0; j < val[0].length; j++) {
if (val[i][j] == 1) {
rowsSum[i]++;
colsSum[j]++;
}
}
}
int count = 0;
for (int i = 0; i < rowsSum.length; i++) {
if (rowsSum[i] == 1) {
for (int j = 0; j < colsSum.length; j++) {
if (val[i][j] == 1) {
if (colsSum[j] == 1) {
count++;
break;
}
}
}
}
}
return count;
}
public static void main(String[] args){
int[][] val = new int[][]{ //1: black, 0: white
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
System.out.print(getLonelyPixelCount(val));
}
}
DFS solution
public class PermutationDistance {
public static List<List<Integer>> findPermutaionInDistance(int n) {
List<List<Integer>> retList = new ArrayList<>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n * 2; i++) {
result.add(0);
}
helper(retList, result, n);
return retList;
}
public static void helper(List<List<Integer>> retList, List<Integer> result, int n) {
// printOne(result);
Set<Integer> resultVals = new HashSet<>();
for (int val : result) {
if (val != 0) {
resultVals.add(val);
}
}
if (resultVals.size() == n) {
retList.add(new ArrayList<>(result));
return;
}
for (int i = 1; i < n + 1; i++) {
if (resultVals.contains(i)) {
continue;
}
for (int j = 0; j < result.size() - i -1; j++) {
if (result.get(j) == 0 && result.get(j + i + 1) == 0) {
result.set(j, i);
result.set(j + i + 1, i);
helper(retList, result, n);
result.set(j, 0);
result.set(j + i + 1, 0);
}
}
}
}
public static void print(List<List<Integer>> res) {
for (List<Integer> result : res) {
for (int va : result) {
System.out.print(va + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
List<List<Integer>> res = findPermutaionInDistance(3);
print(res);
}
Should be wrong, the count make no sense to put into recursive, and I cannot understand what you try to do in the recursive.
- flyingforce May 09, 2019