上岸算法LeetCode Weekly Contest 277解题报告

上岸算法 · 发表于 2022-1-24 14:38:24

登录后可回复主题

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

x

【 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<Integer> pos = new ArrayList<>();
   List<Integer> neg = new ArrayList<>();
   for (int num : nums) {
         if (num > 0) {
            pos.add(num);
      } else {
            neg.add(num);
      }
   }
   List<Integer> 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<Integer> findLonely(int[] nums) {
   Map<Integer, Integer> cnt = new HashMap<>();
   for (int num : nums) {
         cnt.put(num, cnt.getOrDefault(num, 0) + 1);
   }
   List<Integer> 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;
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 277解题报告

登录后可回复主题