小猫咪吃python

前置知识：滑动窗口，前缀和。这两个基本技巧是本文涉及题目的基础，应优先掌握。 # 单调队列优化 在动态规划的世界中，有那么一个小部落，这个部落里的题目都具有某些相同的特征：在状态转移的部分，上一状态的取值范围是一个给定大小的窗口，而我们要维护窗口中元素的某种极值作为上一状态，此时就可以使用单调队列来维护滑动窗口的极值。 尤其值得注意的一点是，这类的题目中通常伴随着 “连续”、“子序列” 等关键词。 # AcWing 135. 最大子序和 输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。 注意： 子序列的长度至少是...

最近，被安利了一本非常 nice 的书，终于看完了，赶紧第一时间来推荐给大家。 非常出名的一本书，叫做《被讨厌的勇气》。 全书的内容，完全在 “青年” 与 “哲人” 的对话间展开，“青年” 提出自己的困惑，“哲人” 去解答，一问一答之间，将无数生活中的问题，从哲学的角度去思考。 并且问答的文章形式很大的程度上降低了文章的枯燥感，加上全书字数不多，又分为多个小章节，所以比较容易坚持看完。 整体来讲，文章内容是非常 “接地气” 的，讲的是绝大多数人会面临的问题： 如何处理复杂的人际关系？ 如何应对心理创伤？ 如何将 “纵向” 的人际关系变成 “横向” 的？ 你有时也会有 “自卑情节”...

本文参考：https://www.acwing.com/video/371/ 书接上回 完全背包，需掌握如何推导出最终解法。 数据范围较小的多重背包，需掌握朴素版本解法（状态定义、状态转移），以及二进制优化版的解法。 滑动窗口，需熟悉概念，并且能灵活应用到对应场景。 # 多重背包问题 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 sis_isi​ 件，每件体积是 viv_ivi​，价值是 wiw_iwi​。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 数据范围： 0<N<=10000...

本文参考：https://www.acwing.com/video/264/ # 二叉堆 堆是个很大的概念，而本文中的堆，是由二叉树来实现的，所以其实本文的堆特指为二叉堆。 # 概念 优先队列：一种特殊的队列，顾名思义，它可以在 O (1) 的时间复杂度下 pop 出 max/min。 二叉堆：堆有多种的形式，但是我们一般而言的 heap 就是二叉堆，即由完全二叉树来实现的堆，比如：python 中的 heapq。 二叉堆是优先队列的一种实现形式。 # 堆的作用 一般而言，堆的主要作用有以下几点： 快速的 peek 出 max/min 元素，时间复杂度 O (1)。 快速的 pop...

前置知识：并查集，今天的这个题目的做法是并查集的进阶操作，因此必须先熟练应用并查集，并且懂得原理。 题目链接：https://www.acwing.com/problem/content/242/ 参考视频题解：https://www.acwing.com/video/251/ # 题目详情 动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。 A 吃 B，B 吃 C，C 吃 A。 现有 N 个动物，以 1∼N 编号。 每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述： 第一种说法是 1 X...

今天，想推荐一本，我觉得非常 “好用” 的书，书名叫做：《认知觉醒：开启自我改变的原动力》，作者是周龄。 这本书严格意义上来讲更像是一本工具书，所以上面我用了 “好用” 来形容。那它究竟有什么用呢？来看一下简介就知道了。 为什么我们做事总是急于求成、避难趋易？ 所谓有耐心，就是要「咬牙坚持、死磕到底」？ 如何不再用「三分钟热情」和「打鸡血」的方式做事？ 如何保持极度专注？如何消除焦虑？如何提高学习能力？ 这是一部可以穿透时间的个人成长方法论。7 大底层概念，20 个成长关键词，助你彻底走出焦虑与迷茫，拥有清醒的认知、清楚的目标、清晰的路径、清爽的情绪。...

# LeetCode 691. 贴纸拼词 参考视频：https://www.acwing.com/video/2516/ 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。 返回你需要拼出 target  的最小贴纸数量。如果任务不可能，则返回 -1 。 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target  被选择为两个随机单词的连接。 示例 1： 输入： stickers...

这是一篇关于滑动窗口的详细的入门级攻略（真的就只是入门级）。 本文指 ACM 算法中的滑动窗口，而不是 TCP 拥塞控制中使用的滑动窗口协议（虽然两者十分相似）。 一定要看最后的总结呀～ # 滑动窗口的概念 滑动窗口算法是一种在数组中找到满足给定条件的子数组的方法，当然字符串也是适用的。我们通过维护一个子集作为窗口来做到这一点，并在更大的列表中调整和移动该窗口，直到找到解决方案。 # 从经典例题开始 # LeetCode 239. 滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的...

这是一篇关于回溯算法的详细的入门级攻略（真的就只是入门级）。 一定要看最后的总结呀～ # 回溯的含义 回溯本质上是搜索的一种方式，一般情况下，该搜索指深度优先搜索（dfs）。且实现上使用递归的方式。 # 从 “全排列” 开始 全排列是回溯最经典的应用之一，我们以全排列做基本示例，先来理解最简单的回溯是如何执行的。 # LeetCode 46. 全排列 给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。 现在，请你按照字典序将所有的排列方法输出。 输入样例 3 输出样例 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 解释：输入样例为输入的整数...

前置文章：有趣的博弈论问题 # 前情回顾 在文章 “有趣的博弈论问题” 中，主要描述了基础博弈论游戏的胜负结论及证明，具体是：在 “尼姆游戏” 中，如果给出所有的石子堆的个数全部异或起来不等于 0，则先手必胜；否则，必败，为了与本文后面的游戏做区分，我们将这个游戏称为标准尼姆游戏。 # 标准尼姆游戏的扩展 # 台阶 - Nim 游戏 现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子...