360先端校招2019筆記試験プログラミング問題

360は牛客網ではなく自分のサイトで筆記試験をしています.なぜ筆記試験がサブ関数ではなく入出力の形式が好きなのか分からないが、jsアナログ入出力のインタフェースを提供しているが、自分のコンパイラでデバッグできないため、一般的にエラーが発生するのは面倒で、人の目でdebugははははははははは.人がそうした以上,私たちも人に適応しなければならない.私にとってjavaを書くのは久しぶりで、jsの代わりにc++かcで簡単な筆記試験問題をするしかありません.
フロントエンドはアルゴリズムをあまり重視していません.実際の業務面では確かにバックエンドのアルゴリズムが偏っているので、問題は50の選択問題、2つのプログラミング問題です.大体言ってもいいです.
第1題は行列をあげて、行列の上の要素の数字は相応の位置を代表していくつかの小さいブロックを重ねました.最後に表面積を求めさせます.解決の構想:3つの面を投影して、正側の上の面積*2はすぐで、1列ごとに最大値を求めます

#include 
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  int arr[N][M];
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      cin >> arr[i][j];
    }
  }
  //   
  int sum = 0;
  int part1 = 0, part2 = 0;
  for(int j = 0; j < M; j++) {
    int max = 0;
    for(int i = 0; i < N; i++) {
      if(arr[i][j] > max) {
        max = arr[i][j];
      } 
    }
    part1 += max;
  }
  //   
  for(int i = 0; i < N; i++) {
    int max = 0;
    for(int j = 0; j < M; j++) {
      if(arr[i][j] > max) {
        max = arr[i][j];
      }
    }
    part2 += max;
  }
  sum = part1 * 2 + part2 * 2 + M * N * 2;
  cout << sum << endl;

}

第2題は2つの数を与えて、m進数の、各位の上の数字は順序を変えて、加算した後の最大の値を出すことができます.あるビットがキャリーする必要がある場合は、型mですが、キャリーしません.例えば:1 2 3 1 2 3 3 3 0四進数の場合、演算は1 3 3 2 0 3 3 3に調整すべきで、結果は3321です
問題を解く構想:当時、問題を解く時間は比較的にきつくて、多く考える暇もなくて、最も頭のない暴力を選んで解く.forサイクルは各ビット数を対応する数に加算し、欲張りアルゴリズムは、高位を優先的に満たす値が最大であり、1ビットを出すたびに2つの加算数を除去する(c++の中で私は直接値を-1に設定することを選択した).

#include 
using namespace std;
int main() 
{
  int n, m; 
  cin >> n >> m;
  int arr1[n], arr2[n], result[n]; 
  for(int i = 0; i < n; i++) {
    cin >> arr1[i];
  }
  for(int i = 0; i < n; i++) {
    cin >> arr2[i];
  }
  for(int t = 0; t < n; t++) {
    int max = 0;
    int cur_i, cur_j;
    for(int i = 0; i < n; i++) {
      if(arr1[i] == -100) {
        continue;
      } 
      for(int j = 0; j < n; j++) {
        if(arr2[j] == -100) {
          continue;
        }
        int result = (arr1[i] + arr2[j]) % m;
        if(result > max) {
          max = result;
          cur_i = i;
          cur_j = j
        }
      }
    }
    result[t] = max;
    arr1[cur_i] = -1;
    arr2[cur_j] = -1;
  }
  for(int t = 0; t < n; t++) {
    cout << result[t] << ' ';
  }
}

時間的複雑度:n 2+(n−1)2+(n−2)2+..+1 2=n(n+1)(2 n+1)6≒n 3 n^2+(n−1)^2+(n−2)^2+…+1^2=frac{n(n+1)(2 n+1)}{6}approx n^3 n 2+(n−1)2+(n−2)+・+12=6 n(n+1)≒n 3正直、複雑度が悪く、良いアルゴリズムではない.主に最適化可能な部分は、後のサイクルが前のサイクルで計算された値を複数回繰り返し計算することにある.したがって、キャッシュまたはダイナミックプランニングを使用することを想定しています.
考えられる1つの方法は、1番目の加算値が配列Aであり、2番目の加算値が配列Bであると仮定することである.配列Aの各要素について、配列Bの要素を繰り返し使用するかどうかにかかわらず、配列Bの要素に加算しようとします.次に,B中のX元素を繰り返し用いると,A中のどの元素がB中のX元素に加算されて得られる値が最も大きいかを見ることが分かった.X元素をロックして、更に選択されることを許さないで、残りのXのAの中の元素は再びBの中でX以外の元素を選択しなければなりません.例えば、3 2 1 0 1 0 0 0 4進法は3を0とする以外は、Aの中の2、1、0はすべてBの中の1を望んで、そこで2は1を得て、Aの中の残りの1、0は再び選択しなければなりません.しかし、これは必ず隠れた危険を招きます.もし多くの桁数があれば、再び同じものを選ぶかもしれません.そして、毎回1人しか鍵をかけられず、毎回元より1人少ないものを選び直すことになります.時間の複雑さはあまり変わっていないような気がしますが、コードは暴力的な解よりずっと複雑です.
学生に相談した結果、新しい解決策は、上下2行の各数字が何個あるかを統計し、最大の数が得られるかから探すことです.such as
3
2
1
0
1
1
1
1
0
0
1
3
3を配合したのは3+0,2+1,1+2,0+3(m回)で、nビットの複雑度はO(n+nm)で、私の前のn 3 n^3 n 3の複雑度よりずっと良いです.