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

上岸算法 · 发表于 2022-2-15 17:43:08

登录后可回复主题

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

x

【 NO.1 得到 0 的操作数】

解题思路
签到题，模拟操作即可。

代码展示

class Solution {
public int countOperations(int num1, int num2) {
   int res = 0;
   for (; num1 * num2 != 0; res++) {
         if (num1 > num2) {
            num1 -= num2;
      } else {
            num2 -= num1;
      }
   }
   return res;
  }
}

【 NO.2 使数组变成交替数组的最少操作数】

解题思路
统计每种数字在奇数、偶数下标上的数量，然后使用最多的和次多的作为最终数字即可。

代码展示

class Solution {
public int minimumOperations(int[] nums) {
   Map<Integer, Integer> cnt0 = new HashMap<>(); // 偶数下标计数
   Map<Integer, Integer> cnt1 = new HashMap<>(); // 奇数下标计数
   for (int i = 0; i < nums.length; i++) {
         if (i % 2 == 0) {
            cnt0.put(nums[i], cnt0.getOrDefault(nums[i], 0) + 1);
      } else {
            cnt1.put(nums[i], cnt1.getOrDefault(nums[i], 0) + 1);
      }
   }
   int[] cnt0Max = getMax(cnt0);
   int[] cnt1Max = getMax(cnt1);
   if (cnt0Max[0] != cnt1Max[0]) {
         return nums.length - cnt0.getOrDefault(cnt0Max[0], 0) - cnt1.getOrDefault(cnt1Max[0], 0);
   }
   return nums.length - Math.max(
            cnt0.getOrDefault(cnt0Max[0], 0) + cnt1.getOrDefault(cnt1Max[1], 0),
            cnt0.getOrDefault(cnt0Max[1], 0) + cnt1.getOrDefault(cnt1Max[0], 0)
   );
  }

private int[] getMax(Map<Integer, Integer> cnt) {
   int[] res = new int[2];
   for (var c : cnt.keySet()) {
         if (cnt.getOrDefault(res[0], 0) <= cnt.get(c)) {
            res[1] = res[0];
            res[0] = c;
      } else if (cnt.getOrDefault(res[1], 0) <= cnt.get(c)) {
            res[1] = c;
      }
   }
   return res;
  }
}

【 NO.3 拿出最少数目的魔法豆】

解题思路
前缀和。排序后，枚举分界点，分界点之前的全部置零，分界点之后的全部置为与分界点处相同的数目，通过前缀和可以快速计算。

代码展示

class Solution {
public long minimumRemoval(int[] beans) {
   Arrays.sort(beans);
   var sum = new IntervalSum(beans);
   long res = sum.suffix(0) - (long) beans[0] * (long) beans.length;
   for (int i = 0; i < beans.length - 1; i++) {
         // [0, i] -> 0; [i+1, length) -> beans[i + 1]
         res = Math.min(res, sum.prefix(i) + sum.suffix(i + 1) - (long) beans[i + 1] * (beans.length - i - 1));
   }
   return res;
  }
}

class IntervalSum {
private final long[] pre;

public IntervalSum(int[] arr) {
   pre = new long[arr.length];
   pre[0] = arr[0];
   for (int i = 1; i < arr.length; i++) {
         pre[i] = pre[i - 1] + arr[i];
   }
  }

// interval [0, i]
public long prefix(int i) {
   return interval(0, i + 1);
  }

// == interval [i, length)
public long suffix(int i) {
   return interval(i, pre.length);
  }

// [start, end)
public long interval(int start, int end) {
   end--;
   return pre[end] - (start == 0 ? 0 : pre[start - 1]);
  }
}

【 NO.4 数组的最大与和】

解题思路
记忆化搜索，令 f[i] 表示 slots 状态为 i 时，还能获取到多少加和

状态转移：枚举当前数字放到哪个 slot 里面

答案：f[0]

其中 i 是一个 18 位的二进制数，每两位表示一个 slot 里已经放入了多少个数字

代码展示

class Solution {
public int maximumANDSum(int[] nums, int numSlots) {

   Map<Integer, Integer> mem = new HashMap<>();
   return maximumANDSum(0, nums, numSlots, nums.length, mem);
  }

private int maximumANDSum(int stat, int[] nums, int numSlots, int numLeft, Map<Integer, Integer> mem) {
   if (mem.containsKey(stat)) {
         return mem.get(stat);
   }
   if (numLeft == 0) {
         return 0;
   }

   int curRes = 0;
   for (int i = 1; i <= numSlots; i++) {
         int slot = getSlot(stat, i);
         if (slot == 2) {
            continue;
      }
         int and = i & nums[numLeft - 1];
         int stat2 = setSlot(stat, i, slot + 1);
         curRes = Math.max(curRes, and + maximumANDSum(stat2, nums, numSlots, numLeft - 1, mem));
   }

   mem.put(stat, curRes);
   return curRes;
  }

// i start from 1
private int getSlot(int bits, int i) {
   int offset = (i - 1) * 2;
   return (bits >> offset) & 0b11;
  }

// num = 0 or 1 or 2
private int setSlot(int bits, int i, int num) {
   int offset = (i - 1) * 2;
   bits -= bits & (0b11 << offset);
   bits += num << offset;
   return bits;
  }
}

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

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

登录后可回复主题