​LeetCode刷题实战531:孤独像素 I

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 孤独像素 I,我们先来看题面:
https://leetcode-cn.com/problems/lonely-pixel-i/

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.


给定一幅黑白像素组成的图像, 计算黑色孤独像素的数量。
图像由一个由‘B’和‘W’组成二维字符数组表示, ‘B’和‘W’分别代表黑色像素和白色像素。
黑色孤独像素指的是在同一行和同一列不存在其他黑色像素的黑色像素。

示例                         

示例:
输入:
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]

输出: 3
解析: 全部三个'B'都是黑色孤独像素。
 
注意:
输入二维数组行和列的范围是 [1,500]。


解题

https://blog.csdn.net/qq_29051413/article/details/108617060

 定义两个数组 row[] 和 col[]。

  row[i] 表示第 i 行总共有多少个 ‘B’。

  col[j] 表示第 j 列总共有多少个 ‘B’。

  遍历 picture[][],统计每一行每一列分别总共有多少个 ‘B’,同时把 ‘B’ 的坐标保存在一个 List 中。

  遍历 List :若 row[i] == col[j] == 1,说明 (i,j) 是一个孤独的像素,孤独像素的数量加一。

  时间复杂度:O(kmn),m为行数,n为列数,k为黑色像素的数量。

class Solution {
    public int findLonelyPixel(char[][] picture) {
        int ans = 0;
        int rowN = picture.length;
        int colN = picture[0].length;
        int[] row = new int[rowN];
        int[] col = new int[colN];
        List<Integer[]> list = new ArrayList<>();
        for (int i = 0; i < rowN; i++) {
            for (int j = 0; j < colN; j++) {
                if (picture[i][j] == 'B') {
                    row[i]++;
                    col[j]++;
                    list.add(new Integer[]{i, j});
                }
            }
        }
        for (Integer[] blackPoint : list) {
            int i = blackPoint[0];
            int j = blackPoint[1];
            if (row[i] == 1 && row[i] == col[j]) {
                ans++;
            }
        }
        return ans;
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:
LeetCode1-520题汇总,希望对你有点帮助!
LeetCode刷题实战521:最长特殊序列 Ⅰ
LeetCode刷题实战522:最长特殊序列 II
LeetCode刷题实战523:连续的子数组和
LeetCode刷题实战524:通过删除字母匹配到字典里最长单词
LeetCode刷题实战525:连续数组
LeetCode刷题实战526:优美的排列
LeetCode刷题实战527:单词缩写
LeetCode刷题实战528:按权重随机选择
LeetCode刷题实战529:扫雷游戏

​LeetCode刷题实战531:孤独像素 I

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/19777.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息