上岸算法 | LeetCode Weekly Contest 第 277场周赛解题报告

卖大米 5月前 95


【 NO.1 元素计数】

解题思路

签到题,排序后去除首尾的元素即可。

代码展示

class Solution {

   public int countElements(int[] nums) {

       Arrays.sort(nums);

       int start = 0, end = nums.length - 1;

       while (start < end && nums[start] == nums[start + 1]) {

           start++;

      }

       while (start < end && nums[end - 1] == nums[end]) {

           end--;

      }

       return Math.max(0, end - start - 1);

  }

}

【 NO.2 按符号重排数组】

解题思路

分裂再归并即可。

代码展示

class Solution {

   public int[] rearrangeArray(int[] nums) {

       List pos = new ArrayList<>();

       List neg = new ArrayList<>();

       for (int num : nums) {

           if (num > 0) {

               pos.add(num);

          } else {

               neg.add(num);

          }

      }

       List res = new ArrayList<>();

       for (int i = 0; i < pos.size(); i++) {

           res.add(pos.get(i));

           res.add(neg.get(i));

      }

       return res.stream().mapToInt(i -> i).toArray();

  }

}

【 NO.3 找出数组中的所有孤独数字】

解题思路

使用 Map 统计每个数值出现的次数即可。

代码展示

class Solution {

   public List findLonely(int[] nums) {

       Map<Integer, Integer> cnt = new HashMap<>();

       for (int num : nums) {

           cnt.put(num, cnt.getOrDefault(num, 0) + 1);

      }

       List res = new ArrayList<>();

       for (var e : cnt.entrySet()) {

           if (e.getValue() != 1 || cnt.containsKey(e.getKey() - 1) || cnt.containsKey(e.getKey() + 1)) {

               continue;

          }

           res.add(e.getKey());

      }

       return res;

  }

}

【 NO.4 基于陈述统计最多好人数】

解题思路

暴力枚举,枚举哪些人是好人,然后剩下的就是坏人。

如果好人之间的表述有冲突那么说明这个情况是非法的。

代码展示

class Solution {

   public int maximumGood(int[][] statements) {

       int n = statements.length;

       int res = 0;

       for (int i = 1; i < (1 << n); i++) {

           res = Math.max(res, maximumGood(n, i, statements));

      }

       return res;

  }

   // 若 bin 符合条件,则返回 bin 中 1 的数量

   // 否则返回 0

   private int maximumGood(int n, int bin, int[][] statements) {

       int num1 = 0;

       char[] role = new char[n];

       Arrays.fill(role, (char) 2);

       for (int i = 0; i < n; i++) {

           if ((bin & (1 << i)) > 0) {

               num1++;

               // i 是好人

               if (role[i] == 0) {

                   return 0;

              }

               role[i] = 1;

               for (int j = 0; j < n; j++) {

                   if (statements[i][j] != 2) {

                       if (role[j] != 2 && role[j] != statements[i][j]) {

                           return 0;

                      }

                       role[j] = (char) statements[i][j];

                  }

              }

          }

      }

       for (int i = 0; i < n; i++) {

           if ((bin & (1 << i)) > 0) {

               continue;

          }

           // i 是坏人

           if (role[i] == 1) {

               return 0;

          }

      }

       return num1;

  }

}

最新回复 (0)
返回