打家劫舍 题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 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 。 来源: 198. 打家劫舍 - 力扣 (LeetCode) 题解 动态规划 首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中 ...
MATLAB 绘制爱心 如何使用 MATLAB 绘制爱心图像？本文为大家准备了以下 4 种方法： 方法一 这个方法使用的是笛卡尔心形线的极坐标方程： MATLAB 代码如下： 123theta = 0:0.01:2*pi;r = 1-sin(theta);polarplot(theta,r,"LineWidth",2,"Color","r"); 方法二 方法二绘制出的图像如下： 123f = @(x,y) x.^2 - abs(x).*y + y.^2 - 15;fimplicit(f, [-6 6 -6 6],"LineWidth",2,"Color","r");grid on 方法三 方法三绘制出的图像如下： 123f = @(x,y) (x.^2+(y-(x.^2).^(1/3)).^2)-9;fimplicit(f, [-5 5 -5 5],"LineWidth",2,"Color","r"); ...
C++ 标准模板库简介 C++ 标准模板库（Standard Template Library）是 C++ 标准库的一部分，不需要另外安装，直接导入即可使用。 STL 为程序员提供了通用的模板类，这些模板类可以用来实现各种数据结构和算法，从而使程序员不必从头开始编写这些代码。 STL 很好地实现了数据结构和算法的分离，大大降低了模块之间的耦合度，程序员可以自由组合 STL 提供的数据结构和算法。 STL 的核心由以下三个部分组成： 容器（Containers）：各种数据结构，如 vector、deque、map、set 等。 算法（Algorithms）：各种算法，如排序、查找、转换等。 迭代器（Iterators）：用于遍历容器的对象。 下面我们将从这三个部分来介绍 STL。 容器（Containers） 容器是用来存储数据的对象，它们提供了一种高效的方式来存储和访问数据。对于不同的任务，我们可以选择不同的容器来存储数据。 STL 的容器分为三类： 序列容器：序列容器会维护插入元素的顺序。常用的序列容器有 vector、deque。 关联容器：关联容器既有有序，也有无序，存储 ...
学习笔记
未读使用 PyPy 代替 CPython Python 的默认解释器是 CPython，它是用 C 语言实现的。由于 CPython 的执行效率比较低，因此在一些算法竞赛中，会使用 PyPy 代替 CPython。PyPy 是用 Python 语言实现的，它的执行效率比 CPython 平均高出 5 倍。由于某些 Python 早期发展历史原因，许多常用的第三方库都是针对 CPython 解释器进行设计和优化的，使用 PyPy 时可能会使程序变得更慢甚至无法运行，这也是 Python 仍把 CPython 作为默认解释器的原因。 但在日常的算法练习或是正规的算法竞赛中，往往都不会用到这样的第三方库，而 PyPy 的执行效率却比 CPython 高出很多，因此在这些场景中，使用 PyPy 代替 CPython 可以获得很大的加速效果。 使用 sys.stdin.readline 代替 input Python 自带的输入函数 input 可以读取一行输入，并把它以字符串类型返回。但是 input 的执行效率比较低，因此在一些算法竞赛中，会使用 sys.stdin.readline 代替 ...
列表 List 列表是 Python 中常用的容器之一，它的时间复杂度如下： 操作 平均时间复杂度 最坏时间复杂度 Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(n) O(n) Insert O(n) O(n) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) Iterate O(n) O(n) Get slice O(k) O(k) Del slice O(n) O(n) Set slice O(n+k) O(n+k) Extend O(k) O(k) Sort O(n log n) O(n log n) Multiply O(nk) O(nk) x in s O(n) min(s),max(s) O(n) Get length O(1) O(1) Python 中的列表是动态数组，它的底层是一个数组，当列表的长度超过数组的长度时， ...
简介 heapq 库是 Python 标准库中的一部分，它提供了一些堆操作的函数，可以用来实现优先队列。 优先队列是一种特殊的队列，它的每个元素都有一个优先级，元素的出队顺序是按照优先级从高到低的顺序进行的。优先队列的实现有多种方式，其中最常用的是堆。 堆是一种特殊的树，有两种类型，分别是最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。堆的根节点是堆中的最大值（最小堆的根节点是最小值）。 heapq 的大部分操作都是基于最小堆实现的，通过将元素取相反数，可以实现最大堆。 heapq 库的使用 heapq 库提供了 heapify、heappush、heappop、heapreplace、heappushpop、merge、nlargest、nsmallest 等函数，用于堆的操作。 heapify heapify 函数用于原地将列表转换为最小堆，时间复杂度为 O(n)O(n)O(n)。 函数原型如下： 1heapq.heapify(x) 其中，x 是一个列表。 示例： 12345import heapqx = [1, 3, ...
简介 bisect 库是 Python 标准库中的一部分，它提供了二分查找的功能。二分查找是一种在有序列表中查找某一特定元素的搜索算法。它的时间复杂度为 O(logn)O(\log n)O(logn)，比顺序查找的时间复杂度 O(n)O(n)O(n) 要有效率。 bisect 库的使用 bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数，用于在有序列表中查找或插入元素。 bisect_left bisect_left 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的左边位置。 函数原型如下： 1bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None) 其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： 12345678# 导入 bisect 库import bisect# 有序列表a = [1, ...
学习笔记
未读遗传算法 遗传算法是一种模拟自然界生物进化机制的优化算法，它通过模拟自然选择、交叉和变异等操作来寻找问题的最优解。 遗传算法通常包括以下步骤： 定义问题的目标函数和约束条件，以及变量的编码方式。 生成初始种群，即一组随机的可行解。 计算每个个体的适应度值，即目标函数的值。 选择操作，根据适应度值选择一部分个体进入下一代。 交叉操作，对选中的个体进行染色体的交换，产生新的个体。 变异操作，对某些个体的某些基因进行随机改变，增加种群的多样性。 重复3-6步，直到满足终止条件，如达到最大迭代次数或适应度值达到预设阈值。 输出最优解或最优解集。 MATLAB 实现遗传算法 MATLAB 中的遗传算法函数为 ga，其基本语法为： 1[x,fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon) 其中，fun 为目标函数，nvars 为变量个数，A 为不等式约束系数矩阵，b 为不等式约束右端项，Aeq 为等式约束系数矩阵，beq 为等式约束右端项，lb 为变量下界，ub 为变量上界，nonlcon 为非线性约束函数，intcon 为整数变量 ...
学习笔记
未读粒子群算法 粒子群算法是一种启发式算法，它的核心是思想是利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的可行解。 粒子群算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异”操作。 粒子群算法包括以下几个步骤： 预设参数，包括粒子个数、维度、迭代次数、惯性权重、学习因子等。 变量初始化，包括粒子的位置、速度、个体最优解、全局最优解等。 适应度计算，根据目标函数计算每个粒子的适应度值，并更新个体最优解和全局最优解。 速度和位置更新，根据粒子群算法的公式更新每个粒子的速度和位置，使其向最优解靠近。 自适应调整参数，根据迭代过程中的情况调整惯性权重等参数，使其能够平衡全局搜索和局部搜索的能力。 自动退出迭代，根据预设的终止条件判断是否退出迭代，如达到最大迭代次数、最优解变化小于阈值等。 MATLAB 实现粒子群算法 MATLAB 中的粒子群算法函数为 particleswarm，其基本语法为： 1[x,fval ...
学习笔记
未读马尔可夫链 马尔可夫链是一种随机过程，它的状态转移是由当前状态决定的，与过去的状态无关。马尔可夫链的状态转移矩阵是一个方阵，它的每一行元素之和为1，这样的矩阵称为概率转移矩阵。马尔可夫链的状态转移矩阵可以用来表示状态转移的概率。 MATLAB 马尔可夫链预测模型 例1 有一个时齐的马尔可夫链，其状态转移矩阵为： [0.50.30.20.20.60.20.40.20.4]\begin{bmatrix} 0.5 & 0.3 & 0.2\\ 0.2 & 0.6 & 0.2\\ 0.4 & 0.2 & 0.4 \end{bmatrix} 0.50.20.40.30.60.20.20.20.4 当前状态为第二个状态，求经过5步后的状态概率分布。 解 123456% 状态转移矩阵P = [0.5 0.3 0.2; 0.2 0.6 0.2; 0.4 0.2 0.4];% 初始状态x0 = [0 1 0];% 经过15步后的状态概率分布x5 = x0 * P^5 输出结果为： 12x5 = 0.3552 0.3949 0.2 ...
