행 수가 n_rows이고 열이 n_cols인 이진 행렬이 있다고 가정합니다. 여기서 모든 값은 처음에는 0입니다. 무작위로 균일하게 0 값을 선택하고 1로 변경한 다음 해당 값의 위치 [row.id, col.id]를 반환하는 함수 flip()을 정의해야 합니다. 또한 모든 값을 다시 0으로 설정하는 또 다른 함수 reset()을 작성해야 합니다. 시스템의 Math.random() 호출 횟수를 최소화하고 시간 및 공간 복잡성을 최적화해야 합니다.
2x3 차수의 행렬이 있고 flip을 네 번 호출하면 결과는 [0,1], [1,2], [1,0], [1,1]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 구멍이라는 지도 만들기
- 이니셜라이저에서 다음을 수행합니다.
- 난수 생성기 초기화, n :=행 수, m :=열 수,
- 크기 :=n * m
- 플립 방식에서 다음을 수행합니다. -
- id :=난수 모드 크기, 크기를 1만큼 감소, rid :=id
- id가 구멍에 있으면 id :=구멍[id]
- holes[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, ]