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

上岸算法 · 发表于 2022-2-6 16:52:21

登录后可回复主题

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

x

【 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[i]);
      } else {
            odd.add(nums[i]);
      }
   }
   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[10];
   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[i]; 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[i] > 0) {
            res = i;
            d[i]--;
            break;
      }
   }
   for (int i = 0; i <= 9; i++) {
         for (int j = 0; j < d[i]; 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[size];
   rev = false;
   cnt = 0;
  }

public void fix(int idx) {
   if ((!rev && !bits[idx]) || (rev && bits[idx])) {
         cnt++;
         bits[idx] = !rev;
   }
  }

public void unfix(int idx) {
   if ((!rev && bits[idx]) || (rev && !bits[idx])) {
         cnt--;
         bits[idx] = 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] 表示使得前 i 个车厢都不违禁所需的最短时间
   int[] pre = new int[n + 1];
   for (int i = 1; i <= n; i++) {
         // 若当前车厢不违禁，则 pre[i] = pre[i - 1]
         // 若当前车厢违禁，则有两种方案：
         // 1. 在 pre[i - 1] 的基础上使用操作三
         // 2. 使用 i 次操作一
         pre[i] = pre[i - 1];
         if (s.charAt(i - 1) == '1') {
            pre[i] = Math.min(pre[i - 1] + 2, i);
      }
   }
   // suffix[i] 表示后 i 个车厢都不违禁所需的最短时间
   int[] suffix = new int[n + 1];
   for (int i = 1; i <= n; i++) {
         suffix[i] = suffix[i - 1];
         if (s.charAt(n - i) == '1') {
            suffix[i] = Math.min(suffix[i - 1] + 2, i);
      }
   }

   // 将 pre[i] 和 suffix[n - i] 加和就可以表示一种完整的方案
   int res = n * 2;
   for (int i = 0; i <= n; i++) {
         res = Math.min(res, pre[i] + suffix[n - i]);
   }
   return res;
  }
}

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

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

登录后可回复主题