Jingming的博客 | Jingming Blog

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

Leetcode按题目类型总结（六）

深度优先搜索、回溯

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路回溯和dfs的关系：回溯是对隐含的树结构的进行剪枝搜索，dfs是一种对显示树结构（图）进行回溯的算法。共同点是他们的解空间都是树结构。区别是，回溯的话，树是隐含的，而且通常非常大，所以回溯策略就是进行剪枝，对有些走不通的路，会回到之前状态然后继续寻找能走通的路，且每一步访问的结...

Posted by Jingming on October 22, 2017

Leetcode按题目类型总结（五）

宽度优先搜索

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路 BFS的特点是一层层的访问邻居，这样优点是可以最先找到距离起点最近的(边的权重是1)具有某种特征的目标点。与DFS比较例如求解无权图的最短距离时候，DFS是每次对一个邻居深入访问，这样在问题路径比较深的时候（也就是树比较高的时候），却存在路径没有解的情况，所以...

Posted by Jingming on October 20, 2017

Leetcode按题目类型总结（四）

位运算

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路位运算题目的使用情形：（1）要求时间复杂度不变情况下，减小内存使用（例如：不准使用hash）。（2）不允许使用加减乘除运算。具体题目 29.Divide Two Integers 题意：计算两整数相除，不能使用乘除和mod 解：使用位运算。技巧一：判断两个i...

Posted by Jingming on October 18, 2017

Leetcode按题目类型总结（三）

二分搜索

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路二分搜索思想：搜索的内容是未知的，但是，首先知道解空间的是一段连续的上升或者下降空间，有其明确下限和上限（例如整数就有最大值、数组下标其实也存在最大值、或者有序矩阵中最右下角的值就是最大值），同时有条件公式来知道要搜索的内容是大了还是小了，这样就能缩减答案范围，直到范围很小，...

Posted by Jingming on October 15, 2017

Leetcode按题目类型总结（二）

双指针

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路使用同向双指针的场景之一是减少双重循环中的一些废操作，只保留精华部分例如，解决滑动窗口类（连续子数组）的问题，首先，如果窗口大小是固定的k，那么这样的窗口在大小为N的数组有只N-k+1个（理解：考虑滑动窗口的起点，只能是从下标0开始到下标N-k结束），这样，其实...

Posted by Jingming on September 25, 2017

景铭的博客