上岸算法LeetCode Weekly Contest 285解题报告

上岸算法 · 发表于 2022-3-24 05:53:38

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 NO.1 统计数组中峰和谷的数量】

解题思路
先去重，再统计。

代码展示

class Solution {
public int countHillValley(int[] nums) {
   int len = 1;
   for (int i = 1; i < nums.length; i++) {
         if (nums[i] != nums[len - 1]) {
            nums[len] = nums[i];
            len++;
      }
   }
   int res = 0;
   for (int i = 1; i < len - 1; i++) {
         if (nums[i - 1] < nums[i] == nums[i + 1] < nums[i]) {
            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[i] + 1 支箭。

最后多余的箭可以放到位置 0.

代码展示

class Solution {
public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
   int max = 0;
   int[] res = new int[12];
   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[j + 1] + 1;
               score += j + 1;
            }
      }
         if (num > numArrows) {
            continue;
      }
         if (max < score) {
            max = score;
            res[0] = numArrows - num; // 多余的箭
            for (int j = 0; j < 11; j++) {
               if ((i & (1 << j)) > 0) {
                     res[j + 1] = aliceArrows[j + 1] + 1;
               } else {
                     res[j + 1] = 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[queryIndices.length];
   char[] arr = s.toCharArray();
   for (int i = 0; i < queryIndices.length; i++) {
         res[i] = maintain(arr, allIntervals, intervals, queryIndices[i] + 1, queryCharacters.charAt(i));
   }
   return res;
  }

// 将 arr[idx] 替换为 c
// 维护 allIntervals 和 intervals
// 返回单个字符的最长的子字符串长度
private int maintain(char[] arr, TreeSet<Interval> allIntervals, Map<Character, TreeSet<Interval>> intervals, int idx, char c) {
   if (arr[idx] == c) {
         return allIntervals.last().len;
   }

   // 维护原字符 arr[idx] 的 interval
   var treeSet = intervals.get(arr[idx]);
   Interval origin = treeSet.floor(new Interval(idx, 0, arr[idx])); // 调用 treeSet.floor/ceiling 时，只需要 start 即可
   treeSet.remove(origin);
   allIntervals.remove(origin);
   if (origin.start < idx) {
         Interval interval = new Interval(origin.start, idx - origin.start, arr[idx]);
         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[idx]);
         treeSet.add(interval);
         allIntervals.add(interval);
   }

   // 维护新字符 c 的 interval
   treeSet = intervals.get(c);
   if (arr[idx - 1] == c && arr[idx + 1] == 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[idx - 1] == c && arr[idx + 1] != 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[idx - 1] != c && arr[idx + 1] == 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[idx] = c;
   return allIntervals.last().len;
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 285解题报告

登录后可回复主题