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

每日算法-250420

每日算法 - 2025/04/20

记录一下今天刷的几道 LeetCode 题目。

3075. 幸福值最大化的选择方案

题目描述
Problem 3075 Description

思路

贪心

解题过程

核心思想是:为了总幸福值最大化,我们应该优先选择当前能提供最大幸福值的孩子。

  1. 排序:将 happiness 数组降序排序。这样,每次我们考虑的就是当前可选孩子中幸福值最高的。
  2. 选择与更新:我们总共需要选择 k 个孩子。
    • 选择当前幸福值最高的孩子(排序后的数组从左到右选择)。
    • 设我们已经选择了 i 个孩子(i 从 0 开始计数),那么在选择第 i+1 个孩子时,他的原始幸福值 happiness[i] 会因为前面已经选择了 i 个孩子而减少 i
    • 所以,第 i+1 个孩子(数组索引为 i)实际贡献的幸福值是 max(0, happiness[i] - i),因为幸福值不能为负数。
    • 累加这个实际贡献的幸福值。
  3. 迭代:重复步骤 2,直到选满 k 个孩子或者所有可选孩子的实际幸福值都变为 0。

复杂度

  • 时间复杂度: O ( N log ⁡ N ) O(N \log N) O(NlogN),主要由排序决定,其中 N 是 happiness 数组的长度。
  • 空间复杂度: O ( log ⁡ N ) O(\log N) O(logN) O ( N ) O(N) O(N),取决于排序算法使用的栈空间或辅助空间。如果只考虑额外空间(不计输入数组的修改),可以认为是 O ( 1 ) O(1) O(1)

Code

class Solution {public long maximumHappinessSum(int[] happiness, int k) {// 对幸福值数组进行升序排序Arrays.sort(happiness);int n = happiness.length;long maxHappinessSum = 0;int turns = 0; // 记录已经选择了多少个孩子 (即轮数)// 从幸福值最高的孩子开始选择 (数组末尾)for (int i = n - 1; i >= 0 && k > 0; i--) {// 计算当前孩子实际能贡献的幸福值// 原始幸福值 happiness[i] 需要减去已经进行的轮数 turnslong currentHappiness = happiness[i] - turns;// 幸福值不能小于 0if (currentHappiness > 0) {maxHappinessSum += currentHappiness;} else {// 如果当前最大幸福值的孩子贡献都 <= 0,后续的更不可能 > 0break;}turns++; // 轮数增加k--;     // 还需要选择的孩子数量减少}return maxHappinessSum;}
}

2554. 从一个范围内选择最多整数 I

题目描述
Problem 2554 Description

思路

贪心

解题过程

目标是在不超过 maxSum 的前提下,从范围 [1, n] 中选择尽可能多的、不在 banned 列表中的整数。

  1. 贪心策略:为了选择最多的整数,我们应该优先选择数值最小的整数,因为它们消耗的 maxSum 最少。
  2. 排除禁用数:使用一个数组来快速判断一个数是否在 banned 列表中。
  3. 迭代选择:从 1 开始,依次检查每个整数 i1 <= i <= n):
    • 如果 i 不在 banned 列表中。
    • 并且当前 maxSum大于0
    • 那么就选择 i,增加计数 ret,并更新 maxSum -= i
  4. 返回结果:最终的 ret 就是最多能选择的整数数量。

复杂度

  • 时间复杂度: O ( B + n ) O(B + n) O(B+n),其中 B 是 banned 数组的长度(构建哈希表或标记数组),n 是上限范围(遍历 1n)。
  • 空间复杂度: O ( B ) O(B) O(B) 如果使用 HashSet,或者 O ( S ) O(S) O(S) 如果使用大小为 S (如 10001 或 n+1) 的数组来标记 banned 数字。

Code

class Solution {public int maxCount(int[] banned, int n, int maxSum) {int size = 10001;int[] hash = new int[size];for (int x : banned) {hash[x]++;}int ret = 0, sum = 0;for (int i = 1; i <= n && maxSum >= 0; i++) {if (hash[i] == 0) {ret++;maxSum -= i;}}return maxSum < 0 ? ret - 1 : ret;}
}

1283. 使结果不超过阈值的最小除数

题目描述
Problem 1283 Description

这是第二次做这道题,思路已经比较清晰了。详细题解可以参考之前的笔记 每日算法-250408。

Code

class Solution {public int smallestDivisor(int[] nums, int threshold) {Arrays.sort(nums);int left = 1, right = nums[nums.length - 1];while (left <= right) {int mid = left + (right - left) / 2;if (check(nums, mid, threshold)) {right = mid - 1;} else {left = mid + 1;}}return left;}private boolean check(int[] arr, int divisor, int k) {int sum = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] % divisor == 0) {sum += arr[i] / divisor;} else {sum += arr[i] / divisor;sum++;}}return sum <= k;}
}
http://www.xdnf.cn/news/48457.html

相关文章:

  • Java中的锁
  • 【C++】 —— 笔试刷题day_21
  • ARM裸机开发——I.MX6U_汇编LED灯驱动
  • 大模型技术解析与应用 | 大语言模型:从理论到实践(第2版)| 复旦大学 | 533页
  • 地级市-城镇化率(2003-2023年)-社科数据
  • 驱动开发硬核特训 · Day 15:电源管理核心知识与实战解析
  • typeScript基础(类型)
  • Scratch——第18课 列表接龙问题
  • 基于javaweb的SpringBoot儿童爱心管理系统设计与实现(源码+文档+部署讲解)
  • llamafactory的包安装
  • ArcPy Mapping 模块基础(下)
  • 动态调整映射关系的一致性哈希负载均衡算法详解
  • 计算机网络基础
  • 抽象类是“模板”,接口是“契约”——深度对比 Java 两大抽象机制
  • NLP 梳理03 — 停用词删除和规范化
  • git reset和git revert的区别
  • DQN在Gym的MountainCar环境的实现
  • SpringCloud实战
  • 软考复习——知识点软件开发
  • 提示词设计:动态提示词 标准提示词
  • 深入理解 Java 中的 synchronized 关键字
  • 【JavaWeb后端开发02】SpringBootWeb + Https协议
  • OpenCV 对图像进行阈值处理 cv2.threshold
  • 基于 pnpm + Monorepo + Turbo + 无界微前端 + Vite 的企业级前端工程实践
  • Linux教程-Shell编程系列二
  • 一招破敌,掌控 React 渲染术:createRoot 与 root.render
  • 第一章:MySQL视图基础
  • webgl入门实例-矩阵在图形学中的作用
  • Vivado中Tri_mode_ethernet_mac的时序约束、分析、调整——(五)调试注意的问题
  • Java表达式2.0