爱吧机器人网 » 技术 > 机器学习 > 正文

打基础之,LeetCode算法题第7日刷,数组分区

今天更新着实是有些晚了,没办法,有事情拖住了,看来以后得提前备些货才是。

一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧,一开始就弄些重量级的,什么人工智能,机器学习的算法,还要有大量的数学以及优化的知识,小白们估计会很郁闷,当然我也不一定能做出来对吧。

我计划每题给出两种语言的解决方案,一种静态语言,一种动态语言。

我选择C语言和Python,本来考虑Java,但是篇幅有限,有兴趣的朋友自己试试。

LeetCode 561. 数组分区I(Array Partition I)

问题描述:

给定一个包含2n个整数元素的数组,将其拆分成n个仅仅包含2个元素的小数组,如(a1, b1), (a2, b2), ..., (an, bn),求出所有min(ai,bi)的和。

注意:

  1. n取值范围是1~10000;
     
  2. 数组中元素的取值范围是 -10000~10000;
     
示例:

打基础之,LeetCode算法题第7日刷,数组分区

C语言实现:

题目说拆分成小数组,我们不一定真的要这么拆分,多观察多思考还是很有必要的

第一种方法:

思路是先排序,然后求排序后的数组中所有偶数下标的和。

我们这里使用库函数qsort(),除非十分必要,否则不建议大家自己实现排序算法。虽然排序算法原理大家已经很熟悉,但是要是让自己写,还是要花一些时间的,而且你花费的这部分时间造出的车不一定有库提供的好用。

打基础之,LeetCode算法题第7日刷,数组分区
可以看到,这个解决方案虽然实现简单,但是效率却不是很理想。

打基础之,LeetCode算法题第7日刷,数组分区
第二种方式:

按照题目的要求,可以知道,数组的最大长度不会超过20001,因此对于这道题,我们可以用空间换时间的办法,建立一个长度为20001的数组buf,然后遍历给定的数组nums,其元素的值作为作为buf的对应下标,来统计这个值在nums中出现的次数。

说起来比较拗口,这里举例,假设nums=[1,2,2,7,2,9,1,4],遍历nums后填充buf后,buf中的内容如下:

打基础之,LeetCode算法题第7日刷,数组分区
大家可以注意到,这实现了nums的“排序”,只是排序的值变成了buf数组的“序列号”。

这样处理后,再通过对计数值的处理就可以获得最终的sum。这里重要的是理解step变量的作用,它是来控制指向的最小值得位置和状态。例如 10001这个点记录了1在nums中出现了2次,那么很自然我们可以拆分数组为[1,1]; 然后10002这个点表示2出现了3次,那么很自然可以拆分出[2,2],和[2,x],这个x一定10002右边最近的那个,即10004,这个时候step被设置为0了,表示,10004中的一个要拿来给前面的10002组成一对。

代码如下,这个思路可能有些不太好理解,建议大家对照上面的图慢慢琢磨,有问题可以在下面提问,我会及时解答。

打基础之,LeetCode算法题第7日刷,数组分区
可见,这个解决方案的效果还是不错的。

打基础之,LeetCode算法题第7日刷,数组分区

python实现:

排序,切片,求和。一行代码足矣。

打基础之,LeetCode算法题第7日刷,数组分区
貌似python这个运行时间很有问题,相同的代码我试着提交了几次,每次这个时间都不一样,不过不同也是可以理解的。

打基础之,LeetCode算法题第7日刷,数组分区



上一篇:实战:分类算法实践及如何用好Python工具
下一篇:BAT面试官最喜欢问的问题之一:算法Kmeans优化算法有?
精选推荐
为未来战场创造更有效的机器人 美国陆军研究人工纳米马达
为未来战场创造更有效的机器人 美国陆军研究人工纳米马达

[2019-10-11]  为了使机器人在战斗中更有效、更多才多艺地成为士兵的战友,美国陆军研究人员正在执行一项任务,即研究肌肉分子生命功能的价值,以及复制过 ...

通过对抗性图像黑入大脑
通过对抗性图像黑入大脑

[2018-03-02]  在上面的图片中,左边是一张猫的照片。在右边,你能分辨出它是同一只猫的图片,还是一张看起来相似的狗的图片?这两张图片之间的区别在于, ...

一个让深度学习惨败的通用人工智能领域——语境处理
一个让深度学习惨败的通用人工智能领域——语境处理

[2019-11-04]  Context是指用来解释一段给定文本或语句的来源框架,我们可以翻译为上下文或语境。维基百科将context定义为:*在符号学、语言学、社会学和 ...

[2017-03-21]  虽然有很多关于机器人取代工人的担心,但哈佛经济学家James Bessen的论文指出,在过去的67年里机器人仅仅淘汰掉人类工作中的一个。在1950 ...

英伟达用联合学习创建医学影像AI 可共享数据和保护隐私
英伟达用联合学习创建医学影像AI 可共享数据和保护隐私

[2019-10-14]  英伟达(Nvidia)和伦敦国王学院(King’s College London)的人工智能研究人员利用联合学习训练了一种用于脑肿瘤分类的神经网络, ...

智能农业:种地的事儿未来全交给这些机器人吧
智能农业:种地的事儿未来全交给这些机器人吧

[2019-12-07]  SRC公司创始人Sam与温波尔庄园农场经理Callum Weir以及监控机器人Tom总部位于英国的农业科技初创公司SRC(Small Robot Company),正在 ...

CES 2018:英特尔推出49量子位芯片争夺量子霸权
CES 2018:英特尔推出49量子位芯片争夺量子霸权

[2018-01-10]  在与Google、IBM的一场关于建立量子计算系统的马拉松比赛中,英特尔通过了一个关键的里程碑。近日,这个科技巨头已经推出了一个49个量子位 ...

谷歌大脑发布ROBEL基准 鼓励用低成本机器人训练AI系统
谷歌大脑发布ROBEL基准 鼓励用低成本机器人训练AI系统

[2019-10-11]  训练AI系统的机器人D& 39;Claw和D& 39;Kitty用于控制机器人的人工智能系统,测量其性能所使用的基准通常仅限于为工业环境设计的昂贵硬件, ...

本周栏目热点

盘点全球十大最具影响力的机器人摇篮

[1970-01-01]    人工智能(AI)研究现正迅速发展,如无人驾驶汽车、计算机在《危险边缘》智力竞赛节目中获胜、数字私人助手Siri、GoogleNow和语音助手C ...

深度学习反向传播算法(BP)原理推导及代码实现

[2017-12-19]  分析了手写字数据集分类的原理,利用神经网络模型,编写了SGD算法的代码,分多个epochs,每个 epoch 又对 mini_batch 样本做多次迭代计算。这其中,非常重要的一个步骤,......

如何在机器学习项目中使用统计方法的示例

[2018-07-23]  事实上,机器学习预测建模项目必须通过统计学方法才能有效的进行。在本文中,我们将通过实例介绍一些在预测建模问题中起关键作用的统计学方法。...

[2017-08-28]  模拟退火(Simulated Annealing,简称SA)是一种通用概率算法,用来在一个大的搜寻空间内找寻命题的最优解。1、固体退火原理:将固体加温 ...

Machine Learning-感知器分类算法详解

[2018-05-31]  今天我们来讲解的内容是感知器分类算法,本文的结构如下:什么是感知器分类算法,在Python中实现感知器学习算法,在iris(鸢尾花)数据集上训练一个感知器模型,自适应线性神......