【LeetCode每日一题合集】2023.8.28-2023.9.3(到家的最少跳跃次数)

文章目录

  • 57. 插入区间
  • 823. 带因子的二叉树
    • 解法——递推
  • 1654. 到家的最少跳跃次数(BFS,🚹最远距离上界的证明)
  • 1761. 一个图中连通三元组的最小度数
  • 2240. 买钢笔和铅笔的方案数
    • 解法1——完全背包
    • 解法2——枚举买了几支钢笔(推荐解法)
  • 2511. 最多可以摧毁的敌人城堡数目
    • 解法——一次遍历
  • 1921. 消灭怪物的最大数量(贪心)

57. 插入区间

https://leetcode.cn/problems/insert-interval/
在这里插入图片描述
提示:
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5

当前区间与要加入的新区间之间的关系只有两种可能:相交或者不相交。

如果相交,将两者结合即可。
如果不相交,判断新加入的区间是否在当前区间之前,如果是,就先加入答案。

遍历一遍之后,如果没有处理过新加入的区间,就说明新区间应该加在最后。

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if (intervals.length == 0) return new int[][]{newInterval};List<int[]> ans = new ArrayList<>();int s = newInterval[0], e = newInterval[1];boolean f = false;for (int[] interval: intervals) {int a = interval[0], b = interval[1];// 和 newInterval 相交if (b >= s && a <= e) {f = true;a = Math.min(a, s);b = Math.max(b, e);}// 不相交 newInterval 在此区间之前if (a > e) {if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < s) {ans.add(newInterval);f = true;}}if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < a) ans.add(new int[]{a, b});else ans.get(ans.size() - 1)[1] = b;}// 如果没有处理过 newIntervalif (!f) ans.add(newInterval);return ans.toArray(new int[ans.size()][2]);}
}

823. 带因子的二叉树

https://leetcode.cn/problems/binary-trees-with-factors/
在这里插入图片描述
提示:
1 <= arr.length <= 1000
2 <= arr[i] <= 10^9
arr 中的所有值 互不相同

解法——递推

将元素排序之后,从小到大依次处理各个数值作为根节点时的二叉树数量。

class Solution {final long MOD = (long)1e9 + 7;public int numFactoredBinaryTrees(int[] arr) {Arrays.sort(arr);int n = arr.length;long ans = 0;Map<Integer, Long> m = new HashMap<>();         // 存储每个数字作为根节点时的二叉树数量for (int i = 0; i < n; ++i) {long cnt = 1;for (int j = 0; j < i; ++j) {               // 枚举儿子节点if (arr[i] % arr[j] == 0 && m.containsKey(arr[i] / arr[j])) {cnt = (cnt + m.get(arr[j]) * m.get(arr[i] / arr[j])) % MOD;}}ans = (ans + cnt) % MOD;m.put(arr[i], cnt);}return (int)ans;}
}

1654. 到家的最少跳跃次数(BFS,🚹最远距离上界的证明)

https://leetcode.cn/problems/minimum-jumps-to-reach-home/description/
在这里插入图片描述

提示:
1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden 中所有位置互不相同。
位置 x 不在 forbidden 中。

可以证明,一定可以在[0, max(f + a + b, x + b)] 的下标范围内找到最优解,其中 f 是最远进制点的坐标。
因为 f, a, b, x <= 2000,故搜索范围不会超过 6000。(证明略,我也没整明白)

用 bfs 计算最短路。

class Solution {public int minimumJumps(int[] forbidden, int a, int b, int x) {Set<Integer> s = new HashSet<>();for (int v: forbidden) s.add(v);Deque<int[]> q = new ArrayDeque<>();q.offer(new int[]{0, 1});       // 将起点放入队列final int N = 6000;boolean[][] vis = new boolean[N][2];vis[0][1] = true;for (int ans = 0; !q.isEmpty(); ++ans) {for (int t = q.size(); t > 0; --t) {int[] p = q.poll();int i = p[0], k = p[1];// 到达了目的地,直接返回答案if (i == x) return ans;List<int[]> nxt = new ArrayList<>();nxt.add(new int[]{i + a, 1});// 如果上一步 不是向后跳,那么这一步可以向后跳if ((k & 1) == 1) nxt.add(new int[]{i - b, 0});for (int[] e: nxt) {int j = e[0];k = e[1];if (j >= 0 && j < N && !s.contains(j) && !vis[j][k]) {q.offer(new int[]{j, k});vis[j][k] = true;}}}}return -1;}
}

1761. 一个图中连通三元组的最小度数

https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/

在这里插入图片描述

提示:
2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。

构造邻接表,枚举每一个三元组。

class Solution {public int minTrioDegree(int n, int[][] edges) {int[] cnt = new int[n + 1];int[][] isC = new int[n + 1][n + 1];for (int[] edge: edges) {int x = edge[0], y = edge[1];isC[x][y] = 1;isC[y][x] = 1;cnt[x]++;cnt[y]++;}int ans = Integer.MAX_VALUE;for (int i = 1; i <= n; ++i) {for (int j = i + 1; j <= n; ++j) {if (isC[i][j] == 0) continue;for (int k = j + 1; k <= n; ++k) {if (isC[j][k] == 0 || isC[i][k] == 0) continue;ans = Math.min(ans, cnt[i] + cnt[j] + cnt[k] - 6);}}}return ans != Integer.MAX_VALUE? ans: -1;}
}

2240. 买钢笔和铅笔的方案数

https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/

在这里插入图片描述

提示:
1 <= total, cost1, cost2 <= 10^6

解法1——完全背包

套用完全背包模板,对dp数组求和即可。

class Solution {public long waysToBuyPensPencils(int total, int cost1, int cost2) {long[] dp = new long[total + 1];dp[0] = 1;for (int j = cost1; j <= total; ++j) dp[j] += dp[j - cost1];for (int j = cost2; j <= total; ++j) dp[j] += dp[j - cost2];long ans = 0;for (long d: dp) ans += d;return ans;}
}

解法2——枚举买了几支钢笔(推荐解法)

通过枚举购买钢笔的数量,计算此时可以购买铅笔的数量,+1即是购买此时数量钢笔时,购买铅笔的方案数。

class Solution {public long waysToBuyPensPencils(int total, int cost1, int cost2) {long ans = 0;for (int i = 0; i * cost1 <= total; ++i) {ans += (total - i * cost1) / cost2 + 1;}return ans;}
}

2511. 最多可以摧毁的敌人城堡数目

https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/?envType=daily-question&envId=2023-09-02

在这里插入图片描述

提示:
1 <= forts.length <= 1000
-1 <= forts[i] <= 1

解法——一次遍历

题目要求是计算 1 和 -1 之间的 0 的最大数量。

一次遍历,遍历的过程中记录上一个 1 或 -1 出现的位置即可。

class Solution {public int captureForts(int[] forts) {int lastId = 0, ans = 0;for (int i = 0; i < forts.length; ++i) {if (forts[i] == -1 || forts[i] == 1) {if (forts[i] + forts[lastId] == 0) ans = Math.max(ans, i - lastId - 1);lastId = i;}}return ans;}
}

1921. 消灭怪物的最大数量(贪心)

https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/

在这里插入图片描述

提示:
n == dist.length == speed.length
1 <= n <= 10^5
1 <= dist[i], speed[i] <= 10^5

先计算时间,再按时间排序。
贪心的先消灭快要到达城市的怪兽。

class Solution {public int eliminateMaximum(int[] dist, int[] speed) {int n = dist.length;int[] t = new int[n];for (int i = 0; i < n; ++i) {t[i] = (dist[i] + speed[i] - 1) / speed[i]; // 向上取整}Arrays.sort(t);for (int i = 0; i < n; ++i) {if (t[i] <= i) return i;}return n;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/122775.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

qt简易网络聊天室 数据库的练习

qt网络聊天室 服务器&#xff1a; 配置文件.pro QT core gui networkgreaterThan(QT_MAJOR_VERSION, 4): QT widgetsCONFIG c11# The following define makes your compiler emit warnings if you use # any Qt feature that has been marked deprecated (the exac…

Kafka3.0.0版本——文件清理策略

目录 一、文件清理策略1.1、文件清理策略的概述1.2、文件清理策略的官方文档1.3、日志超过了设置的时间如何处理1.3.1、delete日志删除&#xff08;将过期数据删除&#xff09;1.3.2、compact日志压缩 一、文件清理策略 1.1、文件清理策略的概述 Kafka 中默认的日志保存时间为…

Cento7 Docker-compose安装以及使用InfluxDB

InfluxDB是一个时序数据库&#xff0c;主要用于监控场景的数据支撑&#xff0c;对于那些写少读多按时间序查询数据的场景是非常适用的。接下来我们用docker-compose的形式安装。首先先装好docker,docker-compose命令 yum -y install yum-utils device-mapper-persistent-data…

【买华为云产品,返CSDN余额红包】,快来薅羊毛!

华为云828营销季火热进行中&#xff0c;9月15日前首次购买华为云产品官网任意一款产品&#xff0c;可获得相应比例的CSDN红包。 热门产品云服务器、域名、商标、主机安全等产品都在其中&#xff0c;任君挑选。 活动优惠价购买后还是获得相应比例余额红包&#xff0c;实际付费金…

游戏软件报错d3dx9_43.dll丢失怎么解决?这5个解决方法可以修复

我想和大家分享一个关于电脑问题的话题——d3dx9_43.dll丢失怎么解决。这个话题对于很多使用电脑的朋友来说&#xff0c;可能是一个非常棘手的问题。d3dx9_43.dll是 DirectX中非常重要的一部分&#xff0c;许多游戏和应用程序都需要它来正常运行。如果丢失了这个文件&#xff0…

Simulink建模与仿真(3)-Simulink 简介

分享一个系列&#xff0c;关于Simulink建模与仿真&#xff0c;尽量整理成体系 1、Simulink特点 Simulink是一个用来对动态系统进行建模、仿真和分析的软件包。使用Simulink来建模、分析和仿真各种动态系统(包括连续系统、离散系统和混合系统)&#xff0c;将是一件非常轻松的事…

万物互联:软件与硬件的协同之道

在当今数字化时代&#xff0c;我们身边的一切似乎都与计算机和互联网有关。从智能手机到智能家居设备&#xff0c;从自动驾驶汽车到工业生产线&#xff0c;无论我们走到哪里&#xff0c;都能看到软件和硬件的协同作用。本文将探讨这种协同作用&#xff0c;解释软件和硬件如何相…

ThreadLocal

ThreadLocal 参考&#xff1a;https://blog.csdn.net/u010445301/article/details/111322569 ThreadLocal简介 作用&#xff1a;实现线程范围内的局部变量&#xff0c;即ThreadLocal在一个线程中是共享的&#xff0c;在不同线程之间是隔离的。 原理&#xff1a;ThreadLocal存…

c高级day1(9.6) 离线软件安装,文件相关指令,文件权限相关指令,

作业: 使用cut截取出Ubuntu用户的家目录&#xff0c;要求&#xff1a;不能使用":"作为分割 不会 Xmind&#xff1a;

vue2踩坑之项目:生成二维码使用vue-print-nb打印二维码

1. vue2安装 npm install vue-print-nb --save vue3安装 npm install vue3-print-nb --save 2. //vue2 引入方式 全局 main.js import Print from vue-print-nb Vue.use(Print) ------------------------------------------------------------------------------------ //vue2 …

WEBGL(4):动态绘制点并根据详细自定义颜色

1 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, …

前端面试中Vue的有经典面试题三

11. 网页从输入网址到渲染完成经历了哪些过程&#xff1f; 大致可以分为如下7步&#xff1a; 输入网址&#xff1b; 发送到DNS服务器&#xff0c;并获取域名对应的web服务器对应的ip地址&#xff1b; 与web服务器建立TCP连接&#xff1b; 浏览器向web服务器发送http请求&a…

windows 不能ping通虚拟机问题

先查看windows网卡 查看虚拟机种 对应VMnet8种的 nat &#xff08;我用的是这种连接方式&#xff09;设置 问题是不在同一个网段&#xff0c;修改windows VMnet8网卡的配置 保证网关、网段是一样的 现在ping问题解决&#xff0c;也能windows远程连接虚拟机

Bridge Champ举办人机对战赛:NFT游戏与传统竞技共生发展编织新格局

概要 现在,NFT与体育竞技正日益紧密地联系在一起。一些体育项目开始推出与赛事或球队相关的NFT,同时也有部分NFT游戏开始举办电子竞技赛事。这种共生发展正在改变体育竞技的生态。 笔者采访了桥牌冠军项目相关负责人,探讨NFT游戏与传统体育竞技的融合潜力。桥牌冠军近期成功举…

(二十一)大数据实战——Flume数据采集之复制和多路复用案例实战

前言 本节内容我们完成Flume数据采集的一个多路复用案例&#xff0c;使用三台服务器&#xff0c;一台服务器负责采集本地日志数据&#xff0c;通过使用Replicating ChannelSelector选择器&#xff0c;将采集到的数据分发到另外俩台服务器&#xff0c;一台服务器将数据存储到hd…

pytorch-神经网络-手写数字分类任务

Mnist分类任务&#xff1a; 网络基本构建与训练方法&#xff0c;常用函数解析 torch.nn.functional模块 nn.Module模块 读取Mnist数据集 会自动进行下载 %matplotlib inlinefrom pathlib import Path import requestsDATA_PATH Path("data") PATH DATA_PATH / &…

使用 Nacos 在 Spring Boot 项目中实现服务注册与配置管理

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

每日刷题(回溯法经典问题之子集)

食用指南&#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识&#xff1a;回溯法经典问题之组合 ♈️今日夜电波&#xff1a;想着你—郭顶 1:09 ━━━━━━️&#x1f49f;──────── 4:15 …

jmeter setUp Thread Group

SetUp Thread Group 是一种特殊类型的线程组&#xff0c;它用于在主测试计划执行之前执行一些初始化任务。 SetUp Thread Group 通常用于以下几种情况&#xff1a; 用户登录&#xff1a;在模拟用户执行实际测试之前&#xff0c;模拟用户登录到系统以获取访问权限。 创建会话&a…

freertos之资源管理

中断屏蔽 屏蔽中断函数 在任务中使用 taskENTER_CRITICA()/taskEXIT_CRITICAL() 在中断中使用 taskENTER_CRITICAL_FROM_ISR()/taskEXIT_CRITICAL_FROM_ISR() 功能介绍 使用上述函数&#xff0c;进入临界中断&#xff0c;任务不会切换&#xff0c;且中断优先级处于con…