Jingming(Yaxiong)的博客

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

Leetcode按题目类型总结（一）

数组和字符串

所有代码详见：https://github.com/jingminglake/Leetcode 总体思路数组的题目第一反应是暴力求解，把所有解空间找到，并进行遍历，之后再考虑优化，例如使用动态规划优化，双指针或者hash来做。最重要的还是要找到特点：例如字符串问题，是否是固定字母开头。字符串省空间技巧：还是用原来字符串，但是使用新的下标，表示修改后的index。 subse...

Posted by Jingming on September 24, 2017

设计模式概要

设计模式简单理解小结

0. 面向对象的目标可扩展性容易添加新的功能。灵活性代码修改平稳的发生，修改一个方法不会影响另一个方法。可替换性可插入性，将一个同样接口的类加入进来，不影响原来代码。高内聚、低耦合模块内部之间关系紧密，也就是不可分割；低耦合指模块间关系弱。 1. 设计模式分类：创建型模式解决对象创建问题。创建型模式包括：工厂（简...

Posted by Jingming on May 13, 2017

UML类图关系理解

简单理解小结

UML的类之间有几种关系：泛化Generalization（继承Extend、实现Implementation）、依赖Dependence、关联（聚合Aggregation、组合Composition）。首先，这几种关系并不是独立的、非此即彼的关系。他们之间相互关系如下：依赖是最基本的关系，主要体现类之间存在调用的情况；关联关系必然是依赖关系，关联关系主要体现类与类之间的千丝万缕的依...

Posted by Jingming on May 12, 2017

算法与数据结构总结

分治法

一、分治法时间复杂度计算 T（n）＝ aT（n/b）＋ f（n）展成树：则第二层的结点有a个，每个结点为f（n／b），所以整个第二层的和为a＊f（n/b）。这时三种情况：（1）a＊f（n/b）和 f（n）是相等的，例如a＝2，b＝2，f（n）＝n。那么说明每一层开销都是f（n）。而总共有logn层，所以T（n）＝O（f（n）＊logn）。（2）a＊f（n/b）比 f（n）小，例如a＝...

Posted by Jingming on February 17, 2017

亚雄的博客