Giả sử chúng ta có một chuỗi S với 'L', 'R' và các chữ số từ 0 đến 9. Hãy xem xét có một khách sạn có 10 phòng, chúng được đánh số từ 0 đến 9, từ trái sang phải. Khách sạn có hai lối vào - một lối vào từ phía bên trái và một lối vào từ phía bên phải. Khi một khách hàng đến khách sạn qua lối vào bên trái, họ sẽ nhận được một phòng trống gần lối vào bên trái nhất. Tương tự, khi khách hàng đến khách sạn qua lối vào bên phải, họ sẽ nhận được một phòng trống gần lối vào bên phải nhất. Nhưng chúng tôi đã làm mất danh sách phân công phòng. Nhưng chúng tôi nhớ tất cả các khách hàng:khách hàng đến khi nào, từ lối vào nào và khi nào họ rời khách sạn. Ban đầu khách sạn trống rỗng. Chúng tôi phải khôi phục danh sách chỉ định phòng từ bộ nhớ. Trong S, 'L' có nghĩa là người đến từ phía bên trái, nếu là 'R' thì người đó đến từ phía bên phải và chữ số d cho biết khách hàng rời khỏi phòng d. Chúng tôi phải trả lại tình trạng phòng. Một chuỗi có độ dài là 10 và độ dài bằng 0, nghĩa là không gian trống, nếu không thì nó đã bị chiếm dụng.
Vì vậy, nếu đầu vào là S ="LLRL1RL1", thì đầu ra sẽ là "1010000011", bởi vì
Trước hết, tất cả các phòng đều trống. Trạng thái 0000000000.
L - Khách hàng đến khách sạn qua lối vào bên trái. Trạng thái 1000000000.
L - Khách hàng từ lối vào bên trái. Trạng thái 1100000000.
R - Khách hàng từ lối vào bên phải. Trạng thái 1100000001.
L - Khách hàng từ lối vào bên trái. Trạng thái 1110000001.
1 - Khách hàng ở phòng 1 rời đi. Trạng thái 1010000001.
R - Khách hàng từ lối vào bên phải. Trạng thái 1010000011.
L - Khách hàng từ lối vào bên trái. Trạng thái 1110000011.
1 - Khách hàng ở phòng 1 rời đi. Trạng thái 1010000011.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
n := size of S a := "0000000000" for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is same as 'L', then: set left most 0 in a to 1 if S[i] is same as 'R', then: set right most 0 in a to 1 Otherwise set S[i]th place in a to 0 return a
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
string solve(string S) {
int n = S.size();
string a = "0000000000";
for (int i = 0; i < n; i++) {
if (S[i] == 'L')
a[a.find('0')] = '1';
if (S[i] == 'R')
a[a.rfind('0')] = '1';
else
a[S[i] - '0'] = '0';
}
return a;
}
int main() {
string S = "LLRL1RL1";
cout << solve(S) << endl;
} Đầu vào
"LLRL1RL1"
Đầu ra
1010000011