每日一题_781.森林中的兔子

leetcode每日一题

1.png

• 总体思路是：

1. 我们只需要考虑: 每一个 【兔兔自己】 与 【和此兔兔同种类兔兔的数量】，如样例{1, 1, 1}每个兔兔都有一个和自己颜色相同的兔兔，满足最少条件的话，我们应该尽量把更多的兔兔归到同种颜色里
2. 所以考虑用【哈希表】，哈希的下标表示【兔兔的种类】(详见代码), 我们把声称还有k个和自己同色的兔兔归为一类可以保证最优解， else特判: 如上例{1, 1, 1} 我们只能把两个兔兔归为一种颜色，所以当ump[index]为0的时候代表【这类兔兔已经计算完了，开始计算新的兔兔了】

int numRabbits(vector<int>& answers) {
        int len=answers.size();
        if (len==0) return 0;

        int res=0;
        unordered_map<int, int > ump;
        for (int i=0; i<len; ++i)
        {
            if (ump[answers[i]]==0)
            {
                ump[answers[i]]=answers[i];
                res += (answers[i]+1);  //还有相同兔兔的数量+自己
            }
            else
            {
                ump[answers[i]]--;
            }
        }

        return res;
    }