【 NO.1 统计包含给定前缀的字符串】

解题思路

签到题，枚举即可。

代码展示

class Solution {

   public int prefixCount(String[] words, String pref) {

       int count = 0;

       for (String word : words) {

           if (word.indexOf(pref) == 0) {

               count++;

          }

      }

       return count;

  }

}

【 NO.2 使两字符串互为字母异位词的最少步骤数】

解题思路

字母异位词 (anagram) 只需要满足各种字符的数量一致即可，所以统计两个字符串中，每种字母的出现次数，将少的补充直到达到数量相同即可。

代码展示

class Solution {

   public int minSteps(String s, String t) {

       int[] countS = countLetters(s);

       int[] countT = countLetters(t);

       int result = 0;

       for (int i = 0; i < 26; i++) {

           result += Math.max(countS[i], countT[i]) - Math.min(countS[i], countT[i]);

      }

       return result;

  }

   private int[] countLetters(String s) {

       int[] count = new int[26];

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

           count[s.charAt(i) - 'a']++;

      }

       return count;

  }

}

【 NO.3 完成旅途的最少时间】

解题思路

典型的二分答案题目。

代码展示

class Solution {

   public long minimumTime(int[] time, int totalTrips) {

       long left = 0, right = (long) 1e14;

       while (left + 1 < right) {

           long mid = (left + right) / 2;

           if (check(mid, time, totalTrips)) {

               right = mid;

          } else {

               left = mid;

          }

      }

       return check(left, time, totalTrips) ? left : right;

  }

   private boolean check(long limit, int[] time, long totalTrips) {

       for (int t : time) {

           totalTrips -= limit / t;

      }

       return totalTrips <= 0;

  }

}

【 NO.4 完成比赛的最少时间】

解题思路

动态规划问题。

先预处理求出 g[i] 表示不换轮胎完成 i 圈的最短时间，枚举所有的轮胎即可。

然后定义状态 f[i] 表示完成 i 圈的最短时间，状态转移方程即 f[i] = min{ f[i - j] + g[j] + changeTime }

注意最终答案要减去多加的一次 changeTime, 以及运算过程中的溢出问题。

由数据范围可知，最终答案一定不会超过 1e5 1000 2 (每次都换胎)，该数值未超过 int 最大值，所以运算过程溢出的状态可以直接丢弃。

代码展示

class Solution {

   public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {

       // g[i] 表示不换轮胎完成 i 圈的最短时间

       long[] g = new long[numLaps + 1];

       Arrays.fill(g, Long.MAX_VALUE);

       for (int[] t : tires) {

           long pn = 1, sum = t[0];

           for (int i = 1; i <= numLaps && sum < Integer.MAX_VALUE; i++) {

               g[i] = Math.min(g[i], sum);

               pn *= t[1];

               sum += t[0] * pn;

          }

      }

       // f[i] 表示完成 i 圈的最短时间

       long[] f = new long[numLaps + 1];

       Arrays.fill(f, Integer.MAX_VALUE);

       f[0] = 0;

       for (int i = 1; i <= numLaps; i++) {

           for (int j = 1; j <= i && g[j] < Integer.MAX_VALUE; j++) {

               f[i] = Math.min(f[i], f[i - j] + g[j] + changeTime);

          }

      }

       return (int) (f[numLaps] - changeTime);

  }

}