前言
是啊。
虽然我从更高更远的地方看过悬浮岛，
可是至今为止，我都没有好好地从城里俯望过整座城市。
所以我想，至少应该看过一次才对。
嗯。我的梦想实现了，也留下美好的回忆，我已经没有任何遗憾了。
今天真的很谢谢你。
发生了好多美好的事情。
全都是讬你的福。
整体评价
其实我感觉质量还可以，t1分类讨论，t2思维题吧，t3二维异或和，t4找规律。
推荐VP。
快速通道：第225场周赛
更多解题报告详见：珂朵莉MM的解题报告汇总
1. 替换隐藏数字得到的最晚时间
这里需要贪心，因为小时和分钟，是有约束的，因此需要分类讨论。所幸的是，小时和分钟都是独立的。
其实整个分类讨论的分支没那么多。
类似题 2437. 有效时间的数目
Java
class Solution {
public String maximumTime(String time) {
char[] buf = time.toCharArray();
// Hour 独立
if (buf[0] == '?' && buf[1] == '?') {
buf[0] = '2'; buf[1] = '3';
} else if (buf[0] == '?') {
if (buf[1] <= '3') {
buf[0] = '2';
} else {
buf[0] = '1';
}
} else if (buf[1] == '?') {
if (buf[0] == '2') {
buf[1] = '3';
} else {
buf[1] = '9';
}
}
// minute独立
if (buf[3] == '?' && buf[4] == '?') {
buf[3] = '5';
buf[4] = '9';
} else if (buf[3] == '?') {
buf[3] = '5';
} else if (buf[4] == '?') {
buf[4] = '9';
}
return new String(buf);
}
}2. 满足三条件之一需改变的最少字符数
本质是分类讨论，既三种情况下的最优解
- 字符串a 和 字符串b相等
- 字符串a 小于 字符串b
- 字符串a 大于 字符串b
这里的change其实挺麻烦，因为不光a中字符可以变，b中的字符也可以变。
所以可能要转换下思路：
巧用枚举
比如字符串a变成 小于 字符串b
可以枚举最终转变后a中最大的字母，这样a和b中，需要改变的字符数就马上出来了。
就这么简单， 感觉时间复杂度为, n为字符串长度。
Java
class Solution {
int same(char[] sa, char[] sb) {
int[] hash = new int[26];
for (int i = 0; i < sa.length; i++) {
hash[sa[i] - 'a']++;
}
for (int i = 0; i < sb.length; i++) {
hash[sb[i] - 'a']++;
}
int ans = hash[0];
for (int i = 0; i < 26; i++) {
ans = Math.max(ans, hash[i]);
}
return sa.length + sb.length - ans;
}
// *) 也是枚举吗？
int small(char[] sa, char[] sb) {
int[] hash1 = new int[26];
for (int i = 0; i < sa.length; i++) {
hash1[sa[i] - 'a']++;
}
int[] hash2 = new int[26];
for (int i = 0; i < sb.length; i++) {
hash2[sb[i] - 'a']++;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < 25; i++) {
int v = 0;
for (int j = i + 1; j < 26; j++) {
v += hash1[j];
}
for (int j = 0; j <= i; j++) {
v += hash2[j];
}
ans = Math.min(ans, v);
}
return ans;
}
// 分类讨论
public int minCharacters(String a, String b) {
char[] sa = a.toCharArray();
char[] sb = b.toCharArray();
return Math.min(
same(sa, sb),
Math.min(small(sa, sb), small(sb, sa))
);
}
}3. 找出第 K 大的异或坐标值
这题的数据规模，决定了求第K大值，可以用常规方法。
不过这里所谓的坐标，本质对应二维前缀异或和。这边有个预处理。
Java
class Solution {
// *) 赢算了
public int kthLargestValue(int[][] matrix, int k) {
List<Integer> arr = new ArrayList<>();
int r = matrix.length, c = matrix[0].length;
// xor 前缀和
int[][] opt = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 && j == 0) opt[i][j] = matrix[i][j];
else if (i == 0) {
opt[i][j] = opt[i][j - 1] ^ matrix[i][j];
} else if (j == 0) {
opt[i][j] = opt[i - 1][j] ^ matrix[i][j];
} else {
opt[i][j] = opt[i - 1][j - 1] ^ opt[i - 1][j] ^ opt[i][j - 1] ^ matrix[i][j];
}
arr.add(opt[i][j]);
}
}
Collections.sort(arr);
int idx = r * c - k;
return arr.get(idx);
}
}4. 放置盒子
这个真的是找规律题，就是每层尽量构建直角等边形，这样最稳定，上面可放的块也越多。
既然构建思路出来了，问题就演变成，如果一层放块, 其上方可以放几块？
就是找总数最接近的直角等边三角形的边长
求一元二次方程的根：
找到这个k后，可产生,剩余的数可构建个方块。
最终为
最后程序的最外层，搞一个二分，枚举底层用的方块数，这样就能得到最后的解了。
Java
class Solution {
int convert(int m) {
// (k + 1) * k / 2 <= m
// k^2 + k - 2m = 0;
// k = (-1 + sqrt(1 + 8*m)) / 2
int k = (int)((-1 + Math.sqrt(1l + 8l*m)) / 2.0);
long ck = 1l * (k + 1) * k / 2;
long rk = 1l * k * (k - 1) / 2;
if (ck == m) return (int)rk;
return (int)rk + (int)(m - ck - 1);
}
// *) 假设地面放m块地板
boolean check(int m, int n) {
int left = n - m;
while (left > 0 && m > 0) {
// 3 -> 1, 5 -> 2, 6 -> 3,
int delta = convert(m);
left -= delta;
if (left <= 0) return true;
m = delta;
}
return left <= 0;
}
// 这是找规律题目吗？
public int minimumBoxes(int n) {
// 二分？
int ans = 0;
int l = 0, r = n;
while (l <= r) {
int m = l + (r - l) / 2;
if (check(m, n)) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}写在最后
评论 (2)
