【 NO.1 对奇偶下标分别排序】

解题思路

拆分、排序、合并即可。

代码展示

class Solution {

   public int[] sortEvenOdd(int[] nums) {

       List odd = new ArrayList<>();

       List 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 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;

  }

}