LeetCode Weekly Contest 258解题报告
【 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;
}@Overridepublic 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;
}@Overridepublic int hashCode() {return Objects.hash(num, den);
}
}
public long interchangeableRectangles(int[][] rectangles) {
Map 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> 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
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;
}
【LeetCode Weekly Contest 258解题报告】}
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- 推酷《Guru|推酷《Guru Weekly》第十四期
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路