抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

54 | 面试题:朋友圈

547. 朋友圈 按题目思路分析后,实际上也是一个并查集的问题 对角线没有意义,因为是自己认识自己相邻则可以合为一个并集 即:看有多少个并查集,多少个 root 老师说与上一节的代码类似,我写了下: ...

53 | 面试题:岛屿的个数

200. 岛屿数量 解法一:染色 FloodFill 写一个循环,遍历所有的节点,是1(陆地)的话,将count++,同时节点和附近节点都变成0(染色),依次递归。 实现方式: DFS:对任意一个为1...

52 | 理论讲解:并查集

并查集 (union & find) 是一种树型的数据结构,⽤于处理⼀些不交集(Disjoint Sets)的合并及查询问题。 Find:确定元素属于哪一个⼦集。它可以被用来确定两个元素是否属...

51 | 面试题:编辑距离

72. 编辑距离 解法一:暴力求解,DFS/BFS BFS 相对于 DFS 更优一点。推荐题解:点我 虽然我没看懂,甚至翻译都没翻译对。以后再来看。(TODO) 解法二:DP,这类型的字符操作需要死记...

50 | 面试题:零钱兑换

322. 零钱兑换 解法一:暴力 枚举每个面额,看需要走多少次。递归判断可行路径。从最大的开始枚举,返回总面额 count 最小的。 时间复杂度:O(2^n) 解法二:贪心 行不通 解法三:DP 状态...

49 | 面试题:最长上升子序列

300. 最长上升子序列 解法一:暴力求解 剪枝:后面的要比前面的大,不然就不用继续查找了。 时间复杂度:O(2^n) 解法二:动态规划 可以发现最优子结构。 状态定义:DP[ i ] 从头到 i 元...

48 | 面试题:股票买卖系列

开胃菜: 121. 买卖股票的最佳时机 特点:只能买一次,也只能卖一次 解法一:遍历 遍历时记录每次的最小值,同时和之前的最小值判断利润是否是最大,最大则记录下来,最后的全局最大值则是需要的答案 解法...

47 | 面试题:乘积最大子序列

152. 乘积最大子数组 解法一:暴力递归 每个数都有两个选择,乘与不乘,乘则记录结果,不乘则从1重新开始。每次都要 得出一个 max,最后的 max,就是结果。 解法二:动态规划 状态定义:DP[ ...

46 | 面试题:三角形的最小路径和

120. 三角形最小路径和 解法一:回溯 走所有的路径,计算每条路径的和,再判断最小值。 时间复杂度:O( 2^n ) 解法二:动态规划 状态的定义:从下往上推,定义DP[ i , j ],存储从最下...

45 | 面试题:爬楼梯

70. 爬楼梯 解法一:回溯,类似斐波拉契 枚举所有的路径,不断的判断路径是否可以走通。 f [ n ] = f [ n - 1 ] + f [ n - 2 ]f [ 0 ] = f [ 1 ] = ...