ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে n_rows সারি এবং n_cols কলাম সহ। এখানে সব মান প্রাথমিকভাবে 0। আমাদের flip() নামে একটি ফাংশন সংজ্ঞায়িত করতে হবে যা 0 মানটি যাদুকরীভাবে একনিষ্ঠভাবে বেছে নেয়, এটিকে 1 এ পরিবর্তন করে, এবং তারপর সেই মানের পজিশন [row.id, col.id] ফেরত দেয়। অপরerseits, আমাদের reset() নামে আরেকটি ফাংশন লিখতে হবে যা সব মান 0-এ সেট করে। আমাদের সিস্টেমের Math.random() কলের সংখ্যা ন্যূনতম রাখতে হবে এবং টাইম ও স্পেস কমপ্লেক্সিটি অপ্টিমাইজ করতে হবে।
যদি আমাদের 2x3 আকারের ম্যাট্রিক্স থাকে, এবং আমরা flip চারবার কল করি, তবে ফলাফল হবে [0,1], [1,2], [1,0], [1,1]。
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- holes নামে একটি ম্যাপ তৈরি করুন,
- ইনিশিয়ালাইজারে নিম্নলিখিত কাজ করুন
- র্যান্ডম নাম্বার জেনারেটর ইনিশিয়ালাইজ করুন, n := সারির সংখ্যা, m := কলামের সংখ্যা,
- size := n * m
- flip মেথডে, নিম্নলিখিত কাজ করুন −
- id := র্যান্ডম নাম্বার mod size, size ১ হ্রাস করুন, rid := id
- যদি id holes-এ থাকে, তবে id := holes[id]
- holes[rid] := holes[size] যখন size holes-এ থাকে অন্যথায় size
- একটি জোড়া ফেরত দিন (id / m, id mod m)
- reset মেথডে, করুন
- size := n x m, এবং holes ক্লিয়ার করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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()); }ইনপুট
কন্সট্রাক্টর 2,2 দিয়ে ইনিশিয়ালাইজ করুন এবং flip চারবার কল করুন
আউটপুট
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]
