Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで海が見える場所から建物を見つけるプログラム

さまざまな建物の高さのリストがあるとします。高さの値がheights[i]の建物は、右側のすべての建物がその建物よりも短い場合に海を見ることができます。海が見える場所から昇順で建物のインデックスを見つける必要があります。

したがって、入力が高さ=[8、12、12、9、10、6]のようである場合、インデックス2の建物の高さ12から海を見ることができるため、出力は[2、4、5]になります。インデックス10の建物の高さ10およびインデックス5の最後の建物から。

これを解決するには、次の手順に従います-

  • スタック：=新しいリスト
  • 各インデックスidxと高さhの高さについて、実行します
    • スタックが空ではなく、heights[スタックの最上部]<=hの場合、実行
      • スタックから最後の要素を削除する
  • idxをスタックにプッシュします
  • スタックを返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(heights):
   stack = []
   for idx, h in enumerate(heights):
      while stack and heights[stack[-1]] <= h:
         stack.pop()
      stack.append(idx)
   return stack

heights = [8, 12, 12, 9, 10, 6]
print(solve(heights))

入力

[8, 12, 12, 9, 10, 6]

出力

[2, 4, 5]

  1. Pythonで捕まえることができる雨の総量を見つけるためのプログラム

    n個の非負の整数の配列があるとします。これらは、各バーの幅が1である高さを表しており、雨が降った後にどれだけの水を捕まえることができるかを計算する必要があります。したがって、マップは次のようになります- ここでは、8つの青いボックスがあることがわかります。したがって、出力は8になります。 これを解決するには、次の手順に従います- スタックst、water：=0およびi：=0を定義します whilei<身長のサイズ =height [i]の場合、iをスタックにプッシュし、iを1増やします それ以外の場合 x：=スタックトップ要素、スタックからトップを削除 スタックが空でない場合

  2. Pythonで範囲内のノード数を見つけるプログラム

    BSTがあり、左と右の境界lとrもあるとすると、lとrの間に値が存在するルート内のすべてのノードの数を見つける必要があります。 したがって、入力が次のような場合 l =7、r =13の場合、8、10、12の3つのノードがあるため、出力は3になります。 これを解決するために、次の手順に従います- スタック：=スタックと最初にルートを挿入し、カウント：=0 スタックが空でないときに、実行します node：=スタックの最上位要素、およびポップ要素 ノードがnullでない場合、 l<=ノードのデータ<=rの場合、 count：=count + 1