小猫咪吃python

# AcWing 338. 计数问题 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一行，包含两个整数 a 和 b。 当读入一行为 0 0...

# AcWing 291. 蒙德里安的梦想 求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。 例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。 如下图所示： 输入格式 输入包含多组测试用例。 每组测试用例占一行，包含两个整数 N 和 M。 当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。 输出格式 每个测试用例输出一个结果，每个结果占一行。 数据范围 1 ≤ N, M ≤ 11 输入样例 1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0...

# AcWing 895. 最长上升子序列 给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N。 第二行包含 N 个整数，表示完整序列。 输出格式 输出一个整数，表示最大长度。 数据范围 请重点关注一下此处的数据范围 1 ≤ N ≤ 1000 ， −109{-10^9}−109 ≤ 数列中的数 ≤ 109{ 10^9 }109. 输入样例 7 3 1 2 1 8 5 6 输出样例 4 # 题目分析 最长上升子序列 是 最经典、最基础、最简单 的动态规划题目。 # 先简单看一下题意 给出一个长度为 N 的数列 nums...

# LeetCode 373. 查找和最小的 K 对数字 给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。 示例 1: 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6] 解释：返回序列中的前 3...

# AcWing 898. 数字三角形 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行包含整数 n，表示数字三角形的层数。 接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。 输出格式 输出一个整数，表示最大的路径数字和。 数据范围 1 ≤ n ≤ 500, −10000 ≤ 三角形中的整数 ≤ 10000 输入样例 5 7 3 8 8 1 0 2 7 4 4 4...

# LeetCode 913. 猫和老鼠 两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。 图的形式是：graph [a] 是一个列表，由满足  ab 是图中的一条边的所有节点 b 组成。 老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。 在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph [1] 中的任一节点。 此外，猫无法移动到洞中（节点...

# 导读 本文作为 asyncio 专题系列的引导文章，主要定位是引导读者熟悉 asyncio 相关的前置知识生成器。文章字数较多（不算代码字数 1w+，算上代码 1.8w+），全部阅读完大概需要 43 分钟。 笔者深知字数较多的文章会让人丧失继续阅读的兴趣，并且读者水平不同，可能有人早已掌握文章内容，因此我在下面简单描述了本文四个小节的重点内容，您可以根据自身情况选择阅读。 # 初始阶段，迭代器 来自 PEP234。本节重点描述了迭代器的功能与优势。 迭代器的出现增强了 python 中的迭代能力，并且给 dict 和 file 类型提供更方便、快速的迭代方式。 其主要依赖的魔术方法有两个...

# 问题描述 给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。 数据保证任意一条边的两个端点都不可能在同一部分中。 请你求出二分图的最大匹配数 1、二分图：在一个图中，可以把所有的点划分到两个集合，满足所有的边都在两个集合之间连通，我们认为这个图是二分图。 2、二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M...

manacher 算法是非常巧妙的算法，它与 KMP 的思想一样，都是利用已知的条件避免重复工作。该算法只有一个作用就是求解最长回文串的问题。 # 问题描述 给定一个长度为 n 的由小写字母构成的字符串，求它的最长回文子串的长度是多少。 示例： 输入：a b c b a b c b a b c b a 输出：13 回文串的含义是无论从前往后读，还是从后往前读，这个字符串都是一样的。 # manacher 算法 在 O (n) 的时间复杂度下求出给定字符串中的最长回文子串。 #...

# AcWing 854. Floyd 求最短路 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。 数据保证图中不存在负权回路。 输入格式 第一行包含三个整数 n,m,k。 接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。 输出格式 共 k...