LeetCode.781 森林中的兔子

题目描述:

森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你(指被提问的兔子)颜色相同?" ,将答案收集到一个整数数组 answers 中,其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ,返回森林中兔子的最少数量。

 

理解此题的关键是:

1、说出与自己颜色相同兔子数量相等的兔子划分为同一组,并且数量为n;

2、在1的基础上,从前往后遍历answers数组,当遍历到n  + 1个n,则需要重新进行计数。

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        map<int, int> m; // 另外的兔子个数,剩余的个数
        for (int i = 0; i < answers.size(); i++) {
            if (!m.count(answers[i])) {
                m[answers[i]] = answers[i]; 
            } else {
                if (m[answers[i]] > 0) {
                    m[answers[i]]--;
                } else {
                    m[answers[i]] = answers[i];
                }
            }
        }

        int cnt = answers.size();
        for (auto &[first, second]: m) {
            if (second > 0) {
                cnt += second;
            }
        }
        return cnt;
    }
};

  

上一篇:2022.01.08 模拟赛


下一篇:1582. 二进制矩阵中的特殊位置