设计模式：工厂模式1. 什么是工厂模式？
工厂模式是一种创建型设计模式，它定义了一个用于创建对象的接口，但让子类决定实例化哪个类。换句话说，工厂模式将对象的创建过程封装起来，使得客户端不需要知道具体的创建细节，而是通过工厂接口来获取对象实例。
工厂模式的主要有三种变体：
简单工厂模式（Simple Factory Pattern）：不属于GoF的23种设计模式之一，但常被提及。它是通过一个工厂类来创建对象，通常会有一个静态方法根据参数来返回不同的对象实例。
简单来说就是一个窗口打菜，想吃什么得告诉窗口的阿姨让他帮你找
工厂方法模式（Factory Method Pattern）：定义一个创建对象的接口，让子类决定实例化哪个类。工厂方法使得一个类的实例化延迟到其子类。
可以理解为同时有多个窗口卖吃的，但是每个窗口只卖一种
抽象工厂模式（Abstract Factory Pattern）：提供一个接口，用于创建相关或依赖对象的家族，而无需明确指定具体类。
2. 如何使用工厂模式？
2.1 工厂方法
假设我们有一个产品接口Product，以及两个具体的产品实现类Concr ...
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
123>输入: nums = [2,3,-2,4]>输出: 6>解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
123>输入: nums = [-2,0,-1]>输出: 0>解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
代码：
123456789101112class Solution(object): def maxProduct(self, nums): ...
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
123>输入：n = 12>输出：3 >解释：12 = 4 + 4 + 4
示例 2：
123>输入：n = 13>输出：2>解释：13 = 4 + 9
提示：
1 <= n <= 104
把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
动规五部曲分析如下：
1.确定dp数组（dp table）以及下标的含义dp[j]：和为j的完全平方数的最少数量为dp[j]
2.确定递推公式dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]) ...
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
123>输入：nums = [1,5,11,5]>输出：true>解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
123>输入：nums = [1,2,3,5]>输出：false>解释：数组不能分割成两个元素和相等的子集。
同，暂时还没看懂，先贴代码：
123456789101112131415161718192021222324252627class Solution(object): def canPartition(self, nums): total = sum(nums) if total % 2 == 1: # 总和无法等分 return False target = total // 2 if max(nums) > target: # ...
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
123>输入：nums = [2,3,1,1,4]>输出：true>解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
123>输入：nums = [3,2,1,0,4]>输出：false>解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
要成功跳跃，即每一步要落点在不等于0且下一次条约距离足够远的点，正向去做非常复杂，因此，正难则反…反过来思考。从最后一个节点开始，从后往前寻找能到达它的结点，重复此步骤，更新跳跃者的位置，如果在此位置前无法找到一个节点能到达此位置，说明跳跃会失败返回False…如果跳跃者位置更新到了下标为0的节点，说明跳跃成功，返回True 这里从后往前找到第一个能到达此 ...
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
12>输入: numRows = 5>输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
12>输入: numRows = 1>输出: [[1]]
把杨辉三角的每一排左对齐：
$$ [1][1,1][1,2,1][1,3,3,1][1,4,6,4,1] $$
递推公式：
$$c[i][j]=c[i−1][j−1]+c[i−1][j]$$
12345678class Solution(object): def generate(self, numRows): c = [[1] * (i + 1) for i in range(numRows)] for i in range(2, numRows): for j in range(1, i): # 左 ...
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
123>输入: s = "leetcode", wordDict = ["leet", "code"]>输出: true>解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
1234>输入: s = "applepenapple", wordDict = ["apple", "pen"]>输出: true>解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" " ...
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
123>输入：nums = [3,4,5,1,2]>输出：1>解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
123>输入：nums = [4,5,6,7,0,1,2]>输出：0>解释：原数 ...
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
12345678910111213141516>输入：>["MinStack","push","push","push","getMin","pop","top","getMin"]>[[],[-2],[0],[-3],[],[],[],[]]>输出：>[null,null,null,null,-3,null,0,-2]>解释：>MinStack minStack = new MinStack();&g ...
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
1234>输入：[1,2,3,1]>输出：4>解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
1234>输入：[2,7,9,3,1]>输出：12>解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
定义子问题：
原问题是 “从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是 “从 k 个房子中能偷到的最大金额 ”，用 f(k) 表示。
假设有n个房子，那么偷到第k个房子（不偷第K个 ...
