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

leetcode每日一题

题面

  • 总体思路是:

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

    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]]=ans~~~~wers[i];
            res += (answers[i]+1);  //还有相同兔兔的数量+自己
        }
        else
        {
            ump[answers[i]]--;
        }
    }
    
    return res;

    }

评论

暂无评论