2

聞かれました：

リスト内の各数値を残りの要素の合計に置き換えます。リストはソートされません。
のような数字のリストがある場合{2, 7, 1, 3, 8}、各要素を残りの要素の合計に置き換える必要があるとします。出力は次のようになります。

    {(7 + 1 + 3 + 8), (2 + 1 + 3 + 8), (2 + 7 + 3 + 8), (2 + 7 + 1 + 8), (2 + 7 + 1 + 3)}
==  {19, 14, 20, 18, 13}

私は明らかな解決策に答えました。
最初sumにすべての数値を評価し、次に から各要素を減算しsumます。したがって、上記のリストsumは2 + 7 + 1 + 3 + 8=21であり、出力は次のようになります。

    {sum - 2, sum - 7, sum - 1, sum - 3, sum - 8}
    {21 - 2, 21 - 7, 21 - 1, 21 - 3, 21 - 8}
==  {19, 14, 20, 18, 13}

リストを 2 回繰り返すだけで済みます。

それからインタビュアーは私に尋ねました：今度は減算なしでそれをしますか？そして私は答えることができませんでした:(

他の解決策は可能ですか？他のトリックを共有できますか？より良いトリックは可能ですか？

追加のメモリ スペースを使用できます (数分間試してみた後で質問しましたが、それでも答えられませんでした)。

4

6 に答える 6

5

1 つの可能性は、配列のプレフィックスとサフィックスの合計を計算してから、適切なエントリを結合することです。これはまだ O(n) になりますが、より多くのメモリ領域が必要になるため、元の方法の方が優れていると思います。

つまり、{2, 7, 1, 3, 8} から {2, 2+7, 2+7+1, 2+7+1+3, 2+7+1+3+8} と { 2+7+1+3+8, 7+1+3+8, 1+3+8, 3+8, 8} を入力し、適切なエントリを追加します。

于 2013-08-19T20:32:32.470 に答える
1

私はあなたのものより良いものを考えることはできません.

しかし、これはどうですか：

(n-1)xnマトリックスを作成します。

[ 2, 7, 1, 3, 8 ]

| 7, 1, 3, 8, 2 |  rotate by 1
| 1, 3, 8, 2, 7 |         by 2
| 3, 8, 2, 7, 1 |         by 3
| 8, 2, 7, 1, 3 |         by 4

次に、列を合計します

C++std::rotate_copyを使用してマトリックスを作成できます

  std::vector<int> v1 {2, 7, 1, 3, 8 };
  std::vector<int> v2 (v1.size());
  int i,j;

  std::vector< std::vector<int> > mat;  
  for (int i=1; i<v1.size();++i){
     std::rotate_copy(v1.begin(),v1.begin()+i,v1.end(),v2.begin());
     mat.push_back(v2);
    }                                            

  for(j=0;j<v1.size();++j)  
    for(i=0;i<v1.size()-2;++i)
       v2[j]+=mat[i][j];

 for(i=0;i<v2.size();++i)
  std::cout<<v2[i]<<" ";
于 2013-08-19T20:52:11.197 に答える
1

解決策は、要素以外のすべてを合計することです。その後、事後的に減算する必要はありません。現在のインデックスに要素を追加するのをスキップするだけです。

または、現在のインデックスの要素を除外するリストのサブセットを取得し、サブセットを合計するだけです。実装の詳細を追加した最初の提案とほぼ同じです。

于 2013-08-19T20:30:28.143 に答える
0 
#include <iostream.h>
#include <stdio.h>

int main() {
    int a[] = {2,7,1,3,8};

    int sum[5]={0};


     for(int j = 0; j < 5; j++){
       for(int i = 1; i < 5; i++) {
        sum[j]=sum[j]+a[(j+i+5)%5];
        }
      printf("%d ", sum[j]);  }
}
于 2013-12-11T17:41:15.407 に答える
-1

要素を減算する代わりに、-1 を掛けた要素を追加できます。掛け算と足し算は許可されていると思います。

于 2013-08-19T20:32:42.720 に答える