Jingming的博客 | Jingming Blog

Leetcode按题目类型总结（十六）

系统设计

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

Posted by Jingming on January 8, 2018

Leetcode按题目类型总结（十五）

贪心法

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

Posted by Jingming on January 5, 2018

Leetcode按题目类型总结（十四）

分治法

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

Posted by Jingming on January 3, 2018

Leetcode按题目类型总结（十三）

动态规划

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

Posted by Jingming on December 30, 2017

Leetcode按题目类型总结（十二）

哈希表

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

Posted by Jingming on December 27, 2017

Leetcode按题目类型总结（十一）

堆、栈和队列

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

Posted by Jingming on November 17, 2017

Leetcode按题目类型总结（十）

链表

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

Posted by Jingming on November 16, 2017

Leetcode按题目类型总结（八）

二叉树

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

Posted by Jingming on November 15, 2017

Leetcode按题目类型总结（九）

并查集

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

Posted by Jingming on November 15, 2017

Leetcode按题目类型总结（七）

数据结构实现

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

Posted by Jingming on October 28, 2017

景铭的博客