CUG23届硕士毕业生

题解

/ 注册

全部文章 / 题解（共7篇）

题解 | #两个序列#

看到互不相同的元素，一定想到hash！题目简述 n个互不相同的数，排列组合成两个序列a和b，每次操作只能从a中选择第一个或最后一个数字并插入a中任意位置，问最少需要多少次操作把a变成b。算法分析设n个元素为x1, x2, ..., xn，因为要从a变成b，所以把b中的值[xk1, xk2, ....

C++ hash 映射最长上升子串

2022-04-13

2 424

题解 | #合法连续子段#

简单滑动窗口算法题目简述长度为n的数组a，求有多少个存在某元素出现次数 >= m 的连续子区间[l,r] 算法分析我们可以发现：若子区间[i,j]不满足情况，固定i不动，j每次后移一步，一次添加一个元素，直到恰好满足 num[a[j]] == m 时，所有以i为起点，以j后面为终点的区...

C++ 滑动窗口双指针

2022-04-12

1 564

题解 | #方案数量#

简单动态规划题题目简述 n * m 的方格，每一个都有一个能量值，初始在左上角，终点在右下角，初始能量就是起点方格的能量值。每步只能向右或向下走一格，一步消耗1能量，一次可以走若干步，只有一次走完后才更新能量，中间经过的方格能量无效；每走一次，能量清零，新的初始能量为当前方格的能量值。求有多少种...

C++ 动态规划递推回溯题面唬人

2022-04-11

1 256

题解 | #牛牛们吃糖果#

经典0-1背包问题题目简述： n个牛牛吃m个糖果，每个牛牛吃ai个，k对牛牛绑定必须一起吃或不吃，每个牛牛只会出现在一对绑定中（不会重婚）求能够吃到糖果的牛牛的最大数量。很显然，我们把配对了的两只牛牛看作一个权值为2的物品，所需容积为二者之和；把单身的牛牛看作权值为1的物品，所需容积就是其本身...

C++ 背包问题 0-1背包动态规划

2022-04-11

1 560

题解 | #树上最短链#

树上BFS问题题意简述： n个城市有n-1条无向边的连通图（也是树结构），每条边的时间权值都是1；每个城市有一个等级，求以等级相同的任意两城市作为起点和终点时，最小的时间花费。（每条边至多经过一次）算法设计我们可以以任意结点为起点，以其他任意结点为终点，基本上就是《任意两点间的最短路径问题》...

C++ 最短路树形bfs

2022-04-11

3 632

题解 | #知识竞赛#

巧妙逻辑归纳题题意简述： n个(A,B)，找出两个人，使得 X=(B1+B2)/2, Y=(A1+A2)/2，求min(X,Y)的最大值注意：这里让X=(A1+A2)/2, Y=(B1+B2)/2时，结果不变，利于顺序理解。逻辑树分析：我们需要选择两个人，记为i和j，先选i再选j，则所有情况...

C++ 逻辑树归纳分析

2022-04-10

9 305

题解 | #判断链表中是否有环#

快慢指针法判断链表中是否有环，且能够找到环的起始结点： /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int ...

C++ 双指针链表

2022-04-02

0 207