亲宝软件园·资讯

展开

Android开发岛屿数量算法示例解析

流浪汉kylin 人气:0

前言

最近没有什么比较好的思路,之前有写过关于数据结构相关的内容。所以想往算法这方面看不看能不能捣鼓点出一些开发思路。

岛屿数量

之前接触过一个算法,比较有意思,可以拿出来说说,这个算法是这样的。

给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。(岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。)

比如

输入

[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]

输出3。因为1相连的就3块

那这道题要如何做呢,其实有个思路,我去遍历二维数组,判断到如果为1,我就把与1相连的上下左右都置0,这样在接下来的遍历中就不会受到已统计数量的影响。

如果只听这样的描述还是没理解也没关系,可以看看代码,我这是用java写的,挺简单的,应该能很容易看懂。

public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */
    public int solve (char[][] grid) {
        int total = 0;
        if(grid.length == 0 || grid[0].length == 0){
            return total;
        }
        int wl = grid[0].length;
        for(int i=0; i < grid.length; i++){
            for(int j =0; j < wl; j++){
                if(grid[i][j] == '1'){
                    total++;
                    cancel(grid, i, j);
                }
            }
        }
        return total;
    }
    private void cancel(char[][] grid, int i, int j){
        if(grid[i][j] == '1'){
            grid[i][j] = '0';
            if(i > 0){
                cancel(grid, i-1, j);
            }
            if(j > 0){
                cancel(grid, i, j-1);
            }
            if(j < grid[0].length -1){
                cancel(grid, i, j+1);
            }
            if(i < grid.length - 1){
                cancel(grid, i+1, j);
            }
        }
    }
}

那能从这个算法中学会什么呢?学会了这道算法,被问到就有题库了【狗头】,那也太血亏了,还是要扩展一下思路。

我觉得有意思的地方在于,它是通过一个反向的思路,去设置状态,以此来把这个问题变得更简单。

有个比较基础的坑,在循环中删除元素,这是会出问题的。假设我有一堆学生,我生日了要发出邀请,我想把所有的男生都给排除掉。

public class Student {
    public int sex; // 男是1
}
List<Student> students = new getAllStudents();
for (int i = 0; i < students.size(); i++) {
    if (students.get(i).sex == 1){
        students.remove(students.get(i));
    }
}

这样写肯定会出问题,这是一个也算是经典的BUG场景了,相信所有人都碰到过。因为我们的思路是“排除所有男生”,但是如果反着去想,这个问题也就很好解决,反着就是“保留所有女生”

List<Student> students = new getAllStudents();
List<Student> girls = new ArrayList<>();
for (int i = 0; i < students.size(); i++) {
    if (students.get(i).sex == 0){
        girls.add(students.get(i));
    }
}
students = girls;

应该没什么问题吧,我直接就在这写了,类似伪代码那种,大概懂什么意思就行,这个其实就是copy and write

虽然这个场景可能不能很好的表现出这个思路,但是意思就是如果我们开发中碰到一些问题或者复杂的逻辑流程,我们可以试着反着思考,说不定会有更好的出路。

加载全部内容

相关教程
猜你喜欢
用户评论