📢前言

• 🌲 每天打卡一道算法題，既是一個(gè)學(xué)習(xí)過(guò)程，又是一個(gè)分享的過(guò)程😜
• 🌲 提示：本專欄解題 編程語(yǔ)言一律使用 C# 和 Java 兩種進(jìn)行解題
• 🌲 要保持一個(gè)每天都在學(xué)習(xí)的狀態(tài)，讓我們一起努力成為算法大神吧🧐！
• 🌲 今天是力扣算法題持續(xù)打卡第58天🎈！

🌲原題樣例：島嶼的周長(zhǎng)

給定一個(gè)row x col的二維網(wǎng)格地圖 grid，其中：grid[i][j] = 1表示陸地， grid[i][j] = 0 表示水域。

網(wǎng)格中的格子 水平和垂直方向相連（對(duì)角線方向不相連）。整個(gè)網(wǎng)格被水完全包圍，但其中恰好有一個(gè)島嶼（或者說(shuō)，一個(gè)或多個(gè)表示陸地的格子相連組成的島嶼）。

島嶼中沒(méi)有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。
格子是邊長(zhǎng)為 1 的正方形。網(wǎng)格為長(zhǎng)方形，且寬度和高度均不超過(guò) 100 。計(jì)算這個(gè)島嶼的周長(zhǎng)。

示例1:

輸入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
輸出：16
解釋：它的周長(zhǎng)是上面圖片中的 16 個(gè)黃色的邊

示例 2：

輸入：grid = [[1]]
輸出：4

示例 3：

輸入：grid = [[1,0]]
輸出：4

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 為 0 或 1

🌻C#方法：排序

使用return nums.Sum() - nums.Min() * nums.Length;就可以搞定，但是Sum會(huì)溢出

所以修改為以下代碼，遍歷一遍即可！

代碼：

public class Solution {
    public int MinMoves(int[] nums) {
             int iSum = nums.Min() * nums.Length * -1;
            foreach (var num in nums)
            {
                iSum += num;
            }
            return iSum;
    }
}

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：156 ms，在所有 C# 提交中擊敗了53.85%用戶
內(nèi)存消耗：48.1 MB，在所有 C# 提交中擊敗了23.08%的用戶

🌻Java 方法一：迭代

思路解析

• 對(duì)于一個(gè)陸地格子的每條邊，它被算作島嶼的周長(zhǎng)當(dāng)且僅當(dāng)這條邊為網(wǎng)格的邊界或者相鄰的另一個(gè)格子為水域。

• 因此，我們可以遍歷每個(gè)陸地格子，看其四個(gè)方向是否為邊界或者水域，

• 如果是，將這條邊的貢獻(xiàn)（即 111）加入答案 ans\textit{ans}ans 中即可。

代碼：

class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; ++k) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            cnt += 1;
                        }
                    }
                    ans += cnt;
                }
            }
        }
        return ans;
    }
}

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：8 ms，在所有 Java  提交中擊敗了74.95%的用戶
內(nèi)存消耗：40 MB，在所有 Java 提交中擊敗了43.71%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O( nm )，其中 n 為數(shù)組長(zhǎng)度，k 為最大值和最小值的差。
空間復(fù)雜度：O( 1) 

🌻Java 方法二：深度優(yōu)先搜索

思路解析

• 我們也可以將方法一改成深度優(yōu)先搜索遍歷的方式，此時(shí)遍歷的方式可擴(kuò)展至統(tǒng)計(jì)多個(gè)島嶼各自的周長(zhǎng)。

• 需要注意的是為了防止陸地格子在深度優(yōu)先搜索中被重復(fù)遍歷導(dǎo)致死循環(huán)，

• 我們需要將遍歷過(guò)的陸地格子標(biāo)記為已經(jīng)遍歷過(guò)，下面的代碼中我們?cè)O(shè)定值為 2 的格子為已經(jīng)遍歷過(guò)的陸地格子。

代碼：

class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ans += dfs(i, j, grid, n, m);
                }
            }
        }
        return ans;
    }

    public int dfs(int x, int y, int[][] grid, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(tx, ty, grid, n, m);
        }
        return res;
    }
}

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：12 ms，在所有 Java  提交中擊敗了10.09%的用戶
內(nèi)存消耗：40.4 MB，在所有 Java 提交中擊敗了6.29%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O( nm )
空間復(fù)雜度：O( nm ) 

💬總結(jié)

• 今天是力扣算法題打卡的第五十八天！
• 文章采用 C#和 Java 兩種編程語(yǔ)言進(jìn)行解題
• 一些方法也是參考力扣大神寫(xiě)的，也是邊學(xué)習(xí)邊分享，再次感謝算法大佬們
• 那今天的算法題分享到此結(jié)束啦，明天再見(jiàn)！