LeetCode 0605. Can Place Flowers

Leetcode：Java

概要

題目：Can Place Flowers

難度：Easy

本文

說明

題目會給我們一個整數「n」以及一個僅包含「0」跟「1」的「整數數列」。

而該「整數數列」作為一「長形花圃」的示意，其中每一格陣列位置都代表著一塊地，若該塊地上已經被種植「花」，則會在數列中，以「1」表示；反之，若該塊地尚未種植「花」，仍為空地，則以「0」表示，圖如下：

另外，整數「n」則代表目前「待栽種」的花的數量。

而題目的需求是，倘若我們可以將「花」任意地種植在「長形花圃」中的任一「空地」上，但必須符合一個條件，就是「花」與「花」之間不能相鄰；那麼在滿足條件的情況下，我們是否能夠將「花」全數種植到「長形花圃」中，若可以的話則返回「是」，反之，則返回「否」。

解析一、暴力破解法

首先是「暴力破解法」。

既然都說是「暴力破解」了，其概念就是直接、粗暴，其作法就是針對「長形花圃」中的每塊「地」逐一判斷。

其具體作法是，將代表「長形花圃」的「陣列」一一遍歷，若當前索引已經有「花」，直接略過，若當前索引是「空地」，就進一步判斷該索引的前後格，是否也為「空地」，若是，將之種花，再往後判斷，直到「花」被全部種植到「花圃」中，或是「長形花圃」遍歷結束，實作代碼如下：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length && n != 0; i++)
            if (flowerbed[i] == 0 && // 代表當前格為空
                    (i == 0 || flowerbed[i - 1] == 0) && // 第一格 or 前一格
                    (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) { // 最後一格 or 後一格
                flowerbed[i++] = 1; // 當種植花以後，下一格必定不能種植花
                n--;
            } else if (flowerbed[i] == 1) i++; // 當前為「花」，下一格必定不能種植花
        return n == 0;
    }
}

上述的代碼雖然相當直觀，但有幾點我們還是稍微說明一下。

首先是「邊界處理」，即「長形花圃」中索引為「0」與「flowerbed.length() - 1」的位置，由於它們位處於邊界，因此，當其在做「前後是否為的空地的檢查」時，須要特別注意例外的判斷。

另外一個「優化」的實現，其概念是這樣的，若當前索引的「位置」，已經是「花」，或是要「被種植為花」；那麼，該位置的下一格位置必須為「空地」，所以我們可以直接略過「下一格」的判斷，示意圖如下：

解析二、連續空地計算法

事實上，「連續空地計算法」是一種「暴力破解法」的變形。

試想一下，「禁止花與花相鄰」這個限制，是不是也能夠解讀成「須有連續三個空地才能種植一朵花」？

簡單說，我們是不是可以將「空地-花-空地」的組合視為「一組花」，其概念圖如下：

所以其作法是，先建立一個「flag」參數，將其作為「連續空地」的計數器；當「flag」為「1」時，則代表是該空地是連續空地的「第一塊」，而當「flag」為「2」時，則代表是該空地是連續空地的「第二塊」；而當「flag」等於「3」時，則代表該已經有三塊連續空地，此時，我們可以將其中間的那塊空地種植上花。

依照上述概念，程式碼實作如下：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int idx = 0, flag = 1; // 起點
        do {
            if (flowerbed[idx] == 1) { // 代表空格有花
                idx++;
            } else if (++flag == 3) { // 代表空格無花且已經累積連續三塊空地
                n--; // 種花
            } else continue;
            flag = 1;
        } while (++idx < flowerbed.length && n != 0);
        // 末端
        if (n == 1 && flowerbed[flowerbed.length - 1] == 0 && flag > 1) return true;
        return n == 0;
    }
}

在上述代碼中，有幾個地方要注意。

首先是「邊界處理」，例如「起點」與「終點」，由於「起點」與「終點」是「數列邊界」，而題目的限制是，「禁止花與花相鄰」，所以，我們其實可以將邊界外視為「一塊空地」，如下圖：

先說明「起點」的部分，因為我們將邊界外視為「一塊空地」，這也意味著，當我們在索引「首項」時，其已經累積「一塊連續空地」了，也就是說，我們只須要須將「flag」初始值設置為「1」即可，圖如下：

終點的概念也是，但由於邏輯的因素，其在程式碼的撰寫上，就特地以藉由判斷式來判斷，即上面完整代碼中迴圈之後的判斷式的內容。

另外，我們來稍微說明一下「flag」的控制邏輯，當我們開始遍歷後，會遇到兩種情況，第一種是遇到「花」，這時候不管已經「連續」幾塊空地，反正都要重算，對吧？所以，將「flag」歸零。

但仔細思考一下，我們剛剛有說過，「花」的下一格，必須為空地，所以我們可以略過其判斷，此外，該空地也可以視為「下一組」的第一塊連續空地；所以我們可以將索引加「1」，同時「flag」也加「1」，如下：

剛才說第一種情況是遇到「花」，而另外一種情況就是遇到「空地」，那這也會存在兩種情況，其一是當前這塊空恰為「第三塊」的連續空地；這也就意味著，我們湊齊「一組」連續空地，可以種一朵花了。

但要注意，我們是種植在「連續三塊空地」中的「第二塊」空地；所以「第三塊空地」必然還是空地，既然是空地，我們當然可以將它視為下一個「連續三塊空地」的「第一塊空地」，概念與前述遇到「花」的情況是類似的，所以我們也可以將索引加「1」，同時「flag」也加「1」。

但倘若該塊空地不是「第三塊」的連續空地呢？

那還不簡單，「flag」加「1」，收工。

其實至此，本文已經結束；但有一個想法，其實筆者覺得很酷，跟大家分享一下。

在前面的邊界判斷中，為了避免「IndexOutOfBoundsException」的發生，因此我們都需要額外的「判斷式」，但記得我們說過嗎？

我們可以將邊界視為「空地」，所以，我們是不是可以將「長型花圃」加大。

基於「連續空地計算法」的代碼來修改，如下：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] newFlowerbed = Arrays.copyOf(flowerbed, flowerbed.length + 1);

        for (int i = 0, flag = 1; i < newFlowerbed.length && n != 0; i++) {
            if (newFlowerbed[i] == 1) i++;
            else if (++flag == 3) n--;
            else continue;
            flag = 1;
        }
        return n == 0;
    }
}

由於其前邊界是處理方式是將「flag」初始值設置為「1」，所以我們就不改寫了，關鍵是是後邊界的部分。

所以我們產生了一個長度多「1」的新陣列，其前面「數值」全部相同，而其多出來最後一項，因為視為空地，所以值設置為「0」；如此一來，我們就可以直接判斷到原陣列長度，也不會發生「IndexOutOfBoundsException」。

剩餘的邏輯都一樣，只是此處筆者手癢，改以「for」迴圈來實作而已。

tags: leetcode java easy