Android開發(fā)島嶼數(shù)量算法示例解析
前言
最近沒有什么比較好的思路,之前有寫過關于數(shù)據(jù)結(jié)構(gòu)相關的內(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ù)量的影響。
如果只聽這樣的描述還是沒理解也沒關系,可以看看代碼,我這是用java寫的,挺簡單的,應該能很容易看懂。
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);
}
}
}
}
那能從這個算法中學會什么呢?學會了這道算法,被問到就有題庫了【狗頭】,那也太血虧了,還是要擴展一下思路。
我覺得有意思的地方在于,它是通過一個反向的思路,去設置狀態(tài),以此來把這個問題變得更簡單。
有個比較基礎的坑,在循環(huán)中刪除元素,這是會出問題的。假設我有一堆學生,我生日了要發(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;
應該沒什么問題吧,我直接就在這寫了,類似偽代碼那種,大概懂什么意思就行,這個其實就是copy and write
雖然這個場景可能不能很好的表現(xiàn)出這個思路,但是意思就是如果我們開發(fā)中碰到一些問題或者復雜的邏輯流程,我們可以試著反著思考,說不定會有更好的出路。
以上就是Android開發(fā)島嶼數(shù)量算法示例解析的詳細內(nèi)容,更多關于Android開發(fā)島嶼數(shù)量算法的資料請關注腳本之家其它相關文章!
相關文章
Flutter基于Dart Unwrapping Multiple Optional小技巧
這篇文章主要為大家介紹了Flutter Unwrapping Multiple Optional打開多個選項小技巧示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-12-12
Android實現(xiàn)向Launcher添加快捷方式的方法
這篇文章主要介紹了Android實現(xiàn)向Launcher添加快捷方式的方法,涉及Android添加快捷方式的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-09-09
Android ListView實現(xiàn)無限循環(huán)滾動
這篇文章主要為大家詳細介紹了Android ListView實現(xiàn)無限循環(huán)滾動,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2020-06-06
Android優(yōu)化查詢加載大數(shù)量的本地相冊圖片
本文介紹了Android優(yōu)化查詢加載大數(shù)量的本地相冊圖片,可以方便的照片的查詢,,感興趣的小伙伴們可以參考一下。2016-10-10
Android 自定義彈性ListView控件實例代碼(三種方法)
關于在Android中實現(xiàn)ListView的彈性效果,有很多不同的方法,網(wǎng)上一搜,也有很多,下面貼出在項目中經(jīng)常用到的兩種實現(xiàn)ListView彈性效果的方法(基本上拿來就可以用),需要的朋友參考下本段代碼2016-01-01

