1.-算法

优质

小牛编辑

142浏览

2023-12-01

名称	原理	复杂度
插入排序	对于元素索引i（i>=1），从头开始，若能找到比 a[i] 大对元素 a[j]，则记录 a[i] 的值，将索引 j~i-1 的元素向后移动一位，使用 a[i] 替换 a[j]。优化思路：针对数组可以采用二分查找找到当前元素的插入位置，链表不需要位移操作。	O(n^2/2)
选择排序	从当前元素开始遍历，记录最小值的索引，根据索引交换当前值的最小值，选择排序每次选出最小的元素和当前元素交换。选择排序基于链表实现，使用指针记录最小元素。选择排序最多只需进行 n 次赋值操作。	O(n^2/2)
堆排序	首先将队列中元素全部入堆，再将其依次出堆。堆，堆顶元素为堆中的最大（小）值的完全二叉树,完全二叉树,把元素顺序排成树的形状。Sift UP 原理：只有战胜底层子节点，才能向上。Sift Down 原理：临时小弟被打败。第 K 大元素（Top N）,使用 K 小顶堆。	O(n*log(2,n))
冒泡排序	从头到尾，发现前一位大于后一位，互换位置，第一排序保证数值最大的元素排到最后，尾部减 1。头尾相等时停止。冒泡排序交换次数多。	O(n^2/2)
快速排序	使用 parttion 函数，将数组中的第一个元素置于正确的顺序位置（左边元素比他小，右边大于等于），对基点左右的队列递归进行快速排序。快排的终止条件，左右界相等，则返回左界或右界。partition 函数：x 为第一个元素，小于 x 左边，大于等于 x 右边，左边初始数组 [-1,0)，右边初始数组[0,0], i 从位置 1 开始遍历,若小于 x，和右边数组的第一位置换，左右边数组向后移动一位。	O(n*log(2,n))
归并排序	对左边进行归并排序，得到数组 left，对右边进行归并排序，得到结果 right，合并 left 和 right，结束条件，进行归并排序到数组长度为 1 时，返回原数组，归并是一种外部排序。	O(n*log(2,n))

2. 数组

关键词	解题思路	例
初始定义	0 1 排序,复杂度为 O(n),使用 i 指向第一个 1，j 指向 i 后的第一个 0，swap(i++,j++)
	删除排序数组中的重复项，使用 O(1)的空间复杂度。时间复杂度低,使用双指针法,头指针 i 指向将被替换的元素，尾指针 j 指向用来替换的元素，j替换 i 的下一位,直到 j 遍历到底。	26
	删除排序数组中的重复项，使每个元素的频率不超过2，使用 O(1)的空间复杂度。使用双指针法，i 指针指向待替换的前一位元素,j 指针用来替换的元素，当相同元素使用了两次时，第三次跳出。	80
对撞指针	盛最多水的容器，原理：右节点左移，最右节点和数组中其他节点的组合不满足条件，舍弃。	腾讯笔试问题 11
两数之和 1	原理：对于当前数组。两数之和大于目标值时，右边值和其他任何数的组合无效。小于目标值，左边值和其他任何数的组合无效。数组有序时间复杂度为 O(n)	1
两数之和 2	使用 map 记录数组中每一位元素的值和位置，遍历数组，若 map 中存在 target-num[i]，且 value 不为 i,时间复杂度为 O(n)。	1
三数之和	使用 map 记录数组中每一位元素的值和位置，	15
滑动窗口	最小连续数组，和大于目标值。滑动窗口原理，在上次循环的计算结果基础上进行计算。
下一个排列	可描述为从后倒数第二个元素 i 开始往后排序，记录排序后当前值的索引 j，如果 j!=nums.length-1，取 nums[j+1],将 i 到 j 元素后移，nums[i]=num[j+1]。	31
二分法	条件：数组有序。若中间值小于目标值，左端点等于中间值的右一位，若中间值小于目标值，右端点等于中间值的左一位。思想，每次舍弃掉不合要求的元素，直至找到目标值相等的元素（多个返回一个）。若左右端点相等，且该值不等于目标值，则数组中不包括目标值。	33、35
搜索旋转数组	（1）数组为两段局部有序数组，且第一段全部大于第二段（如果第一个数小于最后一个，则为有序数组）。在该数组中找到 val，如果是有序数组的话，有序数组能使用二分查找做到 O(log2n) 。（2）在两段的情况下，如果查找值大于第一个值，则只能在第一个数组中查找，若小于第一个值大于最后一个值，则不存在，因为有序数组中，最后一个值的后一个元素为第一个元素，若小于最后一个值，则只能在后一个数组中查找。（3）此时采用二分法解决问题，如果当前值在第二段，而查找值在第一段，左；反之右；在所处段正确的条件下，根据当前值和查找值的大小比较进行左右移动。	33
根据值移除元素	依次使用后面的元素替换重复元素，替换后的元素可能依旧需要被替换。	27
	两个排序数组的中位数，该问题主要思路是将数组分成尽量均匀的两堆，将 (len1+len2)/2 放入左边;如果 (len1+len2)%2==0,中位数=(max(左边)+min(右边))/2;如果 (len1+len2)%2!=0,中位数=min(右边)	4

3. 链表

3.1 查找

关键词	解题思路	例
相对位置问题	倒数 n，使用 first 指针先走 n 步，再和 last 指针同步走。	19
	访问链表中间节点，first 指针每次走两步，last 指针每次走一步。如果有奇数个节点，则 last 指针指向中间元素；如果有偶数个节点，则 last 指针指向中间靠右元素。	876

3.2 遍历

关键词	解题思路	例
将链表中两数相加，链表头为个位数	使用 flag 记录上一位是否进一，注意不等长问题。	2
将链表中两数相加，链表头为最高位数	在以上 2 例的基础上结合栈使用。	445

3.3 修改

关键词	解题思路	例
旋转链表	俩俩交换，如果头节点为空或只有一个节点，则返回头节点。否则如流程图（1）	24
	k 个一组旋转	25
	指定旋转的位数	61
	指定旋转的段	92
反转链表	如下流程图（2）	206
重排链表	从前往后，插入从后往前，使用栈实现。	143
根据值删除元素	简单	203
删除重复元素	删除全部重复元素，使用 Map 记录元素出现次数。	82
删除重复元素	去重，重复元素留一个，如果下一个元素等于当前元素，则删除下一个元素。	83

3.4 修改

关键词	解题思路	例
分割列表（partition）	小于 x 左边，大于 x 右边，从左往右找到第一个大于 x 的节点，从该节点开始找到第一个小于 x 的节点，交换两个节点，将第二个节点赋给第一个节点。	86
环形链表	判断链表是否有环。快指针每次移动两个节点，慢指针每次移动一个节点。如果有环，当慢指针进入环时，快指针必然在慢指针从后追赶慢指针，并且每次超越一个节点。	141
	寻找链表的入环口。	142
相交链表	相交必同尾，	160
合并链表	合并两个有序链表	21
	合并 K 个有序链表,调用合并两个有序列表的方法。	23
回文链表	将后半段反转	234
奇偶链表	依次将奇偶链表重连	328
链表组件	链表中连续一段在数组中，将数组转为集合

4. 树

4.1 二叉树遍历

算法	实现	例
前序遍历	迭代实现前序遍历。先遍历左，将右压栈，右出栈，再对右进行左，右压栈。	144
层次遍历	普通层次遍历采用单个队列即可，首先将跟节点入队列，出队列时依次将左右孩子入队列。
	将每个每层写进一个链表，首先将根节点入队列，然后出队列进入另一队列，另一队列出对，节点的子节点入队。	102
	交替，使用栈替换临时队列来存储，使用 flag 记录从左或从右。	103
	填充普通二叉树的每个 next 指针，让这个指针指向其下一个右侧节点。参考层序遍历,将刚出队列的 next 指针指向队列的首位元素。	117
深度遍历	二叉树的最大深度，取左右子数的最大深度的最大值加1，若为 null，深度取 0。	104
	二叉树的最小深度，取左右子树深度较小值加 1，若为 null，深度取 0。	111
	给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。。	112
	给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。	113
	给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字，计算根节点到叶子节点的数字之和。同 113。	129
路径问题	最大路径和。路径被定义为一条从树中任意节点出发，达到任意节点的序列。	124
	最长同值路径。路径被定义为一条从树中任意节点出发，达到任意节点的序列。两个节点之间的路径长度由它们之间的边数表示。longestFromRoot 方法计算从根节点出的最长线长度，root.val==left.val,res=1+longestFromRoot(root.left),若 root.val==right.val,res=1+longestFromRoot(root.right),取 res 和 max的最大值。	687
二叉树的构造	从中序和后序遍历序列构造二叉树。根据前序确定根节点，在中序中找到根节点，前面是左子树，后面是右子树，再对左右子树进行递归。	105
	从前序和中序遍历序列构造二叉树。根据后序确定根节点，在中序中找到根节点，前面是左子树，后面是右子树，再对左右子树进行递归。	106
对称二叉树	根节点对称，则根节点的左子树和另一个根节点的右子树对称。	101
平衡二叉树	判断二叉树是否为平衡二叉树，自身的深度等于左右子树较深的一个加1，求出左右子树深度同时作差，若大于1，则将 flag 设置为 false。若 flag 为 fasle,则函数终止。	110

4.2 二叉搜索树

关键词	解题思路	例
验证二叉搜索树	中序遍历有序，使用常数级空间复杂度，调用 inOrderVisit（root.left）==false ,则直接返回，比较 prev 和 root,将 root 赋值给 prev,调用 inOrderVisit（root.right）。	98
恢复二叉搜索树	二叉搜索树两个位置互换,中序遍历俩次，第一次记录小于前面值的节点 count 值，第二次相第一小于前面值节点的前一个节点和第二个小于前面值互换。若没有第二个点，则将第一个小于前面点和前面点互换。	99
二叉搜索树迭代器	中序遍历。先找右子树最左，再向上遍历，再找父节点。先将最左边一列节点入栈，然后，使用指针记录最后一个节点，使用 map 记录下每层最右节点，刚好大于。	173
将有序数组转换为平衡二叉搜索树	找到中间节点（偶数偏左），再将中心节点左边的数组转为二叉搜索树，为根节点的左子树；再将中心节点右边的数组转为二叉搜索树，为根节点的右子树。	108
AVL 树	即是二叉树搜索树，又是平衡二叉树。实现方法：当前节点的平衡因子的绝对值大于 1 时，存在 LL、RR、LR、RL 四种情况：分别采取右旋、左旋、先对左子树左旋再对节点右旋、先对右子树右旋再对节点左旋对方式，是当前节点是平衡二叉树。

5. 哈希表

关键词	解题思路	例
频率统计	字母异位词分解，使用 map 统计每个字符串的词频，再进行比较。	49

流程图

(1)

first=head
1------2---3---4---5
|      
first  

// 开始循环
second=first.next
1------2---3---4---5
|      |
first  second

first.next=first.next.next
    first
    |
    1
    |
2---3---4---5
|      
second

second.next=first
2------1---3---4---5
|      |
second first

tmp=first.next
2------1------3---4---5
|      |      |
second first  tmp

first.next=first.next.next
2------1------4---5
|      |      |
second first  3
              |
              tmp

2---1------4---5
|          |
second     3
           |
           cur

2---1------4---5
|          |
second     3
           |
           first

（2）

1------>2--->3--->4--->5
|       |    |
prev    cur  next

1<------>2   3--->4--->5
|        |   |
prev     cur next

1<------>2    3--->4--->5
         |    |    |
         prev cur  next
......

1.-算法

2. 数组

3. 链表

3.1 查找

3.2 遍历

3.3 修改

3.4 修改

4. 树

4.1 二叉树遍历

4.2 二叉搜索树

5. 哈希表

流程图

参考资料