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

上岸算法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]
查看完整版本: 上岸算法LeetCode Weekly Contest 285解题报告