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

上岸算法 · 发表于 2022-4-11 17:11:03

登录后可回复主题

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

x

【 NO.1 按奇偶性交换后的最大数字】

解题思路
分别提取奇数和偶数，排序后按照奇偶性顺序还原即可。

代码展示

class Solution {
public int largestInteger(int num) {
   List<Integer> type = new ArrayList<>();
   List<Integer> odd = new ArrayList<>();
   List<Integer> even = new ArrayList<>();
   for (int n = num; n > 0; n /= 10) {
         int d = n % 10;
         if (d % 2 == 0) {
            type.add(0);
            even.add(d);
      } else {
            type.add(1);
            odd.add(d);
      }
   }
   odd.sort(Collections.reverseOrder());
   even.sort(Collections.reverseOrder());
   int res = 0;
   for (int i = type.size() - 1; i >= 0; i--) {
         List<Integer> list = type.get(i) == 0 ? even : odd;
         res = res * 10 + list.get(0);
         list.remove(0);
   }
   return res;
  }
}

【 NO.2 向表达式添加括号后的最小结果】

解题思路
枚举左右括号插入位置即可。

代码展示

class Solution {
public String minimizeResult(String expression) {
   var elems = expression.split("\\+");
   long min = Long.MAX_VALUE;
   String res = "";
   for (int i = 1; i <= elems[0].length(); i++) {
         for (int j = 1; j <= elems[1].length(); j++) {
            long left = i == elems[0].length() ? 1 : Long.parseLong(elems[0].substring(0, elems[0].length() - i));
            long add1 = Long.parseLong(elems[0].substring(elems[0].length() - i));
            long add2 = Long.parseLong(elems[1].substring(0, j));
            long right = j == elems[1].length() ? 1 : Long.parseLong(elems[1].substring(j));
            long sum = left * right * (add1 + add2);
            if (sum >= min) {
               continue;
            }
            min = sum;
            res = i == elems[0].length() ? "" : elems[0].substring(0, elems[0].length() - i);
            res += "(";
            res += elems[0].substring(elems[0].length() - i);
            res += "+";
            res += elems[1].substring(0, j);
            res += ")";
            res += j == elems[1].length() ? "" : elems[1].substring(j);
      }
   }
   return res;
  }
}

【 NO.3 K 次增加后的最大乘积】

解题思路
每次将最小的数字加 1 即可。

代码展示

class Solution {
public int maximumProduct(int[] nums, int k) {
   PriorityQueue<Integer> heap = new PriorityQueue<>();
   for (int num : nums) {
         heap.add(num);
   }
   for (int i = 0; i < k; i++) {
         heap.add(heap.poll() + 1);
   }
   long res = 1;
   while (!heap.isEmpty()) {
         res = (res * heap.poll()) % 1000000007;
   }
   return (int) res;
  }
}

【 NO.4 花园的最大总美丽值】

解题思路
两根指针。

将花园排序，最优结果一定是令 [0, l] 的花园中花的数目都达到 x (x < target), 并且令 [r, n) 的花园中花的数目都达到 target

此时的美丽值即 x * partial + (n - r) * full

枚举 r 即可，l 随着 r 单调递增。

代码展示

class Solution {
public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
   Arrays.sort(flowers);
   long[] presum = new long[flowers.length];
   presum[0] = flowers[0];
   for (int i = 1; i < presum.length; i++) {
         presum[i] = presum[i - 1] + flowers[i];
   }

   long[] toTarget = new long[flowers.length + 1]; // toTarget[i] 表示将 [i, n) 的花园变成完善的需要多少朵花
   for (int i = flowers.length - 1; i >= 0; i--) {
         toTarget[i] = Math.max(0, target - flowers[i]);
   }
   for (int i = flowers.length - 2; i >= 0; i--) {
         toTarget[i] += toTarget[i + 1];
   }

   long res = 0;
   for (int f = 0, p = -1; f <= flowers.length; f++) {
         if (f < flowers.length && newFlowers < toTarget[f]) {
            continue;
      }
         long left = newFlowers - toTarget[f];
         while (p + 1 < f && flowers[p + 1] < target && (long) flowers[p + 1] * (p + 2) - presum[p + 1] <= left) {
            p++;
      }
         if (p == -1) {
            res = Math.max(res, (long) (flowers.length - f) * full);
            continue;
      }
         left -= (long) flowers[p] * (p + 1) - presum[p];
         long min = Math.min(target - 1, flowers[p] + left / (p + 1));
         res = Math.max(res, (long) (flowers.length - f) * full + partial * min);
   }
   return res;
  }
}

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

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

登录后可回复主题