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

打基础之,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-04]  深度学习是一个计算繁重的过程。 降低成本一直是 Data curation 的一大挑战。 关于深度学习神经网络大功耗的训练过程,已经有研究人员 ...

深度神经网络揭示了大脑喜欢看什么
深度神经网络揭示了大脑喜欢看什么

[2019-11-06]  爱吧机器人网编者按:近日,《自然-神经科学》发表了一篇论文,研究人员创建了一种深度人工神经网络,能够准确预测生物大脑对视觉刺激所产 ...

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

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

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

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

[2018-01-26]  纽约时报的报道,德国的研究人员已经开发出一种长约七分之一英寸的机器人,首先看起来不过是一小块橡皮条。然后它开始移动。机器人走路,跳跃,爬行,滚动和游泳。它甚至爬出......

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

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

哈佛大学《自然》发表新驱动技术,让飞行机器人悬停且不受损伤
哈佛大学《自然》发表新驱动技术,让飞行机器人悬停且不受损伤

[2019-11-06]  哈佛大学研究人员发表在《自然》杂志上的一项最新研究,他们开发了一种由柔软的人造肌肉驱动的机器人蜜蜂(RoboBee),这种机器人在撞墙、 ...

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

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

本周栏目热点

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

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

机器学习选择深层模型的原因

[1970-01-01]   深度学习采用的模型为深层神经网络(Deep Neural Networks,DNN)模型,即包含多个隐藏层(Hidden Layer,也称隐含层)的神经网络(Ne ...

机器学习—自由编码器

[1970-01-01]   一种常见的深层模型是由自编码器(Auto-Encoder)构造的。自编码器可以利用一组无标签的训练数据{x(1), x(2), &hellip }(其中x(i)是一个n ...

【NIPS最佳论文出炉】冷扑大师能战胜AlphaZero吗?No(Science论文)

[2017-12-19]  拿下NIPS2017 最佳论文,登上Science,“冷扑大师”最近有点热。18日,两位作者,CMU博士生Noam Brown和Tuomas Sandholm教授在Reddit上回答问题。对“为什么不使用深度学习......

日本开发团队给机器人嵌入神经网络

[2016-08-18]    近日在日本国立科学博物馆展出的 机器人 Alter,可谓是目前世界上最为先进的机器人之一,因为它是一款嵌入了神经网络的机器人,来自日本 ...