LeetCode Weekly Contest 258解题报告

上岸算法 · 发表于 2021-9-12 23:22:37

登录后可回复主题

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

x

【 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<Integer>> 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<Integer> dfs(int cur, Map<Integer, List<Integer>> children, int[] nums, int[] ans) {
   Set<Integer> 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<Integer> 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;
  }
}

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

[吹水聊天] LeetCode Weekly Contest 258解题报告

登录后可回复主题

浏览过的版块