第一阶段学习算法总结

截止到现在算法学习了有一周了，对于算法的学习也陆陆续续的进行了n次了，每次都是无疾而终，之前一直认为这道算法题做出来了就over了，也没有进行总结记忆等等，这次看算法课程，学到了一些新的方法。

首先就是学习算法同学习英语背单词一样，都是需要进行刻意练习的，并且这个过程需要一直反复进行，也是利用艾宾浩斯的记忆曲线强化记忆。

再一个就是，学习是输入，但是只有输入是不够的，你以为你懂了就是你懂了吗？其实可能你没懂。类似小黄鸭测试法，懂了之后能不能用自己的话说出来或者写出来，这个是真正考验你是否真的懂了。所以开始了现在的每天学习总结，通过这段时间的学习发现，确实当天学习的算法理解之后印象很深刻，第二天回顾一下，手写出来也是OK，但是在一周后的总结中发现，时间越是靠前的学习，印象越是模糊，对于一些算法，脑袋里大约的还有印象是什么思路，但是在白板代码的时候一些逻辑和细节有很多的遗忘。还是需要不断地进行反复练习和记忆。

下面回顾总结一下上一阶段学习的内容，上周开始进入学习算法的课程，对于算法、数据结构再次总结一下有哪些内容。
算法，基础的概括一下主要包含一下三部分

• if-else
• for/while
• recursion

数据结构，主要由一维、二维、其他特殊结构组成

• 一维
  数组、链表、 栈、队列、集合、映射等等
• 二维
  树、图、堆、并查集等等
• 特殊
  位运算、布隆过滤器、LRU cache

几个算法

• 移动零 [0,1,0,3,12] -> [1,3,12,0,0]
  • 暴力解法
    直接进行两次循环，类似冒泡排序，外层循环 i，内层循环 j，内层循环里进行判断外层循环的值为零且内层循环的值不为零时进行交换，直到全部循环结束。
    时间复杂度为O(n^2)，空间复杂度为O(1)

  • 双指针解法
    利用快慢指针，快指针 i 正常循环，慢指针lastNonZeroIndex 指向数组中最后一个为零的元素的位置，一次循环，快指针位置的元素不为零时与慢指针位置的元素进行交换。这是大致的思路，具体到算法上还有一些具体的小优化，可以点击我之前发的具体算法文章查看。
    时间复杂度O(n)，空间复杂度O(1)
    过程如下

    
    

具体算法：https://www.jianshu.com/p/b5bcab69913d

• 爬楼梯
  爬楼梯的算法总结出来就是斐波那契数列问题。

  • 递归
    最简单的就是利用公式 f(n) = f(n-1) + f(n-2) 进行递归计算。
    时间复杂度为O(2^n)，空间复杂度为O(1)
  • 空间换时间
    在递归的基础上进一步优化，想到利用空间换时间，使用另外的数组保存每次计算的结果，这样就不需要进行递归的调用，时间复杂度优化很多。
    时间复杂度为O(n)，空间复杂度O(n)

  • 滚动数组
    由斐波那契数列的公式发现，每次计算的时候其实只用到了临近的三个数值，类似UITableView中cell 的缓存策略，利用这三个数值进行滚动也可以，，每次向前移动一位，最后的位置移动到最前面的位置。
    时间复杂度为O(n)，空间复杂度O(1)
    过程如下

    
    

  • 移动两个元素
    在上一步的基础上发现，实际过程中也可以只使用两个元素进行向后平移。
    时间复杂度为O(n)，空间复杂度O(1)
    如下图所示

    
    
  • 斐波那契数列结果公式
    
    直接把上面的公式用代码表示也可以得到结果
    时间复杂度为O(logn)，空间复杂度为O(1)
    具体算法：https://www.jianshu.com/p/725da889281c

• 盛最多水的容器
  

  
  maxAero = (right - left) * min(nums[left], nums[right])
  • 暴力解法
    两次循环，计算出所有的结果，返回最大值。
    时间复杂度为O(n^2)，空间复杂度为O(1)
  • 双指针
    利用头尾双指针进行计算，头尾指针根据结果判断向中间靠拢，通过一次循环就可以得到最大值。
    时间复杂度为O(n)，空间复杂度为O(1)
    
    算法链接：https://www.jianshu.com/p/86d74cf6176a

• 3数之和
  • 暴力解法
    使用三次循环，最内层进行判断是否存在三数为零的结果，结果使用Set保存(去重)。
    时间复杂度为O(n^3)，空间复杂度为O(1)

  • 双指针
    a + b + c = 0
    先对数组进行排序，方便后续判断，第一次循环，
    a + b = -c
    假设第一个位置的值为target（-c），然后利用头尾指针寻找a、b的值，根据a、b的和与target判断头尾指针哪一个向中间靠拢。
    时间复杂度为O(n^2)，空间复杂度为O(1)
    图解如下👇

    
    

算法链接：https://www.jianshu.com/p/25a5924f31cf

GitHub：https://github.com/huxq-coder/LeetCode
欢迎star