LeetCode Weekly Contest 257解题报告
【 NO.1 统计特殊四元组】解题思路
签到题，枚举即可。
代码展示
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int res = 0;
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
for (int c = b + 1; c < n; c++) {
for (int d = c + 1; d < n; d++) {
if (nums + nums + nums == nums) {
res++;
}
}
}
}
}
return res;
}
}
【 NO.2 游戏中弱角色的数量】
解题思路
按照攻击力、防御力从小到大排序，然后逆序统计即可。要注意处理攻击力相同的情况。
代码展示
class Solution {
public int numberOfWeakCharacters(int[][] properties) {
Arrays.sort(properties, (a, b) -> {
if (a == b) {
return a - b;
}
return a - b;
});
int res = 0;
int lastAttack = properties;
int lastDefense = properties;
int maxDefense = 0; // maxDefense 表示大于 lastAttack 的角色中，最大的防御力
for (int i = properties.length - 2; i >= 0; i--) {
if (properties < lastAttack) {
maxDefense = Math.max(maxDefense, lastDefense);
lastAttack = properties;
lastDefense = properties;
}
if (properties < maxDefense) {
res++;
}
}
return res;
}
}
【 NO.3 访问完所有房间的第一天】
解题思路
动态规划，dp 表示访问完第 i 个房间的最小天数。
代码展示
class Solution {
public int firstDayBeenInAllRooms(int[] nextVisit) {
int n = nextVisit.length;
long[] dp = new long;
long P = (long) (1e9 + 7);
for (int i = 1; i < n; ++i) {
dp = (2 * dp - dp] + 2 + P) % P;
}
return (int) dp;
}
}
【 NO.4 数组的最大公因数排序】
解题思路
只要元素之间有公因数，那么他们就可以任意排序。所以我们将有相同公因数的元素排序，最后再看序列整体是否有序即可。
代码展示
class UnionFind {
public UnionFind(int size) {
f = new int;
Arrays.fill(f, -1);
}
public int find(int x) {
if (f < 0)
return x;
return f = find(f);
}
public boolean merge(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa == fb)
return false;
f = fb;
return true;
}
public Map<Integer, List<Integer>> sets() {
Map<Integer, List<Integer>> res = new HashMap<>();
for (int i = 0; i < f.length; i++) {
int fi = find(i);
if (!res.containsKey(fi)) {
res.put(fi, new ArrayList<>());
}
res.get(fi).add(i);
}
return res;
}
private int[] f;
}
class Solution {
public boolean gcdSort(int[] nums) {
Map<Integer, List<Integer>> set = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
for (int j = 1; j * j <= nums; j++) {
if (nums % j == 0) {
if (!set.containsKey(j)) {
set.put(j, new ArrayList<>());
}
set.get(j).add(i);
if (j * j < nums) {
int k = nums / j;
if (!set.containsKey(k)) {
set.put(k, new ArrayList<>());
}
set.get(k).add(i);
}
}
}
}
UnionFind uf = new UnionFind(nums.length);
for (var e : set.entrySet()) {
if (e.getKey() < 2) {
continue;
}
var list = e.getValue();
for (int i = 1; i < list.size(); i++) {
uf.merge(list.get(i - 1), list.get(i));
}
}
var sets = uf.sets();
int[] res = new int;
for (var e : sets.entrySet()) {
var list = e.getValue();
var sortedList = new ArrayList<>(list);
sortedList.sort(Comparator.comparingInt(a -> nums));
for (int i = 0; i < list.size(); i++) {
res = nums;
}
}
for (int i = 1; i < res.length; i++) {
if (res < res) {
return false;
}
}
return true;
}
}
页:
[1]