上岸算法LeetCode Weekly Contest 257解题报告 leetcode算法刷题

【 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[a] + nums[b] + nums[c] == nums[d]) { res++; } } } } } return res;

}
}
【 NO.2 游戏中弱角色的数量】
解题思路
按照攻击力、防御力从小到大排序，然后逆序统计即可。要注意处理攻击力相同的情况。
代码展示
class Solution {
public int numberOfWeakCharacters(int[][] properties) {

Arrays.sort(properties, (a, b) -> { if (a[0] == b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); int res = 0; int lastAttack = properties[properties.length - 1][0]; int lastDefense = properties[properties.length - 1][1]; int maxDefense = 0; // maxDefense 表示大于 lastAttack 的角色中，最大的防御力 for (int i = properties.length - 2; i >= 0; i--) { if (properties[i][0] < lastAttack) { maxDefense = Math.max(maxDefense, lastDefense); lastAttack = properties[i][0]; lastDefense = properties[i][1]; } if (properties[i][1] < maxDefense) { res++; } } return res;

}
}
【 NO.3 访问完所有房间的第一天】
解题思路
动态规划，dp[i] 表示访问完第 i 个房间的最小天数。
代码展示
class Solution {
public int firstDayBeenInAllRooms(int[] nextVisit) {

int n = nextVisit.length; long[] dp = new long[n]; long P = (long) (1e9 + 7); for (int i = 1; i < n; ++i) { dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + P) % P; } return (int) dp[n - 1];

}
}
【 NO.4 数组的最大公因数排序】
解题思路
只要元素之间有公因数，那么他们就可以任意排序。所以我们将有相同公因数的元素排序，最后再看序列整体是否有序即可。
代码展示
class UnionFind {
public UnionFind(int size) {

f = new int[size]; Arrays.fill(f, -1);

}
public int find(int x) {

if (f[x] < 0) return x; return f[x] = find(f[x]);

}
public boolean merge(int a, int b) {

int fa = find(a); int fb = find(b); if (fa == fb) return false; f[fa] = fb; return true;

}
public Map> sets() {

Map> 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> set = new HashMap<>(); for (int i = 0; i < nums.length; i++) { for (int j = 1; j * j <= nums[i]; j++) { if (nums[i] % j == 0) { if (!set.containsKey(j)) { set.put(j, new ArrayList<>()); } set.get(j).add(i); if (j * j < nums[i]) { int k = nums[i] / 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[nums.length]; for (var e : sets.entrySet()) { var list = e.getValue(); var sortedList = new ArrayList<>(list); sortedList.sort(Comparator.comparingInt(a -> nums[a])); for (int i = 0; i < list.size(); i++) { res[list.get(i)] = nums[sortedList.get(i)]; } } for (int i = 1; i < res.length; i++) { if (res[i] < res[i - 1]) { return false; } } return true;

【上岸算法LeetCode Weekly Contest 257解题报告】}
}