6265. Count Pairs Of Similar Strings
给你一个下标从 0 开始的字符串数组 words 。
如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。
- 例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
- 然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。
请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= word.length - 1 。
测试样例：
输入：words = ["aba","aabb","abcd","bac","aabc"]
输出：2
解释：共有 2 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。
- i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。
解答: 由于只包含小写字母，而且只需要判断字符串是否有相同的字符构成。所以只需要状态压缩一下，建立HashMap。然后根据排列组合公式，计算对数即可。
class Solution {
public int similarPairs(String[] words) {
HashMap<Integer, Integer> map = new HashMap<>();
for (String w : words) {
int key = 0;
for (int i = 0; i < w.length(); ++i) {
int o = w.charAt(i) - 'a';
key |= (1 << o);
}
map.put(key, map.getOrDefault(key, 0) + 1);
}
int res = 0;
for (Map.Entry<Integer, Integer> kv : map.entrySet()) {
int v = kv.getValue();
res += (1 + v - 1) * (v - 1) / 2;
}
return res;
}
}6266. Smallest Value After Replacing With Sum of Prime Factors
给你一个正整数 n 。
请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。
- 注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。
返回 n 可以取到的最小值。
测试样例
输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 2 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。
解答：这道题目考察质因数分解。套用数学公式即可
class Solution {
public int smallestValue(int n) {
int last = n;
n = change(n);
while (last != n) {
last = n;
n = change(n);
}
return last;
}
private int change(int n) {
int max = (int) (Math.sqrt(n) + 1);
int res = 0;
for (int i = 2; i <= max; ++i) {
while (n % i == 0) {
res += i;
n /= i;
}
}
if (n > 1) {
res += n;
}
return res;
}
}6267. Add Edges to Make Degrees of All Nodes Even
给你一个有 n 个节点的无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。图不一定连通。
你可以给图中添加至多两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。
如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。
点的度数是连接一个点的边的数目。
测试样例：
输入：n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
输出：true
解释：上图展示了添加一条边的合法方案。
最终图中每个节点都连接偶数条边。
解答：这道题目需要分类讨论类型。如果度数是奇数的点存在奇数个，则无法满足要求。又因为最多添加2条边，所以如果度数是奇数的点超过5个，也无法满足要求。
如果奇数点个数是2个，则2点之间没有边，或者2点可以找到一个点，且2点都不与这个点有边。则返回true
如果奇数点个数是4个，且存在一个方案添加2条之前不存在的边，则返回true
否则都返回false
class Solution {
private static final long mul = 1_000_02;
public boolean isPossible(int n, List<List<Integer>> edges) {
int[] count = new int[n];
Set<Long> edgeSet = new HashSet<>();
for (List<Integer> e : edges) {
int min = Math.min(e.get(0), e.get(1)) - 1, max = Math.max(e.get(0), e.get(1)) - 1;
count[min] += 1;
count[max] += 1;
edgeSet.add(calKey(min, max));
}
List<Integer> odd = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (count[i] % 2 == 1) {
odd.add(i);
}
}
if (odd.isEmpty()) {
return true;
} else if (odd.size() % 2 == 1 || odd.size() >= 5) {
return false;
} else if (odd.size() == 2) {
int n1 = odd.get(0), n2 = odd.get(1);
if (!edgeSet.contains(calKey(n1, n2))) {
return true;
} else {
for (int i = 0; i < n; ++i) {
if (i != n1 && i != n2 && !edgeSet.contains(calKey(i, n1)) && !edgeSet.contains(calKey(i, n2))) {
return true;
}
}
return false;
}
} else {
if (!edgeSet.contains(calKey(odd.get(0), odd.get(1))) && !edgeSet.contains(calKey(odd.get(2), odd.get(3)))) {
return true;
} else if (!edgeSet.contains(calKey(odd.get(0), odd.get(2))) && !edgeSet.contains(calKey(odd.get(1), odd.get(3)))) {
return true;
} else if (!edgeSet.contains(calKey(odd.get(0), odd.get(3))) && !edgeSet.contains(calKey(odd.get(1), odd.get(2)))) {
return true;
}
return false;
}
}
private long calKey(int x, int y) {
return Math.min(x, y) * mul + Math.max(x, y);
}
}6268. Cycle Length Queries in a Tree
给你一个整数 n ，表示你有一棵含有 2n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在[1, 2n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足：
- 左子节点的编号为 2 * val
- 右子节点的编号为 2 * val + 1
给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [ai, bi] 。对于每个查询，求出以下问题的解：
- 在节点编号为 ai 和 bi 之间添加一条边。
- 求出图中环的长度。
- 删除节点编号为 ai 和 bi 之间新添加的边。
注意：
- 环 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
- 环的长度是环中边的数目。
在树中添加额外的边后，两个点之间可能会有多条边。- 请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。
测试样例：
输入：n = 3, queries = [[5,3],[4,7],[2,3]]
输出：[4,5,3]
解释：上图是一棵有 23 - 1 个节点的树。红色节点表示添加额外边后形成环的节点。
- 在节点 3 和节点 5 之间添加边后，环为 [5,2,1,3] ，所以第一个查询的结果是 4 。删掉添加的边后处理下一个查询。
- 在节点 4 和节点 7 之间添加边后，环为 [4,2,1,3,7] ，所以第二个查询的结果是 5 。删掉添加的边后处理下一个查询。
- 在节点 2 和节点 3 之间添加边后，环为 [2,1,3] ，所以第三个查询的结果是 3 。删掉添加的边。
解答：这题的主要是寻找公共父节点。寻找到公共父节点之后，计算路径上不共享的节点数即可
class Solution {
public int[] cycleLengthQueries(int n, int[][] queries) {
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
List<Integer> l1 = parent(queries[i][0]), l2 = parent(queries[i][1]);
int common = 0;
while (common < l1.size() && common < l2.size()) {
if (l1.get(common).equals(l2.get(common))) {
++common;
} else {
break;
}
}
common -= 1;
res[i] = l1.size() - common + l2.size() - common - 1;
}
return res;
}
private List<Integer> parent(int num) {
List<Integer> list = new ArrayList<>();
while (num > 0) {
list.add(num);
num /= 2;
}
Collections.reverse(list);
return list;
}
}虽然这周新冠阳了，但是感谢LeetCode这周出题简单。小阳人还是可以快乐4/4