上岸算法LeetCode Weekly Contest 279解题报告
【 NO.1 对奇偶下标分别排序】解题思路
拆分、排序、合并即可。
代码展示
class Solution {
public int[] sortEvenOdd(int[] nums) {
List<Integer> odd = new ArrayList<>();
List<Integer> even = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) {
even.add(nums);
} else {
odd.add(nums);
}
}
Collections.sort(even);
Collections.sort(odd, (a, b) -> (b - a));
List<Integer> res = new ArrayList<>();
while (!odd.isEmpty() && !even.isEmpty()) {
res.add(even.get(0));
res.add(odd.get(0));
even.remove(0);
odd.remove(0);
}
odd.forEach(res::add);
even.forEach(res::add);
return res.stream().mapToInt(i -> i).toArray();
}
}
【 NO.2 重排数字的最小值】
解题思路
正负数分开处理，负数相当于取绝对值的最大值。
求最大值只需要按照数字排序即可，求最小值则先取出一位最小的非零数字作为首尾，然后按照数字排序即可。
代码展示
class Solution {
public long smallestNumber(long num) {
if (num < 0) {
return -max(-num);
}
return min(num);
}
private int[] cnt(long num) {
int[] res = new int;
while (num > 0) {
res[(int) (num % 10)]++;
num /= 10;
}
return res;
}
private long max(long num) {
int[] d = cnt(num);
long res = 0;
for (int i = 9; i >= 0; i--) {
for (int j = 0; j < d; j++) {
res = res * 10 + i;
}
}
return res;
}
private long min(long num) {
int[] d = cnt(num);
long res = 0;
for (int i = 1; i < 10; i++) {
if (d > 0) {
res = i;
d--;
break;
}
}
for (int i = 0; i <= 9; i++) {
for (int j = 0; j < d; j++) {
res = res * 10 + i;
}
}
return res;
}
}
【 NO.3 设计位集】
解题思路
使用一个 rev 标志位表示当前是否反转过即可。
代码展示
class Bitset {
boolean[] bits;
boolean rev;
int cnt; // count of 1
public Bitset(int size) {
bits = new boolean;
rev = false;
cnt = 0;
}
public void fix(int idx) {
if ((!rev && !bits) || (rev && bits)) {
cnt++;
bits = !rev;
}
}
public void unfix(int idx) {
if ((!rev && bits) || (rev && !bits)) {
cnt--;
bits = rev;
}
}
public void flip() {
rev = !rev;
cnt = bits.length - cnt;
}
public boolean all() {
return cnt == bits.length;
}
public boolean one() {
return cnt > 0;
}
public int count() {
return cnt;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (var b : bits) {
if (b == rev) {
sb.append('0');
} else {
sb.append('1');
}
}
return sb.toString();
}
}
【 NO.4 移除所有载有违禁货物车厢所需的最少时间】
解题思路
动态规划，分别考虑前缀和后缀，详见注释。
代码展示
class Solution {
public int minimumTime(String s) {
int n = s.length();
// pre 表示使得前 i 个车厢都不违禁所需的最短时间
int[] pre = new int;
for (int i = 1; i <= n; i++) {
// 若当前车厢不违禁，则 pre = pre
// 若当前车厢违禁，则有两种方案：
// 1. 在 pre 的基础上使用操作三
// 2. 使用 i 次操作一
pre = pre;
if (s.charAt(i - 1) == '1') {
pre = Math.min(pre + 2, i);
}
}
// suffix 表示后 i 个车厢都不违禁所需的最短时间
int[] suffix = new int;
for (int i = 1; i <= n; i++) {
suffix = suffix;
if (s.charAt(n - i) == '1') {
suffix = Math.min(suffix + 2, i);
}
}
// 将 pre 和 suffix 加和就可以表示一种完整的方案
int res = n * 2;
for (int i = 0; i <= n; i++) {
res = Math.min(res, pre + suffix);
}
return res;
}
}
页:
[1]