奇奇怪怪的题

1.LeetCode 41.缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

示例 1:

输入:nums = [1,2,0]
输出:3
示例 2:

输入:nums = [3,4,-1,1]
输出:2
示例 3:

输入:nums = [7,8,9,11,12]
输出:1

提示:

  • 0 <= nums.length <= 300
  • -231 <= nums[i] <= 231 - 1
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
            int n=nums.size();
            for(int i=0;i<n;i++){
                while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
                    swap(nums[i],nums[nums[i]-1]);
                }
            }
            
            for(int i=0;i<n;i++){
                if(i+1!=nums[i]){
                    return i+1;
                }
            }
                
            return n+1;
    }
};

2.多路归并

1.LeetCode5703.最大平均通过率

一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] = [passi, totali] ,表示你提前知道了第 i 个班级总共有 totali 个学生,其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ,表示额外有 extraStudents 个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

示例 1:

输入:classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出:0.78333
解释:你可以将额外的两个学生都安排到第一个班级,平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2:

输入:classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出:0.53485

提示:

  • 1 <= classes.length <= 105
    classes[i].length == 2
  • 1 <= passi <= totali <= 105
  • 1 <= extraStudents <= 105
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
            struct Node{
                double v;
                int a,b;
                bool operator< (const Node& t)const{
                    return v<t.v;
                }
            };
            priority_queue<Node> heap;
            double sum=0;
            for(auto &c:classes){
                int a=c[1],b=c[0];
                sum+=(double)b/a;
                heap.push({(a-b)/(a*(a+1.0)),a,b});
            }
            while(extraStudents--){
                auto t=heap.top();
                heap.pop();
                sum+=t.v;
                int a=t.a+1,b=t.b+1;
                heap.push({(a-b)/(a*(a+1.0)),a,b});
            }
            return sum/classes.size();
    }
};

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×