-
4、AbstractFactory
目录 抽象工厂模式 抽象工厂实现 - 工厂类 抽象工厂实现 - 产品类 抽象工厂实现 - 使用 总结抽象工厂模式简单工厂模式和工厂模式，解决了增加产品对象时的可扩展性，但都是增加的单一类产品，比如CardWatchCenter和Vehicle接口。当我们需要增加产品族（比如冰箱、电视、洗衣机三个物品就是一个产品族）时，就可以使用抽象工厂抽象工厂实现 - 工厂类一、创建抽象工厂接口protocol Factory { func createTelevison() -> ...…
-
3、Factory
目录 工厂模式 工厂模式实现 - 工厂类 工厂模式实现 - 产品类 工厂模式实现 - 使用工厂模式简单工厂模式在产品数量较少时很好用，当数量很多时，工厂类就会很重，代码很多。这个时候我们可以使用工厂模式，使用多个解耦的工厂类，每个工厂类负责创建对应的产品对象这就需要我们有一个工厂类接口，一个产品类接口工厂模式实现 - 工厂类一、创建一个工厂类接口protocol VehicleFactory { func create() -> Vehicle}二、多个 (解耦的) 工...…
-
2、SimpleFactory
目录 什么是工厂模式 简单工厂模式实现 总结什么是工厂模式一、工厂模式工厂模式也是最常用的实例化对象模式了，是用工厂方法代替 new 操作的一种模式。但为什么有了初始化方法，还要有工厂模式？1、是为了控制生产过程，并将生产和使用隔离开。实际开发过程中创建一个产品对象的逻辑可能很复杂，这时我们把这个过程交给工厂。使用时并不关心产品对象是怎么创建的。2、便于扩展，使用工厂模式当我们添加一个新的产品对象时，并不会影响之前的逻辑。开闭原则，对扩展开放，对修改关闭所以工厂模式也是用来创建实例对...…
-
1、Singleton
目录 什么是单例模式 单例模式实现 单例模式应用 补充什么是单例模式最简单，最常用的设计模式之一，主要解决了一个全局使用的类频繁地创建与销毁。 当您想控制实例数目，节省系统资源的时候，就可以使用单例模式1、全局唯一，只初始化一次，只有一个实例 2、只提供一个接口，私有化初始化接口 3、线程安全 4、最好能懒加载（不强求）单例模式实现一、实现class Singleton: NSObject { //存储类型属性在初始化时必须赋值，因为没有初始化器来初始化它，...…
-
【题目】9、高频
目录 283. 移动零 1. 两数之和 283. 移动零题目描述 283. 移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/move-zeroes 著作权归领扣网络所有。商业转载...…
-
【题目】8、DFS
目录 17. 电话号码的字母组合 46. 全排列 47. 全排列 II 22. 括号生成17. 电话号码的字母组合题目描述17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的，但是你可以...…
-
【题目】7、二叉树
目录 236. 二叉树的最近公共祖先 99. 恢复二叉搜索树 333. 最大BST子树二叉树的绝大部分题目都可以直接通过递归 遍历解决 前序遍历 中序遍历 后序遍历 层序遍历236. 二叉树的最近公共祖先题目描述236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q， 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自...…
-
【题目】6、动态规划
目录 47. 礼物的最大价值 64. 最小路径和 62. 不同路径 121. 买卖股票的最佳时机 72. 编辑距离 5. 最长回文子串47. 礼物的最大价值题目描述在一个 m*n 的棋盘的每一格都放有一个礼物， 每个礼物都有一定的价值（价值大于0）。 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例 1: 输入: [ [1,3,1], [1,5,1], ...…
-
【题目】5、字符串
目录 01.09. 字符串轮转 242. 有效的字母异位词 572. 另一个树的子树 151. 翻转字符串里的单词 3. 无重复字符的最长子串01.09. 字符串轮转题目描述 01.09. 字符串轮转 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（ 比如，waterbottle是erbottlewat旋转后的字符串）。 示例1: 输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True 示例2: 输入...…
-
【题目】4、栈与队列（二）
目录 739. 每日温度 654. 最大二叉树739. 每日温度题目描述739. 每日温度 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为： 要想观测到更高的气温，至少需要等待的天数。 如果气温在这之后都不会升高，请在该位置用 0 来代替。 例如， 给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]， 你的输出应该 results = [1, 1, 4, 2, 1, 1, 0, 0...…
-
【题目】3、栈与队列
目录 基本概念 155.最小栈 20.有效的括号 232.用栈实现队列 239.滑动窗口最大值基本概念栈 先进后出，后进先出 对称队列、双端队列 先进先出，后进后出 顺序155.最小栈题目描述155. 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 ...…
-
【题目】2、链表
目录 链表相关算法建议 203.移除链表元素 237.删除链表中的节点 206.反转一个单链表 2.两数相加 160.相交链表 86.分隔链表 234.回文链表 141.环形链表 21.合并两个有序链表 23.合并K个升序链表链表相关算法建议一、解题建议一定要多画图二、解题技巧虚拟头结点 快慢指针 多指针 ……三、常用代码要非常熟练链表节点的插入、删除 反转（翻转）一个链表 快慢指针求中心节点 计算链表的长度 ……203.移除...…
-
【题目】1、数组排序
目录 88.合并两个有序数组 75.颜色分类 16.16.部分排序 977.有序数组的平方88.合并两个有序数组题目描述 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素 来源：力扣（Le...…
-
【进阶】24、速览(数据结构与算法二)
目录 【进阶】1、排序 【进阶】2、排序（二） 【进阶】3、排序（三） 【进阶】4、排序（四） 【进阶】5、排序（五） 【进阶】6、并查集 【进阶】7、图 【进阶】8、图（二） 【进阶】9、图（三） 【进阶】10、图（四） 【进阶】11、图（五） 【进阶】12、图（六） 【进阶】13、递归(Recursion) 【进阶】14、递归(二 Recursion) 【进阶】15、回溯(Back Tracking) 【进阶】16、贪心、分治 【进阶】17、动态规划 ...…
-
【进阶】23、串
目录 串(Sequence) 蛮力（Brute Force） KMP KMP - next表 KMP - 性能分析串(Sequence)一、介绍本课程研究的串是开发中非常熟悉的字符串，是由若干个字符组成的有限序列 String Text = “thank” t h a n k 字符串 thank 的前缀（prefix）、真前缀（proper prefix）、后缀（suffix）、真后缀（proper...…
-
【进阶】22、跳表
目录 跳表(SkipList) 跳表实现 跳表的层数 跳表的复杂度分析跳表(SkipList)一、思考一个有序链表搜索、添加、删除的平均时间复杂度是多少？ O(n)能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至 O(logn)？ 链表没有像数组那样的高效随机访问（O(1) 时间复杂度），所以不能像有序数组那样直接进行二分搜索优化 那有没有其他办法让有序链表搜索、添加、删除的平均时间复杂度降低至 O(logn)？ 使用跳表（Skip...…
-
【进阶】21、布隆过滤器
目录 布隆过滤器（Bloom Filter） 代码实现布隆过滤器（Bloom Filter）一、思考如果要经常判断 1 个元素是否存在，你会怎么做？ 很容易想到使用哈希表（HashSet、HashMap），将元素作为 key 去查找 时间复杂度：O(1)，但是空间利用率不高，需要占用比较多的内存资源 如果需要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过？ 很显然，HashSet、HashMap 并不是非常好的选择 ...…
-
【进阶】20、动态规划（四）
目录 最长公共子串（Longest Common Substring） 0-1背包 0-1背包，恰好装满最长公共子串（Longest Common Substring）一、最长公共子串 - 题目最长公共子串（Longest Common Substring） 子串是连续的子序列 求两个字符串的最长公共子串长度 ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3二、最长公共子串 – 思路假设 2 个字符串分别是 str1、str2 i ∈ [1,...…
-
【进阶】19、动态规划（三）
目录 最长公共子序列（Longest Common Subsequence，LCS） 代码实现最长公共子序列（Longest Common Subsequence，LCS）一、问题求两个序列的最长公共子序列长度 [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，可能是 ✓ ABCBDAB 和 BDCABA > BDAB ✓ ABCBD...…
-
【进阶】18、动态规划（二）
目录 动态规划（Dynamic Programming） 最大连续子序列和 最长上升子序列（LIS） 最长上升子序列-二分搜索实现动态规划（Dynamic Programming）一、常规步骤动态规划中的“动态”可以理解为是“会变化的状态” ① 定义状态（状态是原问题、子问题的解） ✓ 比如定义 dp(i) 的含义② 设置初始状态（边界） ✓ 比如设置 dp(0) 的值③ 确定状态转移方程 ✓ 比如确定 dp(i) 和 dp(i – 1) 的关系二、...…
