【算法】队列

2022-06-11
阅读 4 分钟
633
请实现如下类型MovingAverage,计算滑动窗口中所有数字的平均值,该类型构造函数的参数确定滑动窗口的大小,每次调用成员函数next时都会在滑动窗口中添加一个整数,并返回滑动窗口中所有数字的平均值。

【算法】栈

2022-05-31
阅读 3 分钟
621
题目:后缀表达式是一种算术表达式,它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式,请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如,后缀表达式["2","1","3","","+"]对应的算术表达式是“2+13”,因此输出它的计算结果5。

【算法】图

2022-05-28
阅读 15 分钟
890
图是一种非常重要的数据结构,用来表示物体与物体之间的关系。图由若干节点及节点之间的边组成。确定图中的节点和边是应用图相关算法解决问题的前提。通常,物体对应图中的节点,如果两个物体存在某种关系,那么它们在图中对应的节点有一条边相连。

【算法】汇总

2022-05-20
阅读 1 分钟
779
慢慢完善前言算法是亲力亲为的事,所以需要大量的时间去练习。由于时间有限,所以往往经典的题目是值得钻研的。同时在这个过程中分门别类,再进行大量总结。目录整数数组*字符串*链表*哈希表*栈*堆队列*树*堆前缀树二分查找*排序*(TODO)回溯*动态规划*图(TODO)*表示需要重点关注思维导图

【算法】动态规划

2022-05-15
阅读 13 分钟
906
一个数组 cost 的所有数字都是正数,它的第 i 个数字表示在一个楼梯的第 i 级台阶往上爬的成本,在支付了成本 cost[i]之后可以从第 i 级台阶往上爬 1 级或 2 级。假设台阶至少有 2 级,既可以从第 0 级台阶出发,也可以从第 1 级台阶出发,请计算爬上该楼梯的最少成本。例如,输入数组[1,100,1,1,100,1],则爬上该...

【算法】回溯

2022-05-05
阅读 7 分钟
775
回溯法可以看作蛮力法的升级版,它在解决问题时的每一步都尝试所有可能的选项,最终找出所有可行的解决方案。回溯法非常适合解决由多个步骤组成的问题,并且每个步骤都有多个选项。在某一步选择了其中一个选项之后,就进入下一步,然后会面临新的选项。就这样重复选择,直至到达最终的状态。

【算法】二分查找

2022-04-17
阅读 5 分钟
931
二分查找算法每次将查找范围减少一半,因此对于一个长度为n的数组可能需要O(logn)次查找,每次查找只需要比较当前查找范围的中间数字和目标数字,在O(1)的时间可以完成,因此二分查找算法的时间复杂度是O(logn)。

【算法】前缀树

2022-04-09
阅读 5 分钟
1.1k
前缀树主要用来解决与字符串查找相关的问题。如果字符串的长度为k,由于在前缀树中查找一个字符串相当于顺着前缀树的路径查找字符串的每个字符,因此时间复杂度是O(k)。

【算法】堆

2022-04-07
阅读 3 分钟
928
堆分类最大堆最小堆在最大堆中,每个节点的值总是大于或等于其任意子节点的值在最小堆中,每个节点的值总是小于或等于其任意子节点的值堆的最大特点是最大值或最小值位于堆的顶部,只需要 O(1)的时间就可以求出一个数据集合的最大值或最小值如果面试题需要求出一个动态数据集合中的最大值或最小值,那么可以考虑使用堆...

【算法】树

2022-04-05
阅读 9 分钟
1k
不管是哪种深度优先搜索算法,也不管是递归代码还是迭代代码,如果二叉树有n个节点,那么它们的时间复杂都是O(n)。如果二叉树的深度为h,那么它们的空间复杂度都是O(h)。在二叉树中,二叉树的深度h的最小值是log2(n+1),最大值为n。例如,包含7个节点的二叉树,最少只有3层(二叉树的第1层有1个节点,第2层有2个节...

【算法】哈希表

2022-04-03
阅读 5 分钟
969
哈希表是一种常见的数据结构,在解决算法面试题的时候经常需要用到哈希表。哈希表最大的优点是高效,在哈希表中插入、删除或查找一个元素都只需要O(1)的时间。因此,哈希表经常被用来优化时间效率。

【算法】链表

2022-04-01
阅读 5 分钟
705
哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部,它的值没有任何意义。在一个有哨兵节点的链表中,从第2个节点开始才真正保存有意义的信息。

【算法】字符串

2022-03-28
阅读 6 分钟
784
可以在移动这两个指针的同时,统计两个指针之间的字符串中字符出现的次数,这样可以解决很多常见的面试题,如在一个字符串中定位另一个字符串的变位词等。

【算法】数组

2022-02-24
阅读 4 分钟
830
双指针是一种常用的解题思路,可以使用两个相反方向或相同方向的指针扫描数组从而达到解题目的。值得注意的是,本书在不同的章节都提到了双指针。本书中的“指针”并不专指C语言中的指针,而是一个相对宽泛的概念,是能定位数据容器中某个数据的手段。在数组中它实际上是数字的下标。

【算法】整数

2022-02-21
阅读 5 分钟
976
题目:输入2个int型整数,它们进行除法计算并返回商,要求不得使用乘号'*'、除号'/'及求余符号'%'。当发生溢出时,返回最大的整数值。假设除数不为0。例如,输入15和2,输出15/2的结果,即7。