Số lượng ếch tối thiểu chui rúc trong C ++

Giả sử chúng ta có một chuỗi gọi là croakOfFrogs, điều này đại diện cho sự kết hợp của chuỗi "tiếng kêu" từ các con ếch khác nhau, nhiều con ếch có thể kêu cùng một lúc, do đó nhiều "tiếng kêu" được trộn lẫn. Chúng ta phải tìm ra số con ếch khác nhau tối thiểu để hoàn thành tất cả các con ếch trong chuỗi đã cho.

Ở đây, "tiếng kêu" hợp lệ có nghĩa là một con ếch đang tạo ra 5 chữ cái ‘c’, ’r’, ’o’, ’a’, ’k’ một cách tuần tự. Những con ếch phải tạo ra tất cả năm chữ cái để hoàn thành một tiếng kêu. Nếu chuỗi không phải là chuỗi "croak" hợp lệ thì trả về -1.

Vì vậy, nếu đầu vào giống như "crcoakroak", thì đầu ra sẽ là 2 vì con ếch đầu tiên có thể kêu "crcoakroak". Con ếch thứ hai sau đó có thể hét lên "crcoakroak".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ m

• Xác định một mảng ch có kích thước:5 gán nó với {'c', 'r', 'o', 'a', 'k'}

• temp:=0, ret:=0

• đối với mỗi phần tử c trong s, thực hiện

  • (tăng m [c] lên 1)

  • maxVal:=m [ch [0]]

  • để khởi tạo i:=0, khi tôi <5, hãy cập nhật (tăng i lên 1), thực hiện -

    • nếu maxVal

      • trả về -1

    • maxVal:=m [ch [i]]

  • nếu c giống với 'c' thì -

    • (tăng nhiệt độ lên 1)

  • ngược lại khi c giống với 'k' thì -

    • (giảm nhiệt độ xuống 1)

  • ret:=tối đa ret và tạm thời

• để khởi tạo i:=1, khi tôi <5, hãy cập nhật (tăng i lên 1), thực hiện -

  • nếu m [ch [0]] không bằng m [ch [i]] thì -

    • trả về -1

• trả lại ret

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;
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"));
}

Đầu vào

"crcoakroak"

Đầu ra

2