LeetCode Weekly Contest 257解题报告

上岸算法 · 发表于 2021-9-5 18:43:23

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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<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[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解题报告

登录后可回复主题