0

グリッドが与えられた場合、ロボットがX、Y（座標）の両方の桁の合計がKよりも小さいポイントを探索できる場合、ロボットがナビゲートできるポイントの数を見つけます。

1つの明白な解決策はO（n ^ 2）です。（2D行列をループし、条件に基づいて点を受け入れる/無視する）その他は、配列内の0からK-1の要素を取り、合計が次のようになる2つの要素を見つけることです。 K.はO（k）空間とO（k）時間を含みます。

誰もが時空の観点から何かを改善する、より良いアプローチを提案できますか？より良い答えを探しています。

4

1 に答える 1

5

この方程式は、北西の点から南東の点まで、グリッドの対角線x+y = Kを定義します。

x + y=Kグラフ

グリッド内のポイントがすべてとの整数値でxありy、K整数でもある場合、対角線（x+y < K）の南のポイントの数はになりますK(K-1)/2。

x+y <= K対角線（ ）を含むグリッド内のポイントの数はになりますK(K+1)/2。

明らかに、これは定数時間で計算されO(1)ます。

于 2012-10-28T13:15:53.240 に答える