Zxy's Blog

牛客acm模式总结 0.开头结尾统一代码 123456789'''try ：可能抛出异常的语句。except ：捕获异常，处理异常。'''while True: try: core code except: break 1.单个元素 列输入，列输出 1234567891011121314151617181920'''输入 3567输出567其中第一个3代表着一共有3个数字需要将他们依次输出输入实际上就是一个迭代器，每次获取一个元素就用一次input()函数我们可以首先获得第一个输入的值然后 for 循环对应的次数，将剩余待输入的元素依次输出'''n = int(input()) # 获得第一个输入，n=3for i in range(n): print(int(input())) 单个元素...

2024-10-24 92.反转链表|| 标签 链表 给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5] 输入：head = [5], left = 1, right =...

参考资料 本博客数据结构与算法部分涉及的文章参考Hello算法，只用于学习交流。

小结 贪心算法通常用于解决最优化问题，其原理是在每个决策阶段都做出局部最优的决策，以期获得全局最优解。 贪心算法会迭代地做出一个又一个的贪心选择，每轮都将问题转化成一个规模更小的子问题，直到问题被解决。 贪心算法不仅实现简单，还具有很高的解题效率。相比于动态规划，贪心算法的时间复杂度通常更低。 在零钱兑换问题中，对于某些硬币组合，贪心算法可以保证找到最优解；对于另外一些硬币组合则不然，贪心算法可能找到很差的解。 适合用贪心算法求解的问题具有两大性质：贪心选择性质和最优子结构。贪心选择性质代表贪心策略的有效性。 对于某些复杂问题，贪心选择性质的证明并不简单。相对来说，证伪更加容易，例如零钱兑换问题。 求解贪心问题主要分为三步：问题分析、确定贪心策略、正确性证明。其中，确定贪心策略是核心步骤，正确性证明往往是难点。 分数背包问题在 0-1 背包的基础上，允许选择物品的一部分，因此可使用贪心算法求解。贪心策略的正确性可以使用反证法来证明。 最大容量问题可使用穷举法求解，时间复杂度为 O(n2)O(n^2)O(n2) 。通过设计贪心策略，每轮向内移动短板，可将时间复杂度优化至...

最大切分乘积问题 question 给定一个正整数 $n$ ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少，如下图所示。 假设我们将 nnn 切分为 mmm 个整数因子，其中第 iii 个因子记为 nin_ini​ ，即 n=∑i=1mnin = \sum_{i=1}^{m}n_i n=i=1∑m​ni​ 本题的目标是求得所有整数因子的最大乘积，即 max⁡(∏i=1mni)\max(\prod_{i=1}^{m}n_i) max(i=1∏m​ni​) 我们需要思考的是：切分数量 mmm 应该多大，每个 nin_ini​ 应该是多少？ 贪心策略确定 根据经验，两个整数的乘积往往比它们的加和更大。假设从 nnn 中分出一个因子 222 ，则它们的乘积为 2(n−2)2(n-2)2(n−2) 。我们将该乘积与 nnn 作比较： 2(n−2)≥n2n−n−4≥0n≥4\begin{aligned} 2(n-2) & \geq n \newline 2n - n - 4 & \geq 0 \newline n & \geq...

最大容量问题 question 输入一个数组 $ht$ ，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。 容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。 请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。示例如下图所示。 容器由任意两个隔板围成，因此本题的状态为两个隔板的索引，记为 [i,j][i, j][i,j] 。 根据题意，容量等于高度乘以宽度，其中高度由短板决定，宽度是两隔板的数组索引之差。设容量为 cap[i,j]cap[i, j]cap[i,j] ，则可得计算公式： cap[i,j]=min⁡(ht[i],ht[j])×(j−i)cap[i, j] = \min(ht[i], ht[j]) \times (j - i) cap[i,j]=min(ht[i],ht[j])×(j−i) 设数组长度为 nnn ，两个隔板的组合数量（状态总数）为 Cn2=n(n−1)2C_n^2 = \frac{n(n - 1)}{2}Cn2​=2n(n−1)​...

分数背包问题 question 给定 $n$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$ ，和一个容量为 $cap$ 的背包。每个物品只能选择一次，**但可以选择物品的一部分，价值根据选择的重量比例计算**，问在限定背包容量下背包中物品的最大价值。示例如下图所示。 分数背包问题和 0-1 背包问题整体上非常相似，状态包含当前物品 iii 和容量 ccc ，目标是求限定背包容量下的最大价值。 不同点在于，本题允许只选择物品的一部分。如下图所示，我们可以对物品任意地进行切分，并按照重量比例来计算相应价值。 对于物品 iii ，它在单位重量下的价值为 val[i−1]/wgt[i−1]val[i-1] / wgt[i-1]val[i−1]/wgt[i−1] ，简称单位价值。 假设放入一部分物品 iii ，重量为 www ，则背包增加的价值为 w×val[i−1]/wgt[i−1]w \times val[i-1] / wgt[i-1]w×val[i−1]/wgt[i−1]...

贪心算法 贪心算法（greedy algorithm）是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。贪心算法简洁且高效，在许多实际问题中有着广泛的应用。 贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同。 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。 贪心算法不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。 我们先通过例题“零钱兑换”了解贪心算法的工作原理。这道题已经在“完全背包问题”章节中介绍过，相信你对它并不陌生。 question 给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i - 1]$ ，目标金额为 $amt$ ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 $-1$...

小结 动态规划对问题进行分解，并通过存储子问题的解来规避重复计算，提高计算效率。 不考虑时间的前提下，所有动态规划问题都可以用回溯（暴力搜索）进行求解，但递归树中存在大量的重叠子问题，效率极低。通过引入记忆化列表，可以存储所有计算过的子问题的解，从而保证重叠子问题只被计算一次。 记忆化搜索是一种从顶至底的递归式解法，而与之对应的动态规划是一种从底至顶的递推式解法，其如同“填写表格”一样。由于当前状态仅依赖某些局部状态，因此我们可以消除 dpdpdp 表的一个维度，从而降低空间复杂度。 子问题分解是一种通用的算法思路，在分治、动态规划、回溯中具有不同的性质。 动态规划问题有三大特性：重叠子问题、最优子结构、无后效性。 如果原问题的最优解可以从子问题的最优解构建得来，则它就具有最优子结构。 无后效性指对于一个状态，其未来发展只与该状态有关，而与过去经历的所有状态无关。许多组合优化问题不具有无后效性，无法使用动态规划快速求解。 背包问题 背包问题是最典型的动态规划问题之一，具有 0-1 背包、完全背包、多重背包等变种。 0-1 背包的状态定义为前 iii 个物品在容量为 ccc...

编辑距离问题 编辑距离，也称 Levenshtein 距离，指两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。 question 输入两个字符串 $s$ 和 $t$ ，返回将 $s$ 转换为 $t$ 所需的最少编辑步数。 你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。 如下图所示，将 kitten 转换为 sitting 需要编辑 3 步，包括 2 次替换操作与 1 次添加操作；将 hello 转换为 algo 需要 3 步，包括 2 次替换操作和 1 次删除操作。 编辑距离问题可以很自然地用决策树模型来解释。字符串对应树节点，一轮决策（一次编辑操作）对应树的一条边。 如下图所示，在不限制操作的情况下，每个节点都可以派生出许多条边，每条边对应一种操作，这意味着从 hello 转换到 algo 有许多种可能的路径。 从决策树的角度看，本题的目标是求解节点 hello 和节点 algo 之间的最短路径。 动态规划思路 第一步：思考每轮的决策，定义状态，从而得到 dpdpdp...