Giả sử trên một bàn có N thẻ, với một số nguyên dương được in trên cả hai mặt của mỗi thẻ (có thể khác nhau). Chúng tôi phải lật bất kỳ số lượng thẻ nào, và sau khi chúng tôi chọn một thẻ. Nếu số X ở mặt sau của quân bài đã chọn không nằm ở mặt trước của bất kỳ quân bài nào, thì số X được gọi là tốt. Chúng ta phải tìm số nhỏ nhất là số tốt? Khi không có số nào là tốt, trả về 0. Ở đây, mặt trước [i] và mặt sau [i] đại diện cho số ở mặt trước và mặt sau của thẻ i. Một lần lật sẽ hoán đổi số trước và số sau, vì vậy giá trị ở mặt trước bây giờ nằm ở mặt sau và ngược lại.
Vì vậy, nếu đầu vào giống như trước =[1,2,4,4,7] và sau =[1,3,4,1,3], thì đầu ra sẽ là 2. Vì vậy, nếu chúng ta lật thẻ thứ hai, giá trị phía trước sẽ là [1,3,4,4,7], và phía sau sẽ là [1,2,4,1,3]. Chúng tôi sẽ chọn thẻ thứ hai, có số 2 ở mặt sau và nó không nằm ở mặt trước của bất kỳ thẻ nào, vì vậy 2 là một số tốt.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- xác định một tập hợp s, n:=kích thước của mặt trước, ret:=inf
- cho tôi trong phạm vi từ 0 đến n - 1
- nếu front [i] =back [i], thì chèn front [i] vào s
- cho tôi trong phạm vi từ 0 đến n - 1
- if front [i] in set then ret:=tối thiểu ret và front [i]
- cho tôi trong phạm vi từ 0 đến n - 1
- nếu back [i] không được đặt thì ret:=tối thiểu ret và back [i]
- trả về 0 khi ret =inf, nếu không thì ret.
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;
class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
set <int> s;
int n = fronts.size();
int ret = INT_MAX;
for(int i = 0; i < n; i++){
if(fronts[i] == backs[i])s.insert(fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(fronts[i]) == 0) ret = min(ret, fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(backs[i]) == 0) ret = min(ret, backs[i]);
}
return ret == INT_MAX? 0 : ret;
}
};
main(){
vector<int> v1 = {1,2,4,4,7};
vector<int> v2 = {1,3,4,1,3};
Solution ob;
cout << (ob.flipgame(v1, v2));
} Đầu vào
[1,2,4,4,7] [1,3,4,1,3]
Đầu ra
2