【 NO.1 将字符串拆分为若干长度为 k 的组】

解题思路

签到题。

代码展示

class Solution {

   public String[] divideString(String s, int k, char fill) {

       String[] res = new String[(s.length() + k - 1) / k];

       for (int i = 0; i < res.length; i++) {

           if (k * i + k <= s.length()) {

               res[i] = s.substring(k i, k i + k);

          } else {

               res[i] = s.substring(k i) + repeat(fill, k - (s.length() - k i));

          }

      }

       return res;

  }

   private String repeat(char fill, int i) {

       StringBuilder sb = new StringBuilder();

       for (; i > 0; i--) {

           sb.append(fill);

      }

       return sb.toString();

  }

}

【 NO.2 得到目标值的最少行动次数】

解题思路

逆序贪心，优先用除法。

代码展示

class Solution {

   public int minMoves(int target, int maxDoubles) {

       if (target == 1) {

           return 0;

      }

       if (maxDoubles == 0) {

           return target - 1;

      }

       if (target % 2 == 1) {

           return minMoves(target - 1, maxDoubles) + 1;

      }

       return minMoves(target / 2, maxDoubles - 1) + 1;

  }

}

【 NO.3 解决智力问题】

解题思路

动态规划，定义状态 f[i] 表示解决问题 i 时，前 i 个问题最多得到的分数

则有状态转移方程 f[i] = max(f[j]) + score[i], 其中 j 满足 forbid[j] + j < i

使用 TreeMap 维护 forbid[j] + j 即可

代码展示

class Solution {

   public long mostPoints(int[][] questions) {

       long[] f = new long[questions.length];

       f[0] = questions[0][0];

       TreeMap<Integer, Long> cand = new TreeMap<>();

       cand.put(questions[0][1], f[0]);

       long max = 0;

       for (int i = 1; i < f.length; i++) {

           while (!cand.isEmpty() && cand.firstKey() < i) {

               var e = cand.pollFirstEntry();

               max = Math.max(max, e.getValue());

          }

           f[i] = questions[i][0] + max;

           int key = questions[i][1] + i;

           cand.put(key, Math.max(cand.getOrDefault(key, 0L), f[i]));

      }

       return Arrays.stream(f).max().getAsLong();

  }

}

【 NO.4 同时运行 N 台电脑的最长时间】

解题思路

二分答案，详见注释。

代码展示

class Solution {

   public long maxRunTime(int n, int[] batteries) {

       long l = 1, r = Arrays.stream(batteries).mapToLong(i -> i).sum() / n;

       while (l + 1 < r) {

           long mid = (l + r) / 2;

           if (check(n, batteries, mid)) {

               l = mid;

          } else {

               r = mid;

          }

      }

       return check(n, batteries, r) ? r : l;

  }

   // 判断电池能否供给 n 台电脑使用 time 分钟

   // 相当于每块电池最多使用 time 分钟

   // 如果一块电池容量小于 time 分钟，那么它需要和其他电池拼一起才能组成 time 分钟

   // 如果一块电池容量多于 time 分钟，那么可以认为它将被浪费，可以认为这个电池容量只有 time 分钟

   // 因为换电池是不消耗时间的，所以只需检查电池容量之和是否达到了 time * n 即可

   private boolean check(int n, int[] batteries, long time) {

       return Arrays.stream(batteries).mapToLong(i -> Math.min((long) i, time)).sum() >= n * time;

  }

}