美文网首页
常见数据结构和算法

常见数据结构和算法

作者: bug去无踪 | 来源:发表于2022-02-25 13:46 被阅读0次

    常见数据结构

    线性数据结构(按顺序具有数据元素的数据结构):数组,堆栈,链表(单链表 双链表),队列
    非线性数据结构(以非顺序方式存储数据):树,图,表。

    时间复杂度和空间复杂度

    时间复杂度执行这个算法耗费的时间

    空间复杂度是指执行这个算法所需要的内存空间

    1.数组

    在内存内连续的存储
    查找十分快捷,a[k]_address = base_address + k * type_size k从0开始
    下标不从1开始,如果从1开始,需要做一次减法 k-1,每次都要
    但是不利于插入或者删除元素,需要对元素进行移动

    2.单链表

    不需要连续的存储空间,插入或者删除一个节点方便,但是删除的时候需要先查找,也是会耗时,每个节点不仅要存储自己节点的值,还需要存储下一个节点的地址,比数组的存储空间需要更大。
    循环单链表,尾指针指向头节点


    image.png
    package main
    
    import "fmt"
    
    func main() {
        //构建一个单链表
        result:=GetNewListNode(6)
       // 在链表头部增加一个元素
       result=AddOneNodeBeforeHead(result,9)
       result.Println()
       // 在链表尾部增加一个元素
       result.AddOneNodeFromLast(10)
       result.Println()
       fmt.Println("链表长度:",result.GetListLength(),"\n")
        //链表反转
      result= result.ListRever()
      result.Println()
      
       //找出链表的中间元素
       //删除链表的倒数第n个元素
       //移除链表的某个元素
       
       //链表有换头操作需要返回新链表
    
        //result.Println()
     
    }
    
    type ListNode struct {
        Val  int
        Next *ListNode
    }
     // 新增一个指定长度的链表
    func GetNewListNode(max int)*ListNode{
      result:=&ListNode{
        Val:max,
      }
      
      for i:=max-1;i>=1;i--{
        node:=&ListNode{
          Val:i,
        }
        node.Next=result
        result=node
      }
      return result
    }
    // 链表头部增加一个元素
    func AddOneNodeBeforeHead(n *ListNode,val int)*ListNode{
      node:=&ListNode{Val:val}
      node.Next=n
      return node
    }
    // 尾部增加一个节点
    func (list *ListNode) AddOneNodeFromLast(val int){
      for list!=nil{
        if list.Next==nil{
          list.Next=&ListNode{Val:10}
          return 
        }
        list=list.Next
      }
    }
    // 打印链表的值
    func  (n *ListNode) Println(){
      for n!=nil{
          fmt.Println(n.Val)
          n=n.Next
      }
      fmt.Println("\n")
    }
    //获取链表长度
    func (list *ListNode) GetListLength()int{
      n:=0
      for list!=nil{
         n++
        list=list.Next
      }
      return n
    }
    // 链表反转
    func (list *ListNode) ListRever()*ListNode{
      curl:=list
      var pre *ListNode=nil
      for curl!=nil{
        pre,curl,curl.Next=curl,curl.Next,pre
      }
      return pre
    }
    //递归链表反转
    func ListRever1(head *ListNode) *ListNode {
        if head == nil || head.Next == nil {
            return head
        }
        newList := ListRever1(head.Next)
        // 改变 1,2节点的指向。
        // 通过 head.next获取节点2
        t1 := head.Next
        // 让 2 的 next 指向 2
        t1.Next = head
        // 1 的 next 指向 null.
        head.Next = nil
    
        return newList
    }
    
    
    // 链表反转(迭代法)
    //定义三节点,名字前中后,中如不为空,继续遍历表,
    //前中后换位,同时往后移动,最后返回前,得到反转表
    func (list *ListNode) ListRever2()*ListNode{
      var pre *ListNode
      middle:=list
      var next*ListNode
      var pre *ListNode=nil
      for middle!=nil{
       next=middle.Next
       middle.Next=pre
       pre=middle
       middle=next
        
      }
      return pre
    }
    // 快慢节点法查找中间节点
    func (list *ListNode) GetMiddleNode() (middle []int){
      fast:=list
      slow:=list
      for slow!=nil{
        //奇数个节点
        if fast.Next==nil{
          return append(middle,slow.Val)
        }
        //偶数个节点
        if fast.Next!=nil&&fast.Next.Next==nil{
          return append(middle,slow.Val,slow.Next.Val)
        }
         
        slow=slow.Next
        fast=fast.Next.Next
      }
      return middle
      
    }
    // 删除元素,以当前节点是否为nil为循环结束条件
    func (head *ListNode) DeleteNodeByVal(val int)*ListNode{
       // 构建一个虚拟节点
        newHead := &ListNode{0,head}
        pre, cur := newHead, head
        for cur != nil {
            if cur.Val == val {
                pre.Next = cur.Next
                break
            }
            pre = cur
            cur = cur.Next
        }
        return newHead.Next
    }
    // 删除一个节点 以下一个元素是否为nil为循环条件。找到要删除节点的前一个节点,修改它的后继指针
    func (head *ListNode) DeleteNodeByVal11(val int){
      //删除第一个
       if head.Val==val{
        head=head.Next
        return
       }
        pre:=head
        for pre.Next != nil {
            if pre.Next.Val == val {
                pre.Next = pre.Next.Next
                break
            }
            pre = pre.Next
        }
        return 
    }
    // 增加一个环
    func (n *ListNode) AddOneCycle(){
      head:=n
      var pre*listNode=nil
        for n!=nil{
        if n.Next==nil{
        // 来到尾部
         // 最后一个元素指向前一个元素
          n.Next=pre
          return
        }
        pre=n
        n=n.Next
      }
    }
     //检测链表中是否有环 快慢指针法,类似环形跑到,两个人在上面跑步,总有会相遇的时候,相遇时两个人的位置一样
    func (n *ListNode)  HasCycle()bool{
      fast:=n
      slow:=n
      for fast!=nil&&fast.Next!=nil{
         fast=fast.Next.Next
         slow=slow.Next
        if slow==fast{
          return true
        }
      }
      return false
        
    }
    //足迹法找环,存在的话就用map记录一次这个指针
    func LinkedLoopDetection1(node *ListNode) bool {
        if node == nil || node.Next == nil {
            return false
        }
    
        nodeMap := make(map[*ListNode]bool, 0)
        for node != nil && node.Next != nil {
            if _,ok:=nodeMap[node] ;ok {
                return true
            } else {
                nodeMap[node] = true
            }
                  node=node.Next
        }
    
        return false
    }
    
    
    2.2删除倒数第n个节点

    先找到要删除节点的前一个节点,也就是倒数第n+1个节点

    if head==nil{
            return head
        }
        length:=0
        temp:=head
        for temp!=nil{
            length++
            temp=temp.Next
        }
        count:=0
        del:=length-n+1 //倒数第n个,就是正数第length-n+1
        if del==0{
            return head.Next
        }
        tmp:=head
        for tmp!=nil{
            count++
            // 找到要删除元素的前一个元素,将这个元素的next节点指向要删除节点的下一个节点
            if count==(del-1){
                tmp.Next = tmp.Next.Next
                break
            }
            tmp = tmp.Next
        }
        return head
    
    // 快慢指针 快指针先走n
    func removeFromEnd(head *ListNode, n int) *ListNode {
       if head==nil{
            return head
        }
    //构建虚拟节点,防止删除头结点时找不到
        newHead:=&ListNode{Value:-1,Next:head}
        fast:=newHead
        slow:=newHead
        i:=0
        for fast!=nil{
            if i<=n{
                fast=fast.Next
                i++
            }else{
               slow= slow.Next
               fast=fast.Next
            }
        }
        slow.Next=slow.Next.Next
         //剔除虚拟节点
        return newHead.Next
    
    }
    
    2.5 两个有序链表合并
    2.6 两个无环有序链表是否相交,如果有返回交点

    1.空间复杂度为O(n),时间复杂度也是O(n) // 使用map,判断另一个链表的地址
    2.空间复杂度为O(1),时间复杂度是O(n) // 先计算出两个链表的长度,判断尾节点是否相同,不相同肯定不相交,长的先走差的长度步数,然后再一起走,判断节点的地址是否相同

    func NoLoop(headA, headB *ListNode) *ListNode {
        //1.先判断尾节点是否相同,计算两个链表的长度length1 length2
        if headA==nil||headB==nil{
            return nil
        }
        n1:=headA
        n2:=headB
        length:=0
        for n1.Next!=nil{
            length++
            n1=n1.Next
        }
         for n2.Next!=nil{
            length--
            n2=n2.Next
        }
        // 2.尾节点不相等,一定不相交
        if n1!=n2{
            return nil
        }
        n1=headA
        n2=headB
        if length<0{
           n1=headB
           n2=headA
        }
        length = int(math.Abs(float64(length)))
        for ;length!=0;length--{
            n1=n1.Next
        }
        // 3.让长链表先走两个链表的差值步数,然后一起走,判断节点是否相同
        for n2!=n1{
            n1=n1.Next
            n2=n2.Next
        }
        return n1
    }
    
    2.7 某个有序链表如果存在环,返回入环节点

    1.空间复杂度为O(n),时间复杂度也是O(n) // 使用map,判断地址
    2.空间复杂度为O(1),时间复杂度是O(n) // 快慢指针

    func detectCycle(head *ListNode) *ListNode {
       if head==nil||head.Next==nil||head.Next.Next==nil{
            return nil
        }
        //快慢指针找到相遇的节点,慢指针不动,
        f:=head.Next.Next
        s:=head.Next
        for f!=s{
            if f.Next==nil||f.Next.Next==nil{
                return nil
            }
            f=f.Next.Next
            s=s.Next
        }
        
        //快指针从头开始走,当快慢指针相等时,即是入口节点
        f=head
        for f!=s{
            f=f.Next
            s=s.Next
        }
        return s
    }
    
    2.8 返回某两个链表的相交节点(分为有环和无环)
    1.无环情况为2.6代码所示
    2.有环有交点的情况
    两个链表有环情况的可能性.png

    2.1 两个链表共用一个环,环的入口一致,使用2.7的方法找到入口节点,将两个链表的结束节点为环的入口节点即可,图中左边的情况 终止条件为当前节点到了环入口节点时
    2.2 如果两个链表共用一个环,环的入口不是一个,同理也是先找到两个链表的入环节点loop1和loop2,如图右边的情况

    func BothLoop(headA, headB, loop1, loop2 *ListNode) *ListNode {
        //1.先判断尾节点是否相同,计算两个链表的长度length1 length2
        if headA == nil || headB == nil {
            return nil
        }
        n1 := headA
        n2 := headB
        if loop1 == loop2 {
            length := 0
            for n1.Next != loop1 {
                length++
                n1 = n1.Next
            }
            for n2.Next != loop2 {
                length--
                n2 = n2.Next
            }
            // 2.尾节点不相等,一定不相交
            if n1 != n2 {
                return nil
            }
            n1 = headA
            n2 = headB
            if length < 0 {
                n1 = headB
                n2 = headA
            }
            length = int(math.Abs(float64(length)))
            for ; length != 0; length-- {
                n1 = n1.Next
            }
            //3.让长链表先走两个链表的差值步数,然后一起走,判断节点是否相同
            for n2 != n1 {
                n1 = n1.Next
                n2 = n2.Next
            }
            return n1
        } else {
            //如果转回了loop1,还没遇到loop2,则说明不相交
            n1 = loop1.Next
            for n1 != loop1 {
                if n1 == loop2 {
                    //返回loop1和loop2都可以
                    return loop1
                }
                n1 = n1.Next
            }
            return nil
        }
    
    }
    func NoLoop(headA, headB *ListNode) *ListNode {
        //1.先判断尾节点是否相同,计算两个链表的长度length1 length2
        if headA == nil || headB == nil {
            return nil
        }
        n1 := headA
        n2 := headB
        length := 0
        for n1.Next != nil {
            length++
            n1 = n1.Next
        }
        for n2.Next != nil {
            length--
            n2 = n2.Next
        }
        // 2.尾节点不相等,一定不相交
        if n1 != n2 {
            return nil
        }
        n1 = headA
        n2 = headB
        if length < 0 {
            n1 = headB
            n2 = headA
        }
        length = int(math.Abs(float64(length)))
        for ; length != 0; length-- {
            n1 = n1.Next
        }
        //3.让长链表先走两个链表的差值步数,然后一起走,判断节点是否相同
        for n2 != n1 {
            n1 = n1.Next
            n2 = n2.Next
        }
        return n1
    }
    func detectCycle(head *ListNode) *ListNode {
        if head == nil || head.Next == nil || head.Next.Next == nil {
            return nil
        }
        //快慢指针找到相遇的节点,慢指针不动,
        f := head.Next.Next
        s := head.Next
        for f != s {
            if f.Next == nil || f.Next.Next == nil {
                return nil
            }
            f = f.Next.Next
            s = s.Next
        }
    
        //快指针从头开始走,当快慢指针相等时,即是入口节点
        f = head
        for f != s {
            f = f.Next
            s = s.Next
        }
        return s
    }
    //主代码入口
    func GetListSameNode(headA, headB *ListNode) *ListNode {
        loop1 := detectCycle(headA)
        loop2 := detectCycle(headB)
             //无环情况
        if loop1 == nil && loop2 == nil {
            return NoLoop(headA, headB)
        }
           //有环情况, 有两种情况,如图所示
        if loop1 != nil && loop2 != nil {
            return BothLoop(headA, headB, loop1, loop2)
        }
        return nil
    }
    

    3.双链表

    记录链表的前驱节点和后继节点,双链表,
    循环双链链表,头尾指针相连
    LRU算法链表简单实现

    func main() {
        lRUCache := Constructor(2)
        lRUCache.put(1, 1)           // 缓存是 {1=1}
        lRUCache.put(2, 2)           // 缓存是 {1=1, 2=2}
        lRUCache.get(1)              // 返回 1
        lRUCache.put(3, 3)           // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
        fmt.Println(lRUCache.get(2)) // 返回 -1 (未找到)
        lRUCache.put(4, 4)           // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
        lRUCache.get(1)              // 返回 -1 (未找到)
        lRUCache.get(3)              // 返回 3
        lRUCache.get(4)              // 返回 4
    }
    
    //LRU算法
    type LRUCache struct {
        size, cap  int               //缓存的大小和容量
        cache      map[int]*LinkNode //存储的key和节点的对应关系
        head, tail *LinkNode         //头尾节点 不存储数据,不包括在size里面
        sync.Mutex
    }
    
    //双链表
    type LinkNode struct {
        key, val  int
        pre, next *LinkNode 
    }
    
    func NewLinkNode(k, v int) *LinkNode {
        return &LinkNode{key: k, val: v}
    }
    
    // 初始化
    func Constructor(capacity int) LRUCache {
        l := LRUCache{
            cap:   capacity,
            size:  0,
            cache: make(map[int]*LinkNode),
            head:  &LinkNode{key: 0, val: 0},
            tail:  &LinkNode{key: 0, val: 0},
        }
        l.head.next = l.tail
        l.tail.pre = l.head
        return l
    }
    
    // 删除一个节点
    func RemoveNode(node *LinkNode) {
        node.pre.next = node.next
        node.next.pre = node.pre
    }
    
    // 删除尾部节点
    func (this *LRUCache) RemoveTail() *LinkNode {
        //尾节点不存储数据,所以取前一个节点作为有效尾节点
        node := this.tail.pre
        RemoveNode(node)
        return node
    }
    
    func (this *LRUCache) AddHead(node *LinkNode) {
        node.next = this.head.next
        node.pre = this.head
        this.head.next.pre = node
        this.head.next = node
    
    }
    
    //将节点删除并移动到头部
    func (this *LRUCache) MoveToHead(node *LinkNode) {
        //删除节点
        RemoveNode(node)
        //移动到头部
        this.AddHead(node)
    }
    
    func (this *LRUCache) get(key int) int {
        //读取元素,被读取的放到头部去
        this.Lock()
        defer this.Unlock()
        if node, ok := this.cache[key]; ok {
            //移动到头部
            this.MoveToHead(node)
            return node.val
        }
        return -1
    }
    
    func (this *LRUCache) put(key int, value int) {
        //存入元素,已经存在修改值,并移动到头部,不存在放入,并插入到头部
        this.Lock()
        defer this.Unlock()
        if node, ok := this.cache[key]; ok {
            // 存在,修改vaL
            node.val = value
            // 移动元素到头部
            this.MoveToHead(node)
        } else {
            newNode := NewLinkNode(key, value)
            //插入到头部
            this.AddHead(newNode)
            this.cache[key] = newNode
            this.size++
            //容量超了删除尾部元素,size减少,删除缓存key
            fmt.Println("key:", key, "size:", this.size)
            if this.size > this.cap {
                //删除尾部元素
                node := this.RemoveTail()
                fmt.Println("wei bu", node.key)
                this.size--
                delete(this.cache, node.key)
            }
        }
    }
    
    

    4.队列

    先进先出,可以用数组实现一个队列,也可以链表实现采用头插法,尾部取元素

    5.栈

    先进后出,可以用数组或者链表实现一个栈
    应用:浏览器的前进和后退,两个栈

    type Pop struct {
        Arr []interface{}
    }
    
    func NewPop() *Pop {
        return &Pop{Arr: make([]interface{}, 0)}
    }
    
    func (p *Pop) AddTenNumber() {
        for i := 1; i <= 10; i++ {
            p.AddPop(i)
        }
    }
    
    func (p *Pop) OutFiveNumber() {
        for i := 1; i <= 5; i++ {
            p.OutPop()
        }
    }
    
    // 入栈元素
    func (p *Pop) AddPop(a interface{}) {
        p.Arr = append(p.Arr, a)
    }
    func (p *Pop) Length() int {
        return len(p.Arr)
    }
    
    // 出栈元素
    func (p *Pop) OutPop() {
        if p.Length() <= 1 {
            p.Arr = nil
            return
        }
        //fmt.Println(p.Arr)
        p.Arr = p.Arr[:p.Length()-1]
    }
    
    // 打印栈的元素
    func (p *Pop) PrintlnPop() {
        for i := p.Length() - 1; i >= 0; i-- {
            fmt.Println("a=", p.Arr[i])
        }
    }
    
    

    6.二叉树

    二叉树的遍历(递归和非递归)

    6.1递归遍历
    type TreeNode struct {
        value int
        left  *TreeNode
        right *TreeNode
    }
    func main() {
        PreDigui(GetATree())
        fmt.Println()
        MiddleDigui(GetATree())
        fmt.Println()
        LastDigui(GetATree())
    }
    
    func GetATree() *TreeNode {
        a := TreeNode{
            value: 7,
            left:  nil,
            right: nil,
        }
        b := TreeNode{
            value: 6,
            left:  nil,
            right: nil,
        }
        c := TreeNode{
            value: 5,
            left:  nil,
            right: nil,
        }
        d := TreeNode{
            value: 4,
            left:  nil,
            right: nil,
        }
        e := TreeNode{
            value: 3,
            left:  &b,
            right: &a,
        }
        f := TreeNode{
            value: 2,
            left:  &d,
            right: &c,
        }
        return &TreeNode{
            value: 1,
            left:  &f,
            right: &e,
        }
    
    }
    
    //前序遍历 根左右
    func PreDigui(head *TreeNode) {
        if head == nil {
            return
        }
        fmt.Print(head.value)
        PreDigui(head.left)
        PreDigui(head.right)
    }
    
    //中序遍历 左根右
    func MiddleDigui(head *TreeNode) {
        if head == nil {
            return
        }
        MiddleDigui(head.left)
        fmt.Print(head.value)
        MiddleDigui(head.right)
    }
    
    //后序遍历 左右根
    func LastDigui(head *TreeNode) {
        if head == nil {
            return
        }
        LastDigui(head.left)
        LastDigui(head.right)
        fmt.Print(head.value)
    }
    
    6.2非递归遍历
    //非递归遍历 前序遍历 准备一个栈
    func Pre(tree *TreeNode) {
        //放入一个栈中,右左,最后打印头左右
        // 采用栈实现
        fmt.Print("前序非递归:")
        //定义一个栈
        stack := make([]*TreeNode, 0)
        stack = append(stack, tree) // 入栈
        for len(stack) > 0 {
            tree = stack[len(stack)-1] //取栈顶元素
            fmt.Print(tree.value)
            stack = stack[:len(stack)-1] // 出栈
            if tree.right != nil {
                stack = append(stack, tree.right)
            }
            if tree.left != nil {
                stack = append(stack, tree.left)
            }
        }
    
    }
    
    //非递归遍历 中序遍历 准备一个栈(二叉树深度优先遍历)
    func Middle(head *TreeNode) {
        fmt.Print("中序非递归(深度优先遍历):")
        //定义一个栈
        stack := make([]*TreeNode, 0)
        for len(stack) > 0 || head != nil {
            // 压入左边界
            if head != nil {
                stack = append(stack, head)
                head = head.left
                //没有左边界就弹出
            } else {
                //弹出,头结点赋值为右节点
                head = stack[len(stack)-1]
                fmt.Print(head.value)
                stack = stack[:len(stack)-1] // 出栈
                head = head.right
            }
        }
    
    }
    
    //非递归遍历 后序遍历 准备两个栈
    func Last(head *TreeNode) {
        // 采用栈实现 左右根
        fmt.Print("后序非递归:")
        //按照头左右入栈,然后再放入收集栈,最好打印收集栈
        //结果收集栈
        result := make([]*TreeNode, 0)
        stack := make([]*TreeNode, 0)
        stack = append(stack, head) // 入栈
        for len(stack) > 0 {
            head = stack[len(stack)-1]    //取栈顶元素
            stack = stack[:len(stack)-1]  // 出栈
            result = append(result, head) //不打印放入结果集
            if head.left != nil {
                stack = append(stack, head.left)
            }
            if head.right != nil {
                stack = append(stack, head.right)
            }
    
        }
        for i := len(result) - 1; i >= 0; i-- {
            fmt.Print(result[i].value)
        }
    }
    
    // 二叉树广度优先遍历 利用队列去实现
    func LevelTravesalRange(head *TreeNode) {
        fmt.Print("广度优先/层序遍历:")
        queue := make([]*TreeNode, 0)
        queue = append(queue, head)
        for len(queue) > 0 {
            head = queue[0]
            fmt.Print(head.value)
            queue = queue[1:]
            if head.left != nil {
                queue = append(queue, head.left)
            }
            if head.right != nil {
                queue = append(queue, head.right)
            }
    
        }
    
    }
    
    //二叉树的最大宽度(同一层最大节点数)
    func TreeMaxWidth(head *TreeNode) {
        max := -1
        hashMap := make(map[*TreeNode]int, 0) //所有节点所处的层数
        hashMap[head] = 1
        currentLevel := 1 //当前层数
        currentNodes := 0 //当前层数的节点数
        queue := make([]*TreeNode, 0)
        queue = append(queue, head)
        for len(queue) > 0 {
            cur := queue[0]
            queue = queue[1:] //出栈
            currentNodeLevel := hashMap[cur]
            //当前节点所在层和当前层一样
            if currentNodeLevel == currentLevel {
                currentNodes++
            } else {
                //不在一层
                currentLevel++
                //新的层来了
                currentNodes = 1
            }
            //节点数和最大值比较
            if max < currentNodes {
                max = currentNodes
            }
            if cur.left != nil {
                hashMap[cur.left] = currentNodeLevel + 1
                queue = append(queue, cur.left)
            }
            if cur.right != nil {
                hashMap[cur.right] = currentNodeLevel + 1
                queue = append(queue, cur.right)
            }
        }
        fmt.Println("同一层最大宽度(节点数):", max)
    }
    
    
    var preValue = 0
    //判断一棵树是否是搜索二叉树(左边的节点小于根节点,右边的节点大于根节点)方法1
    func IsSerachTree(head *TreeNode) bool {
        if head == nil {
            return false
        }
        //检查左树
        is := IsSerachTree(head.left)
        if !is {
            return false
        }
        if preValue >= head.value {
            return false
        } else {
            preValue = head.value
        }
        //检查右树
        return IsSerachTree(head.right)
    }
    
    
    //非递归-判断是否是二叉搜索树 方法2
    func IsSerachTree1(head *TreeNode) bool {
        fmt.Print("是否是二叉搜索树:")
        //定义一个栈
        stack := make([]*TreeNode, 0)
        preValue := 0
        for len(stack) > 0 || head != nil {
            // 压入左边界
            if head != nil {
                stack = append(stack, head)
                head = head.left
                //没有左边界就弹出
            } else {
                //弹出,头结点赋值为右节点
                head = stack[len(stack)-1]
                if preValue >= head.value {
                    return false
                } else {
                    preValue = head.value
                }
                fmt.Print(head.value)
                stack = stack[:len(stack)-1] // 出栈
                head = head.right
            }
        }
        return true
    }
    
    //判断树是否是完全二叉树
    func WanQuanBinaryTree(head *TreeNode) bool {
        if head == nil {
            return false
        }
        var L *TreeNode
        var R *TreeNode
        leaf := false
        queue := make([]*TreeNode, 0)
        queue = append(queue, head)
        for len(queue) > 0 {
            head = queue[0]
            fmt.Print(head.value)
            queue = queue[1:]
            L = head.left
            R = head.right
            // 遇到了非双全节点,并且当前节点不是叶子节点或 (左孩子为空,右孩子不为空)
            if (leaf && !(L == nil && R == nil)) || (L == nil && R != nil) {
                return false
            }
            if head.left != nil {
                queue = append(queue, head.left)
            }
            if head.right != nil {
                queue = append(queue, head.right)
            }
            if L == nil || R == nil {
                //遇到了非双全节点
                leaf = true
            }
    
        }
        return true
    }
    
    
    //节点的后继节点
    func HouJiJieDian(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }
        //右节点不为空
        if node.right != nil {
            //往上找,知道左节点不为空
            return GetNodeLeftNode(node.right)
        } else {
            parent := node.Parent
            for parent != nil && parent.left != node { //当前节点是其父亲节点的又孩子
                node = parent
                parent = node.Parent
            }
            return parent
        }
    
    }
    func GetNodeLeftNode(node *TreeNode) *TreeNode {
        if node == nil {
            return nil
        }
        for node.left != nil {
            node = node.left
        }
        return node
    }
    

    7.查找树(基本都可以使用递归的思想)

    搜索二叉树:左边的节点小于根节点,右边的节点大于根节点
    完全二叉树:除了每个节点都有
    满二叉树:每一层的节点数都是最大节点数
    平衡二叉树:当且仅当两个子树的高度差不超过1时,这个树是平衡二叉树。(同时是排序二叉树)

    两个节点最近的共同祖先节点:
    1.可以用一个map,记录节点A的祖先节点,遍历查找另一个节点的祖先节点,判断是否在map中,最先找到的那个节点就是最近祖先节点

    后继节点:中序遍历顺序的节点的前后关系,DBACDE
    D的后继节点是B,B的后继节点是A

    广度优先遍历和深度优先遍历(中序)

    8.排序算法

    8.1冒泡 O(n的平方)
    func BubbleSort(a []int){
      aLen:=len(a)
      for i:=0;i<aLen;i++{
        for j:=0;j<aLen-i-1;j++{
          //相邻元素做比较
          if a[j]>a[j+1]{
             a[j],a[j+1]=a[j+1],a[j]
          }
        }
      }
    }
    
    8.2 选择排序 O(n的平方)
    func SelectSort(a []int){
      aLen:=len(a)
      for i:=0;i<aLen;i++{
        minIndex:=i
        for j:=i+1;j<aLen;j++{
          if a[j]<a[minIndex]{
             minIndex=j
          }
        }
     // 交换比第i个位置小的值
        if minIndex!=i{
          a[i],a[minIndex]=a[minIndex],i
        }
        
      }
      
    }
    
    8.3 插入排序 O(n的平方)
    func InsertSort(arr []int) {
        arrcount := len(arr)
        if arrcount < 2 {
            return
        }
        for i := 1; i < arrcount; i++ { //0-i范围上有序  
            //将j和左边的数一个个对比,跳出条件是j不能小于等于0,
            //并且大于它左边的数。因为它左边的数都已排好序
            for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
                    arr[j], arr[j-1] = arr[j-1], arr[j]
            }
        }
    }
    
    8.4 归并排序(递归合并)
    //先把左侧的元素按照递归排好序,再把右边的元素按照递归排好序
    //最后将左边和右边排好序的部分合并即可
    //3 2 4 8 1 7 
    //左右两边偏好序:2 3 4 1 7 8
    //开辟一个新的空间,比较左侧第一个元素2和右侧第一个元素1的大小,
    //小的放前面,大的放后面,继续往下比较,直到有一方越界,另一半的直接拷贝进来即可
    //时间复杂度:O(N*logN),空间复杂度O(N)
    // 归并排序 数组左边的范围L==0,右边的范围R==length-1
    func Process(arr []int, L, R int) []int {
        if L == R {
            return arr
        }
        mid := L + (R-L)>>1
        //递归使得左边的元素有序
        Process(arr, L, mid)
        //递归使得右边的元素有序
        Process(arr, mid+1, R)
           //合并左边和右边的元素
        merge(arr, L, mid, R)
        return arr
    
    }
    
    //合并左右两边的元素
    func merge(arr []int, L, m, R int) {
        help := make([]int, R-L+1)
        i := 0
        p1 := L
        p2 := m + 1
        for p1 <= m && p2 <= R {
            // 如果p1位置的值小于等于p2位置的值,将p1位置的值放入help
            if arr[p1] <= arr[p2] {
                help[i] = arr[p1]
                p1++
            } else {
                // 如果p1位置的值大于p2位置的值,将p1位置的值放入help
                help[i] = arr[p2]
                p2++
            }
            i++
        }
        //如果p1没有越界,将剩余元素拷贝进help
        for p1 <= m {
            help[i] = arr[p1]
            i++
            p1++
    
        }
        // 如果p2没越界,将p2的元素拷贝到help里面去
        for p2 <= R {
            help[i] = arr[p2]
            i++
            p2++
        }
        // 将help的值赋给arr
        for i := 0; i <= len(help)-1; i++ {
            arr[L+i] = help[i]
        }
    
    }
    
    8.5二分法查找有序数组是否存在某个元素 o(logn)
    // 有序数组,必须先排好序
    func binarySearch(arr []int, a int) (result int) {
        if len(arr)==0{
            return -1
        }
        //首先要排好序
        end := len(arr) - 1
        start := 0
        index := int(0)
        for start <= end {
            index = (start + end)
            if arr[index] < a {
                start = index + 1
            } else if arr[index] > a {
                end = index - 1
            } else {
                result = index
                return result
            }
    
        }
        return -1
    }
    
    
    // 给定一个数组,数组左边的数小于给定的num,右边的数大于等于给定的num,要求空间复杂度O(1),时间复杂度O(n)
    func HelanMethod(arr []int, num int) {
        if len(arr) <= 1 {
            return
        }
        min := -1
        for i := 0; i < len(arr); i++ {
            if arr[i] < num {
                arr[min+1], arr[i] = arr[i], arr[min+1]
                min++
            }
        }
        fmt.Println(min)
    }
    
    //荷兰国旗问题 给定一个数组,数组左边的数小于给定的num,数组中间的数等于num,右边的数大于给定的num, 要求空间复杂度O(1),时间复杂度O(n)
    func HelanMethod1(arr []int, num int) {
        if len(arr) <= 1 {
            return
        }
        min := -1
        max := len(arr)
        // for i := 0; i < len(arr); i++ {
        //  //小于 交换a[i]和小于界限的后一个元素,小于界限min往右移动,i++
        //  if arr[i] < num {
        //      arr[min+1], arr[i] = arr[i], arr[min+1]
        //      min++
        //      //大于 交换a[i]和大于界限的前一个元素,大于界限max往左移动,i不变,在判断交换后的元素和小于界限的元素关系的大小
        //  } else if arr[i] > num {
        //      //当max与i相等时停止
        //      if i == max {
        //          break
        //      }
        //      arr[i], arr[max-1] = arr[max-1], arr[i]
        //      max--
        //      //比较交换的值和最小区域值的大小关系
        //      if arr[i] < num {
        //          arr[min+1], arr[i] = arr[i], arr[min+1]
        //          min++
        //      }
        //  }
        //  //a[i]==num不动,i自增
    
        // }
        //当max与i相等时停止
        for i := 0; i < max; {
            //小于 交换a[i]和小于界限的后一个元素,小于界限min往右移动,i++
            if arr[i] < num {
                arr[min+1], arr[i] = arr[i], arr[min+1]
                min++
                i++
                //大于 交换a[i]和大于界限的前一个元素,大于界限max往左移动,i不变,在判断交换后的元素和小于界限的元素关系的大小
            } else if arr[i] > num {
                arr[i], arr[max-1] = arr[max-1], arr[i]
                max--
            } else {
                i++
                //a[i]==num不动,i自增
            }
    
        }
    }
    
    
    
    8.6快速排序

    借助荷兰国旗问题思想(小于 等于 大于),进行递归操作(该思想下时间复杂度O(n的平方))
    快排1.0:时间复杂度O(n的平方)
    快排2.0:时间复杂度O(n的平方)
    快排3.0:时间复杂度O(nlogn) 随机选一个数做参考值,快排最好最坏情况变成了一个概率问题

    //快速排序 arr[L....R]排好序
    func quickSort(arr []int, L, R int) {
        if L < R {
            //等概率随机选一个数作为参照数,和数组最右边的数做交换,降低了时间复杂度
            Swap(arr, L+rand.Intn(R-L+1), R)
            p := Partiation(arr, L, R)
            quickSort(arr, L, p[0]-1) //<区
            quickSort(arr, p[1]+1, R) //>区
        }
    }
    func Swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
    }
    
    func Partiation(arr []int, L, R int) []int {
        min := L - 1
        max := R
        for L < max {
            if arr[L] < arr[R] {
                arr[min+1], arr[L] = arr[L], arr[min+1]
                min++
                L++
                //大于 交换a[i]和大于界限的前一个元素,大于界限max往左移动,i不变,在判断交换后的元素和小于界限的元素关系的大小
            } else if arr[L] > arr[R] {
                arr[L], arr[max-1] = arr[max-1], arr[L]
                max--
            } else {
                L++
                //a[i]==num不动,i自增
            }
    
        }
        Swap(arr, max, R)
        return []int{min + 1, max}
    }
    
    8.7堆排序 O(nlogn)
    大顶堆和小顶堆.png
    //大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  
    //小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  
    func heapSort(arr []int) []int {
            arrLen := len(arr)
            buildMaxHeap(arr, arrLen)
            for i := arrLen - 1; i >= 0; i-- {
                    swap(arr, 0, i)  //将堆顶元素与数组末尾的元素进行交换
                    arrLen -= 1
                    heapify(arr, 0, arrLen)//数组的前i分元素重新整理为大顶堆
            }
            return arr
    }
    //构建大顶堆
    func buildMaxHeap(arr []int, arrLen int) {
            for i := arrLen / 2; i >= 0; i-- {
                    heapify(arr, i, arrLen)
            }
    }
    
    func heapify(arr []int, i, arrLen int) {
            left := 2*i + 1
            right := 2*i + 2
            largest := i
            if left < arrLen && arr[left] > arr[largest] {
                    largest = left
            }
            if right < arrLen && arr[right] > arr[largest] {
                    largest = right
            }
            if largest != i {
                    swap(arr, i, largest)
                    heapify(arr, largest, arrLen)
            }
    }
    
    func swap(arr []int, i, j int) {
            arr[i], arr[j] = arr[j], arr[i]
    }
    

    100亿的两个大文件,求形同的url。精确查找和大致模糊匹配
    1.分治法,将两个文件的url进行相同的hash运算,分成很多个小文件,hash值相同的文件进行url比较相同即可 (精确的匹配)
    2.利用布隆过滤器思维,先计算第一个文件的hash值,将它存储,然后计算第二个的值,判断是否存在,存在即可能是相同的url(模糊的匹配)

    一个整形数组,一种数出现奇数次,其他都是偶数次,找出这个数,时间复杂度o(n),空间复杂度(1)
    知识:异或 b^b=0,满足交互律

    假设出现奇数次的数是a
    arr:={a,a,a,b,b,c,c}
    结果 aaabbcc=a
    代码:

    result:=0
    for i:=0;i<len(arr);i++;{
          result^=arr[i]
    }
    

    一个整形数组(均不等于0),两种数出现奇数次,其他都是偶数次,找出这两个数,时间复杂度o(n),空间复杂度(1)
    假设两个出现奇数次的数是a,b
    数组所有数异或操作后,得到result:=a^b
    取出一个数的最右侧的1,a&(~a+1)
    与数组中的所有数做与运算,

    result:=0
    for i:=0;i<len(arr);i++;{
          result^=arr[i]
    }
    rightOne:=result&(~result+1) //取出result最右侧的1
    result1:=0
    for i:=0;i<len(arr);i++;{
    if arr(arr[i]&right==0){
       result1^=arr[i]
    }  
    fmt.Println(result1,result^result1)
    }
    

    则两个数是:result1 和result^result1

    对数器,验证算法是否正确,随机生成测试数据,验证n次,不同算法实现相同功能,验证结果是否一样,可以验证算法是否正确

    递归方法的使用步骤:
    1.确定方法要做什么
    2.找到递归结束的条件
    3.找出函数的等价关系式
    
    //斐波那契数列和青蛙跳台阶问题
    //自顶向下递归
    func method1(n int) int {
        if n <= 2 {
            return 1
        }
        // f(n)=f(n-1)+f(n-2)
        return method1(n-1) + method1(n-2)
    }
    
    //自下向顶递推(减少重复计算的次数)
    func method2(n int) int {
        if n <= 2 {
            return 1
        }
        sum := 0
        f1 := 1
        f2 := 1
        for i := 3; i <= n; i++ {
            sum = f1 + f2
            f1 = f2
            f2 = sum
        }
        return sum
    }
    
    // 阶乘 自下向上递推
    func method3(n int) int {
        if n <= 2 {
            return n
        }
        sum := 1
        for i := 1; i <= n; i++ {
            sum *= i
        }
        return sum
    }
    // 阶乘 自顶向下
    func method4(n int) int {
        if n <= 2 {
            return n
        }
        return method4(n-1) * n
    }
    

    求两个数R,L的中点:
    常规写法(R+L)/2 R+L可能越界
    L+(R-L)>>1 (R>L),防止R+L越界,造成异常

    master公式:递归时间复杂度
    T(N)=aT(N/b)+O(N^d)
    a递归次数
    N/b子问题规模
    O(N^d) 除去递归操作后的时间复杂度
    各占情况总的时间复杂度计算公式:

    master公式.png
    归并排序时间复杂度符合log(b,a)=d=1故时间复杂度为N
    logN
    归并排序衍生出小和问题和逆序对问题算法题

    排序算法的稳定性:值相同的元素排完序之后相对位置不会变,则是稳定的(基础数据类型没啥问题,对象的时候稳定性比较重要)


    常见排序算法时间空间稳定性分析.png

    稳定性和空间复杂度不能同时满足。

    相关文章

      网友评论

          本文标题:常见数据结构和算法

          本文链接:https://www.haomeiwen.com/subject/fkmglrtx.html