Giả sử chúng ta có một ma trận nhị phân với n_rows số hàng và n_cols số cột. Ở đây tất cả các giá trị ban đầu là 0. chúng ta phải xác định một hàm flip () chọn ngẫu nhiên đồng nhất một giá trị 0, thay đổi nó thành 1, rồi trả về vị trí [row.id, col.id] của giá trị đó. Ngoài ra, chúng ta phải viết một hàm reset () khác đặt tất cả các giá trị về 0. Chúng ta phải cố gắng giảm thiểu số lượng lệnh gọi đến Math.random () của hệ thống và tối ưu hóa độ phức tạp về thời gian và không gian.
Nếu chúng ta có ma trận bậc 2x3 và chúng ta gọi là lật bốn lần, thì kết quả sẽ là [0,1], [1,2], [1,0], [1,1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Tạo một bản đồ được gọi là lỗ,
- Trong trình khởi tạo, hãy làm như sau
- khởi tạo trình tạo số ngẫu nhiên, n:=số hàng, m:=số cột,
- kích thước:=n * m
- Trong phương pháp lật, hãy thực hiện như sau -
- id:=kích thước mod số ngẫu nhiên, giảm kích thước đi 1, rid:=id
- nếu id có trong lỗ, thì id:=lỗ [id]
- lỗ [rid]:=lỗ [kích thước] khi kích thước trong lỗ bằng kích thước khác
- trả về một cặp (id / m, id mod m)
- Trong phương pháp đặt lại, hãy thực hiện
- kích thước:=n x m và xóa các lỗ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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());
} Đầu vào
Initialize the constructor using 2,2 and call flip four times
Đầu ra
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]