สมมติว่าเรามีสตริง S ที่มี 'L', 'R' และตัวเลขตั้งแต่ 0 ถึง 9 พิจารณาว่ามีโรงแรมที่มีห้องพัก 10 ห้องซึ่งมีตัวเลขตั้งแต่ 0 ถึง 9 จากซ้ายไปขวา โรงแรมมีทางเข้าสองทาง ทางหนึ่งจากด้านซ้าย และอีกทางจากด้านขวา เมื่อลูกค้ามาถึงโรงแรมผ่านทางทางเข้าด้านซ้าย พวกเขาจะได้ห้องว่างใกล้กับทางเข้าด้านซ้ายที่สุด ในทำนองเดียวกัน เมื่อลูกค้ามาถึงโรงแรมทางทางเข้าขวา ก็จะได้ห้องว่างใกล้กับทางเข้าขวาที่สุด แต่เราทำรายการมอบหมายห้องหาย แต่เราจำลูกค้าได้ทุกคน:เมื่อลูกค้ามาถึง จากทางเข้าใด และเมื่อพวกเขาออกจากโรงแรม ตอนแรกโรงแรมว่างเปล่า เราต้องกู้คืนรายชื่อห้องจากหน่วยความจำ ในภาษา S 'L' หมายถึงบุคคลที่มาจากด้านซ้าย หากเป็น 'R' เขา/เธอมาจากด้านขวา และหลัก d หมายถึงลูกค้าออกจากห้อง d เราต้องคืนสถานะห้อง สตริงที่มีความยาว 10 และเท่ากับ 0 หมายความว่าห้องว่าง มิฉะนั้น จะไม่ว่าง
ดังนั้น หากอินพุตเป็น S ="LLRL1RL1" ผลลัพธ์จะเป็น "1010000011" เพราะ
ก่อนอื่นทุกห้องจะว่างเปล่า สถานะ 0000000000
L – ลูกค้ามาถึงโรงแรมโดยใช้ทางเข้าด้านซ้าย สถานะ 1000000000
L – ลูกค้าจากทางเข้าด้านซ้าย สถานะ 1100000000
R – ลูกค้าจากทางเข้าด้านขวา สถานะ 1100000001
L – ลูกค้าจากทางเข้าด้านซ้าย สถานะ 11100001
1 – ลูกค้าในห้อง 1 ออกไป สถานะ 1000000001
R – ลูกค้าจากทางเข้าด้านขวา สถานะ 10000000001
L – ลูกค้าจากทางเข้าด้านซ้าย สถานะ 1110000011
1 – ลูกค้าในห้อง 1 ออกไป สถานะ 1010000011
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
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
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
"LLRL1RL1"
ผลลัพธ์
1010000011
