Algorithms&Data Structures保研

LeetCode机试练习(主hard)

接下来预推免的机试基本上难度都上来了,基本上难度在NOIP和lc hard左右,所以这段时间重点练习一下

2021.8.8

48:旋转图像

题目大意:将n*n的矩阵90°顺时针旋转

如果行列下标都从1开始,手玩一下可以得到公式b[j][n+1-i]=a[i][j],a为原矩阵,b为答案矩阵

115:不同的子序列

题目大意:给出两个字符串s和t,求t为s的子序列的个数

记忆化搜索,可以明显得到的性质是如果现在匹配到t的某个字符,那么这个字符可以选择匹配或者不匹配,可以搜索出来所有解,然后把搜索记忆化即可

2021.9.8

502:IPO

题目大意:给出n个项目,每个项目有纯利润和所需最小资本,给出初始资本,求最多选k个项目的最大纯利润

注意到贪心的正确性很容易证明,每次选择利润最大且满足最小资本的选k个就完事了,问题是怎样在时间复杂度要求内找到符合条件的项目,我用的线段树,每次查找最大利润的项目并且修改项目的利润为-inf,每次查找的时间复杂度为O(klogn).

1044:最长重复子串

题目大意:求一个字符串出现2次以上的最长子串

一下子就想到二分+字符串哈希,套用了之前单哈希的模板,但是交上去之后始终被lc的数据卡掉,不得不说此题的数据还是相当可以的,双哈希空间又使用太多怕直接爆掉,看网上用的ull自然溢出,用了之后A了, 确实比单哈希好使不少,时间复杂度O(nlogn).

2021.9.9

629:K个逆序对数组

题目大意:求1~n的全排列中有多少逆序对数为K的排列

自己手动玩了一下,然后把手玩的结果放到oeis上直接得到递推公式了/doge,看了一下题解的思路,dp[i][j]表示1~i的全排列中逆序对数为j的个数,最终答案为dp[n][k],考虑1~i排列中i的位置,如果i放在最后则不会添加逆序对数,放在倒数第二位则逆序对数+1,依此类推,可得递推公式dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+\cdots+dp[i-1][j-i+1],这样处理的时间复杂度是O(n^2*k)的,类比高中数列的错位相减可得,dp[i][j-1]=dp[i-1][j-1]+dp[i-1][j-2]+\cdots+dp[i-1][j-i],将这个式子代入上面那个式子,可得dp[i][j]=dp[i-1][j]+dp[i][j-1]+dp[i-1][j-i],注意边界处理

630:课程表 III

题目大意:给出n门课程的上课持续时间和ddl,求问最多能修多少门课程

做的时候想到了类比nlogn的拦截导弹的优先队列做法,但是想了一会没有想到要去掉哪个,其实很明显要去掉那个耗时最长的,这样就有足够的时间来满足下面ddl更靠后的课程,本质上是贪心,时间复杂度O(nlogn).

2021.9.11

600:不含连续1的非负整数

题目大意:给出正整数n,找出不大于整数n的非负整数中二进制不包含连续1的整数个数

首先预处理出n的二进制,我们要保证遍历的时候不能超过该二进制,方法是如果当前位是1,那么可以选择当前位取0或者1,如果取0,那么此时该位后面的位取0或1都不会比n大,因为最高位取的是0不会超过n,用flag来表示是否在当前位为1时取了0,然后就是记忆化搜索累加答案即可

2021.9.14

127:单词接龙

题目大意:给出初始单词和终止单词和一个单词表,每次转换只能从当前状态修改一个字符得到,求初始单词到终止单词的最少转换次数

很明显连边+dijkstra,看了一下数据范围复杂度差不多够,1A了,不过排名很靠后,原因有两个:一是连边的时候没有优化,有些不需要的边也连上增加了时空复杂度,二是空间方面理论上如果是全连接会MLE的,但是lc数据不卡人所以过了

 

发表评论

邮箱地址不会被公开。 必填项已用*标注