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

打基础之,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年:AI渗入云端
2017年:AI渗入云端

[2017-12-29]  云中的人工智能不仅仅是科技巨头的权力游戏,它也可能是人工智能领域的下一个飞跃。加利福尼亚州的Rigetti Computing公司刚刚使用其原型量子芯片之一在其云平台上运行机器学......

人工智能民主化能否实现取决于科技巨头
人工智能民主化能否实现取决于科技巨头

[2017-12-29]  我们经常听到像谷歌和微软这样的公司说他们希望人工智能民主化。这是一个很好的词,民主化。 但这些公司如何界定“民主化”还不清楚,像AI本身一样,它似乎有点炒作的味道...

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

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

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

7种常见的机器人焊接类型
7种常见的机器人焊接类型

[2017-12-17]  机器人焊接是工业领域最常见的机器人应用之一,近几十年来主要由汽车行业驱动。机器人焊接在完成大批量,重复性的焊接任务时效率最高。...

MIT最新“人机”互连系统 让双腿机器人复制人体技能
MIT最新“人机”互连系统 让双腿机器人复制人体技能

[2019-11-01]  MIT的小爱马仕想借用你的大脑 ,图片来自: João Ramos爱吧机器人网消息,麻省理工学院(MIT)的研究人员展示了一种新型遥操作系 ...

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

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

如何让人工智能机器人快速自我纠正错误并吃一堑长一智?
如何让人工智能机器人快速自我纠正错误并吃一堑长一智?

[2017-08-23]  莱斯特大学数学系的研究人员在《Neural Networks》杂志上发表了一篇文章,概述了新算法的数学基础,可以使人工智能收集错误报告并立即纠正,而不影响现有技能 ,同时还会积......

本周栏目热点

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

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

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

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

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

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

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

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

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