type
status
date
slug
summary
tags
category
icon
password
算法是指用来操作数据，解决程序问题的一组方法。通过时间复杂度和空间复杂度可以衡量算法的优劣。通常时间复杂度比空间复杂度更容易出问题，所以更多研究的是时间复杂度。
📝 1. 时间复杂度和空间复杂度
1.1 时间复杂度
通常来说，运行一遍程序就可以得到对应的消耗时间，可是由于机器性能，数据规模等因素不同都有可能得出不同的结果。理论上来说，只要得到一个时间评估的指标，获得算法消耗时间的大致趋势即可。
通常，一个算法所花费的时间和代码语句执行次数成正比，代码执行次数越多，消耗的时间越长。我们把一个算法的执行次数称为时间频度，记作T(n)。渐进时间复杂度（简称时间复杂度）用大写O表示，所以也称作大O表示法，算法的时间复杂度为：T(n)=O(f(n))。它表示当 n 趋于正无穷大时，T(n) 的趋近于 f(n)。常见的时间复杂度有：O(1)常数型；O(log n)对数型；O(n)线性型；O(nlog n)线性对数型；O(n2)平方型；O(2n)指数
上图为不同类型函数的增长趋势图，可以看出，随着问题规模 n 的不断扩大，时间复杂度也跟着不断增大。常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜＜Ο(2^n)。值的注意的是，算法时间复杂度的大小比较只是从增长趋势来看，在某个阈值之前可能会出现相反的结果。
时间复杂度一般是这样计算的，找到执行语句，计算语句的执行次数，用大O进行表示。其中在用大O表示的时候，使用1表示常量级的执行次数，只保留函数的最高阶项，存在最高阶去掉前面的系数。
上述代码中，语句①的频度是1，语句②的频度是 n，语句③的频度是 n-1，语句④的频度是 n-1，所以时间频度 T(n)=1+n+n-1+n-1=3n-1，省略系数和常数项得到 T(n)=O(n)
1.2 空间复杂度
空间复杂度主要指执行算法所需的内存的大小，类似于时间复杂度，空间复杂度也是预估的，使用 S(n)=O(f(n)) 表示，S(n) 是空间复杂度，所需的存储空间使用 f(n) 表示。
上述代码中，只有创建 m 的时候分配了数组空间，在 for 循环当中没有增加内存空间，所以空间复杂度 S(n)=O(n)。
📝 2. 题目
两数之和
题目是需要返回两数之和等于目标数的数组下标，不同于返回两数之和等于目标数的两个数，这里不能修改数组下标的位置，因而不能使用双指针法。在编写具体的代码过程中，使用了 map，然后对数组中的数据进行遍历，map 中没有的数则保存和为目标数的另一个数做为键，而该数的下标作为值；map 中有该数则获取对应的值和该数的下标放到数组中并返回。
三数之和
求三数之和的时候用到了双指针法，所以首先需要按照递增的顺序进行排列。第一个数通过数组遍历进行获取，第二和第三个数通过双指针法进行获取，并把每次满足条件的三个数放到数组里面。值得注意的是，题意中明确说明不能包含重复的三元组，所以每确定一个数都需要进行去重，防止重复。而且获取到符合题意的三元组后，需要先去重然后再移动下标。
四数之和
看过三数之和后，四数之和很好理解，前两个数通过数组遍历获取，后两个通过双指针获取。
最接近的三数之和
类似于三数之和，这里另外需要做的是，每次得到三数之和后都需要和之前的进行比较，找到最接近的。
二叉树的前序遍历
首先要知道，前序遍历先获取根节点，再获取左子树节点，最后获取右子树节点。当然递归的方式比较简单，感兴趣的话可研究迭代的写法。
二叉树的中序遍历
中序遍历先获取左子树的节点，再获取根节点，最后获取右子树的节点。
二叉树的后序遍历
前序遍历先获取左子树的节点，再获取右子树节点，最后获取根节点。
二叉树的最大深度
使用了 DFS，如果节点为空返回0，否则获取左子树和右子树的深度并计算出较大的值，由于当前节点不为空所以需要增加1。
平衡二叉树
这题和求二叉树的最大深度关联。如果节点为空直接判断为平衡二叉树，否则判断左右子树的高度差是否大于1，大于的话不是平衡二叉树，否则继续递归判断左子树和右子树。
二叉树的镜像
如果节点为空，返回 null，否则获取左右子树的镜像，交换子树的位置。
对称二叉树
leetcode 地址
这里通过 compare 函数比较两个相同的树，如果都为空则是对称的二叉树，一个为空另一个不为空则不是对称的二叉树，其他情况需要比较两个节点的值，如果相等需要递归比较第一颗树的左节点和第二颗树的右节点，如果也相等则需要递归比较第一颗树的右节点和第二颗树的左节点。
合并两个有序链表
leetcode 地址
这里通过 compare 函数比较两个相同的树，如果都为空则是对称的二叉树，一个为空另一个不为空则不是对称的二叉树，其他情况需要比较两个节点的值，如果相等需要递归比较第一颗树的左节点和第二颗树的右节点，如果也相等则需要递归比较第一颗树的右节点和第二颗树的左节点。
相交链表
本题使用了双指针的思想。如果两个链表有一个为空，则返回 null。在两个链表都不为空的情况，将指针 a，b 分别指向 headA 和 headB，如果 a,b 两个指针不相等则一直进行判断，指针 a 不为空指向下一个节点，为空则指向 headB，同理，指针 b 不为空指向下一个节点，为空志向 headA；如果 a,b 两个指针相等（可能都为 null）则返回其中一个指针，这个就是相交节点（可能为 null）
删除链表中的节点
这里要删除 node 节点，就直接把 node 节点值修改为 node.next 节点值即可。
环形链表
本题使用了快慢指针的思想。使用快指针进行迭代，如果快指针的下一个节点为 null，则返回 null，否则快指针走两步，慢指针走一步。当快慢指针相遇后就说明有环，于是将快指针重置到头节点，然后快慢指针再没次走一步，当它们再次相遇后就是环的入口。
从尾到头打印链表
使用一个数组存放打印结果，遍历链表的每一个节点，把结果从数组的头部进行插入，得到的数组则是从尾到头的打印结果。
链表中倒数第K个节点
本题是用了快慢指针的思想。先让快指针走 k 步，走完 k 步之后，快慢指针一起走，返回慢指针
反转链表
将 prev 做为 head 的前一个节点，将 prev 指向 head.next 节点，将 head.next 和 head 分别指向对应的前一个节点
爬楼梯
本题可使用动态规划的思想。首先，可以把 f(x) 当作爬 x 阶楼梯的方案数，那么可以得到方程 f(x)=f(x-1)+f(x-2)，也就是说 x 阶楼梯的方案数就是 x-1 阶楼梯的方案数加上 x-2 阶楼梯的方案数。如果使用数组来存放每一阶楼梯的方案数可以得出空间复杂度为 O(n) 的方案，可实际上只需要得出 x 阶楼梯的方案数，于是可以利用滚动数组思想，把空间复杂度降为 O(1)
斐波那契数列
和爬楼梯类似，应该说爬楼梯就是斐波那契数列的应用。
连续子数组的最大和
贪心法的题目比较少见，而且一般都比较难证明。本题的贪心法的思路是：在循环中找到不断找到当前最优的和 sum。
注意：sum 是 nums[i] 和 sum + nums[i]中最大的值。这种做法保证了 sum 是一直是针对连续数组算和。
代码实现如下：
和为s的连续正数序列
本题采用滑动窗口的思想。首先找到中间值 mid，当 i 小于或等于 mid 的时候执行循环。当累加值小于目标值的时候累加值递增，数值存放到临时数组 temp；当累加值大于或等于目标值的时候，如果累加值等于目标值，临时数组 temp 可以放到结果数组中，而累计值通过减少 temp 数组中第一个元素值的方式进行递减。递减到小于目标值的时候又再次递增。
无重复字符的最长子串
本题采用滑动窗口的思想。遍历数组的每个元素，存放到一个数组中，遇到已经存在于数组的元素，则删除该重复元素之前的数和当前元素。每次遍历的时候都将数组的长度和之前数组的长度进行比较，取较大值。
排序数组中只出现一次的数字
使用Map储存遍历的数组，然后获取Map中储存次数唯一的值
二叉搜索树的第k大节点
采用中序遍历，将二叉搜索树的节点值以升序放在数组中；
然后采用数组的逆序方法，返回第k-1个数值
- Author:老张杂货铺
- URL:https://20011102.xyz/article/example-11
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!