【 NO.1 反转单词前缀】

解题思路

签到题。

代码展示

class Solution {

   public String reversePrefix(String word, char ch) {

       int index = word.indexOf(ch);

       return new StringBuffer(word.substring(0, index + 1)).reverse().toString() +

               word.substring(index + 1);

  }

}

【 NO.2 可互换矩形的组数】

解题思路

将矩形按照长宽比分类，计数即可。

代码展示

class Solution {

   static class Frac {

       int den;

       int num;

       public static int gcd(int a, int b) {

           return b == 0 ? a : gcd(b, a % b);

      }

       public Frac(int num, int den) {

           int g = gcd(num, den);

           this.num = num / g;

           this.den = den / g;

      }

       @Override

       public boolean equals(Object o) {

           if (this == o) return true;

           if (o == null || getClass() != o.getClass()) return false;

           Frac frac = (Frac) o;

           return den == frac.den && num == frac.num;

      }

       @Override

       public int hashCode() {

           return Objects.hash(num, den);

      }

  }

   public long interchangeableRectangles(int[][] rectangles) {

       Map<Frac, Integer> count = new HashMap<>();

       for (var rec : rectangles) {

           Frac f = new Frac(rec[0], rec[1]);

           count.put(f, count.getOrDefault(f, 0) + 1);

      }

       long res = 0;

       for (var k : count.entrySet()) {

           int v = k.getValue();

           res += (long) v * (v - 1) / 2;

      }

       return res;

  }

}

【 NO.3 两个回文子序列长度的最大乘积】

解题思路

暴力枚举。使用二进制位表示一个子序列，枚举所有情况即可。

代码展示

class Solution {

   public int maxProduct(String s) {

       int len = s.length();

       int res = 0;

       int[] mem = new int[1 << len];

       Arrays.fill(mem, -1);

       for (int i = 0; i < (1 << len); i++) {

           for (int j = 0; j < (1 << len); j++) {

               if ((i & j) > 0) {

                   continue;

              }

               res = Math.max(res, length(s, i, mem) * length(s, j, mem));

          }

      }

       return res;

  }

   private int length(String s, int bitset, int[] mem) {

       if (mem[bitset] >= 0) {

           return mem[bitset];

      }

       mem[bitset] = 0;

       for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {

           while (i <= j && (bitset & (1 << i)) == 0) i++;

           while (i <= j && (bitset & (1 << j)) == 0) j--;

           if (!(i <= j && (bitset & (1 << i)) != 0 && (bitset & (1 << j)) != 0)) {

               break;

          }

           if (s.charAt(i) == s.charAt(j)) {

               mem[bitset] += i == j ? 1 : 2;

          } else {

               mem[bitset] = 0;

               break;

          }

      }

       return mem[bitset];

  }

}

【 NO.4 每棵子树内缺失的最小基因值】

解题思路

DFS 合并 Set 即可。但是有两个优化很重要： 1. 假如子树中缺失的最大的是 x, 那么枚举查找当前树缺失的只需要从 x 开始即可，而不是 1

2. 合并 Set 时由小 Set 合并到大 Set 中

代码展示

class Solution {

   public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {

       Map<Integer, List> children = new HashMap<>();

       for (int i = 1; i < parents.length; i++) {

           if (!children.containsKey(parents[i])) {

               children.put(parents[i], new ArrayList<>());

          }

           children.get(parents[i]).add(i);

      }

       int[] ans = new int[parents.length];

       dfs(0, children, nums, ans);

       return ans;

  }

   private Set dfs(int cur, Map<Integer, List> children, int[] nums, int[] ans) {

       Set set = new HashSet<>();

       set.add(nums[cur]);

       if (!children.containsKey(cur)) {

           ans[cur] = nums[cur] == 1 ? 2 : 1;

           return set;

      }

       var child = children.get(cur);

       int start = 1;

       for (var c : child) {

           var r = dfs(c, children, nums, ans);

           if (r.size() > set.size()) {

               Set tmp = r;

               r = set;

               set = tmp;

          }

           set.addAll(r);

           start = Math.max(start, ans[c]);

      }

       while (set.contains(start)) {

           start++;

      }

       ans[cur] = start;

       return set;

  }

}