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

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

登录后可回复主题

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

x

【 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);
  }
}

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

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

登录后可回复主题