【 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 即可。然而有两个优化很重要：
- 如果子树中缺失的最大的是 x, 那么枚举查找以后树缺失的只须要从 x 开始即可，而不是 1
- 合并 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;}
}