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

打基础之,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优化算法有?
精选推荐
通过对抗性图像黑入大脑
通过对抗性图像黑入大脑

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

为未来战场创造更有效的机器人 美国陆军研究人工纳米马达
为未来战场创造更有效的机器人 美国陆军研究人工纳米马达

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

比利时研发出可以自我愈合伤口的软体机器人
比利时研发出可以自我愈合伤口的软体机器人

[2017-09-03]  软体机器人是机器人技术的新兴领域; 他们“可以与人类相互作用,而不会杀死他们,并拿起像西红柿这样柔软的物体。” 从长远来看,布鲁塞尔大学队伍正在努力创建一个类似的材......

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

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

可编辑神经网络,有望简化深度学习?
可编辑神经网络,有望简化深度学习?

[2019-10-04]  深度学习是一个计算繁重的过程。 降低成本一直是 Data curation 的一大挑战。 关于深度学习神经网络大功耗的训练过程,已经有研究人员 ...

MIT研制出可以像植物一样生长的机器人
MIT研制出可以像植物一样生长的机器人

[2019-11-09]  麻省理工学院开发了一种新型机器人,这种机器人可以本质上自我延伸,其生长方式与植物幼苗向上生长的方式惊人相似。值得注意的是,研究人员 ...

搭载人工智能的太空机器人CIMON 2乘SpaceX抵达国际空间站
搭载人工智能的太空机器人CIMON 2乘SpaceX抵达国际空间站

[2019-12-09]  12月5日,搭载人工智能的太空机器人西蒙2号(CIMON 2)乘坐SpaceX火箭Dragon货运舱,从佛罗里达州卡纳维拉尔角空军基地升空,前往国际空间 ...

Waymo:人性和行为心理学才是无人驾驶最大的挑战
Waymo:人性和行为心理学才是无人驾驶最大的挑战

[2019-11-03]  自动驾驶汽车作为AI领域内最大的挑战之一,谷歌致力于其研发已有十余载,现在他们逐渐意识到,最困难的是如何让人们享受驾驶的乐趣。这是一 ...

本周栏目热点

深度学习反向传播算法(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(鸢尾花)数据集上训练一个感知器模型,自适应线性神......

机器人是怎么深度学习的?

[2016-03-29]      一个人独处时,感觉有点孤单,怎么办?微软亚洲研究院推出的微软小冰,或许 ...