当先锋百科网

首页 1 2 3 4 5 6 7

剑指offer-day2

题1：小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一:

使用当前带宽下载插件
将带宽加倍（下载插件数量随之加倍）
请返回小扣完成下载 n 个插件最少需要多少分钟。

注意：实际的下载的插件数量可以超过 n 个

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/Ju9Xwi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

c++实现.

class Solution {
public:
    int leastMinutes(int n) {
    int cur = 1;
    int res = 0;

    while(n>0){
        if(n<=cur){
            n -= cur;
            res += 1;
        }
        else{
            res += 1;
            cur *= 2;
        }
    }
    
    return res;
    }
};

python实现.

class Solution:
    def leastMinutes(self, n: int) -> int:
        
        cur = 1

        res = 0

        while n > 0:
            if n <= cur:
                n -= cur
                res += 1

            else:
                res += 1
                cur *= 2
            
        return res

题2：有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目，整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。

若每位扣友选择不同的一题，请返回被选的 N 道题目至少包含多少种知识点类型。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/WqXACV
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
c++实现.

class Solution {
public:
    int halfQuestions(vector<int>& questions) {
        int half = questions.size()/2;
        vector<int> v(1001);
        for(int q:questions) v[q]++;
        sort(v.begin(), v.end());
        int times = 0;
        for(int i = 1000; half > 0; i--){
            half -= v[i];
            times++;
        }
        return times;
    }
};

python实现.

class Solution:
    def halfQuestions(self, questions: List[int]) -> int:
        dic = collections.Counter(questions)
        n = len(questions)
        m = n / 2
        times = 0
        for val in sorted(list(dic.values()))[::-1]:
            if m >= val:
                m -= val
                times += 1
            elif m == 0:
                return times
            else:
                return times + 1