HeRen's Blog

为大作业编写简单的shell脚本起因对大作业选择刷100道leetcode的同学,老师的要求是 把100段代码和解释心得贴到一个md文档或其它格式文档。比如cat *.cpp>ans.md 然而,一来呢,我并没有在文件内标注题目和题干,这样做会分不清哪题是哪题;二来呢,把代码直接输入到markdown文档中显示会很丑(因为没有写代码框) 所以我现学现卖,上网查了查shell脚本的语法,看着还行,就决定自己编写一个脚本来处理这个问题 目标 由于题目写在文件名里,所以应该是先输出文件名再输出文件内容 文件的内容应该是按照题号排序的 对文件的内容进行标注,即放在代码块里 由于题目数量还在更新,所以应该在文件开头标注日期和题目数 实现思路删除之前的answer.md->获得当前日期和目录下的cpp文件数目,写入answer.md->扫描当前目录->对每一cpp个文件,先输出文件名->然后加上代码框,即开头加上```cpp->输出文件内容(遍历每一行并输出)->在每个文件末尾追加```作为代码框的结束 代码及注释123456789101112131 ...

期末pre——回溯的剪枝策略做题分析 因为很多算法还没学过,做得最多的困难题就是回溯和动态规划了,不过我也不太会动态规划,解决的方法通常是回溯+剪枝,在做题的过程中,我发现回溯+剪枝可以解决很多的动态规划问题,而且写起来比较容易 回溯介绍 回溯搜索是深度优先搜索（DFS）的一种,通俗地讲,回溯法采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。 回溯的基本思想是：为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解 回溯是搜索算法中的一种控制策略。 未经剪枝的回溯将探索所有合理的解空间,因此复杂度也会比较高,比如N皇后问题的复杂度就达到了O(N!) 回溯的模板 123456789101112131415全局变量 ansvoid solve(深度){ if(满足条件) 保存解 else { for(可以进行的操作) { 保存结果 ...

题目描述leetcode44. 通配符匹配 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。 '?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。 示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2: 输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。 示例 3: 输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 ...

题目描述leetcode32. 最长有效括号 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。   示例 1： 输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 示例 2： 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 示例 3： 输入：s = "" 输出：0   提示： 0 <= s.length <= 3 * 104 s[i] 为 '(' 或 ')' 题解——计数法(滑动窗口) 思路想要求一个满足条件的最长连续子串，很自然地想到使用滑动窗口我们需要知道的是左边界滑动的条件所以要考虑，如果不能形成有效括号，是怎样的情况应当说，要么是有多余的左括号，要么是有多余的右括号（好像是废话😂，但其实这就是本质）考虑"())"这个字符串，扫描到第二个)时，就知道不可能有基于前面的合法的括号了，因为这个右括号是永远匹配不上的，此时，应当移动左边界到下一个位置继续搜索。 ...

博客建站历程与复现说明从输入公网IP,看到第一篇Hello World 到现在,已经有六十余天了 在这六十多天里,我也对博客进行了许多许多的更新 趁现在还记得,我想把我的博客建站历程记录下来,便于以后查看 同时,也希望它可以作为一篇教程。为此,我开了一个临时的阿里云ECS服务器,尝试对整个过程进行复现 准备工作首先要有一台服务器,也有人选择先在本地写好页面之后托管到一些平台,比如gitee,github 但是这可能受到服务商的限制,还有可能被审查而关停,为什么好好的博客被Gitee服务直接关停了？ - 知乎 由于可能在无意中就出现了什么禁词,导致连怎么修改都不知道,所以建议还是自己搞一台服务器 像是阿里云,腾讯云这些老牌的云服务器提供商会有针对学生和新用户的优惠,至少前几年花不了太多钱的 另外,他们还提供了几个月的试用服务,在这里可以白嫖一个月的阿里云服务器 我下面的操作都是在对一台即将到期的ecs服务器初始化后进行的,可以认为是一个纯净的系统 远程连接ecs并安装必要的工具购买完ecs服务器后,可以进入控制台,设置密码后进行远程连接,之后会进 ...

题目描述leetcode2287. 重排字符形成目标字符串 给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。 从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。   示例 1： 输入：s = "ilovecodingonleetcode", target = "code" 输出：2 解释： 对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。 对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。 形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。 可以形成最多 2 个 "code" 的副本，所以返回 2 。 示例 2： 输入：s = "abcba", target = "abc" 输出：1 解释： 选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 可以形成最多 1 个 "abc" 的副本，所以返回 1 。 注意，尽管下标 3 和 4 分别有 ...

题目描述leetcode2285.道路的最大总重要性 给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。 给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间有一条 双向 道路。 你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用 一次 。道路的 重要性 定义为这条道路连接的两座城市数值 之和 。 请你返回在最优安排下，所有道路重要性 之和 最大 为多少。   示例 1： 输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：43 解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。 - 道路 (0,1) 重要性为 2 + 4 = 6 。 - 道路 (1 ...

南京大学120周年校庆,邀您共襄盛举 很庆幸在大一经历南京大学120校庆,也没有因临近期末繁重的学习任务错过这些活动 南京大学120周年校庆公告> 薪火相续，源远流长。南京大学的历史可溯源至创立于1902 年的三江师范学堂。此后历经两江师范学堂、南京高等师范学校、国立东南大学、第四中山大学、国立中央大学、南京大学等历 史 时期；至1952年，创立于1888年的金陵大学并入，二源汇流，波澜壮阔，在新中国高等教育的发展历程中砥砺奋进、铸造辉煌，始终走在中国大学的第一方阵，为中华民族培育了一批又一批栋梁人才。 民族复兴，使命担当。近代以来，家国多舛，南京大学虽校名屡易、校址迁移，然学脉绵延、弦歌不绝，始终与时代同呼吸、与民族共命运，谋国家之富强、求科学之进步。在社会主义建设和改革开放的征程中，南京大学倡导解放思想，勇攀科学高峰，跃入顶尖大学行列。进入新时代，南京大学努力推进“双一流”建设，聚力内涵式发展、着力高质量提升，在培育英才、创新知识、传承文化、服务国家等方面，引领新风尚、树立新标杆，向党和人民交出了优异的成绩单，向“第一个南大”的宏伟目标迈出了坚实的步 ...

今日c++学习心得理论课学习了关联容器的有关内容关联容器支持高效的关键字查找和访问,主要有map和set两类map中储存键-值对,可以高效地通过关键字查找值,而set只保存关键字,支持高效的关键字查询他们都可以选择可重复(multi)和无序(umordered_)的前缀,所以一共有2^3=8种关联容器有序保存的关联容器底层是红黑树,无序保存的关联容器底层是哈希函数相比之下,无序储存效率更高,因此,如果不严格要求一直有序,最好选择无序储存关联容器是根据关键字存储的,所以不支持顺序容器的push_back等位置相关的操作作为有序容器的关键字的类型必须定义了元素比较的方法,即严格弱序;作为无序容器关键字则要定义相等关系map类型的元素是pair,pair有两个public成员,分别是first和second,可以用点运算符获得或者用关联容器的迭代器的箭头运算符得到,即it->first和it->second一些泛型算法可以用于关联容器,但通常是一个坏主意,因为它们定义了更高效的成员函数版本的算法向map类型插入元素可以用insert函数,更直观的是用下标运算符和at()函数区别在 ...

题目描述leetcode462. 最少移动次数使数组元素相等 II 给你一个长度为 n 的整数数组 nums，返回使所有数组元素相等需要的最少移动数。 在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。 示例 1： 12345678输入：nums = [1,2,3]输出：2解释：只需要两步操作（每步操作指南使一个元素加 1 或减 1）：[1,2,3] => [2,2,3] => [2,2,2]Copy 示例 2： 1234输入：nums = [1,10,2,9]输出：16Copy 提示： n==nums.length 1<=nums.length<=105 −109<=nums[i]<=109 题解——双指针与直观证明其实,这道题可以转化为求数轴上n个点到某个点距离和的最小值。关键就是找到这个使距离和最小的点,其实就是中位数(或中间区间任意点)，用三角不等式自然能得到最严谨的证明，我在这里给出一种更直观的证明方法。 不妨设各点为xi,目标点为x，首先考虑奇数个点的情况,以三个点为例。如下图显然x取中间点使距离和最小,而且值为L。 ...