C++のランダムフリップマトリックス

n_rowsの行数とn_colsの列数のバイナリ行列があるとします。ここでは、すべての値が最初は0です。0の値をランダムに均一に選択して1に変更し、その値の位置[row.id、col.id]を返す関数flip（）を定義する必要があります。また、すべての値を0に戻す別の関数reset（）を作成する必要があります。システムのMath.random（）の呼び出し回数を最小限に抑え、時間とスペースの複雑さを最適化する必要があります。

次数2x3の行列があり、flipを4回呼び出すと、結果は[0,1]、[1,2]、[1,0]、[1,1]になります。

これを解決するには、次の手順に従います-

• 穴と呼ばれる地図を作成します
• 初期化子で、次の手順を実行します
• 乱数ジェネレーターの初期化、n：=行数、m：=列数、
• サイズ：=n * m
• フリップ方式では、次のようにします-
• id：=乱数modサイズ、サイズを1減らし、rid：=id
• idが穴に存在する場合、id：=hole [id]
• 穴[rid]：=穴[サイズ]の場合は穴のサイズ、それ以外の場合はサイズ
• ペアを返す（id / m、id mod m）
• リセット方法では、次のようにします
• サイズ：=n x m、穴を空ける

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   unordered_map <int, int> holes;
   int n;
   int m;
   int size;
   Solution(int n_rows, int n_cols) {
      srand(time(NULL));
      n = n_rows;
      m = n_cols;
      size = n * m;
   }
   vector<int> flip() {
      int id = rand() % size;
      size--;
      int rid = id;
      if(holes.count(id)){
         id = holes[id];
      }
      holes[rid] = holes.count(size) ? holes[size] : size;
      return {id / m, id % m};
   }
   void reset() {
      size = n * m;
      holes.clear();
   }
};
main(){
   Solution ob(2,2);
   print_vector(ob.flip());
   print_vector(ob.flip());
   print_vector(ob.flip());
   print_vector(ob.flip());
}

入力

Initialize the constructor using 2,2 and call flip four times

出力

[1, 1, ]
[0, 0, ]
[1, 0, ]
[0, 1, ]