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

打基础之,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优化算法有?
精选推荐
这些人型机器人是如此真实,你的肉眼几乎无法区分
这些人型机器人是如此真实,你的肉眼几乎无法区分

[2017-09-03]   我们生活在一个区分现实与幻想变得越来越困难的世界。由于机器人技术的进步,创造人工的人类正在逐渐接近完美的最终目标。我们现在看到的机器人不再只是一块发光二极管,......

人工智能准确预测患者一年内的死亡风险,原理却无法解释
人工智能准确预测患者一年内的死亡风险,原理却无法解释

[2019-11-13]  图片来自BURGER PHANIE SCIENCE PHOTO LIBRARY美国最新研究显示,人工智能通过查看心脏测试结果,以高达85%以上的准确率预测了一个人在一 ...

集群机器人领域最新研究:一种用于探测未知环境的微型无人机群
集群机器人领域最新研究:一种用于探测未知环境的微型无人机群

[2019-10-26]  (图:无人机扩散至不同方向来探索环境。当一个无人机注意到另一个无人机在它的首选方向,它将试图飞到另一个方向。若首选方向冲突,低优先 ...

国外眼科手术机器人为视网膜静脉阻塞患者带来希望
国外眼科手术机器人为视网膜静脉阻塞患者带来希望

[2017-03-20]  视网膜静脉阻塞,简称RVO,对患者来说是一种严重的疾病。该病病因为视网膜静脉中存在血液凝块,这可能导致视力严重下降,在某些情况下,病 ...

美国喷气推进实验室的AI驱动无人机挑战人类飞行员
美国喷气推进实验室的AI驱动无人机挑战人类飞行员

[2017-12-08]  随着无人机及其组件越来越小,效率越来越高,功能越来越强大,我们已经看到越来越多的研究开始让无人机自主飞行在半结构化的环境中,而不依赖于外部定位。 宾夕法尼亚大学在......

MIT用深度学习处理3D点云数据 应用于无人汽车等领域
MIT用深度学习处理3D点云数据 应用于无人汽车等领域

[2019-10-23]  如果你见过自动驾驶汽车,也许会对车顶上那个一直在旋转的圆柱体感到好奇。这是一个雷达传感器,无人驾驶汽车依靠它在现实世界中进行导航。 ...

基于生物启发的机器人很容易适应丢失附属器官
基于生物启发的机器人很容易适应丢失附属器官

[2017-12-17]  很多机器人被设计应用在危险环境,如灾难现场。在这些地方,他们的运动系统完全有可能被损坏。那这样会吓跑这些机器人吗?也许不是,如果它们像日本的东北和北海道大学创造的......

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

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

本周栏目热点

深度学习反向传播算法(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]      一个人独处时,感觉有点孤单,怎么办?微软亚洲研究院推出的微软小冰,或许 ...