模拟
模拟指的是将题目描述转化为可执行的代码，其中我们会用到编程语言的基础内容，最常见的就是循环。
简单的题目，通常直接模拟就够了，比如 874. 模拟行走机器人 。
而如果是中等和困难的题目，除了使用模拟，我们还需要使用一些别的技巧。比如有的题目就是模拟 + 堆，这是因为模拟的过程我们需要动态获取极值。再比如 799. 香槟塔，其实就是模拟 + 动态规划。可以看出，中等的题目通常模拟只是辅助，还需要结合其他知识。
那么是否所有的题目都是模拟？当然不是。比如动态规划的题目，这就不能说是模拟。因为题目并没有告诉你明确的操作步骤，而是需要你根据题目信息，自己挖掘转移方程进行求解。
Leetcode874
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:#tql
dx,dy=0,1
dist=0
x,y=0,0
obstacles = {(x, y) for x, y in obstacles}#tuple更快
for c in commands:
if c==-1:#左转
dx,dy=dy,-dx
elif c==-2:#右转
dx,dy=-dy,dx
else:
for _ in range(c):
if (x+dx,y+dy) in obstacles:
break
x,y=x+dx,y+dy
dist=max(dist,x**2+y**2)
return dist
leetcode799
class Solution:
def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
dp=[[0 for _ in range(1,q+2)] for q in range(query_row+1)]
dp[0][0]=poured
for i in range(query_row):
for j in range(i+1):
if dp[i][j]>=1:
dp[i+1][j]+=(dp[i][j]-1)/2
dp[i+1][j+1]+=(dp[i][j]-1)/2
return min(1,dp[query_row][query_glass])
枚举
枚举简单来说就是指尝试所有可能，是一种最基本的算法。
最常见的枚举就是暴力搜索。即在解空间中暴力枚举所有解空间中的值，并逐个判断其是否是答案。
枚举可以很简单。比如枚举一个数组的所有项。实际上枚举也可以很复杂。比如：
维度的上升（枚举 3 维数组）;方向的选择（从前往后还是从后往前）等。
枚举三要素
枚举有三个东西需要考虑。
-
状态。都有哪些状态需要我们枚举？
-
不重不漏。如何枚举才不会重复，且不会漏过正确解？
-
效率。采取怎么样的枚举策略可以最大化提供算法效果？
接下来，我们通过一个具体的例子，带大家领会这三点。
经典实例 - 枚举子集
比如需要枚举一个数字集合 S 的所有子集，你会如何做？
- 状态。
我们可以用一个和 S 相同大小的数组 picked 记录每个数被选取的信息， 用 0 表示没有选取，用 1 表示选取。
比如 S 大小为 3， picked 数组 [1,1,0]，表示 S 中的第一项和第二项被选择（索引从 1 开始）。如果 S 的大小为 n，就需要用一个长度为 n 的数组来存储，那么就有 2 n 2^n 2n种状态。
由于数组的值不是 0 就是 1，满足二值性，因此更多时候我们会使用一个数字 y 来表示状态，而不是上面的 picked 数组。其中 y 的二进制位对应上面提到的 picked 数组中的一项。 比如如上的 picked 数组 [1,1,0] 可以用 ob110，也就是二进制的 6 来表示。
- 不重不漏。
我们可以用一个数 x 来模拟集合 S，用 y 来模拟 picked 数组。这样问题就转化为两个数（x 和 y）的位运算。
由于我们使用 1 表示被选取， 0 表示选取。因此 如果 x 对应位为 0，其实 y 也只能是 0，而如果 x 对应位是 1，y 却可能是 0 或者 1。也就是说 y 一定小于等于 x， 因此可以枚举所有小于等于 x 的数的二进制，并逐个判断其是否真的是 x 的子集。
具体来说，我们可以令 n 为 x 的二进制位数。不难写出如下代码：
// 外层枚举所有小于等于 x 的数
ans = [];
for (i = 1; i < 1 << n; i++) {
if ((x | i) === x) ans.push(i);
}
// ans 就是所有非空子集
这种算法的复杂度大约是 O ( 4 n ) O(4^n) O(4n)，也就是说和 x 成正比。这种算法 n 最多取到 12 左右。这样做不重不漏么？答案是可以的。因为 (x | i) === x 就是 i 是 x 的子集的充要条件，当然你也可用 & ，即 (x | i) & i == i 来表示 i 是 x 的子集。
如果二进制你不好理解，其实你可以转化为十进制理解。比如我给你一个数 132，让你找 132 的子集，这里的子集我简单定义为当前位的数字是否小于等于原数字当前位的数字。这样我们就可以先从 1 枚举到 132，因为这些数潜在都可能是 132 的子集。如果我枚举了一个数字 030，由于 0 小于等于 1，3 小于等于 3，0 小于等于 2，因此 030 是 132 的子集。而如果我枚举了一个数字 040，由于 4 大于 3，因此 040 不是 132 的子集。
- 效率。
上面的枚举方法虽然也可保证不重不漏，但是却不是最优的，这里介绍一种更好的枚举方法。
具体做法就是x_i和 x 进行&（与）运算。与运算可以快速跳到下一个子集。
ans = [];
// 外层枚举所有小于等于 x 的数
for (i = x; i != 0; i = (i - 1) & x) {
ans.push(i);
}
// ans 就是所有非空子集
这样做不重不漏么？算法的关键在于 i = (i - 1) & x。这个操作首先将 i - 1，从而把 i 最右边的 1 变成了 0，然后把这位之后的所有 0 变成了 1。经过这样的处理再与 x 求与，就保证了得到的结果是 x 的子集，并且一定是所有子集中小于 i 的最大的一个。直观来看就是倒序枚举除了所有非空子集。
对于有 n 个 1 的二进制数字，需要 2 n 2^n 2n的时间复杂度。而有 n 个 1 的二进制数字有 C ( n , i ) C(n,i) C(n,i)个，所以这段代码的时间复杂度为 ∑ i = 0 n C ( n , i ) × 2 i \sum_{i=0}^{n} C(n,i)\times2^i ∑i=0nC(n,i)×2i ，大约是 O ( 3 n ) O(3^n) O(3n)。和上面一样，这种算法的时间复杂度也和 x 成正比。但是这种算法 n 最多取到 15 左右。这种方法对题目有一定要求， 即：1.数据范围要合适，否则数字无法表示了;2.只能有两种状态，这样才可以用二进制位 0 和 1 进行模拟。
枚举技巧
当你需要枚举 n 元组的时候，可以长度枚举 n - 1，然后使用一些技巧找第 n 个数。比如三数和为 target 的元组，我们可以先枚举两个数，然后使用二分或者哈希表加速找第三个数。
枚举的剪枝也是一个技巧。比如前面提到的有时候从后往前遍历可以剪枝。有时候利用序列的单调性进行剪枝。
大家可以通过以下题目进行联系，感受一下这两个技巧。
- 有效三角形的个数
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums=sorted(nums)
res=0
n=len(nums)
for i in range(n-2):
if nums[i]==0:continue
for j in range(i+1,n-1):
sums=nums[i]+nums[j]
k=bisect.bisect_left(nums,sums)#k-1是寻找的数最大值的位置
res+=k-1-j
return res
n 数和问题。
