LonelyPixelII [source code]
public class LonelyPixelII {
static
/******************************************************************************/
class Solution {
public int findBlackPixel(char[][] picture, int N) {
int R = picture.length, C = picture[0].length;
Map<String, Integer> sameRows = new HashMap<> ();
int[] xCountsInCols = new int[C];
for (int i = 0; i < R; i++) {
StringBuilder sb = new StringBuilder ();
int rowBs = 0;
for (int j = 0; j < C; j++) {
sb.append (picture[i][j]);
if (picture[i][j] == 'B') {
rowBs++;
xCountsInCols[j]++;
}
}
if (rowBs != N)
continue;
String rowHash = sb.toString ();
sameRows.put (rowHash, sameRows.getOrDefault (rowHash, 0) + 1);
}
int res = 0;
for (String sameHash : sameRows.keySet ()) {
int sameCount = sameRows.get (sameHash);
if (sameCount == N) {
for (int j = 0; j < C; j++) {
if (sameHash.charAt (j) == 'B' && xCountsInCols[j] == N)
res += N;
}
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
LonelyPixelII.Solution tester = new LonelyPixelII.Solution();
char[][][] inputs1 = {
{{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','W','B','W','B','W'}},
{{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'B','W','B','W','W','B'}},
};
int[] inputs2 = {
3,
1,
};
int[] answers = {
6,
0,
};
for (int i = 0; i < inputs1.length; i++) {
char[][] picture = inputs1[i];
int N = inputs2[i], ans = answers[i];
System.out.println (Printer.separator ());
int output = tester.findBlackPixel (picture, N);
System.out.printf ("%s and %d -> %s, expected: %d\n",
Matrix.printMatrix (picture), N, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
题目意思比较绕, 不过看完好像大概有点思路; 开写;
这个是一开始的一个代码, 用的integer hash, 但是被后面的大case给break掉了:
class Solution {
public int findBlackPixel(char[][] picture, int N) {
int R = picture.length, C = picture[0].length;
int[] ysInRows = new int[R];
Map<Integer, Integer> sameRows = new HashMap<> ();
int[] xCountsInCols = new int[C];
for (int i = 0; i < R; i++) {
int rowBits = 0;
int j = C - 1;
while (j >= 0) {
if (picture[i][j] == 'B')
xCountsInCols[j]++;
rowBits = 2 * rowBits + (picture[i][j] == 'B' ? 1 : 0);
j--;
}
ysInRows[i] = rowBits;
sameRows.put (rowBits, sameRows.getOrDefault (rowBits, 0) + 1);
}
int res = 0;
for (int sameHash : sameRows.keySet ()) {
if (Integer.bitCount (sameHash) != N)
continue;
int sameCount = sameRows.get (sameHash);
if (sameCount == N) {
for (int j = 0; j < C; j++) {
if (((sameHash >> j) & 1) > 0 && xCountsInCols[j] == N)
res += N;
}
}
}
return res;
}
}
也不知道这种题目非要用这种大case来break掉integer hash有什么意思, 难怪这个题目这么多downvote;
不过最后好歹还是过掉了; 而且加了一些优化; 在处理row的时候, 顺便count这个row的B, 如果数量不等于N的row, 根本不用保留其记录, 直接跳过就行了;
最后速度是38ms (21%), 还可以接受;
2018-01-13 17:45:25 暂时还没有editorial;
discussion最优解, 跟我的思路几乎是一样的, 不过比我的快一点;
@shawngao said in Verbose Java O(m*n) Solution, HashMap:
The difficult parts are validating the two rules:
- Row
Rand columnCboth contain exactlyNblack pixels.- For all rows that have a black pixel at column
C, they should be exactly the same as rowRMy solution:
- Scan each row. If that row has
Nblack pixels, put a stringsignature, which is concatenation of each characters in that row, as key and how many times we see thatsignatureinto a HashMap. Also during scan each row, we record how many black pixels in each column in an arraycolCountand will use it in step 2.
For input:
[['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'W', 'B', 'W', 'B', 'B']]
We will get a HashMap:
{"WBWBBW": 3, "WWBWBB": 1}
and colCount array:
[0, 3, 1, 3, 4, 1]- Go through the HashMap and if the count of one
signatureisN, those rows potentially contain black pixels we are looking for. Then we validate each of those columns. For each column of them hasNblack pixels (lookup incolCountarray), we getNvalid black pixels.
For above example, only the firstsignature"WBWBBW" has count == 3. We validate 3 column 1, 3, 4 where char == 'B', and column 1 and 3 have 3 'B', then answer is 2 * 3 = 6.Time complexity analysis:
Because we only scan the matrix for one time, time complexity is O(m*n). m = number of rows, n = number of columns.
public class Solution {
public int findBlackPixel(char[][] picture, int N) {
int m = picture.length;
if (m == 0) return 0;
int n = picture[0].length;
if (n == 0) return 0;
Map<String, Integer> map = new HashMap<>();
int[] colCount = new int[n];
for (int i = 0; i < m; i++) {
String key = scanRow(picture, i, N, colCount);
if (key.length() != 0) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
}
int result = 0;
for (String key : map.keySet()) {
if (map.get(key) == N) {
for (int j = 0; j < n; j++) {
if (key.charAt(j) == 'B' && colCount[j] == N) {
result += N;
}
}
}
}
return result;
}
private String scanRow(char[][] picture, int row, int target, int[] colCount) {
int n = picture[0].length;
int rowCount = 0;
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
if (picture[row][j] == 'B') {
rowCount++;
colCount[j]++;
}
sb.append(picture[row][j]);
}
if (rowCount == target) return sb.toString();
return "";
}
}
submission最优解: 16(99):
class Solution {
public int findBlackPixel(char[][] picture, int N) {
int rowLength = picture.length;
if (0 == rowLength)
return 0;
int colLength = picture[0].length;
if (0 == colLength)
return 0;
if (N == 0 || N > rowLength || N > colLength)
return 0;
int[] rows = new int[rowLength];
int[] cols = new int[colLength];
String[] strings = new String[rowLength];
for (int i = 0; i < rowLength; i++) {
for (int j = 0; j < colLength; j++) {
if (picture[i][j] == 'B') {
rows[i]++;
cols[j]++;
}
}
strings[i] = new String(picture[i]);
}
int res = 0;
main: for (int j = 0; j < colLength; j++) {
if (cols[j] != N)
continue;
int i = 0;
while (picture[i][j] != 'B')
i++;
if (rows[i] != N)
continue;
String s = strings[i++];
for (int k = N - 1; k > 0; k--, i++) {
while (picture[i][j] != 'B')
i++;
if (rows[i] != N)
continue main;
if (!strings[i].equals(s))
continue main;
}
res += N;
}
return res;
}
}
一个学习的地方是看他做hash的方式, 直接用new String来做就行了, 不用傻乎乎的自己用StringBuilder去append;
感觉就是自己人工用循环做一个判断而已, 懒得看了; 而且这个人用了很多类似goto的操作;
Problem Description
Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:
- Row R and column C both contain exactly N black pixels.
- For all rows that have a black pixel at column C, they should be exactly the same as row R
The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.
Example:
Input:
[['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'W', 'B', 'W', 'B', 'W']]
N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
0 1 2 3 4 5 column index
0 [['W', 'B', 'W', 'B', 'B', 'W'],
1 ['W', 'B', 'W', 'B', 'B', 'W'],
2 ['W', 'B', 'W', 'B', 'B', 'W'],
3 ['W', 'W', 'B', 'W', 'B', 'W']]
row index
Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels.
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.
Note:
- The range of width and height of the input 2D array is [1,200].
Difficulty:Medium
Total Accepted:5K
Total Submissions:11.1K
Contributor:fallcreek
Companies
google
Related Topics
arraydepth-first search
Similar Questions
Lonely Pixel II