🐡

LeetCode 605. Can Place Flowers - 貪欲法(Greedy Algorithm）で解く

2025/08/15に公開

LeetCode

tech

605. Can Place Flowers

Institution

与えれたflowerbed配列に隣接禁止でflowerをn個配置できるどうか
- flowerbed=[1,0,0,0,1]でflower=1の場合はtrue
- flowerbed=[1,0,0,0,1]でflower=2の場合はfalse
配列をすべて走査してフラグを立てて行き、結果的にflowerの数を上回ればtrueを返すようにしてみる。
- 3つずつflowerbed配列を処理しているため[1,0,0,0,1]のときにしか上手くいかない。

def can_place_flowers(flowerbed, n)
    result = 0
    index = 0
    flowerbed.each do |b|
      if b.zero?
        index = index + 1
        if index == 3
          result = result + 1
          index = 0
          return true if result == n
        end
      end
    end  
    return false   
end

3つずつではなく、対象の配列の前後を考える
- 配列で範囲外のときがあるため、終端のケアができていなかった
- 左端と右端で処理を変える必要があるため処理を追加
  - flowerbed = [0]、n = 1のパターンなどが処理できていないためパターン網羅できていない。

def can_place_flowers(flowerbed, n)
    return true if n == 0

    max = flowerbed.length 
    return false if max <= 2

    flowerbed.each.with_index do |b, index|
      if (index == 0 && b.zero? && flowerbed[index+1].zero? ) ||
          ( index == (max - 1) && b.zero? && flowerbed[index-1].zero? ) ||
          ( b.zero? && flowerbed[index-1].zero? && flowerbed[index+1].zero?)
        flowerbed[index] = 1
        n = n -  1
        return true if n == 0
      end
    end
    return false
end

パターン網羅できずに他にうまい方法があるのかと考えたが、方針としてはあっていたが条件分岐を詳細に詰めれていなかったため、解けなかった
- LeetCodeを確認してコーディング

def can_place_flowers(flowerbed, n)
    return true if n == 0
    max = flowerbed.length 

    flowerbed.each.with_index do |b, index|
      if b.zero?
        empty_left_plot = (index == 0) || (flowerbed[index-1].zero?)
        empty_right_plot = (index == (max - 1)) || (flowerbed[index+1].zero?)

        if empty_left_plot && empty_right_plot
          flowerbed[index] = 1
          n = n -  1
          return true if n == 0
         end
      end
    end
    return false
end

アプローチ

同じアルゴリズムで各言語で実装する

python

rubyコードからの改善
- flower nのデクリメントのコードになっていたため、n=0のケアが事前に必要。最後に植えることができた数>植えたい数を超える判定に修正

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                empty_left = (i == 0) or (flowerbed[i-1] == 0)
                empty_right = (i == len(flowerbed)-1) or (flowerbed[i+1] == 0)

                if empty_left and empty_right:
                    flowerbed[i] = 1
                    count += 1
        return count >= n

typescript

==と===の違い
- ===は型変換を行わないため、比較結果が予測しやすいため、基本的には===を使う

	==（等価演算子）	===（厳密等価演算子）
比較内容	値が同じかどうかを比較	値と型の両方が同じかどうかを比較
型変換	比較する前に自動的に型変換を行う	型変換を行わない
例	1 == '1' は true	1 === '1' は false
安全性	予期せぬ挙動につながることがある	予期せぬ挙動が少なく安全

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let count: number = 0;
    for(let i = 0; i<flowerbed.length; i++){
        if (flowerbed[i] === 0){
            const empty_left = (i===0) || (flowerbed[i-1] === 0);
            const empty_right = (i === flowerbed.length -1) || (flowerbed[i+1]===0);

            if (empty_left && empty_right){
                flowerbed[i] = 1;
                count++;
            }
        }
    }
    return count >= n;
};

golang

func canPlaceFlowers(flowerbed []int, n int) bool {
    var count int = 0
    for i := 0; i < len(flowerbed); i++ {
        if flowerbed[i] == 0 {
            var empty_left bool = (i == 0) || (flowerbed[i-1]==0)
            var empty_right bool = (i == len(flowerbed) - 1) || (flowerbed[i+1]==0)

            if empty_left && empty_right{
                flowerbed[i] = 1
                count++
            }
        }
    }
    return count >= n
}

学習のポイント

貪欲法(GreedyAlgorithm)という名前を知った
typescriptでは、===は型変換を行わないため安全のため利用する

「貪欲法」（Greedy Algorithm）

貪欲法とは、各ステップで局所的に最適な選択を繰り返すことで、最終的に全体としても最適な解を得ようとするアルゴリズムのこと。

今回のcan_place_flowers関数では、具体的に以下の手順で動作しています。

最初から順に確認する: 花壇の最初から最後まで、1マスずつ確認していきます。
植えられる場所を見つける: どのマスも、花が植えられていない0で、かつ、その両隣も0（または花壇の端）であれば、花を植えることができます。
すぐに植える: 植えられる場所が見つかったら、すぐにそこに花を植えて（1に変更して）、必要な花の数nを減らします。
終了: nが0になった時点で、すべての花を植えられたことになるので、trueを返して終了します。

この方法がこの問題に対して正しいのは、ある場所に花を植えることが、その両隣のマスにしか影響しないため。そのため、「今、植えられる場所に植える」という局所的な最適な選択が、全体の最適な結果（植えられる花の最大数）に繋がる。

605. Can Place Flowers

Institution

アプローチ

学習のポイント

「貪欲法」（Greedy Algorithm）

Discussion