กระต่ายในป่าใน C++

สมมติว่าในป่า กระต่ายแต่ละตัวมีสีอยู่บ้าง ตอนนี้กระต่ายบางชุด (อาจทั้งหมด) จะบอกเราว่ากระต่ายตัวอื่นๆ มีสีเหมือนกันกี่ตัว คำตอบเหล่านั้นจะอยู่ในอาร์เรย์ เราต้องหาจำนวนกระต่ายขั้นต่ำที่สามารถอยู่ในป่าได้ ดังนั้นหากอินพุตเป็น [1,1,2] ผลลัพธ์จะเป็น 5 เนื่องจากกระต่ายสองตัวที่ตอบว่า "1" ซึ่งทั้งคู่อาจมีสีเดียวกัน ให้พูดว่า สีขาว ตอนนี้กระต่ายกว่าตอบว่า "2" สีขาวไม่ได้ มิฉะนั้นคำตอบจะไม่สอดคล้องกัน สมมติว่ากระต่ายที่ตอบว่า "2" เป็นสีดำ จากนั้นควรมีกระต่ายสีดำอีก 2 ตัวในป่าที่ไม่ตอบในแถว ดังนั้นจำนวนกระต่ายที่น้อยที่สุดในป่าคือ 5:3 ที่ตอบบวก 2 ที่ไม่ได้

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

• สร้างแผนที่ m และ n :=ขนาดของอาร์เรย์ ans
• ตั้งค่า ret เป็น 0
• สำหรับ i ในช่วง 0 ถึง n – 1
  • x :=ans[i]
  • ถ้า x =0 ให้เพิ่ม ret โดย 1 และข้ามส่วนถัดไปของการทำซ้ำนี้
  • ถ้า m มี x ให้เพิ่ม ret โดย (x + 1) ตั้งค่า m[x] :=0
  • อย่างอื่น
    • เพิ่ม m[x] ขึ้น 1
    • ถ้า m[x] =x ให้ลบ x ออกจาก m
• คืนสินค้า

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numRabbits(vector<int>& ans) {
      map <int, int> m;
      int n = ans.size();
      int ret = 0;
      for(int i = 0; i < n; i++){
         int x = ans[i];
         if(x == 0){
            ret++;
            continue;
         }
         if(!m.count(x)){
            ret += (x + 1);
            m[x] = 0;
            }else{
               m[x]++;
           if(m[x] == x){
               m.erase(x);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.numRabbits(v));
}

อินพุต

[1,1,2]

ผลลัพธ์

5