上岸算法 发表于 2022-2-27 23:33:14

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

【 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, countT) - Math.min(countS, countT);
      }
       return result;
}

   private int[] countLetters(String s) {
       int[] count = new int;
       for (int i = 0; i < s.length(); i++) {
         count++;
      }
       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 圈的最短时间,枚举所有的轮胎即可。

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

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

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

代码展示
class Solution {
   public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
       // g 表示不换轮胎完成 i 圈的最短时间
       long[] g = new long;
       Arrays.fill(g, Long.MAX_VALUE);
       for (int[] t : tires) {
         long pn = 1, sum = t;
         for (int i = 1; i <= numLaps && sum < Integer.MAX_VALUE; i++) {
               g = Math.min(g, sum);
               pn *= t;
               sum += t * pn;
          }
      }

       // f 表示完成 i 圈的最短时间
       long[] f = new long;
       Arrays.fill(f, Integer.MAX_VALUE);
       f = 0;
       for (int i = 1; i <= numLaps; i++) {
         for (int j = 1; j <= i && g < Integer.MAX_VALUE; j++) {
               f = Math.min(f, f + g + changeTime);
          }
      }
       return (int) (f - changeTime);
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 282解题报告