网站首页 > java教程 正文
题目
给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
代码
public class DayCode {
public static void main(String[] args) {
int[] nums = new int[]{1,1,0,1,1,1};
Integer ans = new DayCode().arrayPairSum(nums);
System.out.println("ans is " + ans);
}
/**
* https://leetcode-cn.com/problems/array-partition-i/
* @param nums
* @return
*/
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < nums.length; i += 2) {
ans += nums[i];
}
return ans;
}
}
总结
* 上述代码的时间复杂度是O(n log(n))
* 解题的代码比较简洁,主要应用了贪心算法的思想。
* 贪心算法在有最优子结构的问题中尤为有效。
* 贪心算法有两种证明方法:反证法和归纳法。一般情况下,一道题只会用到其中的一种方法来证明。
反证法:如果交换方案中任意两个元素/相邻的两个元素后,答案不会变得更好,那么可以推定目前的解已经是最优解了。
猜你喜欢
- 2024-11-18 「Java基础知识」string是什么?
- 2024-11-18 Java设置字符串的首字母为大写
- 2024-11-18 100个Java工具类之2:字符串之多种个性化格式处理
- 2024-11-18 LeetCode力扣官方题解|842将数组拆分成斐波那契序列
- 2024-11-18 JAVA之多级目录下查找文件中是否含有某个字符串功能实现
- 2024-11-18 从字符串拆分获取字符数组查看字符串是否有子字符串contains方法
- 2024-11-18 Java—Throwing Exceptions
- 2024-11-18 JAVA String类
- 2024-11-18 JAVA系列之:String的特点是什么?它有哪些重要的方法?
- 2024-11-18 Spring Boot 项目如何按模块进行拆分?
你 发表评论:
欢迎- 最近发表
-
- 搞趣网:我的世界全新皮肤包原始居民下载地址
- 我的世界拔刀剑MOD下载(我的世界拔刀剑mod下载国际版)
- 我的世界无正版账号的简单联机方法(非网易版,仅适用于局域网)
- 一些可以显著提高大型 Java 项目启动速度的尝试
- 常见的java敏感异常介绍(java 常见的异常)
- Java 开发者必看!三招实现外部 Jar 包动态加载(含热更新方案)
- Java JAR 启动内存参数配置指南:从基础设置到性能优化
- 对Spring MVC接口进行Mock测试(springmvc对外接口)
- 还在用策略模式解决 if-else?Map+函数式接口方法才是YYDS
- 干掉OpenFeign,SpringBoot 3.0 自带的 HTTP 客户端真香!
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论,来添加一个吧(●'◡'●)