black927 赞了文章 · 2020-03-19
区别于数组,数组的所有的元素在内存中都是连续存储的,而链表则是分散在内存中的,通过指针连接起来的一种数据结构。接下来,我们尝试使用js合并两个有序链表。
首先我们需要声明一些我们需要用到的函数。
每一个节点通常最少有两个属性,一个表示该节点的值,可以用key来表示,另外一个就是指向下一个节点的指针,可以用next表示。
先声明一个Node类:
function Node (key) {
this.key = key;
this.next = null;
}
接着,声明一个链表类LinkedList:
function LinkedList () {
//表示链表的长度
this.length = 0;
//表示链表的头结点(第一个节点)
this.head = null;
}
然后,再声明一个基本的链表方法append,用来向链表尾部插入一个新节点:
LinkedList.prototype.append = function (key){
var node = new Node(key);
//如果链表还没有节点
if (!this.head) {
this.head = node;
} else {
//通过循环找到最后一个节点,然后让最后一个节点指向新节点
var current = this.head;
while(current.next){
current = current.next;
}
current.next = node;
}
// 修改链表的长度
this.length++;
}
我们的目的是合并有序链表,所以这里,我们先用两个有序数组,去构建两个有序链表:
var arr1 = [2, 4, 6, 8];
var arr2 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
list1.append(key);
});
arr2.forEach(function(key){
list2.append(key);
});
就是把两个链表中所有key都拿出来放进一个数组里,庵后,再对数组排序,根据数组,重新构建一个链表。
function mergeLinkedList (list1, list2) {
// 存放两个链表key的数组
var array = [];
// 最终需要返回的新链表
var list = new LinkedList();
// 第一个链表的头节点
var listHead1 = list1.head;
// 第二个链表的头节点
var listHead2 = list2.head;
// 把第一个链表的所有key存进数组
while (listHead1) {
array.push(listHead1.key);
listHead1 = listHead1.next;
}
// 把第二个链表的所有key存进数组
while (listHead2) {
array.push(listHead2.key);
listHead2 = listHead2.next;
}
// 对数组排序
array = array.sort(function(a, b){
return a - b;
})
// 使用数组重新构建一个链表
array.forEach(function(key){
list.append(key);
});
return list;
}
function mergeLinkedList (list1, list2) {
var list = new LinkedList();
// 第一个链表的头节点
var current1 = list1.head;
// 第二个链表的头节点
var current2 = list2.head;
// 用循环把两个链表的key按顺序插入到新链表
while (current1 && current2) {
if (current1.key < current2.key) {
list.append(current1.key);
current1 = current1.next;
} else {
list.append(current2.key);
current2 = current2.next;
}
}
// 找到新链表的最后一个节点
var current = list.head;
while(current.next){
current = current.next;
}
// 循环完成以后,把第二个链表剩余部分插入到新链表
if (current2) {
while (current2) {
list.append(current2.key);
current2 = current2.next;
}
}
// 循环完成以后,把第一个链表剩余部分插入到新链表
if (current1) {
while (current1) {
list.append(current1.key);
current1 = current1.next;
}
}
return list;
}
function mergeLinkedList (list1, list2) {
var listHead1 = list1.head;
var listHead2 = list2.head;
var previous = listHead1;
// 如果第二个链表的首节点key小于第一个链表的首节点key
// 则构造一个新节点,并把新节点插入到第一个链表头部
if (listHead1.key > listHead2.key) {
var node = new Node(listHead2.key);
node.next = listHead1;
list1.head = listHead1 = previous = node;
listHead2 = listHead2.next;
}
// 循环比较两个链表的key,把第二个链表中的key插入到第一个链表合适的位置
while (listHead1 && listHead2) {
if (listHead2.key < listHead1.key) {
var node = new Node(listHead2.key);
node.next = previous.next;
previous.next = node;
previous = node;
listHead2 = listHead2.next;
} else {
previous = listHead1;
listHead1 = listHead1.next;
}
}
// 如果第二个链表比较长,则把剩余部分插入到第一个链表
while (listHead2) {
var node = new Node(listHead2.key);
if (listHead1) {
listHead1.next = node;
listHead1 = node;
} else if (previous) {
previous.next = node;
previous = node;
}
listHead2 = listHead2.next;
}
// 修正第一个链表的长度
list1.length = list1.length + list2.length;
return list1;
}
还是构造两个有序链表
var arr1 = [2, 4, 6, 8];
var arr2 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
list1.append(key);
});
arr2.forEach(function(key){
list2.append(key);
});
var list = mergeLinkedList(list1, list2);
自控制台查看结果:
换一组测试数据(arr1和arr2调换一下):
var arr2 = [2, 4, 6, 8];
var arr1 = [1, 3, 5, 7];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
list1.append(key);
});
arr2.forEach(function(key){
list2.append(key);
});
var list = mergeLinkedList(list1, list2);
看结果:
来一个复杂点的测试数据:
var arr1 = [99, 100, 104, 106];
var arr2 = [1, 3, 5, 7, 102, 103, 107];
var list1 = new LinkedList();
var list2 = new LinkedList();
arr1.forEach(function(key){
list1.append(key);
});
arr2.forEach(function(key){
list2.append(key);
});
var list = mergeLinkedList(list1, list2);
结果如下:
以上代码中,都省去了参数合法性校验的过程,真实环境里是需要的。
查看原文赞 16 收藏 10 评论 0
black927 关注了专栏 · 2020-03-18
Java后端开发,欢迎关注个人微信公众号 Java建设者 及时关注最新技术文章。
关注 8395
black927 关注了专栏 · 2020-03-18
在这里,我们将为你推送 SegmentFault 思否公司官方合作信息,和合作伙伴最新动态。SegmentFault 思否是中国领先的开发者社区和技术媒体,中国最大的 Hackathon 组织者。我们致力于成为科技企业和开发者沟通的桥梁,帮助科技企业和开发者对话。 显示全部
关注 19045
black927 关注了专栏 · 2020-03-18
分享虚拟化、容器化、API化、微服务化的WEB技术,更多务实、能看懂、可复现的原创文章尽在作者公众号 CodeSheep,欢迎订阅
关注 5182
black927 关注了专栏 · 2020-03-18
SegmentFault 思否对开发者行业的洞见、观察与报道
关注 27825
black927 关注了标签 · 2020-03-18
Web前端开发是从网页制作演变而来的,名称上有很明显的时代特征。在互联网的演化进程中,网页制作是Web 1.0时代的产物,那时网站的主要内容都是静态的,用户使用网站的行为也以浏览为主。2005年以后,互联网进入Web 2.0时代,各种类似桌面软件的Web应用大量涌现,网站的前端由此发生了翻天覆地的变化。网页不再只是承载单一的文字和图片,各种富媒体让网页的内容更加生动,网页上软件化的交互形式为用户提供了更好的使用体验,这些都是基于前端技术实现的。
关注 191211
black927 关注了标签 · 2020-03-18
层叠样式表(英语:Cascading Style Sheets,简写CSS),又称串样式列表,由W3C定义和维护的标准,一种用来为结构化文档(如HTML文档或XML应用)添加样式(字体、间距和颜色等)的计算机语言。
关注 94201
black927 关注了标签 · 2020-03-18
Android(安卓或安致)是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。
简介
Android一词的本义指“机器人”,同时也是Google于2007年11月5日宣布的基于Linux平台的开源手机操作系统的名称,该平台由操作系统、中间件、用户界面和应用软件组成。
系统架构
android的系统架构和其操作系统一样,采用了分层的架构。从架构图看,android分为四个层,从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和linux核心层。
应用程序
Android会同一系列核心应用程序包一起发布,该应用程序包包括客户端,SMS短消息程序,日历,地图,浏览器,联系人管理程序等。所有的应用程序都是使用JAVA语言编写的。
应用程序框架
开发人员也可以完全访问核心应用程序所使用的API框架。该应用程序的架构设计简化了组件的重用;任何一个应用程序都可以发布它的功能块并且任何其它的应用程序都可以使用其所发布的功能块(不过得遵循框架的安全性)。同样,该应用程序重用机制也使用户可以方便的替换程序组件。
隐藏在每个应用后面的是一系列的服务和系统, 其中包括;
丰富而又可扩展的视图(Views),可以用来构建应用程序, 它包括列表(lists),网格(grids),文本框(text boxes),按钮(buttons), 甚至可嵌入的web浏览器。
内容提供器(Content Providers)使得应用程序可以访问另一个应用程序的数据(如联系人数据库), 或者共享它们自己的数据
资源管理器(Resource Manager)提供 非代码资源的访问,如本地字符串,图形,和布局文件( layout files )。
通知管理器 (Notification Manager) 使得应用程序可以在状态栏中显示自定义的提示信息。
活动管理器( Activity Manager) 用来管理应用程序生命周期并提供常用的导航回退功能。
有关更多的细节和怎样从头写一个应用程序,请参考 如何编写一个 Android 应用程序。
系统运行库
Android 包含一些C/C++库,这些库能被Android系统中不同的组件使用。它们通过 Android 应用程序框架为开发者提供服务。以下是一些核心库:
* 系统 C 库 - 一个从BSD继承来的标准 C 系统函数库( libc ), 它是专门为基于 embedded linux的设备定制的。
* 媒体库 - 基于PacketVideo OpenCORE;该库支持多种常用的音频、视频格式回放和录制,同时支持静态图像文件。编码格式包括MPEG4, H.264, MP3, AAC, AMR, JPG, PNG 。
* Surface Manager - 对显示子系统的管理,并且为多个应用程序提 供了2D和3D图层的无缝融合。
* LibWebCore - 一个最新的web浏览器引擎用,支持Android浏览器和一个可嵌入的web视图。
应用程序组件
Android开发四大组件分别是:活动(Activity): 用于表现功能。服务(Service): 后台运行服务,不提供界面呈现。广播接收器(BroadcastReceiver):用于接收广播。内容提供商(Content Provider): 支持在多个应用中存储和读取数据,相当于数据库。
活动
Android 中,Activity 是所有程序的根本,所有程序的流程都运行在Activity 之中,Activity可以算是开发者遇到的最频繁,也是Android 当中最基本的模块之一。在Android的程序当中,Activity 一般代表手机屏幕的一屏。如果把手机比作一个浏览器,那么Activity就相当于一个网页。在Activity 当中可以添加一些Button、Check box 等控件。可以看到Activity 概念和网页的概念相当类似。
一般一个Android 应用是由多个Activity 组成的。这多个Activity 之间可以进行相互跳转,例如,按下一个Button 按钮后,可能会跳转到其他的Activity。和网页跳转稍微有些不一样的是,Activity 之间的跳转有可能返回值,例如,从Activity A 跳转到Activity B,那么当Activity B 运行结束的时候,有可能会给Activity A 一个返回值。这样做在很多时候是相当方便的。
当打开一个新的屏幕时,之前一个屏幕会被置为暂停状态,并且压入历史堆栈中。用户可以通过回退操作返回到以前打开过的屏幕。我们可以选择性的移除一些没有必要保留的屏幕,因为Android会把每个应用的开始到当前的每个屏幕保存在堆栈中。
服务
Service 是android 系统中的一种组件,它跟Activity 的级别差不多,但是他不能自己运行,只能后台运行,并且可以和其他组件进行交互。Service 是没有界面的长生命周期的代码。Service 是一种程序,它可以运行很长时间,但是它却没有用户界面。这么说有点枯燥,来看个例子。打开一个音乐播放器的程序,这个时候若想上网了,那么,我们打开Android 浏览器,这个时候虽然我们已经进入了浏览器这个程序,但是,歌曲播放并没有停止,而是在后台继续一首接着一首的播放。其实这个播放就是由播放音乐的Service进行控制。当然这个播放音乐的Service也可以停止,例如,当播放列表里边的歌曲都结束,或者用户按下了停止音乐播放的快捷键等。service 可以在和多场合的应用中使用,比如播放多媒体的时候用户启动了其他Activity这个时候程序要在后台继续播放,比如检测SD 卡上文件的变化,再或者在后台记录你地理信息位置的改变等等,总之服务嘛,总是藏在后头的。
开启service有两种方式:
(1) Context.startService():Service会经历onCreate -> onStart(如果Service还没有运行,则android先调用onCreate()然后调用onStart();如果Service已经运行,则只调用onStart(),所以一个Service的onStart方法可能会重复调用多次 );stopService的时候直接onDestroy,如果是调用者自己直接退出而没有调用stopService的话,Service会一直在后台运行。该Service的调用者再启动起来后可以通过stopService关闭Service。 注意,多次调用Context.startservice()不会嵌套(即使会有相应的onStart()方法被调用),所以无论同一个服务被启动了多少次,一旦调用Context.stopService()或者stopSelf(),他都会被停止。补充说明:传递给startService()的Intent对象会传递给onStart()方法。调用顺序为:onCreate --> onStart(可多次调用) --> onDestroy。
(2) Context.bindService():Service会经历onCreate() --> onBind(),onBind将返回给客户端一个IBind接口实例,IBind允许客户端回调服务的方法,比如得到Service运行的状态或其他操作。这个时候把调用者(Context,例如Activity)会和Service绑定在一起,Context退出了,Srevice就会调用onUnbind --> onDestroyed相应退出,所谓绑定在一起就共存亡了。[20]
广播接收器
在Android 中,Broadcast 是一种广泛运用的在应用程序之间传输信息的机制。而BroadcastReceiver 是对发送出来的Broadcast进行过滤接受并响应的一类组件。可以使用BroadcastReceiver 来让应用对一个外部的事件做出响应。这是非常有意思的,例如,当电话呼入这个外部事件到来的时候,可以利用BroadcastReceiver 进行处理。例如,当下载一个程序成功完成的时候,仍然可以利用BroadcastReceiver 进行处理。BroadcastReceiver不能生成UI,也就是说对于用户来说不是透明的,用户是看不到的。BroadcastReceiver通过NotificationManager 来通知用户这些事情发生了。BroadcastReceiver 既可以在AndroidManifest.xml 中注册,也可以在运行时的代码中使用Context.registerReceiver()进行注册。只要是注册了,当事件来临的时候,即使程序没有启动,系统也在需要的时候启动程序。各种应用还可以通过使用Context.sendBroadcast () 将它们自己的intent broadcasts广播给其他应用程序。
注册BroadcastReceiver有两种方式:
(1)在AndroidManifest.xml进行注册。这种方法有一个特点即使你的应用程序已经关闭了,但这个BroadcastReceiver依然会接受广播出来的对象,也就是说无论你这个应用程序时开还是关都属于活动状态都可以接受到广播的事件;
(2)在代码中注册广播。
第一种俗称静态注册,第二种俗称动态注册,这两种注册Broadcast Receiver的区别:
动态注册较静态注册灵活。实验证明:当静态注册一个Broadcast Receiver时,不论应用程序是启动与否。都可以接受对应的广播。
动态注册的时候,如果不执行unregister Receiver();方法取消注册,跟静态是一样的。但是如果执行该方法,当执行过以后,就不能接受广播了。
内容提供
Content Provider 是Android提供的第三方应用数据的访问方案。
在Android中,对数据的保护是很严密的,除了放在SD卡中的数据,一个应用所持有的数据库、文件等内容,都是不允许其他直接访问的。Andorid当然不会真的把每个应用都做成一座孤岛,它为所有应用都准备了一扇窗,这就是Content Provider。应用想对外提供的数据,可以通过派生Content Provider类, 封装成一枚Content Provider,每个Content Provider都用一个uri作为独立的标识,形如:content://com.xxxxx。所有东西看着像REST的样子,但实际上,它比REST 更为灵活。和REST类似,uri也可以有两种类型,一种是带id的,另一种是列表的,但实现者不需要按照这个模式来做,给你id的uri你也可以返回列表类型的数据,只要调用者明白,就无妨,不用苛求所谓的REST。
另外,Content Provider不和REST一样只有uri可用,还可以接受Projection,Selection,OrderBy等参数,这样,就可以像数据库那样进行投影,选择和排序。查询到的结果,以Cursor(参见:reference/android/database/Cursor.html )的形式进行返回,调用者可以移动Cursor来访问各列的数据。
Content Provider屏蔽了内部数据的存储细节,向外提供了上述统一的接口模型,这样的抽象层次,大大简化了上层应用的书写,也对数据的整合提供了更方便的途径。Content Provider内部,常用数据库来实现,Android提供了强大的Sqlite支持,但很多时候,你也可以封装文件或其他混合的数据。
在Android中,Content Resolver是用来发起Content Provider的定位和访问的。不过它仅提供了同步访问的Content Provider的接口。但通常,Content Provider需要访问的可能是数据库等大数据源,效率上不足够快,会导致调用线程的拥塞。因此Android提供了一个AsyncQueryHandler(参见:reference/android/content/AsyncQueryHandler.html),帮助进行异步访问Content Provider。
在各大组件中,Service和Content Provider都是那种需要持续访问的。Service如果是一个耗时的场景,往往会提供异步访问的接口,而Content Provider不论效率如何,都提供的是约定的同步访问接口。
软件开发
Java方面
Android支持使用Java作为编程语言来开发应用程序,而Android的Java开发方面从接口到功能,都有层出不穷的变化。考虑到Java虚拟机的效率和资源占用,谷歌重新设计了Android的Java,以便能提高效率和减少资源占用,因而与J2ME等不同。其中Activity等同于J2ME的MIDlet,一个 Activity 类(Class)负责创建视窗(Windows),一个活动中的Activity就是在 foreground(前景)模式,背景运行的程序叫做Service。两者之间通过由ServiceConnection和AIDL连结,达到复数程序同时运行效果。如果运行中的 Activity 全部画面被其他 Activity 取代时,该 Activity 便被停止(Stopped),甚至被系统清除(Kill)。
View等同于J2ME的Displayable,程序人员可以通过 View 类与“XML layout”档将UI放置在视窗上,Android 1.5的版本可以利用 View 打造出所谓的 Widgets,其实Widget只是View的一种,所以可以使用xml来设计layout,HTC的Android Hero手机即含有大量的widget。至于ViewGroup 是各种layout 的基础抽象类(abstract class),ViewGroup之内还可以有ViewGroup。View的构造函数不需要再Activity中调用,但是Displayable的是必须的,在Activity 中,要通过findViewById()来从XML 中取得View,Android的View类的显示很大程度上是从XML中读取的。View 与事件(event)息息相关,两者之间通过Listener 结合在一起,每一个View都可以注册一个event listener,例如:当View要处理用户触碰(touch)的事件时,就要向Android框架注册View.OnClickListener。另外还有BitMap等同于J2ME的Image。
关注 64624
black927 关注了标签 · 2020-03-18
MySQL是一个小型关系型数据库管理系统,开发者为瑞典MySQL AB公司。在2008年1月16号被Sun公司收购。而2009年,SUN又被Oracle收购。MySQL是一种关联数据库管理系统,关联数据库将数据保存在不同的表中,而不是将所有数据放在一个大仓库内。这样就增加了速度并提高了灵活性。MySQL的SQL“结构化查询语言”。SQL是用于访问数据库的最常用标准化语言。MySQL软件采用了GPL(GNU通用公共许可证)。由于其体积小、速度快、总体拥有成本低,尤其是开放源码这一特点,许多中小型网站为了降低网站总体拥有成本而选择了MySQL作为网站数据库。
关注 72751
black927 关注了标签 · 2020-03-18
超文本标记语言(英文:HyperText Markup Language,HTML)是为“网页创建和其它可在网页浏览器中看到的信息”设计的一种标记语言。
关注 66314
black927 关注了标签 · 2020-03-18
Linux是一种自由和开放源代码的类Unix计算机操作系统。目前存在着许多不同的Linux,但它们全都使用了Linux内核。Linux可安装在各种各样的计算机硬件设备,从手机、平板电脑、路由器和视频游戏控制台,到台式计算机,大型机和超级计算机。
Linux家族家谱图,很全很强大!! 图中可以清楚的看出各个Linux发行版的血缘关系。无水印原图:http://url.cn/5ONhQb
关注 79120
black927 关注了标签 · 2020-03-18
Reactive Components for Modern Web Interfaces.
Vue.js 是一个用于创建 web 交互界面的。其特点是
关注 134363
black927 关注了标签 · 2020-03-18
JavaScript 是一门弱类型的动态脚本语言,支持多种编程范式,包括面向对象和函数式编程,被广泛用于 Web 开发。
一般来说,完整的JavaScript包括以下几个部分:
它的基本特点如下:
JavaScript常用来完成以下任务:
关注 173172
推荐关注