Android開(kāi)發(fā)島嶼數(shù)量算法示例解析
前言
最近沒(méi)有什么比較好的思路,之前有寫(xiě)過(guò)關(guān)于數(shù)據(jù)結(jié)構(gòu)相關(guān)的內(nèi)容。所以想往算法這方面看不看能不能搗鼓點(diǎn)出一些開(kāi)發(fā)思路。
島嶼數(shù)量
之前接觸過(guò)一個(gè)算法,比較有意思,可以拿出來(lái)說(shuō)說(shuō),這個(gè)算法是這樣的。
給一個(gè)01矩陣,1代表是陸地,0代表海洋, 如果兩個(gè)1相鄰,那么這兩個(gè)1屬于同一個(gè)島。我們只考慮上下左右為相鄰。(島嶼: 相鄰陸地可以組成一個(gè)島嶼(相鄰:上下左右) 判斷島嶼個(gè)數(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。因?yàn)?相連的就3塊
那這道題要如何做呢,其實(shí)有個(gè)思路,我去遍歷二維數(shù)組,判斷到如果為1,我就把與1相連的上下左右都置0,這樣在接下來(lái)的遍歷中就不會(huì)受到已統(tǒng)計(jì)數(shù)量的影響。
如果只聽(tīng)這樣的描述還是沒(méi)理解也沒(méi)關(guān)系,可以看看代碼,我這是用java寫(xiě)的,挺簡(jiǎn)單的,應(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); } } } }
那能從這個(gè)算法中學(xué)會(huì)什么呢?學(xué)會(huì)了這道算法,被問(wèn)到就有題庫(kù)了【狗頭】,那也太血虧了,還是要擴(kuò)展一下思路。
我覺(jué)得有意思的地方在于,它是通過(guò)一個(gè)反向的思路,去設(shè)置狀態(tài),以此來(lái)把這個(gè)問(wèn)題變得更簡(jiǎn)單。
有個(gè)比較基礎(chǔ)的坑,在循環(huán)中刪除元素,這是會(huì)出問(wèn)題的。假設(shè)我有一堆學(xué)生,我生日了要發(fā)出邀請(qǐng),我想把所有的男生都給排除掉。
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)); } }
這樣寫(xiě)肯定會(huì)出問(wèn)題,這是一個(gè)也算是經(jīng)典的BUG場(chǎng)景了,相信所有人都碰到過(guò)。因?yàn)槲覀兊乃悸肥?ldquo;排除所有男生”,但是如果反著去想,這個(gè)問(wèn)題也就很好解決,反著就是“保留所有女生”
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)該沒(méi)什么問(wèn)題吧,我直接就在這寫(xiě)了,類似偽代碼那種,大概懂什么意思就行,這個(gè)其實(shí)就是copy and write
雖然這個(gè)場(chǎng)景可能不能很好的表現(xiàn)出這個(gè)思路,但是意思就是如果我們開(kāi)發(fā)中碰到一些問(wèn)題或者復(fù)雜的邏輯流程,我們可以試著反著思考,說(shuō)不定會(huì)有更好的出路。
以上就是Android開(kāi)發(fā)島嶼數(shù)量算法示例解析的詳細(xì)內(nèi)容,更多關(guān)于Android開(kāi)發(fā)島嶼數(shù)量算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Android隨手筆記44之JSON數(shù)據(jù)解析
本文將主要介紹在Android開(kāi)發(fā)中,如何在服務(wù)器端創(chuàng)建JSON數(shù)據(jù),以及如何在Android客戶端對(duì)JSON數(shù)據(jù)進(jìn)行解析,對(duì)android json解析 相關(guān)知識(shí)感興趣的朋友一起學(xué)習(xí)吧2015-12-12Java實(shí)現(xiàn)Andriod帶看括弧的計(jì)算器代碼
這篇文章主要介紹了Java實(shí)現(xiàn)Andriod帶看括弧的計(jì)算器代碼的相關(guān)資料,需要的朋友可以參考下2016-03-03關(guān)于Android Device Monitor 無(wú)法打開(kāi)問(wèn)題
大家好,本篇文章主要講的是關(guān)于Android Device Monitor 無(wú)法打開(kāi)問(wèn)題,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下2022-01-01android實(shí)現(xiàn)定位與目的地的導(dǎo)航示例代碼
本篇文章主要介紹了android實(shí)現(xiàn)定位與目的地的導(dǎo)航示例代碼,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-02-02Kotlin開(kāi)發(fā)的一些實(shí)用小技巧總結(jié)
Kotlin 是一個(gè)基于 JVM 的新編程語(yǔ)言,用 JetBrains 的話來(lái)說(shuō)是「更現(xiàn)代化、更強(qiáng)大,所以下面這篇文章主要給大家總結(jié)介紹了關(guān)于Kotlin的一些開(kāi)發(fā)實(shí)用小技巧,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面來(lái)一起看看吧。2017-10-10不允許錯(cuò)過(guò)的Anndroid技術(shù)經(jīng)驗(yàn)60條
不允許錯(cuò)過(guò)的Anndroid技術(shù)經(jīng)驗(yàn)60條,與大家分享,希望可以提高大家Android開(kāi)發(fā)水平,感興趣的朋友可以參考一下2016-02-02Android編程實(shí)現(xiàn)圖標(biāo)拖動(dòng)效果的方法
這篇文章主要介紹了Android編程實(shí)現(xiàn)圖標(biāo)拖動(dòng)效果的方法,涉及Android事件響應(yīng)及圖標(biāo)變換的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11簡(jiǎn)單實(shí)現(xiàn)Android驗(yàn)證碼
在登錄或者注冊(cè)的時(shí)候要求輸入驗(yàn)證碼,這篇文章主要為大家詳細(xì)介紹了如何簡(jiǎn)單實(shí)現(xiàn)Android驗(yàn)證碼的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-12-12Android Studio實(shí)現(xiàn)單選對(duì)話框
這篇文章主要為大家詳細(xì)介紹了Android Studio實(shí)現(xiàn)單選對(duì)話框,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05