来自 编程应用 2019-09-13 05:09 的文章
当前位置: 六合联盟网 > 编程应用 > 正文

算法实战之路,学习数据结构

图片 1

一直以来都知道自己在数据结构上是个弱点,大学时期学的东西到现在就只能记得一个概念了,自从期末考完试就都还给老师了。要开始找工作面试了,决定把这些东西都重新温习一遍。

上期我们探讨了使用Swift如何破解数组、字符串、集合、字典相关的算法题。本期我们一起来讲讲用Swift如何实现链表以及链表相关的技巧。本期主要内容有:

数据结构中最基础的应该就是线性表(线性表:零个或多个数据元素的有限序列)了,线性表根据物理结构的不同分为顺序存储结构和链式存储结构,顺序结构实现就是数组了,链式结构就是链表了。

  • 链表基本结构
  • Dummy节点
  • 尾插法
  • 快行指针

定义:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

对于链表的概念,实在是基本概念太多,这里不做赘述。我们直接来实现链表节点。

链表分为单项链表,双向链表和循环链表,一般情况下单项链表居多。推荐看一下J_Knight_在掘金上的文章(末尾有链接,链表要实现节点和链式结构

class ListNode { var val: Int var next: ListNode? init(_ val: Int) { self.val = val self.next = nil }}

节点是链表的基本单元,单项链表节点只有next指针,双向链表包含next和previous两个指针

有了节点,就可以实现链表了。

ADT 节点Data value:持有的数据Operation init:初始化 previous:指向上一节点的指针 next:指向下一节点的指针endADT
class List { var head: ListNode? var tail: ListNode? // 尾插法 func appendToTail(_ val: Int) { if tail == nil { tail = ListNode head = tail } else { tail!.next = ListNode tail = tail!.next } } // 头插法 func appendToHead(_ val: Int) { if head == nil { head = ListNode tail = head } else { let temp = ListNode temp.next = head head = temp } }}

链表实现了一些主要的操作功能,如插入节点,删除节点,查询节点等

有了上面的基本操作,我们来看如何解决复杂的问题。

ADT 链表(linked list)Data linked list:持有的线性表Operation init:初始化 count:持有节点总个数 isEmpty:是否为空 first:头节点 last:尾节点 node:传入index返回节点 insert:插入node到指定index insertToHead:插入节点到表头 appendToTail:插入节点到表尾 removeAll:移除所有节点 remove:移除传入的节点 removeAt:移除传入index的节点endADT

话不多说,我们直接先来看下面一道题目。

具体代码就不贴了,J_Knight_在掘金上写的很清楚了,建议自己敲一遍,还是很有作用的,我想分享一下在iOS面试之道上涉及到链表的三道题并记录一下我当时的想法。

给一个链表和一个值x,要求将链表中所有小于x的值放到左边,所有大于等于x的值放到右边。原链表的节点顺序不能变。例:1->5->3->2->4->2,给定x = 3。则我们要返回 1->2->2->5->3->4

question1:给出一个链表和一个值x,要求将链表中所有小于x的值放到左边,大于等于x的值放到右边,并且保证原链表节点的顺序不变,例子:List:1->5->3->2->4->2 x = 3 结果为:1->2->3->5->3->4

解题思路:使用两个链表,一个记录比x小的值,一个记录比x大的值,使用尾插法来保证节点的顺序是不变的,最后将两个链表连接起来。

Dummy节点:它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个,它有可能是原链表的第一个节点,可能在原链表的中间,也可能在最后,甚至可能不存在。

实现代码:

func LinkedListSort(_ head : LinkedList<Int>, _ x : Int) -> LinkedList<Int>{ let prevDummy = LinkedListNode<Int> , postDummy = LinkedListNode<Int> var prev = prevDummy , post = postDummy var node = head.first while node != nil { if((node?.value)! < x){ prev.next = node prev = node! }else{ post.next = node post = node! } node = node!.next } post.next = nil prev.next = postDummy.next return head}

直觉告诉我们,这题要先处理左边,然后再处理右边,最后再把左右两边拼起来。思路有了,再把题目抽象一下,就是要实现这样一个函数:

question2:如何检测链表中是否有环存在(这道题在去苏宁面试的时候问过的)

解题思路:用两个指针同时访问链表,其中一个的速度是另一个的两倍,如果他们变成相等的,那么链表存在环,反之则链表不存在环(这个理论我思考了很久,不明白为什么快指针一定会和慢指针指向同一个节点,后来想通了,因为有环的链表是不会over的,两个指针一定会指向同一个节点)

实现代码:

func isExistCircle(_ List : LinkedList<Int>) -> Bool{ let head = List.first var slow = head var fast = head while fast != nil && fast?.next != nil{ slow = slow?.next fast = fast?.next?.next if slow === fast{ return true } } return false}
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {}

Question 3:给出链表和一个值x,要求将链表中倒数第x个节点删掉(链表为一个未知长度的单向链表)

解题思路:使用两个速度相同的指针,快指针领先慢指针x个节点,当快指针到达终点时,慢指针的下一个节点就是我们要删除的节点。(我当时直接用链表里面的size函数获得链表长度,用remove函数删除了对应的节点,但是remove函数是基于双向链表实现的,如果是单项链表的话是不可以直接remove的)

实现代码:

func removeFromEnd(_ List : LinkedList<Int>, _ x : Int ) -> LinkedList<Int>{ let head = List.first var slow = head var fast = head //设置快指针初始位置 for _ in 0 ..< x { fast = fast?.next } while fast != nil && fast?.next != nil{ slow = slow?.next fast = fast?.next } //List.remove(node: (slow?.next)!)//remove函数是基于双向链表实现的,单项链表无法使用 slow?.next = slow?.next?.next return List}

链表章节就这三道题了,主要还是学到了dummy节点和快行指针这样的概念,比较有收获。

链接:J_Knight_掘金地址

iOS面试之道 链表章节内容

iOS面试之道

即我们有给定链表的头节点,有给定的x值,要求返回新链表的头结点。接下来我们要想:怎么处理左边?怎么处理右边?处理完后怎么拼接?先来看怎么处理左边。我们不妨把这个题目先变简单一点:

给一个链表和一个值x,要求只保留链表中所有小于x的值,原链表的节点顺序不能变。例:1->5->3->2->4->2,给定x = 3。则我们要返回 1->2->2

我们只要采用尾插法,遍历链表,将小于x值的节点接入新的链表即可。代码如下:

func getLeftList(_ head: ListNode?, _ x: Int) -> ListNode? { let dummy = ListNode var pre = dummy var node = head while node != nil { if node!.val < x { pre.next = node pre = node! } node = node!.next } node.next = nil return dummy.next}

注意,上面的代码我们引入了Dummy节点,它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个,它有可能是原链表的第一个节点,可能在原链表的中间,也可能在最后,甚至可能不存在。而Dummy节点的引入可以巧妙的涵盖所有以上情况,我们可以用dummy.next方便得返回最终需要的头结点。现在我们解决了左边,右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下:

func partition(_ head: ListNode?, _ x: Int) -> ListNode? { // 引入Dummy节点 let prevDummy = ListNode var prev = prevDummy let postDummy = ListNode var post = postDummy var node = head // 用尾插法处理左边和右边 while node != nil { if node!.val < x { prev.next = node prev = node! } else { post.next = node post = node! } node = node!.next } // 左右拼接 post.next = nil prev.next = postDummy.next return prevDummy.next}

注意这句post.next = nil,这是为了防止链表循环指向构成环,是必须的但是很容易忽略的一步。刚才我们提到了环,那么怎么检测链表中是否有环存在呢?

图片 2

笔者理解快行指针,就是两个指针访问链表,一个在前一个在后,或者一个移动快另一个移动慢,这就是快行指针。所以如何检测一个链表中是否有环?用两个指针同时访问链表,其中一个的速度是另一个的2倍,如果他们相等了,那么这个链表就有环了。代码如下:

func hasCycle(_ head: ListNode?) -> Bool { var slow = head var fast = head while fast != nil && fast!.next != nil { slow = slow!.next fast = fast!.next!.next if slow === fast { return true } } return false}

再举一个快行指针一前一后的例子,看下面这道题。

删除链表中倒数第n个节点。例:1->2->3->4->5,n = 2。返回1->2->3->5。注意:给定n的长度小于等于链表的长度。

解题思路依然是快行指针,这次两个指针移动速度相同。但是一开始,第一个指针就落后第二个指针n个节点。接着两者同时移动,当第二个移动到尾节点时,第一个节点的下一个节点就是我们要删除的节点。代码如下:

func removeNthFromEnd(head: ListNode?, _ n: Int) -> ListNode? { guard let head = head else { return nil } let dummy = ListNode dummy.next = head var prev: ListNode? = dummy var post: ListNode? = dummy // 设置后一个节点初始位置 for _ in 0 ..< n { if post == nil { break } post = post!.next } // 同时移动前后节点 while post != nil && post!.next != nil { prev = prev!.next post = post!.next } // 删除节点 prev!.next = prev!.next!.next return dummy.next}

这里还用到了Dummy节点,因为有可能我们要删除的是头结点。

这次我们用Swift实现了链表的基本结构,并且实战了链表的几个技巧。在结尾处,我还想强调一下Swift处理链表问题的两个细节问题:

  • 一定要注意头结点可能就是nil。所以给定链表,我们要看清楚head是不是optional,在判断是不是要处理这种边界条件。
  • 注意每个节点的next可能是nil。如果不为nil,请用"!"修饰变量。在赋值的时候,也请注意"!"将optional节点传给非optional节点的情况。

本文由六合联盟网发布于编程应用,转载请注明出处:算法实战之路,学习数据结构

关键词: