Pythonでロボットが境界ボックス内を移動しているかどうかを確認するプログラム
ロボットの動きを表す文字列sがあるとします。ロボットは現在(0、0)の位置にあり、北を向いています。移動文字列にはこれらの文字が含まれる場合があります
- 「F」で前進方向に移動、1ユニット
- 「L」で左に90度回転
- 「R」で右に90度回転
そのため、ロボットが順番にsの動きを繰り返す場合は、ロボットが決して離れない平面にボックスがあるかどうかを確認する必要があります。
したがって、入力がs ="FFRFRFFRF"の場合、ロボットは2ユニット北に移動するため、出力はTrueになります。次に、90度右に曲がって、1ブロック移動します。次に、もう一度90度右に回転し、2ユニット南に移動してから、もう一度右に移動します。これにより、ボックスが形成されます。
これを解決するには、次の手順に従います-
- moves:=方向を含む配列[[0、-1]、[1、0]、[0、1]、[-1、0]]
- r、c:=0、0
- d:=0
- 0から3の範囲の時間については、
- 0からsのサイズの範囲のiについては、
- s[i]が"F"と同じ場合、
- (r、c):=(r + move [d、0]、c + move [d、1])
- それ以外の場合、s[i]が"L"と同じ場合、
- d:=(d + 3)mod 4
- それ以外の場合、s[i]が"R"と同じ場合、
- d:=(d + 1)mod 4
- s[i]が"F"と同じ場合、
- rが0と同じで、cが0と同じ場合、
- Trueを返す
- 0からsのサイズの範囲のiについては、
- Falseを返す
例
理解を深めるために、次の実装を見てみましょう-
def solve(s): moves = [[0, -1], [1, 0], [0, 1], [-1, 0]] r, c = 0, 0 d = 0 for times in range(4): for i in range(len(s)): if s[i] == "F": r, c = r + moves[d][0], c + moves[d][1] elif s[i] == "L": d = (d + 3) % 4 elif s[i] == "R": d = (d + 1) % 4 if r == 0 and c == 0: return True return False s = "FFRFRFFRF" print(solve(s))
入力
"FFRFRFFRF"
出力
True
-
Pythonで二分木が完成しているかどうかをチェックするプログラム
二分木があるとしましょう。これが完全な二分木であるかどうかを確認する必要があります。完全な二分木でわかっているように、レベルはノードで埋められますが、最後のレベルのノードと最後のレベルのすべてのノードが可能な限り左にある可能性があります。 したがって、入力が次のような場合 その場合、出力はTrueになります これを解決するために、次の手順に従います- q:=両端キュー qの最後にルートを挿入 フラグ:=False qが空でない間、実行します temp:=qの左側から削除した後の要素 tempがnullの場合、 フラグ:=True
-
与えられたグラフがPythonで2部グラフであるかどうかをチェックするプログラム
無向グラフが1つあるとすると、グラフが2部グラフであるかどうかを確認する必要があります。グラフのすべてのエッジ{u、v}がAに1つのノードuを持ち、Bに別のノードvを持つように、グラフのノードを2つのセットAとBに分割できる場合、グラフは2部グラフであることがわかります。 したがって、入力が次のような場合 次に、出力はTrueになり、[0,4]はセットAにあり、[1,2,3]はセットBにあり、すべてのエッジはAからAまたはBからBではなく、AからBまたはBからAになります。 。 これを解決するために、次の手順に従います- 関数dfs()を定義します。これはソースを取ります