前言
什么嘛，我想要留下美好的回忆有什么错！
在自己消失之前，心怀上不像消失的愿望，希望让某个人记住我，希望留下羁绊。
我这么希望着，又有什么不可以吗！
整体评价
国庆出去玩了，所以这场就没参加，现在补了一下。感觉前三题还是蛮简单，第四题有点意思。
t4给了两个玄学解，跟风求hack
1. 公因子的数目
由于这题范围比较小，而且是t1, 所以直接莽了
Java
class Solution {
public int commonFactors(int a, int b) {
int ans = 0;
int r = Math.min(a, b);
for (int i = 1; i <= r; i++) {
if ((a % i) == 0 && (b % i) == 0) {
ans++;
}
}
return ans;
}
}如果这题数据范围放大，我更倾向于求c=gcd(a, b), 然后求c的质因子及个数
结果为
2. 沙漏的最大总和
哈哈，差点求前缀和，转念一想，还是忍住了，比较矩阵窗口才3x3
核心思路是枚举，枚举中心节点，这样比较方便.
Java
class Solution {
public int maxSum(int[][] grid) {
int r = grid.length, c = grid[0].length;
// 3 * 3, 用前缀和，好像多余
// 非负数保证
int ans = 0;
// 枚举中心点
for (int i = 1; i < r - 1; i++) {
for (int j = 1; j < c - 1; j++) {
int ts = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1]
+ grid[i][j]
+ grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1];
// check 没有整数溢出风险
ans = Math.max(ts, ans);
}
}
return ans;
}
}3. 最小 XOR
典型的贪心解吧，先找高位1，进行对消，如果仍有多余，则低位找0，进行补足。
Java
class Solution {
public int minimizeXor(int num1, int num2) {
// 置位数是什么鬼？
int cnt = Integer.bitCount(num2);
int ans = 0;
// 贪心
// 对应num1，从高位找1
for (int i = 30; i >= 0 && cnt > 0; i--) {
if ((num1 & (1 << i)) != 0) {
cnt--;
ans |= (1 << i);
}
}
// 对应num1，从低位找0, 补足
for (int i = 0; i <= 30 && cnt > 0; i++) {
if ((num1 & (1 << i)) == 0) {
cnt--;
ans |= (1 << i);
}
}
return ans;
}
}4. 对字母串可执行的最大删除数
典型的DP
满足 ，
但这里时间复杂度是，如果再外加字符串比较，大概是，对于显然无法接受
这边提供了两种解法(感觉都是"玄学"), 求hack
- 记忆化搜索+剪枝 (已被hqztrue大佬hack, T_T)
Java
class Solution {
Integer[] gOpt;
// DP题
public int deleteString(String s) {
char[] buf = s.toCharArray();
int n = buf.length;
gOpt = new Integer[n];
return solve(buf, 0);
}
int solve(char[] buf, int s) {
if (s >= buf.length) return 0;
if (gOpt[s] != null) {
return gOpt[s];
}
int ans = 1;
for (int i = s; i < buf.length; i++) {
int w = i - s + 1;
int s1 = i + 1;
int e1 = s1 + w - 1;
if (e1 >= buf.length) break;
// *) 这个超级剪枝，感觉刚好对应上了 测试case
// 不加就是超时，加上就是这么华丽
if ((buf.length - i) + 1 <= ans) {
break;
}
if (Arrays.equals(buf, s, s + w, buf, s + w, s + 2 * w)) {
ans = Math.max(ans, 1 + solve(buf, s1));
}
}
return gOpt[s] = ans;
}
}这解法的核心，在于剪枝，效果超级棒
使用了Arrays.equals后，开挂效果明显
- 记忆化搜索+字符串hash
核心是用hash指纹来代替实际的字符串比较
预处理hash指纹（2层，再多就MLE, 哭死）
主体是
Java
class Solution {
int[][] hash1;
int[][] hash2;
int[][] createHash(char[] buf, BiFunction<Integer, Integer, Integer> f) {
int n = buf.length;
int[][] res = new int[n][n];
for (int i = 0; i < n; i++) {
int tv = 0;
for (int j = i; j < n; j++) {
res[i][j] = tv = f.apply(tv, buf[j] - 'a');
}
}
return res;
}
boolean hashEquals(int s0, int e0, int s1, int e1) {
return hash1[s0][e0] == hash1[s1][e1] && hash2[s0][e0] == hash2[s1][e1];
}
Integer[] gOpt;
// DP题
public int deleteString(String s) {
char[] buf = s.toCharArray();
int n = buf.length;
gOpt = new Integer[n];
// *）添加hash，预处理
hash1 = createHash(buf, (a, b) -> (int)((a * 13l + b) % 10_0000_0007));
hash2 = createHash(buf, (a, b) -> (int)((a * 7l + b) % 10_0000_0007));
return solve(buf, 0);
}
int solve(char[] buf, int s) {
if (s >= buf.length) return 0;
if (gOpt[s] != null) {
return gOpt[s];
}
int ans = 1;
for (int i = s; i < buf.length; i++) {
int w = i - s + 1;
int s1 = i + 1;
int e1 = s1 + w - 1;
if (e1 >= buf.length) break;
if (hashEquals(s, i, s1, e1)) {
ans = Math.max(ans, 1 + solve(buf, s1));
}
}
gOpt[s] = ans;
return ans;
}
}收获
这场比赛，虽然是VP赛，但收获还是蛮大的.
LC的java版本，应该是17，需要学习一下新版本的特性.
比如Arrays.equals, 性能真的爆表.
其他
对于t4，我第一印象的滚动hash，应该是Rabin-Karp那版的，先把它补上，主要是节省空间（当然没啥用）
不过rolling hash的标准写法，也学习了一下。
Java
class Solution {
Integer[] gOpt;
// DP题
public int deleteString(String s) {
char[] buf = s.toCharArray();
int n = buf.length;
gOpt = new Integer[n];
return solve(buf, 0, 0);
}
int solve(char[] buf, int s, int tAns) {
final int base = 131;
final long mod = 10_0000_0007l;
if (s >= buf.length) return 0;
if (gOpt[s] != null) {
return gOpt[s];
}
int ans = 1;
long h1 = 0;
long h2 = 0;
long mul = 1l;
for (int i = s; i < buf.length; i++) {
int w = i - s + 1;
int s1 = i + 1;
int e1 = s1 + w - 1;
if (e1 >= buf.length) break;
// rabin-karp这边的核心代码
// h1, 递进
mul = (mul * base) % mod;
h1 = (h1 * base + (buf[i] - 'a')) % mod;
h2 = (h2 * base + (buf[e1 - 1] - 'a')) % mod;
h2 = (h2 * base + (buf[e1] - 'a')) % mod;
h2 = h2 - (buf[i] - 'a') * mul;
h2 = (h2 % mod + mod) % mod;
// rabin-karp
if (h1 == h2) {
ans = Math.max(ans, 1 + solve(buf, s1, tAns + 1));
}
}
return gOpt[s] = ans;
}
}评论 (7)
