สมมติว่าเรามีสตริง S ความยาว n ตัวอักษร S มีตัวอักษรภาษาอังกฤษพิมพ์เล็กและตัวอักษร ')' สตริงเป็น "น่ารังเกียจ" (bad) ถ้าจำนวนตัวอักษร ')' ที่ท้ายสตริง มากกว่าจำนวนตัวอักษรที่เหลืออย่างเคร่งครัด เราต้องตรวจสอบว่า S เป็น bad หรือไม่
เช่น ถ้าค่าที่ป้อนเข้าเป็น S = "fega))))))" ผลลัพธ์จะได้ True เพราะนี่เป็น bad เพราะมีตัวอักษร 4 ตัว และ ')' 6 ตัว
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
ans := 0 n := ขนาดของ S i := n - 1 ในขณะที่ (i >= 0 และ S[i] เท่ากับ ')') ทำ: (ลด i ลง 1) z := n - 1 - i ans := 2 * z - n ถ้า ans > 0 แล้ว: คืนค่า true มิฉะนั้น คืนค่า false
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; bool solve(string S) { int ans = 0; int n = S.size(); int i = n - 1; while (i >= 0 && S[i] == ')') i--; int z = n - 1 - i; ans = 2 * z - n; if (ans > 0) return true; else return false; } int main() { string S = "fega))))))"; cout << solve(S) << endl; }
ข้อมูลนำเข้า
"fega))))))"
ข้อมูลส่งออก
1
