上岸算法LeetCode Weekly Contest 259解题报告
【 NO.1 执行操作后的变量值】
解题思路
签到题。
代码展示
class Solution {
public int finalValueAfterOperations(String[] operations) {
int v = 0;
for (String op : operations) {
if (op.contains("++")) {
v++;
} else {
v--;
}
}
return v;
}
}
【 NO.2 数组美丽值求和】
解题思路
由前缀最大值和后缀最小值即可得到中间元素的美丽值，所以预处理出前缀最大值和后缀最小值数组即可。
【上岸算法LeetCode Weekly Contest 259解题报告】代码展示
class Solution {
public int sumOfBeauties(int[] nums) {
int[] preMax = new int[nums.length];
preMax[0] = nums[0];
for (int i = 1;
i < nums.length;
i++) {
preMax[i] = Math.max(preMax[i - 1], nums[i]);
}
int[] sufMin = new int[nums.length];
sufMin[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2;
i >= 0;
i--) {
sufMin[i] = Math.min(sufMin[i + 1], nums[i]);
}
int res = 0;
for (int i = 1;
i < nums.length - 1;
++i) {
if (preMax[i - 1] < nums[i] && nums[i] < sufMin[i + 1]) {
res += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
res += 1;
}
}
return res;
}
}
【 NO.3 检测正方形】
解题思路
使用 Map 储存所有的顶点，然后在 count 查询时枚举对角线。
代码展示
class DetectSquares {
Map
public DetectSquares() {
count = new HashMap<>();
}
public void add(int[] point) {
int c = comp(point[0], point[1]);
count.put(c, count.getOrDefault(c, 0) + 1);
}
public int count(int[] point) {
int res = 0;
for (var kv : count.entrySet()) {
int x = X(kv.getKey());
int y = Y(kv.getKey());
if (Math.abs(x - point[0]) == Math.abs(y - point[1]) && x != point[0]) {
res += kv.getValue() *
count.getOrDefault(comp(x, point[1]), 0) *
count.getOrDefault(comp(point[0], y), 0);
}
}
return res;
}
private int comp(int x, int y) {
return x * 10000 + y;
}
private int X(int c) {
return c / 10000;
}
private int Y(int c) {
return c % 10000;
}
}
【 NO.4 重复 K 次的最长子序列】
解题思路
注意 2 <= n < k * 8，而如果一个子序列想要重复出现 k 次，那么这个子序列中的每个字符都至少要出现 k 次，所以说答案的长度一定小于等于 7。
我们首先找出来所有出现次数不小于 k 次的字符，然后枚举这些字符的排列组合，依次判断每一个排列组合是否出现了 k 次。
代码展示
class Solution {
public String longestSubsequenceRepeatedK(String s, int k) {
Map count = new HashMap<>();
for (char c : s.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
StringBuilder s2 = new StringBuilder();
for (char c : s.toCharArray()) {
if (count.get(c) >= k) {
s2.append(c);
}
}
count.clear();
for (char c : s2.toString().toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
return solve(new StringBuilder(), count, s2.toString().toCharArray(), k);
}
private String solve(StringBuilder cur, Map
String res = "";
var keys = new HashSet(count.keySet());
for (var c : keys) {
cur.append(c);
if (comp(cur.toString(), res)) {
int cnt = 0, idx = 0;
for (char cc : s) {
if (cc == cur.charAt(idx) && ++idx == cur.length()) {
idx = 0;
if (++cnt == k) {
res = cur.toString();
break;
}
}
}
}
int bak = count.get(c);
if (bak - k < k) {
count.remove(c);
} else {
count.put(c, bak - k);
}
String r = solve(cur, count, s, k);
if (comp(r, res)) {
res = r;
}
cur.deleteCharAt(cur.length() - 1);
count.put(c, bak);
}
return res;
}
private boolean comp(String a, String b) {
return a.length() > b.length() || (a.length() == b.length() && a.compareTo(b) > 0);
}
}
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解