leetcode 1235

2024-05-06 12:20
文章标签 leetcode 1235

本文主要是介绍leetcode 1235，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1235

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

class Solution {
public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {int n = startTime.size();vector<vector<int>> jobs(n);for(int i=0; i<n; i++){jobs[i] = {startTime[i], endTime[i], profit[i]};}sort(jobs.begin(), jobs.end(), [](const vector<int>&job1, const vector<int>&job2){return job1[1] < job2[1]; });vector<int> dp(n+1);for(int i=1; i<=n; i++){//找到结束时间大于i-th job的开始时间的job id, 因为是有序的，所以id 可以转为对应的job数量, dp[2th job] 表示前两个job的最优解答，局部最优成为全局最优解答int k = upper_bound(jobs.begin(), jobs.begin()+i-1, jobs[i-1][0], [](int st, vector<int>& job){return st < job[1];}) - jobs.begin();dp[i] = max(dp[i-1], dp[k] + jobs[i-1][2]);}return dp[n];}
};

例子

在这里插入图片描述
遍历已经排序过的jobs, dp[0] =0;
1,3,20, -> dp[1] = 20
2,3,50 -> dp[2] = 50
4,6,70 -> dp[3] = dp[2] + 70 = 120
6,9,60 -> dp[4] = dp[3] + 60 = 180
3,10,100 -> dp[5] = max (dp[4], dp[2] +100) =180

upper_bound

std::upper_bound 函数在 C++ 标准库 <algorithm> 头文件中定义。以下是一个可能的实现：

template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{ForwardIt it;typename std::iterator_traits<ForwardIt>::difference_type count, step;count = std::distance(first, last);while (count > 0) {it = first;step = count / 2;std::advance(it, step);if (!comp(value, *it)) {first = ++it;count -= step + 1;} else {count = step;}}return first;
}

这段代码展示了 std::upper_bound 的基本工作原理。它采用了二分查找的方法，在已排序的范围 [first, last) 中查找第一个大于 value 的元素。

参数解释：

  • first：范围的起始迭代器
  • last：范围的终止迭代器
  • value：要查找的值
  • comp：比较函数对象，用于定义元素的比较方式

该实现假设了输入的迭代器是随机访问迭代器，因此可以使用 std::advance 和 std::distance 来计算迭代器之间的距离和移动迭代器。实际的标准库实现可能会更加复杂，并且会根据不同的情况进行优化。

upper_bound(jobs.begin(), jobs.begin()+i-1, jobs[i-1][0], [](int st, vector<int>& job){return st < job[1];})

和

upper_bound(jobs.begin(), jobs.begin()+i-1, jobs[i-1][0], [](int st, vector<int>& job){return st > job[1];})

的区别：
这两个 upper_bound 函数调用的区别在于它们所使用的比较函数对象的不同。这些函数都是用来在已排序的序列中查找某个值的上界的。让我们分析一下这两个调用：

  1. 第一个调用使用的比较函数是 [](int st, vector<int>& job){ return st < job[1]; }，它的作用是比较给定的时间 st 和任务的结束时间 job[1]。这个比较函数适用于在结束时间升序排序的情况下查找 st 的上界，即在 jobs 中找到第一个结束时间大于 st 的任务的位置。

  2. 第二个调用使用的比较函数是 [](int st, vector<int>& job){ return st > job[1]; }，它的作用是比较给定的时间 st 和任务的结束时间 job[1]。这个比较函数适用于在结束时间降序排序的情况下查找 st 的上界，即在 jobs 中找到第一个结束时间小于 st 的任务的位置。

所以，这两个调用的区别在于它们所使用的比较函数导致了不同的排序顺序和查找逻辑。

函数对象介绍

函数对象是指可以像函数一样被调用的对象。在C++中，函数对象可以是函数指针、函数、Lambda 表达式或重载了函数调用运算符 operator() 的类对象。

函数对象可以作为参数传递给标准库中的算法，如 std::sort、std::find_if 等，用于指定算法的行为。这种方式使得算法更加灵活，可以根据不同的需求使用不同的比较方式或操作方式。

以下是一些关于函数对象的重要概念和用法：

  1. 函数调用运算符 operator()：重载了这个运算符的类对象可以像函数一样被调用。当对象被调用时，operator() 会被执行。

  2. Lambda 表达式：Lambda 表达式是一种轻量级的匿名函数，可以用于创建临时的函数对象。它可以在需要函数对象的地方直接定义，使代码更加简洁。

  3. 标准库算法：标准库提供了许多算法，如排序、查找、变换等，这些算法通常都可以接受函数对象作为参数，用于指定算法的行为。

  4. 适配器：函数对象可以通过适配器来改变其行为，如 std::bind 可以用于绑定参数，std::not1 可以用于对谓词取反等。

函数对象的灵活性和可重用性使得它们在C++中被广泛应用于各种场景，包括算法、事件处理、回调函数等。

可调用对象

可调用对象是指可以像函数一样被调用的对象。在 C++ 中，可调用对象可以是函数、函数指针、成员函数指针、函数对象（仿函数）、Lambda 表达式等。它们都可以在调用时像函数一样被执行。

不同类型的可调用对象：

  1. 函数：最基本的可调用对象，就是传统的函数。
int add(int a, int b) {return a + b;
}
  1. 函数指针：指向函数的指针，可以像函数一样被调用。
int (*funcPtr)(int, int) = add;
int result = funcPtr(3, 4); // 调用函数指针
  1. 成员函数指针：指向类的成员函数的指针。
class MyClass {
public:int multiply(int a, int b) {return a * b;}
};int (MyClass::*memFuncPtr)(int, int) = &MyClass::multiply;
MyClass obj;
int result = (obj.*memFuncPtr)(3, 4); // 调用成员函数指针
  1. 函数对象（仿函数）：重载了函数调用运算符 operator() 的类对象，可以像函数一样被调用。
class Add {
public:int operator()(int a, int b) {return a + b;}
};Add addObj;
int result = addObj(3, 4); // 调用函数对象
  1. Lambda 表达式：匿名函数，可以直接在需要的地方定义和使用，也可以像函数一样被调用。
auto lambda = [](int a, int b) { return a + b; };
int result = lambda(3, 4); // 调用 Lambda 表达式

在 C++ 中，可调用对象的灵活性和多样性使得它们可以适用于各种不同的场景，例如作为算法的参数、事件处理、回调函数等。

lower_bound 和 upper_bound 的区别？

lower_bound 和 upper_bound 在功能上有所区别，尽管它们都是用于在有序序列中进行查找的算法：

  1. lower_bound：

    • 返回的是第一个大于或等于给定值的元素的位置。
    • 如果在序列中找不到大于或等于给定值的元素，则返回指向序列末尾的迭代器。
    • 如果序列中存在多个等于给定值的元素，lower_bound 会返回它们中第一个元素的位置。

  2. upper_bound：

    • 返回的是第一个大于给定值的元素的位置。
    • 如果在序列中找不到大于给定值的元素，则返回指向序列末尾的迭代器。
    • 如果序列中存在多个等于给定值的元素，upper_bound 会返回大于这些元素的第一个位置。

因此，lower_bound 返回的位置可能是等于给定值的元素的位置，而 upper_bound 则一定是大于给定值的元素的位置。这两个函数在处理有序序列时很有用，尤其是在需要进行范围查询或插入操作时。

sort 函数

std::sort 是 C++ 标准库中的一个算法，位于 <algorithm> 头文件中，用于对序列进行排序。它采用的是快速排序（Quicksort）或者堆排序（Heapsort）等效率较高的排序算法。

std::sort 函数的函数签名如下：

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

其中：

  • first 和 last 是表示要排序的序列的迭代器范围，即 [first, last)，它们定义了要排序的区间。

std::sort 函数会按照默认的升序规则对指定的序列进行排序。

要按照降序规则排序，可以通过传递一个自定义的比较函数作为第三个参数。比较函数应当返回一个布尔值，指示其第一个参数是否应该排在第二个参数之前。如果第一个参数应排在第二个参数之前，则返回 true；否则，返回 false。

以下是一个示例，展示如何使用 std::sort 对序列进行升序和降序排序：

#include <iostream>
#include <algorithm>
#include <vector>// 自定义比较函数，用于降序排序
bool descending(int a, int b) {return a > b;
}int main() {std::vector<int> vec = {5, 2, 9, 3, 7};// 升序排序std::sort(vec.begin(), vec.end());std::cout << "Ascending order: ";for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;// 降序排序std::sort(vec.begin(), vec.end(), descending);std::cout << "Descending order: ";for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

在这个示例中，我们首先使用 std::sort 对序列进行升序排序，然后再次调用 std::sort，但这次传递了自定义的比较函数 descending，从而实现了降序排序。

这篇关于leetcode 1235的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/964339。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...
【JavaScript】LeetCode：21-25

【JavaScript】LeetCode：21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心：连续和（count）< 0时，放弃当前起点的连续和，将下一个数作为新起点，这里提供使用贪心算法解决本题的代码。动态规划：dp[i]：以nums[i]为结尾的最长连续子序列（子数组）和。 dp[i] = max(dp[i - 1]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2