Android開發(fā)島嶼數(shù)量算法示例解析

更新時間：2023年03月01日 10:52:15 作者：流浪漢kylin

這篇文章主要為大家介紹了Android開發(fā)島嶼數(shù)量算法示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

前言

最近沒有什么比較好的思路，之前有寫過關(guān)于數(shù)據(jù)結(jié)構(gòu)相關(guān)的內(nèi)容。所以想往算法這方面看不看能不能搗鼓點出一些開發(fā)思路。

島嶼數(shù)量

之前接觸過一個算法，比較有意思，可以拿出來說說，這個算法是這樣的。

給一個01矩陣，1代表是陸地，0代表海洋，如果兩個1相鄰，那么這兩個1屬于同一個島。我們只考慮上下左右為相鄰。（島嶼: 相鄰陸地可以組成一個島嶼（相鄰:上下左右）判斷島嶼個數(shù)。）

比如

輸入

[
[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塊

那這道題要如何做呢，其實有個思路，我去遍歷二維數(shù)組，判斷到如果為1，我就把與1相連的上下左右都置0，這樣在接下來的遍歷中就不會受到已統(tǒng)計數(shù)量的影響。

如果只聽這樣的描述還是沒理解也沒關(guān)系，可以看看代碼，我這是用java寫的，挺簡單的，應(yīng)該能很容易看懂。

public class Solution {
    /**
     * 判斷島嶼數(shù)量
     * @param grid char字符型二維數(shù)組
     * @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);
            }
        }
    }
}

那能從這個算法中學(xué)會什么呢？學(xué)會了這道算法，被問到就有題庫了【狗頭】，那也太血虧了，還是要擴展一下思路。

我覺得有意思的地方在于，它是通過一個反向的思路，去設(shè)置狀態(tài)，以此來把這個問題變得更簡單。

有個比較基礎(chǔ)的坑，在循環(huán)中刪除元素，這是會出問題的。假設(shè)我有一堆學(xué)生，我生日了要發(fā)出邀請，我想把所有的男生都給排除掉。

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));
    }
}

這樣寫肯定會出問題，這是一個也算是經(jīng)典的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;

應(yīng)該沒什么問題吧，我直接就在這寫了，類似偽代碼那種，大概懂什么意思就行，這個其實就是copy and write

雖然這個場景可能不能很好的表現(xiàn)出這個思路，但是意思就是如果我們開發(fā)中碰到一些問題或者復(fù)雜的邏輯流程，我們可以試著反著思考，說不定會有更好的出路。

以上就是Android開發(fā)島嶼數(shù)量算法示例解析的詳細內(nèi)容，更多關(guān)于Android開發(fā)島嶼數(shù)量算法的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: