机遇屋-基本数据结构和算法

基本数据结构和算法

作者：ych

#### 时间/空间复杂度
##### 算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机
行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

##### 时间复杂度计算方法
有些算法的时间复杂度存在最好、平均和最坏情况：
>最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以该算法时间复杂度为`O(N)`。

#### 常用数据结构
##### 字符串
字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2an”(n>=0)。它是编程语言中表示文本的数据类型。在程序设计中，字符串（string）为符号或数值的一个连续序列，如符号串（一串字符）或二进制数字串（一串二进制数字）。

补充：字符串在存储上类似字符数组，它每一位单个元素都是能提取的，字符串的零位是它的长度，如s[0]=10，这提供给我们很多方便，例如高精度运算时每一位都能转化为数字存入数组。

通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存储方式是顺序存储方式和链接存储方式。

##### 数组
数组（Array）是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。这些有序排列的同类数据元素的集合称为数组。

数组是用于储存多个相同类型数据的集合。
[使用详解](https://www.jiyuwu.com/Article/ShowArticle/461 "使用详解")

##### 链表（知道就行用不到）
链表是一种线性表数据结构，在内存中它可以是非连续的，通过在每个结点中使用指针存储下一个结点的地址来实现逻辑顺序。一个结点由两部分组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表由很多种类，常见的有：单链表、双链表和循环链表，它们实现的原理差别不大，相对于单链表只是多添加了一些特定的功能，所以今天主要讲解最简单、最常用的单链表。

单链表添加、删除结点
由于链表是通过指针来指向下一个结点，所以添加和删除操作需要改变指针的指向即可。并且它们的时间复杂度都是O(1).

##### 二叉树
日常生活中，很多事物都可以用树来描述，例如书的目录、工作单位的组织架构等等。树是计算机中非常重要的一种数据结构，树存储方式可以提高数据的存储、读取效率。比如利用二叉排序树，既可以保证数据的检索速度，同时，也可以保证数据的插入、删除、修改的速度。

其实，树的种类有很多种，比如普通的二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉排序树、平衡二叉树、AVL平衡二叉树、红黑树、B树、B+树、堆等。今天介绍的主要内容是二叉树的基本知识和几种基础类型的二叉树。

二叉树是一种非线性结构。
只有一个根节点，
每一个数据结点上最多只有左右两颗子树。

1.树概念
度：每层横向结点数
深度：最长纵向结点数
树的多重链表：每一数据结点有多个指针域。

2.二叉树概念
第k层结点：2^(k-1)
深度m的总结点: 2^m-1
n个结点的深度: log2^n+1

满二叉树: 每一层都有两个叉

完全二叉树:最后一层右边叉不满

二叉树的链式储存:每个数据有左右两个指针

3.二叉树遍历
不重复访问所有数据的顺序。
前序遍历：根左右
中序遍历：左根右
后续遍历：左右根

##### 队列
队列又称为先进先出（FIFO—first in first out）线性表。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

##### 栈
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

##### 堆
堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。

[更多](https://blog.csdn.net/liuyuchen282828/article/details/89255389 "更多")

#### 常用算法
##### 双指针
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

解题思路
首先要明确，每个位置能存的水，取决与其两边的最大高度值。在此基础上，可以简单写出暴力法或两个数组存高度的“空间换时间”方法。
而双指针法则需要明确，每一个位置在知道其中一边（例如左边）的最大值时，如果左边的最大值已经比右边的临时最大值（因为没有遍历过所有位置，只能知道临时最大值）还要小的话，左边的最大值就是短板，这是靠左的位置就能得到它能存放的雨水量。
右侧同理。

而得到了左边或右边位置的存雨量后，应该移动哪边呢？ 不难想到，如果得到左边存雨量（即左边是短板），去移动右边，那么右边位置的存雨量就丢失了。因此每次移动的都是求出存雨量，或者叫短板的一边。同时需要更新该侧的最大值。

代码
```
func trap(height []int) int {
    n := len(height)
    if n < 3 {return 0} // 小于3格则不能存水
    leftMax,rightMax := height[0],height[n-1]
    ans := 0
    
    for l,r:=1,n-2;l<=r;{
        // 短板一端决定了能装多少水
        if leftMax < rightMax { // 左边是短板，就要移动左边
            ans += max(0,leftMax - height[l]) // 把有效雨水量加入结果
            leftMax = max(leftMax,height[l]) // 每次更新左边最大值
            l++
        }else{ // 右边是短板，移动右边，同理
            ans += max(0,rightMax- height[r])
            rightMax = max(rightMax,height[r])
            r--
        }
    }
    return ans
}

func max(a,b int) int{
    if a> b {return a}
    return b
}
```
复杂度分析
时间复杂度 O(N)，双指针遍历一次数组即可
空间复杂度 O(1)，仅用了几个整数变量

[更多介绍](https://zhuanlan.zhihu.com/p/157554728 "更多介绍")

##### 左右指针
[简单了解](https://blog.csdn.net/qqoies/article/details/125272461 "简单了解")

##### 二叉查找
[二叉查找树](https://blog.csdn.net/Mr_XiMu/article/details/123527662 "二叉查找树")

##### 回溯
[回溯算法](https://blog.csdn.net/weixin_45057817/article/details/125483587 "回溯算法")

##### 排序

[10大排序](https://blog.csdn.net/Haikuotiankong11111/article/details/120526760 "10大排序")

[golang排序](https://www.cnblogs.com/maxzhang1985/p/13373093.html "golang排序")

##### 递归
```
func fib(n int) int {

if n==0{
    return 0
}

if n==1{
    return 1
}
return fib(n-1)+fib(n-2)
}
```

##### 贪心
[学习链接](https://blog.csdn.net/ALEX_CYL/article/details/124267074 "学习链接")

##### 动态规划
```
func fib(n int) int {
    dp:=make([]int,n+2)
    dp[0]=0
    dp[1]=1

if n < 2{
        return dp[n]
    }

for i:=2;i<=n;i++{
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]

}
```

评论区

先去登录

基本数据结构和算法

相关推荐

评论区