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