上岸算法LeetCode Weekly Contest 285解题报告
【 NO.1 统计数组中峰和谷的数量】解题思路
先去重,再统计。
代码展示
class Solution {
public int countHillValley(int[] nums) {
int len = 1;
for (int i = 1; i < nums.length; i++) {
if (nums != nums) {
nums = nums;
len++;
}
}
int res = 0;
for (int i = 1; i < len - 1; i++) {
if (nums < nums == nums < nums) {
res++;
}
}
return res;
}
}
【 NO.2 统计道路上的碰撞次数】
解题思路
从左到右遍历,维护左侧的车的状态,有两种:
若干个向右行驶的
停止
代码展示
class Solution {
public int countCollisions(String directions) {
int res = 0;
int S = 0, R = 0;
for (char c : directions.toCharArray()) {
if (c == 'L') {
if (S + R == 0) {
continue;
}
if (R > 0) {
res += R + 1;
} else {
res += S;
}
S = 1;
R = 0;
}
if (c == 'R') {
S = 0;
R++;
}
if (c == 'S') {
res += R;
S = 1;
R = 0;
}
}
return res;
}
}
【 NO.3 射箭比赛中的最大得分】
解题思路
枚举所有的情况即可,实际一共有 11 个得分位置,枚举 Bob 要在哪些位置得分。
贪心地,当 Bob 要在位置 i 得分时,只需要花费 aliceArrows + 1 支箭。
最后多余的箭可以放到位置 0.
代码展示
class Solution {
public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
int max = 0;
int[] res = new int;
for (int i = 0; i < (1 << 11); i++) {
int num = 0;
int score = 0;
for (int j = 0; j < 11; j++) {
if ((i & (1 << j)) > 0) {
num += aliceArrows + 1;
score += j + 1;
}
}
if (num > numArrows) {
continue;
}
if (max < score) {
max = score;
res = numArrows - num; // 多余的箭
for (int j = 0; j < 11; j++) {
if ((i & (1 << j)) > 0) {
res = aliceArrows + 1;
} else {
res = 0;
}
}
}
}
return res;
}
}
【 NO.4 由单个字符重复的最长子字符串】
解题思路
灵活运用 TreeSet 即可,详见注释。
代码展示
class Solution {
// 一个 Interval 表示一段连续的字符
static class Interval implements Comparable<Interval> {
int start;
int len;
char c;
public Interval(int start, int len, char c) {
this.start = start;
this.len = len;
this.c = c;
}
@Override
public int compareTo(Interval o) {
if (len != o.len) {
return len - o.len;
}
if (start != o.start) {
return start - o.start;
}
return c - o.c;
}
}
public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
// 首尾新增两个其他字符,这样相当于 queryIndices 不会修改字符串首尾,便于后续的处理
s = "_" + s + "_";
// allIntervals 按照 len 排序全部的区间
TreeSet<Interval> allIntervals = new TreeSet<>();
// intervals 按照字符聚合区间,即 intervals.get('a') 表示字符 a 的全部区间,并且按照起始位置排序
Map<Character, TreeSet<Interval>> intervals = new HashMap<>();
for (char c = 'a'; c <= 'z'; c++) {
intervals.put(c, new TreeSet<>(Comparator.comparingInt(o -> o.start)));
}
intervals.put('_', new TreeSet<>());
// 遍历 s 维护 intervals 和 allIntervals
int last = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(last)) {
continue;
}
Interval interval = new Interval(last, i - last, s.charAt(last));
allIntervals.add(interval);
intervals.get(s.charAt(last)).add(interval);
last = i;
}
Interval interval = new Interval(last, s.length() - last, s.charAt(last));
allIntervals.add(interval);
intervals.get(s.charAt(last)).add(interval);
// 每次 query 调用 maintain 维护 intervals 和 allIntervals
int[] res = new int;
char[] arr = s.toCharArray();
for (int i = 0; i < queryIndices.length; i++) {
res = maintain(arr, allIntervals, intervals, queryIndices + 1, queryCharacters.charAt(i));
}
return res;
}
// 将 arr 替换为 c
// 维护 allIntervals 和 intervals
// 返回单个字符的最长的子字符串长度
private int maintain(char[] arr, TreeSet<Interval> allIntervals, Map<Character, TreeSet<Interval>> intervals, int idx, char c) {
if (arr == c) {
return allIntervals.last().len;
}
// 维护原字符 arr 的 interval
var treeSet = intervals.get(arr);
Interval origin = treeSet.floor(new Interval(idx, 0, arr)); // 调用 treeSet.floor/ceiling 时,只需要 start 即可
treeSet.remove(origin);
allIntervals.remove(origin);
if (origin.start < idx) {
Interval interval = new Interval(origin.start, idx - origin.start, arr);
treeSet.add(interval);
allIntervals.add(interval);
}
if (idx + 1 < origin.start + origin.len) {
Interval interval = new Interval(idx + 1, origin.start + origin.len - idx - 1, arr);
treeSet.add(interval);
allIntervals.add(interval);
}
// 维护新字符 c 的 interval
treeSet = intervals.get(c);
if (arr == c && arr == c) { // 左右连接
Interval left = treeSet.floor(new Interval(idx - 1, 0, c));
Interval right = treeSet.ceiling(new Interval(idx + 1, 0, c));
treeSet.remove(left);
treeSet.remove(right);
allIntervals.remove(left);
allIntervals.remove(right);
Interval interval = new Interval(left.start, left.len + right.len + 1, c);
treeSet.add(interval);
allIntervals.add(interval);
} else if (arr == c && arr != c) { // 左连接
Interval left = treeSet.floor(new Interval(idx - 1, 0, c));
treeSet.remove(left);
allIntervals.remove(left);
Interval interval = new Interval(left.start, left.len + 1, c);
treeSet.add(interval);
allIntervals.add(interval);
} else if (arr != c && arr == c) { // 右连接
Interval right = treeSet.ceiling(new Interval(idx + 1, 0, c));
treeSet.remove(right);
allIntervals.remove(right);
Interval interval = new Interval(idx, right.len + 1, c);
treeSet.add(interval);
allIntervals.add(interval);
} else { // 单独一个
Interval interval = new Interval(idx, 1, c);
treeSet.add(interval);
allIntervals.add(interval);
}
arr = c;
return allIntervals.last().len;
}
}
页:
[1]