2024年5月LeetCode

2024-5-14

2244. 完成所有任务需要的最少轮数 – 力扣(LeetCode)

贪心算法找规律即可

Python
class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        total = 0
        tasks_dict = {}
        for i in tasks:
            if i in tasks_dict:
                tasks_dict[i]+=1
            else:
                tasks_dict[i] = 1
        for key,value in tasks_dict.items():
            if value == 1:
                return -1
            total += (value+2) // 3
        return total
C++
class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        using namespace std;
        int total = 0;
        unordered_map<int, int> tasks_map;
        for (int value : tasks){
            if(tasks_map.find(value) != tasks_map.end()){ //kv对存在
                tasks_map[value] ++;
            }
            else{
                tasks_map[value] = 1;
            }
        }
        for(const auto& pair : tasks_map){
            if(pair.second == 1) return -1;
            total += (pair.second+2) / 3;
        }
        return total;
    }
};

2024-5-15

2589. 完成所有任务的最少时间 – 力扣(LeetCode)

看了提示,分别是:
1. 按结束时间升序对任务进行排序(Sort the tasks in ascending order of end time)
2. 由于最多只有2000个时间点需要考虑,所以您可以逐个检查它们(Since there are only up to 2000 time points to consider, you can check them one by one)
3. 尽可能晚地运行任务总是有益的,这样以后的任务可以同时运行。(It is always beneficial to run the task as late as possible so that later tasks can run simultaneously.)

其中提示3很重要,也是后面的主要想法:如果在本段中暂时没有找到其他可以与之前任务同时完成的,则放在最后。
最后的思路也是这样:
如果可以在[start,end]中找到和之前任务同时完成的时间,则同时完成。
如果在本段中暂时没有找到其他可以与之前任务同时完成的,则在end前最后的几个time完成的一个点或者多个点。
(可选,时间优化:如果某个任务已经完成,即task[2]==0,则将遍历task起点移动到这个任务之后)

不过遇到了很大的问题:一直报超时错误,一开始Python使用的是列表,结果问了下ChatGPT,确实某个元素是否在Map中的时间复杂度要明显低,为O(1)但是在List中则是O(n),更换为Map就好了很多。
不过最后的结果仍然在所有解答的时间耗费中是最差的,sad

Python3
class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        sorted_tasks = sorted(tasks, key= lambda x: x[1])
        last_possible_task_index = 0
        times = {}
        for time in range(1,2001):
            for index, task in enumerate(sorted_tasks,start=last_possible_task_index):
                if time >= task[0] and time <= task[1]:
                    if time in times:
                        task[2] -= 1
                    elif (time not in times) and (task[1] - time - task[2] == -1):
                        times[time] = True
                        task[2] -= 1
                    if task[2] == 0:
                        last_possible_task_index = index+1
        return len(times)
        # 一开始是用的
        #len4  : times =[] 
        #len12 : times.append[time]
        #结果总是超过时间限制
        #改用Map之后就没事了
        #Map的查找是O(1),List的查找则是O(n)
C++
class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        using namespace std;
        int total_task_num = tasks.size();
        sort(tasks.begin(),tasks.end(),[](const vector<int>& a, const vector<int>& b){
            return a[1] < b[1];
        });
        unordered_map<int,bool> times_map;
        int last_possible_task_index = 0;
        for(int time=0; time<=2000; time++){
            for(int index=last_possible_task_index;index<total_task_num;index++){
                vector<int>& task = tasks[index];
                if(time>= task[0]&&time<=task[1]){
                    if(times_map.find(time)!=times_map.end()){
                        task[2]--;
                    }
                    else if(times_map.find(time)==times_map.end()&&task[1]-time-task[2]==-1) {
                        times_map[time] = true;
                        task[2] -= 1;
                    }
                    // if(task[2]==0){
                    //     last_possible_task_index = index;
                    // }
                } 
            }
        }
        return times_map.size();
    }
};

2024-5-16

1953. 你可以工作的最大周数 – 力扣(LeetCode)

过还是挺简单的,真的很简单,但是看起来时间和空间效率并不是很高

Python3
class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        sorted_milestones = sorted(milestones,reverse=True)
        sum_all_litter_jobs = sum(sorted_milestones[1:])
        if sum_all_litter_jobs>=sorted_milestones[0]:
            return sum(sorted_milestones)
        else:
            return sum_all_litter_jobs*2+1
C++
class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        using namespace std;
        long long all_smaller_jobs_time = 0;
        sort(milestones.begin(),milestones.end(),greater<int>());
        for(int i=1;i<milestones.size();i++){
            all_smaller_jobs_time += milestones[i];
        }
        if(milestones[0]<=all_smaller_jobs_time) return milestones[0]+all_smaller_jobs_time;
        return all_smaller_jobs_time*2+1;
    }
};

2024-5-17

826. 安排工作以达到最大收益 – 力扣(LeetCode)

我的思路是直接按照profit排序,找到profit最大的能完成的项目
标签里有个二分查找,不知道干嘛用的,不过看起来我的这个时间复杂度也有点高

Python3
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        difficulty_profit_list = []
        n = len(profit)
        total_profit = 0
        for i in range(n):
            difficulty_profit_list.append((difficulty[i],profit[i]))
        
        sorted_difficulty_profit_list = sorted(difficulty_profit_list, key=lambda x:x[1],reverse=True)
        for job in worker:
            for task in sorted_difficulty_profit_list:
                if job >= task[0]:
                    total_profit+=task[1]
                    break
        return total_profit
C++
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        using namespace std;
        long long total_profit = 0;
        vector<pair<int,int>> difficulty_profit_pair;
        int n = difficulty.size();
        for(int i=0;i<n;i++){
            difficulty_profit_pair.push_back(make_pair(difficulty[i],profit[i]));
        }

        sort(difficulty_profit_pair.begin(),difficulty_profit_pair.end(),[](const pair<int,int>& a, const pair<int,int>& b){
            return a.second>b.second;
        });
        int m = worker.size();
        for(int job=0;job<m;job++){
            for(int task=0;task<n;task++){
                if(worker[job] >= difficulty_profit_pair[task].first){
                    total_profit += difficulty_profit_pair[task].second;
                    break;
                }
            }
        }
        return total_profit;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇