专栏首页好好学java的技术栈LeetCode 算法 | 如何拆分数组?

LeetCode 算法 | 如何拆分数组?

阅读文本大概需要 3 分钟。

今天给大家分享的 LeetCode 算法题是和数组相关,关于如何拆分数组的,来一起夯实一下算法内功。

题目

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

拿到这道题,是不是感到一头雾水,大家可能在想,我要通过什么样的算法才能找到分组后,每组最小值之和的值最大呢?大家可以先思考下。

如果你还没有想到好的解决方法,我可以给你一些提示。

1. 如果你想使用蛮力去解,那肯定是无济于事的,就像我上面说的,你怎么知道哪些组合就行呢?所以需要换个角度考虑,比如你可以假设数组是[1,2,3,4,5,6]。

看完这个提示,不知道你有思路了没有?如果还没有,那我再给你一点提示。

2. 你怎么知道哪些组合比较好呢?所以数组必须要搞成某种形式的,方便查看的。

提示到这里,估计你已经有点感觉了,但是好像还不知道怎么把数组搞成所谓的某种形式。那我再给你点提示。

3. 获取两个值的min,你肯定要失去较大的,那么就需要把较小的与较大的顺序给找出来。

到这里,相信你应该知道怎么做了。什么?你还不知道?那好吧,我就跟你明说了吧。

4. 先给数组排序,排好序之后,隔两个直接取和即可。

到这里,你应该可以写得出实现代码了,下面是我给的一个 Java 代码示例:

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for(int i = 0; i < nums.length; i += 2) {
            result += nums[i];
        }
        return result;
    }
}

看到代码,是不是觉得很简单,面试的时候 ,往往就是这样,实现很简单,但是思路很重要,很多同学想不到好的思路,结果半天挤不出几个字来。

今天的 LeetCode 算法题就分享这么多吧。

本文分享自微信公众号 - 好好学java(SIHAIloveJAVA)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分享Github上10个比较优秀的开源项目给大家收藏下!!!

    基于 Angular 2, Bootstrap 4 和 Webpack 的后台管理面板框架。

    好好学java
  • Java 循环队列原理与用法详解

    (1)设一个容量为capacity=8,size=5(a,b,c,d,e)的数组,左侧为队首、右侧为队尾。

    好好学java
  • 特别的520,送给特别的你们,还不来看看?

    好好学java
  • Vue-cli教程

    一、安装vue-cli 安装vue-cli的前提是你已经安装了npm,安装npm你可以直接下载node的安装包进行安装。你可以在命令行工具里输入npm -v  ...

    用户1212940
  • shell基本命令

    有关文件显示的命令: du --exclude=iso  -sh  .        //统计当前除了iso这个目录的其他文件大小 ls -F        ...

    BG彪
  • 最详细的Vue Hello World应用开发步骤

    很多Vue的初学者想尝试这个框架时,都被webpack过于复杂的配置所吓倒,导致最后无法跑出一个期望的hello word效果。今天我就把我第一次使用webpa...

    Jerry Wang
  • gsoap入门:gsoap的plugin机制说明塈使用plugin实现调试soap函数时显示

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • Golang高效实践之array、slice、map实践

    Golang的slice类型为连续同类型数据提供了一个方便并且高效的实现方式。slice的实现是基于array,slice和map一样是类似于指针语义,传递sl...

    用户2937493
  • 最详细的Vue Hello World应用开发步骤

    很多Vue的初学者想尝试这个框架时,都被webpack过于复杂的配置所吓倒,导致最后无法跑出一个期望的hello word效果。今天我就把我第一次使用we...

    Jerry Wang
  • Vue打包优化之code spliting

    如果我们对所有的代码进行合理的拆分,将首屏和非首屏的代码进行剥离,将业务代码和基础库代码进行拆分,在需要某段代码的时候再加载它,下次若再需要用则从缓存中读取.....

    QQ音乐前端团队

扫码关注云+社区

领取腾讯云代金券