上岸算法 发表于 2021-9-21 23:03:20

上岸算法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 数组美丽值求和】

解题思路
由前缀最大值和后缀最小值即可得到中间元素的美丽值,所以预处理出前缀最大值和后缀最小值数组即可。

代码展示

class Solution {
   public int sumOfBeauties(int[] nums) {
       int[] preMax = new int;
       preMax = nums;
       for (int i = 1; i < nums.length; i++) {
         preMax = Math.max(preMax, nums);
      }
       int[] sufMin = new int;
       sufMin = nums;
       for (int i = nums.length - 2; i >= 0; i--) {
         sufMin = Math.min(sufMin, nums);
      }
       int res = 0;
       for (int i = 1; i < nums.length - 1; ++i) {
         if (preMax < nums && nums < sufMin) {
               res += 2;
          } else if (nums < nums && nums < nums) {
               res += 1;
          }
      }
       return res;
}
}

【 NO.3 检测正方形】

解题思路
使用 Map 储存所有的顶点,然后在 count 查询时枚举对角线。

代码展示

class DetectSquares {

   Map<Integer, Integer> count;

   public DetectSquares() {
       count = new HashMap<>();
}

   public void add(int[] point) {
       int c = comp(point, point);
       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) == Math.abs(y - point) && x != point) {
               res += kv.getValue() *
                     count.getOrDefault(comp(x, point), 0) *
                     count.getOrDefault(comp(point, 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<Character, Integer> 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<Character, Integer> count, char[] s, int k) {
       String res = "";
       var keys = new HashSet<Character>(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]
查看完整版本: 上岸算法LeetCode Weekly Contest 259解题报告