共通の差異を持つ配列内の正の整数シーケンス2 たとえば2 4 6 8 ここで、各数字をその正方形で置き換えます。計算を効率的に実行します。 私はこの質問をインタビューで尋ねられ、2の倍数の演算であるためビット演算子を使って彼にo(n)解を与えました。より良い方法があればお勧めします。シーケンス内の正方形の数字
答えて
いいですが再帰的です。 :-)
(n+2)(n+2) = n**2 + 4*n + 4 // and you got n**2
@Chrisが修正されました – Anycorn
@aaa:ごめんなさい、私のコメントを削除しました。ただ編集するつもりでした:) –
+1 - これは面接官が得ていたものだと思います。しかし、私は、これを利用するプログラムが単純な乗算を使うプログラムよりも高速になるとは思っていません。数値がプリミティブ型の整数型を使って表現されていると仮定します。 IMO、これはかなり不自由な質問です。「巧妙な」回答を提供する人を除外することが目的でない限り。 –
class Square
{
public static int[] sequence(int[] array)
{
int[] result=new int[array.length];
for(int i=0;i<array.length;i++)
{
result[i]=array[i]*array[i];
}
return result;
}
}
// test cases:
// Square.sequence(new int[]{2,4,6,8})
//out put->{ 4, 16, 36, 64 }
あなたのアプラックを詳しく説明してください。 –
本当にインタビュアーに依存していて、彼らが「正しいこと」と思っています。それが私だったら、(n < < 2)+ 4がきちんとしていたと思っていたのですが、反対に私は自分のコードでそれを見るのは嫌です。メンテナンスにはもっと多くの考えが必要です。良いオプティマイザがまったくいい仕事をする可能性もあります。
私は、「効率的な操作を実行する」というフレーズは、インタビュアーが速い計算を求めていた可能性が高いと考えています。それはまだO(n)ですが、2つのO(n)アルゴリズムを比較するとき、係数が再び重要になることを忘れないようにしてください。
- 1. 正方形内のポイントC++
- 2. 文字列内のシーケンスの出現数を数えるには?
- 3. 2つの数字の間の完全な正方形
- 4. 配列内の数字のシーケンスを見つける
- 5. 与えられた範囲内の数字のシーケンスを作る
- 6. 点リスト内の正方形を検出
- 7. Pythonのデザイン - 数字がシーケンス内に現れる回数を追跡し、複数のシーケンスを反復する
- 8. CでFactorial While whileループ内の数字の正方形を見つける方法は?
- 9. シーケンス内の非ASCII文字を置き換える方法は?
- 10. 数字のシーケンスの後のr - grep OR
- 11. 正方形と十字の内外の(x、y)を求めるアルゴリズム
- 12. 数字の中で最大の正方形を見つける方法(Java)
- 13. C++のstd ::文字列内の文字/シーケンスを別の文字シーケンスに置き換えます。
- 14. tcpdfは文字列の括弧内に正方形を生成します
- 15. 文字シーケンスのインスタンス数をカウントする
- 16. 科学記法と数字のシーケンス
- 17. YAML複数行の文字列シーケンス
- 18. ルア - 数字のシーケンスを生成する
- 19. 数字の繰り返しシーケンス
- 20. シーケンスの文字数を生成する
- 21. 英数字シーケンスの作成Oracle SQL
- 22. JavaScript:関数内の実行シーケンス
- 23. 文字列の数値シーケンスを取得するための小さな修正
- 24. 正方形のフォーカスカラー
- 25. 正方形の枠
- 26. 1文字の正方形を作成する方法
- 27. 三角形、正方形、円の下の整数点の数を見つける
- 28. 正方形内の2つの三角形のクリック可能な領域
- 29. c#正規表現文字列内の数字のみ
- 30. 正方形の行と列(f.e.正方形34)
「各数字を四角で置き換えてください」という意味を明確にすることはできますか?配列のすべての要素を少なくとも1回訪問して更新する必要があるので、これはΩ(n)時間かかる必要があります。具体的に最適化しようとしているのは何ですか? – templatetypedef
@aboveええ私がやったのと同じアプローチ。私はちょうどビット賢明な演算子でそれをやっているよりも数字を正方形にする方法があることを知りたかった。 –
Ummmmm ...私はあなたのスクエアリングアルゴリズムを取得するか分からない。あなたはそれを説明しようと思いますか?具体的にどのようにビットごとの操作を使用する? –