当前位置: 首页 > news >正文

动态规划+二分查找

题目描述:给定一个区间数组,[[1,2,3],[3,4,2],[2,4,4]],每个区间有价值,求在获取k个区间的条件下面,求获得的最大的价值,关键是dp的定义和二分查找的写法(小于tar额最右下标)

import java.util.*;import java.util.*;
import java.util.*;//[[1,2,3],[3,4,2],[2,4,4]],2class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** 计算小明面试成功可能性的最大和* @param interviews int整型二维数组 interviews[i] = [startTime_i, endTime_i, possibility_i] 第 i 个面试在 startTime_i 时间开始, endTime_i 时间结束,通过的可能性是 possibility_i* @param k int整型 最多参加的面试次数* @return int整型*/
//    int [][]nums = new int[][] {{1,2,3},{3,4,2},{2,4,6}};public static void main(String[] args) {int [][]nums = new int[][] {{1,2,3},{3,4,2},{2,4,6},{3,4,9},{4,5,10}};System.out.println(maxValue(nums, 2));}public static int maxValue (int[][] interviews, int k) {// write code hereint n = interviews.length;Arrays.sort(interviews, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});int dp [][] =new int[n + 1][k + 1];for (int i = 0 ; i <= n; i++){dp[i] = new int[k + 1];}// dp[i][j] 表示前i个面试,参加了k场的总和for (int i = 1 ; i <= n ; i++){int start = interviews[i - 1][0];int index = search(0 , i -1 , start , interviews); // 前面最近的位置for (int j = 1; j <= k && j <= i; j++){dp[i][j] = Integer.max(dp[i-1][j] , dp[i][j]);if (index +1 == i) { // 本身dp[i][j] = Integer.max( interviews[i-1][2] , dp[i][j]);}else {dp[i][j] = Integer.max(dp[index + 1][j-1] + interviews[i-1][2] , dp[i][j]); // 非本身}}}return dp[n][k];}// 找出小于tar的最右下标public static int search(int left , int right , int tar , int[][] interviews){int res = right;while(left <= right){int mid = left + (right - left) / 2;int cur = interviews[mid][1];if (cur >= tar){right = mid - 1;}else {left = mid + 1;}}if (right < 0){return res;}return right;}
}

相关文章:

动态规划+二分查找

题目描述&#xff1a;给定一个区间数组&#xff0c;[[1,2,3],[3,4,2],[2,4,4]]&#xff0c;每个区间有价值&#xff0c;求在获取k个区间的条件下面&#xff0c;求获得的最大的价值&#xff0c;关键是dp的定义和二分查找的写法&#xff08;小于tar额最右下标&#xff09; import…...

8.2小非农ADP数据来袭黄金将会如何表现?

近期有哪些消息面影响黄金走势&#xff1f;黄金多空该如何研判&#xff1f; ​黄金消息面解析&#xff1a; 周二(8月1日)现货黄金价格回落&#xff0c;原因是美元指数升创7月10日以来新高至102.43.美联储官员乐观言论夯实美国经济软着陆预期。此外&#xff0c;中国刺激措施将…...

linux启动oracle

一、启动方法 方法1&#xff1a; Sql代码 cd $ORACLE_HOME/bin #进入到oracle的安装目录 ./dbstart #重启服务器 ./lsnrctl start #重启监听器 ----------------------------------- 方法2&#xff1a; &#xff08;1&#xff09; 以oracle身份登录​​数据库​​&am…...

AssetBundleBrowser导入报错解决方案

第一次导入AssetBundleBrowser遇到报错有 Assets\Scenes\AssetBundles-Browser-master\AssetBundles-Browser-master\Tests\Editor\ABModelTests.cs(13,7): error CS0246: The type or namespace name Boo could not be found (are you missing a using directive or an assem…...

vue-baidu-map-3x 使用记录

在 Vue3 TypeScript 项目中&#xff0c;为了采用 标签组件 的方式&#xff0c;使用百度地图组件&#xff0c;冲浪发现了一个开源库 ovo&#xff0c;很方便&#xff01;喜欢的朋友记得帮 原作者 点下 star ~ vue-baidu-map-3xbaidu-map的vue3/vue2版本&#xff08;支持v2.0、v…...

《GPU并行计算与CUDA编程》笔记

第一个GPU程序 #include <stdio.h>__global__ void square(float* d_out,float* d_in){int idx threadIdx.x;float f d_in[idx];d_out[idx] f * f; }int main(int argc,char** argv){const int ARRAY_SIZE 8;const int ARRAY_BYTES ARRAY_SIZE * sizeof(float);// …...

Shell编程基础(十二)函数

函数 概念定义调用函数综合脚本 概念 和其他编程语言一样&#xff0c;函数作为一种封装代码块&#xff0c;以提高代码复用性和可维护性的存在。 记住一点&#xff0c;先定义&#xff0c;再使用 定义 shell 函数的创建方式 function 函数名 空格{ xxxx return 返回码&#x…...

【雕爷学编程】MicroPython动手做(33)——物联网之天气预报3

天气&#xff08;自然现象&#xff09; 是指某一个地区距离地表较近的大气层在短时间内的具体状态。而天气现象则是指发生在大气中的各种自然现象&#xff0c;即某瞬时内大气中各种气象要素&#xff08;如气温、气压、湿度、风、云、雾、雨、闪、雪、霜、雷、雹、霾等&#xff…...

Screens 4 for mac VNC客户端 强大的远程控制工具

Screens 4 for Mac 是一款功能强大的 VNC 客户端软件&#xff0c;为 Mac 用户提供了便捷的远程访问和控制解决方案。无论您是需要远程管理服务器、办公电脑&#xff0c;还是需要远程协助他人解决问题&#xff0c;Screens 4 都是您的理想选择。 Screens 4 for Mac具备简洁直观的…...

搜索与图论(三)

一、最小生成树 1.1Prim算法 朴素版Prim 一般用于稠密图 算法流程: 集合表示当前已经在连通块的点 1.初始化距离&#xff0c;把所有距离都初始化为正无穷 2.n次迭代,找到集合外距离最小的点 ->t 3.用t来更新其它点到集合的距离 #include<iostream> #include&…...

阿里云“通义千问”开源,可免费商用

我是卢松松&#xff0c;点点上面的头像&#xff0c;欢迎关注我哦&#xff01; 阿里云成为国内首个加入大模型开源行列的大型科技企业。就在昨天&#xff0c;阿里云公开表态&#xff0c;把自家的通义千问大模型开源。 阿里云把通用70亿参数模型&#xff0c;包括Qwen-7B和对话模…...

23.7.31 牛客暑期多校5部分题解

E - Red and Blue and Green 题目大意 构造一个长度为 n n n 的序列&#xff0c;满足 m m m 个条件&#xff0c;每个条件包含三个数 l , r , w l,\space r,\space w l, r, w&#xff0c;表示区间左端点&#xff0c;区间右端点&#xff0c;这个区间的逆序对数的奇偶性&…...

Python爬虫的学习day02 requests 模块post 函数, lmxl 模块的 etree 模块

1. requests 模块post 函数 1.1 post 函数的参数 &#xff08;简单版&#xff09; 参数1&#xff1a; url 网络地址 参数2&#xff1a; data 请求数据 &#xff08;一般数据是 账号&#xff0c;密码&#xff09; 参数3&#xff1a; headers 头请求 &#xff08…...

客户流失分析预测案例 -- 机器学习项目基础篇(7)

客户流失 它是指现有的客户、用户、订阅者或任何类型的回头客停止与公司开展业务或结束与公司的关系。 客户流失的类型 合同客户流失&#xff1a;当客户签订了服务合同并决定取消服务时&#xff0c;例如有线电视&#xff0c;SaaS。自愿流失&#xff1a;当用户自愿取消服务时…...

uniapp中我使用uni.navigateTo跳转webview页面传参,但是接收的参数只有一半。

在uniapp中使用uni.navigateTo跳转webview页面传参时&#xff0c;可能会遇到接收的参数只有一半的情况。这可能是因为在跳转时&#xff0c;url的长度超过了限制。为了解决这个问题&#xff0c;可以使用encodeURIComponent和decodeURIComponent进行编码和解码。 具体的解决办法…...

使用kaminari,在列表页实现分页功能

安装 1. bundller 大于1的话&#xff0c;可以使用这个版本 gem install kaminari -v 0.16.3 或者 gem kaminari 2. 使用命令&#xff1a; $ bundle install 3. 然后使用这个命令可以创建一个config文件 $ rails g kaminari:config 4. 重新启动服务器 bundle exec rail…...

Android 性能调优之bitmap的优化

背景 Android开发中&#xff0c;加载图片过多、过大很容易引起OutOfMemoryError异常&#xff0c;即我们常见的内存溢出。因为Android对单个应用施加内存限制&#xff0c;默认分配的内存只有几M&#xff08;具体视不同系统而定&#xff09;。而载入的图片如果是JPG之类的压缩格…...

HOT74-数组中的第K个最大元素

leetcode原题链接&#xff1a;数组中的第K个最大元素 题目描述 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O…...

类与对象【中】

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;那个传说中的man的主页 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;题目大解析2 目录 &#x1f449;&#x1f3fb;类的默认6个成员函数&#x1f449;&#x1f3fb;构造…...

uni-app:实现列表单选功能

效果图&#xff1a; 核心解析&#xff1a; 一、 <view class"item_all" v-for"(item, index) in info" :key"index"><view classposition parameter-info text-over :classitem.checked?"checked_parameter":""…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...