- 博客(301)
- 收藏
- 关注
RSS订阅
原创 玩转算法面试习题列表
第3章3 无重复字符的最长子串283 移动零27 移除元素26 删除排序数组中的重复项80 删除排序数组中的重复项 II75 颜色分类88 合并两个有序数组215 数组中的第K个最大元素167 两数之和 II - 输入有序数组125 验证回文串344 反转字符串345 反转字符串中的元音字母11 盛最多水的容器209 长度最小的子数组3 无重复字符的最长子串348 找到字符串中所有字母异位词76 最小覆盖子串第4章349 两个数组的交集350 两个数组的交集 I
2020-08-09 13:50:45
1092
2
原创 计算机程序的构造和解释（Structure and Interpretation of Computer Programs）
本科毕设的时候林老师推荐过这本书，但是当时看目录就不知所云。这本书是18年9月刚读研究生的时候买的，只是一直没看，连塑封都没拆开。今年因为疫情的原因没有上学，大概从3月份开始，花了3个多月的时间仔细读了一遍，不得不说这书确实是一片新天地，尤其是当你写了很多年的命令式。第一章是构造过程抽象，印象最深的就是用一种通用的过程来实现对一组聚合元素的操作，应该是模板和泛型的概念。另外如果觉得这括号太蛋疼，一定是因为没有看视频教程。第二章是构造数据抽象，感觉和面向对象是一个概念，通过实现有理数类和复数类，将Lisp
2020-06-14 23:24:11
2692
原创 Win10 64位专业版安装镜像启动过程分析
为了搞明白FAT32文件系统中的操作系统是如何启动的，花了两天时间分析了一下Win10安装镜像的启动过程。可以用UltraISO将下载好的Win10镜像写到U盘中，成功后U盘就被格式化成了FAT32文件系统，正好可以用来学习启动过程，这比光看书，或者用Bochs模拟真实多了。硬盘启动分为3部分。计算机上电自检后，将硬盘中的Master Boot Reocrd所在扇区（第1扇区）加载0000:0...
2020-02-20 22:33:38
1525
原创 UVa上未解决的题目
来自《挑战编程》和《算法竞赛入门经典（第2版）》Programming Challenges习题1.6.3 10137 TheTrip因为这道题的测试用例有错误，详见这里3楼的评论浮点数的题目我一向没有好感习题4.6.3 10037 Bridge网上给出了很多贪心的解法，还有为数不多的动态规划解法，但是我没想明白习题5.9.3 701 The Archeologists’ Dilemma如果尝试枚举E的话那么很快程序就超时了虽然我也感觉不应该暴力枚举求解，应该用对数，但是没想出来
2019-10-02 11:42:41
266
原创 《计算机图形学编程（使用OpenGL和C++）》
总结整本书看下来印象最深的就是搞明白了现代OpenGL的可编程管线，还有就是念着（zhuó）色器，而不是着（zháo）色器????????：顶点着色器，对每个顶点调用一次，将顶点发送给管线的下一阶段曲面细分着色器，分为曲面细分控制着色器、曲面细分器和曲面细分评估着色器。曲面细分控制着色器设置控制顶点的细分级别，并将这些信息传递给曲面细分器进行细分。曲面细分评估着色器对曲面细分器得到的每个顶点调用一次几何着色器，对组成基本图元的一组顶点调用一次，可以修改图元、删除图元、添加图元和更改图元类型片段着
2022-02-22 14:15:01
2309
原创 算法竞赛入门经典 习题6-14
UVa12118Inspector’s Dilemma每两个城市之间都有道路连通，检查员要通过指定的道路，途中可以经过其它未指定的道路。通过每条道路的时间是一样的，求出通过所有指定道路要花费的最小时间。如果指定的道路属于不同的连通子图，则检查员需要经由一条额外的道路来连接不同的连通子图，总共需要经由的额外道路是连通子图的数量减1。下面再来考虑连通子图中需要添加额外道路的数量。假设从任意的城市出发，尽量不重复的通过了尽可能多的道路，如果此时还有未通过的指定道路，那么检查员可以经由一条未指定的道路直接到
2022-01-29 20:56:21
1083
1
原创 算法竞赛入门经典 习题6-13
UVa215Spreadsheet Calculator计算并输出电子表格中每个单元格的值，如果出现循环引用，则输出无法求值的单元格。这道题还是有一些实际意义的，解法就是深搜。根据题目中的描述，表达式中只有单元格的引用、常量、加号和减号，所以在解析表达式时可以存储单元格索引以及求值过程中该单元格的倍数，至于常量可以直接计算。题目中说单元格中要么就只有一个数字，要么就是以单元格索引开始的表达式，并且表达式没有前导空格，中间也没有空格，但是uDebug上的一些样例并不符合上述要求。#include
2022-01-28 21:24:31
423
原创 算法竞赛入门经典 习题6-12
UVa810A Dicey Problem一个迷宫里有一骰子，骰子可以上下左右移动的条件是相邻格中的数字和骰子朝上面的数字相同，或者相邻格子中为*。求一条从起点出发，最终回到起点的路径。深搜和广搜应该都可解，试了下深搜超时了，不得已改成广搜。但是广搜也需要记录状态，否则还是会超时。这道题另外麻烦的地方是骰子的滚动，只能通过空间想象进行硬编码。#include <iostream>#include <array>#include <deque>#includ
2022-01-25 21:57:55
445
原创 算法竞赛入门经典 习题6-11
UVa10410Tree Reconstruction编译原理课留了一个为表达式生成语法树的作业，我写完后却落在图书馆了，幸运的是我朋友捡到了，但是他没有直接还给我，而是把语法树的BFS和DFS遍历结果发给我了。眼看就要交作业了，我没时间重写一份了，只能通过这两个遍历结果重构语法树了。基本思路是先确定根节点的子节点，然后根据每个子树的DFS序列依次重建每棵子树。首先可以确定BFS序列和DFS序列中的第一个元素就是根。接下来应该从DFS序列入手，查找DFS[1]和DFS[2]在BFS中的位置，这两个元
2022-01-23 21:16:34
300
原创 算法竞赛入门经典 习题6-10
UVa24610-20-30模拟10-20-30纸牌游戏。纸牌游戏具体规则见原题。牌堆使用使用双端队列，7个牌堆使用链表即可。PickUp()里面second的索引敲错了，找了半天才找出来。#include <iostream>#include <list>#include <deque>#include <set>#include <string>using namespace std;struct Result{ s
2022-01-21 22:08:35
600
原创 算法竞赛入门经典 习题6-9
UVa127“Accordian” Patience将一副扑克牌顺序排成一列，如果某一张牌和左边的牌或者左边第三张牌匹配，则将这张牌移动到那张牌上面。匹配的规则是花色或者点数一样。每次移动和匹配只针对每堆牌最上面的那张。如果有多张牌可以移动，则优先移动最左边的。编程模拟这一过程。题根据题目描述，使用链表模拟所有牌堆，使用栈模拟每一个牌堆即可。#include <iostream>#include <list>#include <sstream>#includ
2022-01-20 13:24:38
556
原创 算法竞赛入门经典 习题6-8
UVa806Spatial Structures对灰度图的图形表示方法和黑色节点表示方法进行转化。题目不详细描述了，英文原题很清楚，解法都是深搜。#include <iostream>#include <algorithm>#include <array>#include <map>#include <memory>#include <string>#include <vector>using nam
2022-01-19 19:44:31
205
原创 算法竞赛入门经典 习题6-7
UVa804Petri Net SimulationPetri网络由放置token的place和传输token的transition组成，每个transition的输入端连接若干个place，输出端连接若干个place。对于每个transition，当输入place中均有一个可用的token时，会从每个输入place中取出一个token，并向输出place中放入一个token，这个过程称为action。给定一个petri网络，求出若干个action后，petri网络是否还能继续执行action。有三点
2022-01-14 21:36:11
119
1
原创 算法竞赛入门经典 习题6-6
UVa12166Equilibrium Mobile求出使得树形天平平衡需要修改的最小砝码的个数。最开始我想到了这样一个递归方式：对于每一个节点使得左子树平衡，然后调整右子树和左子树的重量一样使得右子树平衡，然后调整左子树和右子树的重量一样但是没有办法通过搜索来实现，因为在搜索算法中，递归到最深层就已经得到可行解了，然后慢慢地回退，再去拓展其它的解，而这道题在递归到最深层时时没有可行解的。顺着这个思路想想，当递归到叶节点时，就可以固定这个砝码的重量，然后去调整其余所有砝码的总量，最终肯定是
2022-01-09 12:58:43
304
原创 算法竞赛入门经典 习题6-5
UVa1600Patrol Robot在长宽分别为m和n的矩形区域中，有些格子存在障碍物，机器人可以连续穿过k个障碍物，求从矩形左上角到右下角的最短路径长度。最短路径长度可以使用广搜求解。这道题不同的地方在于机器人可以连续穿过k个障碍物，所以在广搜扩展时还应该记录机器人还能连续穿过多少个障碍物。然后uDebug上有几个测试用例过不了，感觉应该是记录格子是否访问过的逻辑有错误。想了一下，正确的逻辑应该是记录机器人到达这个格子时还能连续穿过障碍物的数量，并使该值尽可能的大。#include <i
2022-01-05 20:05:43
385
原创 算法竞赛入门经典 习题6-4
UVa439Knight Moves给定起点和终点，求出骑士从起点移动到终点的最小步数。题目中的骑士应该是国际象棋中的骑士，也就是和中国象棋中的马的走法是类似的。求最短距离，用广搜就好了。不得不说方向向量确实好用，能避免很多错误。#include <iostream>#include <array>#include <deque>#include <string>#include <vector>using namespace
2022-01-03 18:33:59
322
原创 算法竞赛入门经典 习题6-3
UVa536Tree Recovery根据二叉树的前序和中序遍历求出后续遍历。#include <iostream>#include <string>using namespace std;class Solution{public: Solution(const string &preorder, const string &inorder) : preorder(preorder), inorder(inorder) { size_
2022-01-03 17:32:05
490
原创 算法竞赛入门经典 习题6-2
UVa712S-Trees满二叉树每一层的节点表示一个自变量，当自变量取值为0时向左到达下一层，当自变量取值为1时向右到达下一层。输入自变量的取值和所有叶节点的值，求出最终因变量的值。虽然说的很复杂，但是就是一个二叉堆的模拟题。#include <iostream>#include <string>#include <vector>using namespace std;char EvaluateSTree(const vector<size_t
2022-01-03 16:33:36
154
原创 算法竞赛入门经典 习题6-1
UVa673Parentheses Balance判断表达式中的括号是否平衡，直接用栈判断就可以了。#include <iostream>#include <string>#include <vector>using namespace std;class Solution{public: Solution(const string &expr) : expr(expr) {} bool correctness() { vector
2021-12-27 21:24:40
310
原创 算法竞赛入门经典 例题6-22
UVa11853Paintball在一个正方形区域中有若干个敌人，每个敌人的攻击范围为r，求是否可以在不被攻击的前提下横穿正方形区域。如果可以横穿，求出最靠近北侧的入口和出口。看起来无从下手，但是画个图就明白了。如果没有可以相互掩护射击的敌人的攻击范围覆盖了从北到南的每一个点，那么就是可以横穿的——只需要从敌人攻击范围之间的缝隙穿过就可以了，所以可以根据是否存在从北到南的连通块判断是否存在解。接下来就是找入口和出口了。如果某个连通块覆盖了北边界，那么可以看包含圆形的连通块是否覆盖了西边界，如果覆盖了
2021-12-19 15:54:49
191
原创 算法竞赛入门经典 例题6-21
UVa506System Dependencies编写程序实现类似Linux下的软件包管理器，其工作方式为：可以通过命令显式安装组件，这个过程也可能隐式安装依赖组件如果没有其它组件仍然依赖一个隐式安装的组件，则该组件可以通过命令显式的卸载，或者当最后一个依赖该隐式安装的组件的其它组件被卸载时，该组件会被隐式的卸载已经隐式安装的组件不会因为命令的显式安装而转换为显式安装第2条原文在下面，需要再解释一下。前半句话有问题，没有其它组件仍然依赖一个隐式安装的组件这个状态是不存在的，因为如果这个组件是
2021-12-18 22:31:40
775
原创 算法竞赛入门经典 例题6-20
UVa1599Ideal Path房间和房间之间存在路径，路径的颜色用整数表示，找到一个从编号为1的房间到编号为n的房间的一条理想路径。理想路径是字典序最小的路径。虽然房间数量多达100000，但我还是试了一下朴素的深搜，超时了然后我又试了朴素的广搜，并在广搜过程中记录了从房间1到各个房间的理想路径，还是超时了。相对于穷举全部理想路径的深搜，广搜只需要穷举全部最短的理想路径为了省事，上面两种方法都是用的邻接矩阵存储的图，所以我又把广搜中的邻接矩阵换成邻接表试了一下（为了去掉重复的路径，其实邻接的
2021-12-18 18:17:27
264
原创 算法竞赛入门经典 例题6-19
UVa1572Self-Assembly假设分子为四边形，每条边用一个字母和符号标识。当两个分子的两条边字母相同且符号不同时，两个分子可以连接在一起。给定一些分子，判断这些分支是否可以无限连接。根据题目中的图片，自然想到将分子视为顶点，然后根据每条边的字母和符号添加图中的边，最后只需要判断图中是否存在环即可。这种方法不仅难写，而且超时了，原因在于分子的种类高达40000。所以要换一种建模方法，也就是将字母和符号的组合视为顶点，这样顶点数量只有52个。添加边的方式为：如果分子表示为A+00A+A+，也
2021-12-16 23:35:52
245
原创 算法竞赛入门经典 例题6-18
UVa12171Sculpture题目要求根据雕塑的图纸制作铜铸的雕塑，但是为了节省材料，那些不可见的部分就不铸造了。成型后需要将雕塑放入化学试剂中，为了保证试剂不会溢出，还需要计算雕塑的体积。特别是如果雕塑形成了一个密闭空间，由于化学试剂不会进入该密闭空间，因此该密闭空间的体积也算为雕塑的体积。出于以上两个目的，需要计算雕塑的表面积和体积。直接计算太困难了，不过题目已经给了提示了，雕塑的体积就是排出化学试剂的体积，因此可以将雕塑放入化学试剂中，用总体积减去化学试剂的体积就得到了雕塑的体积。抽象一点，
2021-12-12 00:32:48
113
原创 算法竞赛入门经典 例题6-17
UVa10562Undraw the Trees根据图形显示的二叉树输出二叉树，好像找到规律就可以了，但是uDebug上的用例比较奇葩。#include <iostream>#include <string>#include <vector>using namespace std;struct Node{ char name; vector<Node> children;};class Solution{publi
2021-11-27 00:42:29
352
原创 算法竞赛入门经典 例题6-16
刷题荒废了一个多月，今日了却一件事情，把此题补上！UVa10129Play on Words有若干个圆盘，每个圆盘上都有一个单词，判断这些圆盘是否能排成一排，使得相邻圆盘的首尾字母相同。3年前做过类似的题目，这道题建模非常重要。最容易想到的是将圆盘看做顶点，圆盘之间首尾字母的关系看做边，若此图中包含一个哈密顿路径，则问题有解。但是哈密顿路径一般只能通过搜索方法求解，且没有办法剪枝，所以会超时。还有一种办法，就是将圆盘看做边，字母看做顶点，那么只要该图中包含欧拉路径，则问题有解，而欧拉路径是可以剪
2021-11-22 21:58:19
476
原创 算法竞赛入门经典 例题6-15
UVa10305Ordering Tasks按照任务的依赖关系，对任务进行拓扑排序。其实我已经忘了该怎么写了，但是大概可以猜一下：首先找到不依赖任何其他任务的任务，然后所有依赖于此任务的任务便有了可以完成的前提条件，如此循环即可。这道题只需要找到解，并不要求解的结构，因此uDebug上的很多测试用例不太方便验证对错。#include <iostream>#include <list>#include <vector>using namespace std
2021-10-16 23:29:43
154
原创 算法竞赛入门经典 例题6-14
UVa816Abbott’s Revenge给定一个带箭头的迷宫，迷宫的每一个格子都规定了从不同方向到达这个格子后下一步可以移动到的格子，搜索一条从起点到终点的最短路径。首先题目中没有说是最短路径，所以提交后就WA了，然后深搜的话会TLE，所以就又改成了广搜。好久不写了，忘记广搜该如何记录解了，只能是在每个节点中都记录得到这个节点方法，写的有些丑。#include <iostream>#include <array>#include <map>#inclu
2021-10-16 10:47:24
80
原创 算法竞赛入门经典 例题6-13
UVa1103Ancient Messages识别象形文字。由于一个象形文字中黑色连通像素块只有一个，且象形文字互不覆盖，因此可以根据黑色联通像素块分割象形文字；又因为每个象形文字中白色连通像素块的数量是不同的，所以可以根据白色连通像素块的数量来识别象形文字，因此问题转化为识别黑白连通像素块的问题，DFS可解。这道题提交了22次才完全AC，但即使是这样还是不知道错误在哪里，只能按照题解提交。为了在统计白色连通像素块的过程中尽可能的缩小象形文字图片的大小，代码在遍历黑色连通像素块的过程中，记录了当前需
2021-10-07 15:41:42
119
原创 算法竞赛入门经典 例题6-12
UVa572Oil Deposits统计m行n列的油田中连成大片的油田的个数。#include <iostream>#include <vector>using namespace std;class Solution{public: Solution(int m, int n, istream &is) : grid(vector<vector<char>>(m, vector<char>(n))), vis
2021-10-06 17:16:34
70
原创 算法竞赛入门经典 例题6-11
UVa297Quadtrees将利用四分树表示的灰度图片进行叠加，并统计结果中黑色像素的数量。根据题目中给出的规律，如果原始图片中有黑色像素，那么结果就是黑色像素；如果原始图片中有白色像素，那么结果由另一张图片决定，因此如果已知原始图片中每个像素块中黑色像素的数量，就可以直接相加，也就避免了计算结果图片。#include <iostream>#include <array>#include <memory>#include <string>u
2021-10-06 13:36:54
92
原创 算法竞赛入门经典 例题6-10
UVa699The Falling Leaves定义二叉树中左子节点距父节点左边一个单位的水平距离，右子节点距父节点右边一个单位的水平距离，求相同水平坐标上的节点值的和。构建树的方式和前面几道题类似，求解的方式也比较简单，这道题中麻烦地方在于没有办法根据输入数据将测试样例分开，需要一次性全部读入才可以。最近总是不信邪，认为题目中的两个输出之间有一个空行和同一行中的输出用空格分开可以理解为最后一个输出后面也可以有空格和换行，结果收获了一堆Presentation error ????????????
2021-10-06 11:41:58
98
原创 算法竞赛入门经典 例题6-9
UVa839Not so Mobile判断树形的杠杆是否平衡。根据题目要求构建二叉树判断平衡即可。#include <iostream>#include <memory>#include <sstream>#include <string>#include <vector>using namespace std;struct Lever{ int W_l, D_l, W_r, D_r;};struct Node{
2021-10-05 22:48:23
91
原创 算法竞赛入门经典 例题6-8
UVa548Tree给定二叉树的中序遍历和后序遍历结果，输出从根节点到叶节点的路径和最小的叶节点的值，如果有多个叶节点满足上述条件，则输出值较小的叶节点。依次遍历后序遍历的结果，在中序遍历中查找该元素，该元素右侧的就是该节点的右子树，左侧的就是该节点的左子树。#include <iostream>#include <algorithm>#include <climits>#include <memory>#include <sstream
2021-10-05 20:40:49
85
原创 算法竞赛入门经典 例题6-7
UVa122Trees on the level层次遍历二叉树。这道题方便的地方在于不需要构建二叉树，可以直接对输入数据排序然后输出。但是由于输入数据可能导致二叉树不完整（或者节点重复），所以需要对二叉树的完整性进行判断，也就是在对输入节点按照层次遍历的要求排序后，先判断是否存在重复节点，然后再判断从根到每个节点的路径上的节点是否都存在。#include <iostream>#include <algorithm>#include <set>#include
2021-10-05 11:46:56
107
原创 算法竞赛入门经典 例题6-6
UVa679Dropping Balls小球沿着一个满二叉树形状的装置下落，树中每一个节点都有一个开关来控制与左子节点和右子节点的连通性，每当有小球经过该节点时，开关的状态都会改切换。根据树的深度和放入装置的球的编号，求出小球最终停留在哪个叶子节点。由于是满二叉树（也就是二叉堆），因此是有规律的，可以不用模拟每个小球的下落过程来确定开关的最终状态，直接根据小球的编号即可以模拟该球的下落过程，具体的规律自己画一画就出来啦 ????????????#include <iostream>u
2021-10-04 20:51:54
89
原创 算法竞赛入门经典 例题6-5
UVa12657Boxes in a Line由于涉及在线性序列中间位置的插入和删除，因此还是应该使用链表。同时为了减少#include <iostream>#include <algorithm>#include <list>using namespace std;int main(){ int cases = 1; int n, m; while (cin >> n) { list<int> boxes; li
2021-10-04 17:01:35
110
原创 算法竞赛入门经典 例题6-4
UVa11988Broken Keyboard (a.k.a. Beiju Text)明确说了就是为了练习使用链表，所以也没什么可以选择的。#include <iostream>#include <list>#include <string>using namespace std;int main(){ string line; while (cin >> line) { list<char> text; list&
2021-10-04 12:21:28
82
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人