首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
课程
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
电专小胖墩
获赞
0
粉丝
0
关注
0
看过 TA
14
杭州电子科技大学
2024
Java
IP属地:浙江
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑电专小胖墩吗?
发布(8)
刷题
电专小胖墩
02-27 12:17
杭州电子科技大学 计算机类
题解 | 区间覆盖问题的变形
时间复杂度:O(mlogm)区间覆盖问题给定n个小区间和一个范围[a, b],选择尽量少的区间,使得[a, b]能够被完全覆盖。解法:贪心如果有区间x和y,x包含了y,显然选择x这个大区间更好。因此考虑对每个区间按左端点升序排序,从第一个小区间开始选择,每次选择区间左端点在目标区间内且右端点尽可能大的区间。每次选择区间后更新目标区间(左端点更新为选中区间的右端点+1)。排序开销:O(nlogn)选区间开销:O(n)总时间复杂度:O(nlogn)区间预处理显然,本题没有明说各个小区间,因此需要预处理出小区间。我们可以把m个请求服务器看成[0,m-1]的区间。每个代理服务器在需要切换之前(后)看成...
0
点赞
评论
收藏
分享
电专小胖墩
02-17 14:08
杭州电子科技大学 计算机类
题解 | #矩阵转置#
矩阵原地转置(时间换空间) 思路引入 参考在一维数组中进行循环位移: a[]={1,2,3,4},要将数组循环左移1位,下标循环: 与循环位移类似,以一个2x3矩阵为例,元素右下角数字为其在一维数组中的下标。 直接从矩阵来看,看不出什么下标规律,但是将其展开为一维数组,就能发现一些下标循环: (重复) (重复) (重复) 因此,考虑用循环数组的思路来处理矩阵转置。 详细思路 后继下标计算 对于N*M原矩阵中(i,j)元素,其在转置矩阵中索引为(j,i),前者在一维数组下标为i*M+j,后者为j*N+i。 找循环 从下标0开始遍历一维数组,根据后继下标的计算方法,循环进行移动,直到...
0
点赞
评论
收藏
分享
电专小胖墩
02-16 20:39
杭州电子科技大学 计算机类
题解 | #C翻转#
观察几个旋转例子,就可以发现n*n矩阵有以下规律:逆时针旋转90度:第i行变为第n-i+1列顺时针旋转90度:第j列变为第n-j+1行若矩阵二维数组a从0开始使用,则有:逆时针旋转90度:a'[n-j-1][i]=a[i][j]顺时针旋转90度:a'[j][n-i-1]=a[i][j]对于有起始坐标偏移的旋转,再分别加上x、y偏移即可。 // // Created by Zed on 2024/2/15. // #include <iostream> using namespace std; const int MAXN = 15; const int INF = 1e7; in...
0
点赞
评论
收藏
分享
电专小胖墩
02-10 21:30
已编辑
杭州电子科技大学 计算机类
题解 | #洋灰三角#
考点:递推式计算 矩阵快速幂 注意点:负数的模应该先加上MOD再模 设s(n)为n个格子铺满需要多少洋灰三角。根据题意,可以得出如下递推式: 因此可以构造出: 以此递推即可得到: 因此问题就转化为求一个三阶矩阵的高次幂,与纯数的快速幂类似,只是将数的乘法改为矩阵乘法即可。(吐槽:牛客MD编辑器真难用,基本的Latex公式都表示不出来) // // Created by Zed on 2024/2/10. // /* * 链接:https://ac.nowcoder.com/acm/problem/17510 来源:牛客网 题目描述 洋灰是一种建筑材料,常用...
0
点赞
评论
收藏
分享
电专小胖墩
02-09 17:40
已编辑
杭州电子科技大学 计算机类
题解 | #Sharing#
记录两种思路:按照链表的观点,找公共结点,可以利用双指针的思想实现(a+c+b=b+c+a,其中a、b分别为两个链表前缀的长度,c为公共后缀的长度)。把链表看成有向图,公共后缀结点其实就是入度为2的结点。这里提供第二种思路的代码 // // Created by Zed on 2024/2/9. // #include <iostream> #include <cstdio> using namespace std; const int MAXN = 1e6 + 100; int in[MAXN];//统计结点的入度 int main() { int s1,...
0
点赞
评论
收藏
分享
电专小胖墩
02-08 21:30
杭州电子科技大学 计算机类
题解 | #最短路径#
从Prim算法和Dijkstra算法两种算法异同的角度说明为何本题最小生成树中包含了所有最短路径。两种思路:最短路+高精度加乘(最容易想到的方法,该题大数可以用二进制数组表示比较方便)最小生成树+dfs这里着重记录第二种思路。首先说明一下为什么最小生成树中包含了所有最短路径。这里不得不提及一下Prim算法和Dijkstra算法,这两种算法有极高的相似度,这两个算法在添加新结点时,都是选择“距离最短”的结点加入集合,但是Prim算法中,“距离最短”是指未访问的结点到已经访问的所有结点距离最小,即将已经访问的结点视为一个整体,将距离最小的结点加入到已访问的集合中;而在Dijkstra算法中,“距离...
0
点赞
评论
收藏
分享
电专小胖墩
02-08 12:20
杭州电子科技大学 计算机类
题解 | #2的幂次方#
典型的递归问题。对于x需要将其转化为2次幂的和而其中指数同样需要按第一条处理因此递归函数就有了基本框架:从大到小,提取x的二次幂的指数x'对指数x'调用递归函数最终代码如下 // // Created by Zed on 2024/2/8. // #include <iostream> using namespace std; void reverse(int x) { if (x == 0) {//递归封口 cout << 0; return; } bool first = false;//为了输出加号准备,...
0
点赞
评论
收藏
分享
电专小胖墩
01-27 21:07
杭州电子科技大学 计算机类
题解 | #剩下的树#
提供一种O(n+m)的思路。利用差分数组可以实现O(1)进行一次区间操作,而计算具体某个元素的时间复杂度为O(n)(一次性计算所有元素的值时间复杂度为O(n))。因为本题先进行一系列区间操作,最后再询问一次所有元素的值,因此十分适合用差分数组求解。对于本题,可将原数组初值设置为0,表示树还在,而后续砍树操作看做区间减1操作,最后再计算修改后的数组的值,当值小于0,说明被砍了,反之还在,统计结果即可。差分数组定义diff[i]=a[i]-a[i-1],i>=1(a为原数组,diff为差分数组)diff[0]=a[0]显然,a[i]=diff[0]+...+diff[i]区间操作对[l,r]...
0
点赞
评论
收藏
分享
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务