531.孤独像素I

531.孤独像素I

题目大意:给一个矩形,由字符’W’和’B’组成,w代表空白,b代表像素,找出矩阵中横竖方向都只有它自己一个像素的像素总数.

解题思路:两次遍历矩阵.第一次建立横竖方向的像素数表rows,cols,第二次根据表中数据,若a[i,j]位置为像素,且rows[i], cols[j]都等于1,则该像素符合. 这里用到一个trick,第二次遍历中,内层j循环时,加上对i的限制条件rows[i]>0可以减少j不必要的遍历.

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int m = picture.size();  //行数
        int n = picture[0].size();  //列数
        vector<int> rows(m);
        vector<int> cols(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    rows[i]++; 
                    cols[j]++;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m ; i++) {  //遍历每行
             for (int j = 0; j < n && rows[i] > 0; j++)   {  //小trick,只遍历rows[i] > 0的列
                 if (picture[i][j] == 'B' && rows[i] == 1 && cols[j] == 1) res++;
             }
        }
        return res;
    }
};