XIAOSUO 记录个人学习的足迹

摘要：一、分治思想 分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。 分治与递归的区别：分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。 二、归并排序 算法原理 先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下 递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件：p = r 不用再继续分解。 代码实现 func mergeSort(arr []int, start, end int) { if start = end { return } mid:=(start + end) / 2 mergeSort(arr, start, mid) mergeSort(arr, mid+1, end) merge(arr, start, mid, end) } func merge(arr []int, start, mid, end int) { var tmparr = []int{} var s1, s2 = start, mid+1 for s1= mid s2= end{ if arr[s1] arr[s2] { tmparr = append(tmparr, arr[s2]) s2++ } else { tmparr = append(tmparr, arr[s1]) s1++ } } if s1=mid { tmparr = append(tmparr, arr[s1: mid+1]...) } if s2=end { tmparr = append(tmparr,…… 阅读全文

摘要：一、排序方法与复杂度归类 几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、算法的执行效率 算法的执行效率 最好、最坏、平均情况时间复杂度。 时间复杂度的系数、常数和低阶。 比较次数，交换（或移动）次数。 排序算法的稳定性 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 排序算法的内存损耗 原地排序算法：特指空间复杂度是O(1)的排序算法。 三、冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。 稳定性：冒泡排序是稳定的排序算法。 空间复杂度：冒泡排序是原地排序算法。 时间复杂度： 最好情况（满有序度）：O(n)。 最坏情况（满逆序度）：O(n^2)。 平均情况： “有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。 最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数比较次数最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。 func BubbleSort(values []int) { for i := 0; i len(values)-1; i++ { for j := i+1; j len(values); j++ { if v…… 阅读全文

摘要：一、什么是递归？ 递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。 基本上，所有的递归问题都可以用递推公式来表示，比如 f(n) = f(n-1) + 1; f(n) = f(n-1) + f(n-2); f(n)=n*f(n-1); 二、为什么使用递归？递归的优缺点？ 优点：代码的表达力很强，写起来简洁。 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。 三、递归需要满足的三个条件 问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。 问题与子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 四、如何实现递归？ 递归代码编写 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 递归代码理解 对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。 那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。 因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 五、递归常见问题及解决方案 警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。 六、如何将递归改写为非递归代码 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。 比如斐波拉契数列的实现 递归实现 func f(int n) int { if n == 1 { return 1 } if n == 2 { ret…… 阅读全文

摘要：一、什么是队列？ 1.先进者先出，这就是典型的“队列”结构。 2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。 3.所以，和栈一样，队列也是一种操作受限的线性表。 二、如何实现队列 1. 数组实现 type Queue struct { items []interface{} length int //数组大小 head int //表示队头下标 tail int //表示队尾下标 } func CreateStack(cap int) *Queue { if cap == 0 { panic(不能创建容量为0的队列！) } return Queue{ items: [capacity]interface, length: capacity, head:0, tail:0 } } func (this *Queue) Enqueue(item interface{})(err error){ if this.tail == this.length { return errors.New(queue full) } this.items[this.rear] = item this.tail++ return } func (this *Queue) Dequeue() (interface{},err error){ if this.head == this.tail { return _,errors.New(queue empty) } item = this.items[this.head] this.head++ return item,err } 比起栈的数组实现，队列的数组实现稍微有点儿复杂。 对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 如下图：当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 …… 阅读全文

摘要：如何理解“栈” 栈是一种操作受限的数据结构，只支持入栈和出栈操作。 典型的“栈”结构：后进者先出，先进者后出。 从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 顺序栈的实现 type Item interface { } type ArrayStack struct { items []Item // 数组 count int //栈中元素个数 size int //栈的大小 } func CreateStack(cap int) *ArrayStack { if cap == 0 { panic(不能创建容量为0的栈！) } return ArrayStack{ items: make([]Item, cap), count: 0, size: cap, } } func (a *ArrayStack) Push(e Item) { if a.size=a.count { panic(栈已经满了！) } a.items[count] = e a.count++ } func (a *ArrayStack) Pop() *Item { if a.count == 0 { panic(栈已经空了！) } tmp = a.items[a.count-1] a.count-- return tmp; } } 链式栈实现 type Item interface { } type StackNode struct { el Item next *StackNode } type ListStack struct { top *StackNode count int //栈中元素个数 } func CreateStack() *ListStack { return new(LinkStack) } func (l *LinkStack) Push(el Item) { s := StackNode{el: el, next: l.top} l.t…… 阅读全文

摘要：什么是链表 和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。 链表的特点 插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。 常用链表 链表结构五花八门，本文来看一下最常见的三种链表结构，它们分别是：单链表、双向链表和循环链表。 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。 从图中可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。 循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。它像一个环一样首尾相连，所以叫作“循环”链表。 双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。 从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种…… 阅读全文