จำนวนกบขั้นต่ำใน C++

สมมติว่าเรามีสตริงที่เรียกว่า croakOfFrogs ซึ่งแสดงถึงการรวมกันของสตริง "croak" จากกบที่แตกต่างกัน กบหลายตัวสามารถบ่นได้พร้อมกัน ดังนั้น "croak" หลายตัวจึงผสมกัน เราต้องหาจำนวนกบให้น้อยที่สุดเพื่อทำการบ่นให้จบในสตริงที่กำหนด

ในที่นี้ "บ่น" ที่ถูกต้องหมายความว่ากบกำลังสร้าง 5 ตัวอักษร 'c', 'r', 'o', 'a', 'k' ตามลำดับ กบต้องสร้างตัวอักษรทั้งห้าตัวเพื่อจบการบ่น หากสตริงนั้นไม่ใช่สตริง "croak" ที่ถูกต้อง ให้คืนค่า -1

ดังนั้น ถ้าอินพุตเป็นเหมือน "crcoakroak" ผลลัพธ์จะเป็น 2 เนื่องจากกบตัวแรกสามารถตะโกน "crcoakroak" กบตัวที่สองสามารถตะโกนว่า "crcoakroak" ในภายหลัง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่ m

• กำหนดขนาดอาร์เรย์:5 กำหนดด้วย {'c', 'r', 'o', 'a', 'k'}

• temp :=0, ret :=0

• สำหรับแต่ละองค์ประกอบ c ใน s ทำ

  • (เพิ่ม m[c] ขึ้น 1)

  • maxVal :=m[ch[0]]

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <5 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

    • ถ้า maxVal

      • กลับ -1

    • maxVal :=m[ch[i]]

  • ถ้า c เหมือนกับ 'c' แล้ว −

    • (เพิ่มอุณหภูมิขึ้น 1)

  • มิฉะนั้นเมื่อ c เหมือนกับ 'k' แล้ว −

    • (ลดอุณหภูมิลง 1)

  • ret :=สูงสุดของ ret และ temp

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <5 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า m[ch[0]] ไม่เท่ากับ m[ch[i]] แล้ว −

    • กลับ -1

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minNumberOfFrogs(string s) {
      map<char, int> m;
      char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
      int temp = 0;
      int ret = 0;
      for (auto& c : s) {
         m[c]++;
         int maxVal = m[ch[0]];
         for (int i = 0; i < 5; i++) {
            if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
               return -1;
            }
            maxVal = m[ch[i]];
         }
         if (c == 'c') {
            temp++;
         }
         else if (c == 'k') {
            temp--;
         }
         ret = max(ret, temp);
      }
      for (int i = 1; i < 5; i++) {
         if (m[ch[0]] != m[ch[i]])
            return -1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minNumberOfFrogs("crcoakroak"));
}

อินพุต

"crcoakroak"

ผลลัพธ์

2