LonelyPixelI [source code]
public class LonelyPixelI {
static
/******************************************************************************/
public class Solution {
public int findLonelyPixel(char[][] picture) {
int m = picture.length, n = picture[0].length, counter = 0;
boolean[] invalidCols = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (picture[i][j] == 'W')
continue;
if (invalidCols[j])
break;
if (isLonely(picture, i, j))
counter++;
invalidCols[j] = true;
break;
}
}
return counter;
}
public boolean isLonely(char[][] picture, int x, int y) {
for (int i = 0; i < picture[0].length; i++)
if (i != y && picture[x][i] == 'B')
return false;
for (int i = 0; i < picture.length; i++)
if (i != x && picture[i][y] == 'B')
return false;
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
LonelyPixelI.Solution tester = new LonelyPixelI.Solution();
char[][][] inputs = {
{{'W', 'W', 'B'},
{'W', 'B', 'W'},
{'B', 'W', 'W'}},
{{'B', 'W'},
{'W', 'B'}},
};
int[] answers = {
3,
2,
};
for (int i = 0; i < inputs.length; i++) {
char[][] picture = inputs[i];
int answer = answers[i];
System.out.println(Printer.seperator());
int output = tester.findLonelyPixel(picture);
System.out.println(Printer.wrapColor(Matrix.printMatrix(picture), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, answer == output ? "green" : "red"));
}
}
}
这题我想到的笨办法是这样做, 1pass, 把所有的黑点的坐标全部都记录下来, 然后就是sort一下(by x or y都行, 比如我们是sort by x). 如果一个黑点的x坐标跟它左右两边的x都不相等, 扔到一个set里面; 然后sort by y, 同样找到一个set的黑点, 然后两个set的intersection就是最后要找的lonely;
不过这个算法最后的速度并不怎么好, 因为要sort; 这个题目的tag给了提示是DFS, 所以考虑能不能用这个思路来做一下;
好像想到一个更笨的办法, 直接扫就行了, 最后的速度也顶多是O(MN), 不知道为什么要用DFS; 先写笨办法算了;
最后就这么写了, 唯一一个想法就是, 一旦碰到一个黑点, 无论这个黑点是否是lonely, 这个黑点所在的column就直接全部都ban了, 因为以后在这俄格column上面出现的任何其他黑点(因为我们的iteration的顺序是左右上下, 所以指的其实是后面的row的在同一个column的黑点). 注意, 这里没有必要ban row, 因为你只要当前row break之后, 就相当于是放弃所有今后其他跟当前这个失败的黑点share same row的黑点了, 所以没有必要记录要ban掉的row;
很奇怪的一个是, 加了这个ban column之后, 反而速度变慢了, 很奇怪好吧. 想了想, 是没有必要ban的? 因为就算你下一行又到了这个column, 那么这个黑点肯定会导致失败, 然后直接会被break. 想了一下, 是我的优化加的方式不对: 首先确定是黑点, 然后确定这个黑点所在的row被ban, 就直接break就行了: 这一行都不用再找了. 这样就可以完成一个优化了.
没有"ban"优化的时候, 速度是27ms (89%); 加了这个优化之后是24ms (94%). 虽然最后的case显示提升不是特别明显, 不过从实际的角度来说, 这种能完成跳掉一整行的优化还是挺有用的;
另外这里这个boolean flag array的设置方式也是之前学来的, 记录false而不是TRUE, 这样就不用额外初始化一次了;
这个算法理论上的复杂度其实不好, 不对, 加了"ban"优化之后其实是挺好的; 不对, 还是不好:
W W B
W B W
B W W
这样一个picture就是一个WorstCase; 没一行都会有一个lonely扫描, 最后的时间是O(M * (M + N)). 空间是O(N).
所以这个算法应该还是属于笨办法的范畴, 真正要是面Google估计这样的算法是过不了关的;
这个题目当时我刚开始拿到的第一个感觉其实是可以是不用纯粹iteration的思路来做, 而是用数学的思路来做, 也就是先一个pass走完之后, 手机足够的数学上的信息, 然后通过对这个数学上的分析来完成. 但是当时因为没有一个很明显的思路, 所以就没有去想了. discussion上面的最优解也是这个思路:
O(nm) Time, O(n+m) Space Solution:
public int findLonelyPixel(char[][] picture) {
int n = picture.length, m = picture[0].length;
int[] rowCount = new int[n], colCount = new int[m];
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B') { rowCount[i]++; colCount[j]++; }
int count = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) count++;
return count;
}
算法本身思路非常简介明快. 如果说怎么想到的, 直接是给自己一个Verbal Logic: a black pixel is lonely iff it occurs exactly once in each row and each column. 然后是有可能直接想到对所有的row和column进行count的;
这个思路比我之前的思路好的地方在于不纠结于记录所有的二维坐标; 如果走这条路, 基本就黑了, 因为这个记录量是非常大的. 但是count类的记录量, 一直就是很小的;
而且这个题目本身就是一个count的题目, 而且count的对象其实是一个单一的entry, 所以这种在首先的时候也用count类的算法好像也是比较好用的;
另外注意, 好像人家高手都是更喜欢把第一维叫做n, 把第二维叫做m;
这个人还给出了一个O(1) space的解:
public int findLonelyPixel(char[][] picture) {
int n = picture.length, m = picture[0].length;
int firstRowCount = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B') {
if (picture[0][j] < 'Y' && picture[0][j] != 'V') picture[0][j]++; //increment counter for column j
if (i == 0) firstRowCount++;
else if (picture[i][0] < 'Y' && picture[i][0] != 'V') picture[i][0]++; //increment counter for row i
}
int count = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] < 'W' && (picture[0][j] == 'C' || picture[0][j] == 'X')) { //if only one black pixel in column j
if (i == 0) count += firstRowCount == 1 ? 1 : 0;
else if (picture[i][0] == 'C' || picture[i][0] == 'X') count++; //if only one black pixel in row i
}
return count;
}
关于O(1) space我们前面总结过很多了, 这里用的技巧就是input inplace的做法; 不过这个InPlace的具体实现技巧还是有点难的;
他这里用的这个逻辑其实还是属于比较复杂的, 如果只是为了完成一个InPlace做flag的目的的话, 直接可以先把第一行和第一列都先单独扫一遍, 然后全部都归到0, 然后单独的对剩下的(M - 1) * (N - 1)个entry进行统计就行了; 不过这样写的逻辑肯定没有他这里这个写法这么elegant;
The hack here is to mutate the first row and first column of the given matrix to store the counts of items in the row/column.
* W + 1 = X --> one item in the row/column
* B + 1 = C --> one item in the row/column, and the first row is the black pixel
* W + 2 = Y --> two items in the row/column
* W - 1 = V --> this prevents wrap-around past W if there are more than 255 black pixels in a row/column
他这个解释其实还不是特别的完整;
这里他的做法首先, 还是确实是第一行和第一列就用来作为counts, 不过因为这两行两列本身有数据, 加上这个人看样子也不想单独把这一行一列先分开扫掉, 所以他这里的做法其实整合了非常复杂的逻辑: 这个也印证了我们以前说过的一个逻辑, 想要把2pass很容易做完的事情整合到1pass里面, 有时候是要付出惨重的代价的; 不过真正对我自己而言, 我觉得要求自己能看懂这个算法就可以了, 真正面试的时候如果让你做O(1), 先要想到InPlace, 然后能够想到单独处理这种思路就Okay;
大体的思路就是[0][j] stores number of black pixels in the column j, and [i][0] stores the number of black pixels in row i. 注意看, 这里有一个问题, 总共有n row, m column, 但是你这上面两种entry加起来总共只有m + n - 1个. 所以他这里要单独做一个firstRowCount来补充一下; 你这个单独的counter记录first column其实也是可以的, 等价的效果;
我们就考虑第一行这个counter array的情况: 某一个entry [0][j]记录column j的情况, 但是这个entry自己在最开始的时候, 有可能是B, 也有可能是W. 所以实际上这个counter的起点有两种情况; 两种情况最后对应的就是被increment之后的值的区间其实有两种; 一种就是B开头的, 一种就是W开头的; 然后这个作者给这两个区间都设置上限, 分别是Y和V, 防止超出各自的划分区域(一共就26个字母, 一人分一半左右).
注意他这里划分区域的一个技巧: 在代码上, 这两个区间是公用一个变量的, 所以这里他区间的写法上, 一个是<Y, 另一个就不能用<V, 必须用!=V. 如果两个都用<,那么最后代码就只会取W, 也就是两者的min, 这个是不对的; 因为我们这个entry的变量的更新只可能是increment 1 at a time, 所以只要V的位置保证neq, 就可以保证两半区间都不会超界了: 这里的<和!=其实完成的作用是一样的, 只不过代码上不方便这样写而已;
代码其他的逻辑基本就在注释里面了, 反正基本的大体思路还是首先把row和column的counter全部都做完, 然后最后分别处理, 检查一下每一个row/column都只有一个黑点就行了;
这里还有一个小的细节是一开始没有看懂, 比如想要判断column j只有一个黑点的时候, 为什么判断的相等的条件是C和X? X其实很好理解, W开头的区间里面, +1表示只有一个黑点, 然后W+1=X; 而C的原因是: 如果我们最后得到了一个C, 我们一定是在B开始的这个区间里面, 也就是[0][j]一开始就是B, 这个在count的环节, 刚开始就会给加成C. 所以这个对应的其实是: only one black pixel in column j and it's exactly [0][j] itself;
刚开始读这个代码的时候其实也是读不懂, 因为这里的逻辑简练的程度太高了. 最后还是举例子: 第一行有黑点什么样的, 第一行没有黑点什么样的; 等等;
这个代码暂时只能看到这里了, 后面有时间再消化;
这个是对之前O(M+N) space算法的一个trivial的优化:
public class Solution {
public int findLonelyPixel(char[][] picture) {
if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
int[] colArray = new int[picture[0].length];
for (int i = 0; i < picture.length; i++) {
for (int j = 0; j < picture[0].length; j++) {
if (picture[i][j] == 'B') colArray[j]++;
}
}
int ret = 0;
for (int i = 0; i < picture.length; i++) {
int count = 0, pos = 0;
for (int j = 0; j < picture[0].length; j++) {
if (picture[i][j] == 'B') {
count++;
pos = j;
}
}
if (count == 1 && colArray[pos] == 1) ret++;
}
return ret;
}
}
这个方法就是在最后检查column counts的同时进行row counts的统计, 这样就节省了一个array, 不是不可取, 不过也是一个不错的技巧;
Problem Description
Given a picture consisting of black and white pixels, find the number of black lonely pixels.
The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.
A black lonely pixel is character 'B' that located at a specific position where the same row and same column don't have any other black pixels.
Example:
Input:
[['W', 'W', 'B'],
['W', 'B', 'W'],
['B', 'W', 'W']]
Output: 3
Explanation: All the three 'B's are black lonely pixels.
Note:
The range of width and height of the input 2D array is [1,500].
Difficulty:Medium
Total Accepted:5.6K
Total Submissions:10.3K
Contributor: fallcreek
Companies
google
Related Topics
array depth-first search