PlanZ

每个励志演讲都应附带关于幸存者偏差的免责声明。

使用金字塔结构表达思想。

LeetCode每日一题题目来源：力扣（LeetCode） 2748. 美丽下标对的数目（简单）暴力枚举 哈希表 题目描述给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。 返回 nums 中 美丽下标对 的总数目。 对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。 示例 1： 输入：nums = [2,5,1,4]输出：5解释：nums 中共有 5 组美丽下标对：i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 1 互质，因此 gcd(2,1) == 1 。i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。5 和 1 互质，因此 gcd(5,1) == 1 。i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。5 和 4 互质，因此 gcd(5,4) == 1 。i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。1 和 4 互质，因此 gcd(1,4) == 1 。因此，返回 5 。 示例 2： 输入：nums = [11,21,12]输出：2解释：共有 2 组美丽下标对：i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1...

LeetCode每日一题题目来源：力扣（LeetCode） 2713. 矩阵中严格递增的单元格数（困难）动态规划 矩阵 题目描述给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。 从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。 你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。 请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。 返回一个表示可访问单元格最大数量的整数。 示例 1： 输入：mat = [[3,1],[3,4]]输出：2解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。 示例 2： 输入：mat = [[1,1],[1,1]]输出：1解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。 示例 3： 输入：mat = [[3,1,6],[-9,5,7]]输出：4解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。 提示： $m == mat.length$ $n == mat[i].length $ $1 <= m, n <= 10^5$ $1 <= m * n <= 10^5$ $-10^5 <= mat[i][j] <= 10^5$ 题解动态规划 设 $d[i][j]$ 为移动到单元格 $(i,j)$ 的最大步数，其中 $(i,j)$ 可以作为起始单元格，也可以是从其他单元格移动而来。考虑从第 $i$ 行以及第 $j$ 列上矩阵单元格数值小于 $mat[i][j]$ 的位置进行转移，即 $d[i][j]$ 取以下数值中的最大值： 第 $i$ 行：$max(d[i][j’]+1)$ ，其中 $mat[i][j’] < mat[i][j]$ 第 $j$ 列：$max(d[i’][j]+1)$ ，其中 $mat[i’][j] <...

LeetCode每日一题题目来源：力扣（LeetCode） 2288. 价格减免（中等）.split() .isnumeric() 题目描述句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个 价格 。 例如 "$100"、"$23" 和 "$6" 表示价格，而 "100"、"$" 和 "$1e5 不是。 给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。 返回表示修改后句子的字符串。 注意：所有价格 最多 为 10 位数字。 示例 1： 输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50输出："there are $0.50 $1.00 and 5$ candies in the shop"解释：表示价格的单词是 “$1“ 和 “$2“ 。 “$1“ 减免 50% 为 “$0.50“ ，所以 “$1“ 替换为 “$0.50“ 。 “$2“ 减免 50% 为 “$1“ ，所以 “$2“ 替换为 “$1.00“ 。 示例 2： 输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"解释：任何价格减免 100% 都会得到 0 。表示价格的单词分别是 “$3“、”$5“、”$6“ 和 “$9“。每个单词都替换为 “$0.00“。 提示： $1 <= sentence.length <= 10^5$ $sentence$ 由小写英文字母、数字、' ' 和...

LeetCode每日一题题目来源：力扣（LeetCode） 522. 最长特殊序列II（中等）贪心 双指针 题目描述给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。 特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。 s 的 子序列可以通过删去字符串 s 中的某些字符实现。 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的字符"e"和"d"来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)等。 示例 1： 输入: strs = [“aba”,”cdc”,”eae”]输出: 3 示例 2: 输入: strs = [“aaa”,”aaa”,”aa”]输出: -1 提示: $2 <= strs.length <= 50$ $1 <= strs[i].length <= 10$ $strs[i]$ 只包含小写英文字母 题解问题转换，枚举字符串，判断子序列 问题转换： 原问题 => 找出字符串列表 strs 中最长的特殊序列 的长度。 假设某个字符串 strs[i] ，如果它的一个子序列sub是「特殊序列」，那么 strs[i]本身也是一个「特殊序列」。 如果 sub 没有在除了 strs[i] 之外的字符串中以子序列的形式出现过，那么即使给 sub 不断地添加字符，它也依旧不会出现。而 strs[i] 就是给 sub 添加若干个（可以为零个）字符得到的结果。即如果 strs[i] 存在特殊序列sub，那么 strs[i] 本身也是一个特殊序列。 即字符串列表 strs 中最长的特殊序列的长度为其中某一非子序列字符串 strs[i] 的长度或-1 新问题 => 判断列表strs 中的每一个字符串 strs[i] 是否为其他字符串 strs[j](i!=j) 的子序列。 思路： 使用一个双重循环，外层枚举每一个字符串 strs[i]...

解决Hexo框架下Latex公式无法被渲染的问题。

LeetCode每日一题题目来源：力扣（LeetCode） 2786. 访问数组中的位置使分数最大（中等）动态规划 数组 题目描述给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。 你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置： 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。 对于你访问的位置 i ，你可以获得分数 nums[i] 。 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。 请你返回你能得到的 最大 得分之和。 注意 ，你一开始的分数为 nums[0] 。 示例 1： 输入：nums = [2,3,6,1,9,2], x = 5输出：13解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。总得分为：2 + 6 + 1 + 9 - 5 = 13 。 示例 2： 输入：nums = [2,4,6,8], x = 3输出：20解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。总得分为：2 + 4 + 6 + 8 = 20 。 提示： $2 <= nums.length <= 10^5$ $1 <= nums[i], x <= 10^6$ 题解动态规划 从左到右遍历数组，遍历到一个元素 $e$ 时，如果移动到此位置，那么能获取的最大分数取决于： 上一次移动到的元素为奇数且得分最大值 $odd$ 上一次移动到的元素为偶数且得分最大值 $even$ 即移动到当前位置可以获得的最大得分 $now$ 等于: 在当前元素为奇数时：$now=max(odd+e,even+e-x)$ 在当前元素为偶数时：$now=max(odd+e-x,even+e)$ 将最大得分之和 $score$ 更新为： $score=max(score,now)$ 1234567891011121314class Solution: def maxScore(self,...

匈牙利算法匈牙利算法步骤 任给初始匹配M 若M饱和V1则结束，否则转(3) 在V1中找一个非M饱和点x，置S={x}，T={ } 若N(S)=T，则停止，否则在N(S)-T中任选一点y 若y为M饱和点转(6)，否则求一条从x到y的M可增广路P，并更新匹配M，转(2) 因为y是M饱和点，所以M中有一边(y，u)，置S=S∪{u}，T=T∪{y}，转(4) 代码部分输入二部图如下： 可以由以下代码表示： 123456# 输入二部图bi_graph = [[0, 1, 1, 0, 0], [1, 1, 0, 1, 1], [0, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 1, 1]] (1). 任给初始匹配M 12345678910111213141516# 初始化匹配def init_matching(graph): x, y = np.shape(graph) matching = np.zeros((x, y), int) matched = [] for i in range(0, x): for j in range(0, y): if graph[i][j] == 1 and j not in matched: matching[i][j] = 1 matched.append(j) break return matching 创建一个与二部图矩阵对应的匹配矩阵，初始化匹配矩阵的规则是：遍历输入的二部图矩阵，从V1出发找到V2找边，如果该边在V2中饱和的点已经在匹配中出现，则不选择该边，当找到一条合适的边时，将其加入匹配矩阵结束本次循环，并在V1中找到下一个点继续重复以上过程。 以上过程结束后即可获得如下(a)所示初始匹配矩阵。由于此初始化方法在本例中直接给出了最大匹配，无法体现完整的算法过程，因此在之后的代码中将采用(b)作为初始匹配。 (b)初始化匹配结果如图所示： (2). 判断匹配M是否饱和V1 12345678# 判断匹配是否饱和所有V1点def...

图论及其应用对于任意无向图G(输入为矩阵)，编写程序实现： 任务一：画出图G，并给所有顶点和边标号 任务二：求出图G的度序列 任务三：画出图G的补图 任务四：判断图G的连通性 任务五：求出图G的边连通度和点连通度 任务六：求出图G的最小点割集和最小边割集(元素最少) 解决方案任务一（画出图G，并给所有顶点和边标号） 通过 BrushTools 类中的 draw_vertex()# 画点, draw_edge()# 画边, show()# 展示绘制图像 方法实现 使用二维矩阵接收点和边，点用坐标表示，边用邻接矩阵表示，如下所示： 123456789import numpy as np# 接收点v = np.array([[1, 1], [1, 4], [7, 3], [5, 1]])# 接收边e = np.array([[1, 2, 0, 0], [2, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 0]]) 使用python绘图库matplotlib实现图的绘制 使用matplotlib中的 scatter(x坐标, y坐标, c="颜色") 函数绘制图的顶点 使用matplotlib中的 plot(x坐标, y坐标, c="颜色") 函数绘制图的边，其中边的始点和终点坐标通过邻接矩阵e找到对应顶点坐标矩阵v中相应的坐标 通过matplotlib中的 add_artist(plt.Circle((圆心坐标), 半径, fill=是否填充, color="颜色")) 函数为画布上添加圆形来表示环 使用matplotlib中的 annotate(注释内容, xy=[添加注释的点的坐标], xytext=[注释文字的坐标]) 注释函数为点和边添加注释。注：在非简单无向图中，平行边通过为一条边添加多个不同的边注释来表示 使用matplotlib中的 show() 函数将绘制完的图像进行展示 任务二（求出图G的度序列） 通过 CalcTools 类中的 calc_degrees() 方法实现度序列的计算 因为是无向图，因此点vi的度数只需要考虑邻接矩阵 e...