景铭的博客

Thinking will not overcome fear but action will.

Leetcode按题目类型总结(十六)

系统设计

所有代码详见:https://github.com/jingminglake/Leetcode 534. Design TinyURL 题意:需要在长url和短url之间进行变换,设计两个接口,一个是long2short,另一个是short2long。 解:使用两张hash表进行保存双向的映射。在处理长变短的时候,去生成,生成完之后,保存双向关系。 关于生成短的6位数字和字母相...

Leetcode按题目类型总结(十五)

贪心法

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 贪心的题目往往比较难,因为很难证明贪心策略是正确的。 至于贪心的解法,一般是求最优解,此时要做的不是暴力看所有的情况,而是以某个接近答案的值作为初始值,然后经过贪心的变形, 就可以变成最后的解。 具体题目 738. Monotone Increasing Digits 题意...

Leetcode按题目类型总结(十四)

分治法

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 分治法和很多其他题型有交集。 具体题目 4. Median of Two Sorted Arrays 题意:找出两个已排序数组中的总的中位数。中位数在总元素为奇数的时候取中间值,偶数时候取中间两个值的平均值。 解:先想办法求两个已排序数组(假设大小分别为m和n)中的第k小的...

Leetcode按题目类型总结(十三)

动态规划

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 动态规划适合求解的问题类型是最值类型,也就是求解决方案中最优的,例如最大值,最小值,最好方案情况,方案个数。 求方案个数 求解有多少个解的问题,一般是使用分治法,也就是递归的解决问题,可以使用动态规划去优化解题思路:使用记忆化搜索,或者是直接构造解题顺序,基于...

Leetcode按题目类型总结(十二)

哈希表

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 技巧 (1)使用数组替换hashmap,前提是key范围有限制,很容易和数组下标对应。 key范围限制举例:(a)字母 (b)字符串长度(c)数组元素数量 (d)整数数组里的值介于最大值和最小值之间。 (2)要注意hash的key已经默认有序的这种隐藏条件,这种情况...

Leetcode按题目类型总结(十一)

堆、栈和队列

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 关于序列中最大最小值的问题常使用的数据结构: 优先级队列 堆(优先级队列),耗时O(logn)插入元素,O(1)时间读取最小(大)值(堆顶),O(logn)时间删除堆顶。 PS.(1)堆和优先级队列的关系:堆是一种具体的数据结构,他的实现可以是数组、链表或者其它...

Leetcode按题目类型总结(十)

链表

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 链表题一开始要判断链表是否为空,或者只有一个元素的时候的情况。 链表题的思路:能递归就递归。 链表题的技巧: (1) 寻找符合特征的两个相邻点:可以使用两个指针一起走,判断空就是后面的指针不为空。 例如判断当前结点是不是最后一个结点:通过cur->next是否为空...

Leetcode按题目类型总结(八)

二叉树

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 树的题目,首先考虑树为空的特殊处理。树的题目类型大概有: 树的遍历 前序、中序、后序、层序等。 树的构造 构造树、合并树等。 树的特殊结点查找 找前驱后继等 树的路径 ...

Leetcode按题目类型总结(九)

并查集

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 并查集是什么 图的信息就是点集合 + 边集合。 并查集在一开始就是表示点集合,但是这些点是一群孤立的点,之后就是通过union操作+边集合信息,把点连接起来,在这种连接的过程中, 可以使用find操作来知道当前的两个点之间是否是连通的。 并查集的具体实现 ...

Leetcode按题目类型总结(七)

数据结构实现

所有代码详见:https://github.com/jingminglake/Leetcode 总体思路 抽象数据结构一般有序列、栈、队列、集合、图(键值对)、优先级队列等。具体数据结构一般有数组、链表、hash表、二分搜索树、二叉堆等。 图的实现:使用hashmap的话,优点是直接,缺点是hashmap有内存和代码的开销;另一种可选方法就是使用数组。如果给出的输入数据是边pai...