上岸算法LeetCode Weekly Contest 288解题报告
【 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.length(); i++) {
for (int j = 1; j <= elems.length(); j++) {
long left = i == elems.length() ? 1 : Long.parseLong(elems.substring(0, elems.length() - i));
long add1 = Long.parseLong(elems.substring(elems.length() - i));
long add2 = Long.parseLong(elems.substring(0, j));
long right = j == elems.length() ? 1 : Long.parseLong(elems.substring(j));
long sum = left * right * (add1 + add2);
if (sum >= min) {
continue;
}
min = sum;
res = i == elems.length() ? "" : elems.substring(0, elems.length() - i);
res += "(";
res += elems.substring(elems.length() - i);
res += "+";
res += elems.substring(0, j);
res += ")";
res += j == elems.length() ? "" : elems.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 花园的最大总美丽值】
解题思路
两根指针。
将花园排序，最优结果一定是令 的花园中花的数目都达到 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;
presum = flowers;
for (int i = 1; i < presum.length; i++) {
presum = presum + flowers;
}
long[] toTarget = new long; // toTarget 表示将 [i, n) 的花园变成完善的需要多少朵花
for (int i = flowers.length - 1; i >= 0; i--) {
toTarget = Math.max(0, target - flowers);
}
for (int i = flowers.length - 2; i >= 0; i--) {
toTarget += toTarget;
}
long res = 0;
for (int f = 0, p = -1; f <= flowers.length; f++) {
if (f < flowers.length && newFlowers < toTarget) {
continue;
}
long left = newFlowers - toTarget;
while (p + 1 < f && flowers < target && (long) flowers * (p + 2) - presum <= left) {
p++;
}
if (p == -1) {
res = Math.max(res, (long) (flowers.length - f) * full);
continue;
}
left -= (long) flowers * (p + 1) - presum;
long min = Math.min(target - 1, flowers + left / (p + 1));
res = Math.max(res, (long) (flowers.length - f) * full + partial * min);
}
return res;
}
}
页:
[1]