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

打基础之,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-12-11]  Weihmann指出:“我特别感到惊讶的是,动物运动稳定机制的变化与腿部协调的变化是一致的。昆虫的慢运行非常稳定,因为它的重心很低,三条腿总是以协调的方式运动。...

机器人灵巧手将成为智能机器人的下一个重大突破
机器人灵巧手将成为智能机器人的下一个重大突破

[2018-01-25]  计算机科学教授兼东北地区助手机器人实验室负责人罗伯特·普拉特(Robert Platt)说:“机器人手操作是下一步要解决的问题。想象一下,一个机器人可以在现实世界中用手去做事......

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

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

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

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

新型轻便机器人套装重5kg,辅助跑步和步行
新型轻便机器人套装重5kg,辅助跑步和步行

[2019-10-23]  虽然步行对大多数人来说似乎不是负担,但对有些人来说,这项简单的运动往往会让人感到筋疲力尽。比如手术或中风后恢复的患者、帕金森氏症患 ...

Crossbar将电阻式RAM推入嵌入式AI
Crossbar将电阻式RAM推入嵌入式AI

[2018-05-17]  电阻RAM技术开发商Crossbar表示,它已与航空航天芯片制造商Microsemi达成协议,允许后者在未来的芯片中嵌入Crossbar的非易失性存储器。此举是在先进制造业节点的领先代工厂选......

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

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

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

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

本周栏目热点

关于应用机器学习作为搜索问题的入门简介

[2018-01-03]  机器学习的应用可以理解为一个搜索问题,即根据某个项目的已知信息和可获取的资源,找到从输入到输出的最好的映射。在本文你即将看到把应用机器学习当作搜索问题的概念...

[2017-03-02]   随着人工智能的不断发展,许多新的机器学习技术、架构和算法被提出,但这里有三个宏观趋势,将成为机器学习中,游戏规则的改变者。 机 ...

顶级AI会议NIPS压轴2017(附PPT、视频、代码大汇总)

[2017-12-19]  NIPS,全称神经信息处理系统大会(Conference and Workshop on Neural Information Processing Systems),是一个关于机器学习和计算神经科学的国际会议。该会议固定在每年的12月举行...

机器学习之——正则化

[2018-05-18]  最近在刷李航的《统计学习方法》这本书,在很多算法的损失函数里,都出现类似的描述:损失函数最小化原则一般就是用正则化的极大似然估计进 ...

机器学习算法可预测出乳腺癌治疗率(图)

[1970-01-01]    据外媒报道,患有同种疾病的不同病人在接受同一种治疗方案时,其获得的疗效也会存在不同,这就给医生留下了一个难题:他们怎样才能知道 ...