- 1627. 带阈值的图连通性(并查集,筛法)
- 1626. 无矛盾的最佳球队(lambda排序)
- 1625. 执行操作后字典序最小的字符串(最大公因数,字符串转换)
- 1622. 奇妙序列(线段树,逆元)
- 1621. 大小为 K 的不重叠线段的数目(dp压缩)
1627. 带阈值的图连通性(并查集,筛法)
首先这道题很显然是可以用并查集解决的,尤其是查找的工作。复杂度主要卡在构造连通图上。我们可以使用类似求素数的埃氏筛的方法。我们去枚举公因数,最小一定是从threshold开始,最大应该是n。然后在枚举可能公因数是这数字的两个数字。最小的肯定是a = x, b = 2*x
, 然后依次增加x
。保证找全这个公因数所有的倍数并且联通。
1 | class Solution { |
如果继续优化的话可以使用埃氏筛等。
1626. 无矛盾的最佳球队(lambda排序)
这道题还是没有想到使用dp的方法。维护了dp[i]表示选取该队员时,和前面的所有人组合能够得到的最大得分。我们对其联合排序,年龄小的在前,相同年龄的话,得分高的在后。
这里有一个新东西,是用Java实现多因素排序的方法。这个在python中是很简单的但是Java中需要调用Comparator<?>
接口并且重写compare
方法。
这里给出两个方法实现,其中lambda表达式会更方便
1 | class Solution { |
1625. 执行操作后字典序最小的字符串(最大公因数,字符串转换)
这道题真的有点难的,需要用枚举的方法。但是这里有一个小技巧可以记住:对于长度为n
的数列,进行长度为m
的轮转,等价于进行长度为两者最大公约数即gcd(m,n)
的轮转。
同时,利用这道题,也可也总结先java中的与字符串相关的各种转换。
String s-> char[] p : p = s.toCharArray();
char[] p -> String s : s = String.valueOf ( p);
int x -> String s : s = String.valueOf(x); 或者 s = Integer.toString(x);
String s -> int x : x = Integer.valueOf(s)
StringBuffer sb -> String s : s = sb.toString();
String s -> StringBuffer sb : sb = new StringBuffer(s);
整个题目的思路在于,首先枚举轮转,这里很巧妙的采用了两个字符串拼接在一起,这样可以得到任意一种开头的方法,然后只需要进行相应的截取就可以。
然后枚举增加,这里需要注意,因为题目给定了字符串的长度一定是偶数,因此我们需要考虑,如果轮转也是偶数的话是没法改变偶数位置的。
最后一个我们再完成累加。
另外有一个板子的方法,求解两个数的最大公因数,是用的辗转相除法。
1 | !! 求最大公因数,背会,真的是不断的交换位置辗转相除。 |
1 | class Solution { |
1622. 奇妙序列(线段树,逆元)
是一道线段树的板子题,但是我还没完全搞定线段树,这里先挖个坑吧。先说一下我目前的方法。从题目可以看出,我们最后返回的值其实可以用一个表达式得到。Y = Ax+B
。我们需要维护三个数列,一个是数值,一个是这个数值在加入时候的A的值,一个是加入进来的B的值。
在求解的时候,对于index位置的数字,其实在数字加入之后的操作都是有效的但是之前的操作都是他享受不到的。已知 A, B, A1, B1, 求解A2,B2,也就是在加入之后的表达式的系数。
Ax +B = A2(A1x+B1)+B2
得到:
A = A1 * A2
B = B1 * A2 + B2
求得:
A2 = A * invA1
B2 = B-B1 * A * invA1
需要注意这里的inv A1
表示逆元,又是一个很板子的方法。
求解逆元:$a^{-1} = a^{m-2}mod(m)$ a
的逆元等于$a^{m-2}$对m取模的结果。要求a,m互质。
1 | class Fancy: |
1621. 大小为 K 的不重叠线段的数目(dp压缩)
动态规划的题目,但是如何优化是关键,首先我们很容易想到子问题是,给定 i
段线段,要求得到 j
段线段覆盖。也就是dp[i][j]
,我们可以想对于这个问题其实可以转化为 ,对于第一段,我们可以选也可以不选,也就是dp[n][k] = dp[n-1][k](不选)+dp[n-1][k-1](选)
但是这样是错误的,因为这里每天线段是可以跨越多个的,我们没有考虑第一条线其实可以覆盖从开头到之后很多区间的情况。
换个更好理解的思路,我们枚举以第一个点为起点的这条线的情况,
- 不存在以第一个点为起点的线,
dp[n-1][k]
- 覆盖一个区间,剩下的k-1条去在n-1个空闲发挥,
dp[n-1][k-1]
- 覆盖两个区间,剩下的k-1条去在n-2个空闲发挥,
dp[n-2][k-1]
… - 最终至少有,
dp[k-1][k-1]
所以!dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-2][k-1]+...+dp[k-1][k-1]
。注意dp的复杂度实在是很高的,因此我们要考虑再写一个,去找规律。dp[n-1][k] = dp[n-2][k]+dp[n-2][k-1]+...+dp[k-1][k-1]
。这样可以看出dp[n][k] = 2*dp[n-1][k]+dp[n-1][k-1]-dp[n-2][k]
。
考虑初始化,肯定dp[i][i] = 1, 但是还需要dp[i][0]也为一,表示在长度为n的线段中,被0个线段的情况也是唯一的。
这里又涉及到了大数的问题,我们还是一样的操作。把int
转换为long
其实只需要在开头乘1L
就可以。同时,由于存在减法,我们需要加上一个mod进行补偿。
1 | class Solution { |